[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug binutils/11843] New: ld long link times due to compute_bucket_count
From: |
todd dot veldhuizen at logicblox dot com |
Subject: |
[Bug binutils/11843] New: ld long link times due to compute_bucket_count() choosing hash table size |
Date: |
26 Jul 2010 21:33:21 -0000 |
In bfd/elflink.c, in compute_bucket_count(), there is a $\Theta(n^2)$ loop (with
n=nsyms) to find a good hash table size. This is okay for n=50, but we have
links taking 15 minutes for a library with n=162099 symbols. The code in
compute_bucket_count() is a bit pointless for large values of n.
Perhaps a different strategy for n > 1024 is needed, e.g., just return size
nsyms/2, or choose the best of (say) sizes n0...n0+k where n0 is the target size
(with k=4 for example, just to eliminate the possibility that the first choice
is astronomically unlucky).
--
Summary: ld long link times due to compute_bucket_count()
choosing hash table size
Product: binutils
Version: 2.21 (HEAD)
Status: NEW
Severity: normal
Priority: P2
Component: binutils
AssignedTo: unassigned at sources dot redhat dot com
ReportedBy: todd dot veldhuizen at logicblox dot com
CC: bug-binutils at gnu dot org
http://sourceware.org/bugzilla/show_bug.cgi?id=11843
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.
- [Bug binutils/11843] New: ld long link times due to compute_bucket_count() choosing hash table size,
todd dot veldhuizen at logicblox dot com <=
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, hjl dot tools at gmail dot com, 2010/07/28
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, todd dot veldhuizen at logicblox dot com, 2010/07/28
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, todd dot veldhuizen at logicblox dot com, 2010/07/28
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, todd dot veldhuizen at logicblox dot com, 2010/07/28
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, hjl dot tools at gmail dot com, 2010/07/30
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, hjl dot tools at gmail dot com, 2010/07/30
- [Bug binutils/11843] ld long link times due to compute_bucket_count() choosing hash table size, hjl dot tools at gmail dot com, 2010/07/31