Re: Slow algorithm used for string merging

[Stephan Tobies <Stephan dot Tobies at nokia dot com>]

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