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

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Thu, Jan 14, 2010 at 7:28 AM, Eirik Byrkjeflot Anonsen
<eirik@opera.com> wrote:
> "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 :)
>

You can choose the hash table size, which makes a big difference
sometimes.



-- 
H.J.