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

H.J. Lu hjl.tools@gmail.com
Thu Jan 14 15:42:00 GMT 2010


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.



More information about the Binutils mailing list