Bug 2442 - ld slow with many local relocs (O(N^2) in get_dyn_sym_info)
Summary: ld slow with many local relocs (O(N^2) in get_dyn_sym_info)
Alias: None
Product: binutils
Classification: Unclassified
Component: ld (show other bugs)
Version: 2.17
: P2 normal
Target Milestone: ---
Assignee: unassigned
Depends on:
Reported: 2006-03-10 18:18 UTC by Michael Matz
Modified: 2006-04-05 21:12 UTC (History)
3 users (show)

See Also:
Target: ia64-linux
Last reconfirmed:


Note You need to log in before you can comment on or make changes to this bug.
Description Michael Matz 2006-03-10 18:18:56 UTC
I can't provide the .o files exhibiting this problem, hence I have to just 
give my analysis.  We have a case where there are big object files containing 
many of such relocations: 
000000030328  042c00000027 R_IA64_DIR64LSB   0000000000000000 .text + 2ee51 
000000030330  042c00000027 R_IA64_DIR64LSB   0000000000000000 .text + 2ed41 
000000030338  042c00000027 R_IA64_DIR64LSB   0000000000000000 .text + 2ee41 
Thousands of them. 
The special thing here is, many relocations against the same symbol (here 
a local pseudo symbol for .text) but differing addends.  The ia64 linker 
in elfNN_ia64_check_relocs goes over all relocs, calling get_dyn_sym_info() 
on each one.  For local symbols (as is the case here) this collects a linked 
list of elfNN_ia64_dyn_sym_info entries _for each addend_ without duplicates. 
As this is a linked list just checking for duplicates is O(N^2) in the number 
of such relocs. 
The above relocs specifically where in the .rela.debug_ranges section, so 
in this case it's debug info which leads to ld breaking down. 
Linking the specific .o files in question needs many hours it seems (I wasn't 
yet patient enough to really leave it running through the end), but in gdb 
one can see that elfNN_ia64_check_relocs doesn't finish for a long time. 
The O(N^2) is quite obvious, but I don't know yet if that's the only cause for 
the huge reported link time.
Comment 1 H.J. Lu 2006-03-16 19:48:07 UTC
I need a testcase to look into it. You can contact me at hongjiu.lu@intel.com if
it helps.
Comment 2 H.J. Lu 2006-03-31 16:02:08 UTC
A patch is posted at


The link time went from 1300 minutes to 1 minute. 
Comment 3 H.J. Lu 2006-04-05 21:12:47 UTC
Fixed by