Slow algorithm used for string merging

[Stephan Tobies]

Hi,

I have a project where switching from gcc-2.95.x to gcc 3.2.2 has 
brought linking time from 10s to ~1h. (Yes, it is a really large 
project.) After some profiling, I have found that the merge_strings 
routine seems to be responsible to most of this time. Further analysis 
shows that the number of collisions in the hash table is causing the 
trouble.

I have seen other references to this problem, where the suggestion was 
to use the --fno-merge-strings option to gcc to solve the problem. 
Unfortunately, this does not really help this much because most of the 
strings that seem to be merged are debug information, which is always 
stored as mergable strings in the object files. Ok, there should be an 
option in gcc that also allows to generate debug info as non-mergable, 
but that does not solve the problem that the algorithm for string 
merging used by ld is rather poor and could use some improvement.

The --traditional-format option does not seem to solve the problem (at 
least not in my experiments) - I assume that this option is either 
ignored when generating stabs debug info, or it is only considered when 
writing thigs to a file, but not during the merging phase, which causes 
the hash tables to be built and then thrown away.

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.

Best regards

Stephan Tobies