This is the mail archive of the
binutils@sources.redhat.com
mailing list for the binutils project.
slow links due to merge_strings
- From: Kevin Nomura <nomura at netapp dot com>
- To: binutils at sources dot redhat dot com, bug-binutils at gnu dot org
- Date: Fri, 1 Aug 2003 18:22:23 -0700
- Subject: slow links due to merge_strings
binutils 2.13.2.1
On a link of 4000 object files, link times went from 13 seconds to 300
when switching from stabs to dwarf2 debug format. gprof showed this
time to be coming from merge_strings() in bfd/merge.c and descendants
doing hash lookups. The hash tables were lightly loaded but experiencing
90% collision rates, with 600 million calls to last4_eq.
The following code in merge_strings looked odd:
s = e->root.string + e->len - e->u.entsize;
hash = 0;
for (i = 0; i < e->u.entsize; i++)
{
c = *--s;
hash += c + (c << 17);
hash ^= hash >> 2;
}
e->u.entsize == 1, I guess because strings are being hashed, and the
"entsize" of a character string is one character.
The code seems to be trying to set s to the end of the string and
work backwards. But it won't get very far with e->u.entsize == 1.
As an experiment I made this change:
for (i = 0; i < e->len; i++)
Link time decreased from 300 -> 60 seconds with a saner-looking profile.
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
36.79 14.10 14.10 23787199 0.00 0.00 sec_merge_hash_lookup
30.34 25.73 11.63 27330752 0.00 0.00 last4_eq
12.26 30.43 4.70 304477 0.00 0.00 htab_find_slot_with_hash
3.44 31.75 1.32 12919123 0.00 0.00 _bfd_merged_section_offset
3.03 32.91 1.16 19092 0.00 0.00 elf_i386_relocate_section
...
The executable output file was bitwise identical.