[Bug ld/2442] New: ld slow with many local relocs (O(N^2) in get_dyn_sym_info)

[matz at suse dot de]

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.

-- 
           Summary: ld slow with many local relocs (O(N^2) in
                    get_dyn_sym_info)
           Product: binutils
           Version: 2.17 (HEAD)
            Status: NEW
          Severity: normal
          Priority: P2
         Component: ld
        AssignedTo: unassigned at sources dot redhat dot com
        ReportedBy: matz at suse dot de
                CC: bug-binutils at gnu dot org
GCC target triplet: ia64-linux


http://sourceware.org/bugzilla/show_bug.cgi?id=2442

------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.