Re: [PATCH] Objcopy: use a hash table for symbol renaming

[Eirik Byrkjeflot Anonsen <eirik at opera dot com>]

"H.J. Lu" <hjl.tools@gmail.com> writes:

> On Thu, Jan 14, 2010 at 5:56 AM, Eirik Byrkjeflot Anonsen
> <eirik@opera.com> wrote:
[...]
>> Ok, I finally got around to spending some time trying to figure out how
>> libiberty's hash tables work. ÂI found the documentation to be somewhat
>> thin, so I ended up implementing the symbol redefinition hash table by
>> the time-honored coding style of "cut and paste". Â(Though the resulting
>> code seems sensible. ÂAnd it seems to do the right thing.)
>>
>> (Astonishingly, this version seems to be about 10% slower than mine.
>> "Astonishingly" because my version was optimized for correctness and
>> readability, not for performance. ÂStill, it's not a performance
>> difference that matters significantly. ÂThe benefits of using a standard
>> implementation of hash tables far outweighs that minor performance hit.)
>>
>
> Can you improve hash table implementation in libiberty to get back that 10%?
>
> Thanks.

After having thought a bit about it, I'm suspecting the main difference
is that my previous patch was using open hashing and libiberty is using
closed hashing.  Every extra collision means doing an extra strcmp.  (Of
course, it is possible that libiberty's collision behaviour is worse
than it should be.  But that would take some real analysis to figure
out...)

If I find myself with "copious free time", I might look into it...

Then again, I never looked at the actual memory usage of my previous
patch.  Maybe I just used ridiculously large hash tables :)

eirik