Slow algorithm used for string merging

[Stephan Tobies]

ext Eric Christopher wrote:

>>My question is: are there plans to work on this issue, or are there even 
>>some patches floating around that would solve this? Before I sit down 
>>and start writing patches for ld, I would like to check if there is not 
>>somebody else who has already done so, and, of course, if such patches 
>>would be welcome by the ld maintainers.
>>    
>>
>
>You didn't say what version of binutils you were using.
>
Sorry - my mistake.

GNU ld version 2.14 20030612
  Supported emulations:
   elf_i386
   i386linux

It uses some form of hashing based on the last char and the last 4 chars 
to divide the set of strings that are considered as possible candidates, 
but then performs more or less a linear, unoptimized search to find the 
new string as a suffix of the known strings. If the last 4 chars would 
be uniformly distributed, this could help quite a bit, but of course 
this, in general, not the case. Also, 'abusing' the hash table to store 
a linked list of strings does not seem to be a good idea to me - jumping 
around in the table using the second hash offset will probably lead to 
lots of cache-misses, but that is just guessing.

>Some work has
>been done to speed up linking already, and yes, patches are always
>accepted if you have a copyright assignment done (assign@gnu.org).
>  
>

Ok, I will have to check with my employer, of course.

BR

Stephan