[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Slow algorithm used for string merging

From: Stephan Tobies
Subject: Re: Slow algorithm used for string merging
Date: Tue, 30 Mar 2004 08:10:36 +0200
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.5) Gecko/20031007

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:

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 (address@hidden).

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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]