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

[Eirik Byrkjeflot Anonsen]

Using objcopy from binutils 2.20:

Symbol renaming in objcopy (from binutils 2.20) uses a linked list and a
linear search through that list.  This is a tad slow when the symbol
list is long (in my case with ~45000 symbols it takes around 20
minutes).

The attached patch replaces the linked list with a hash table
implementation.  I have taken care to retain the behaviour of the old
code (in particular, failing with an error message when the same symbol
appears twice, either as source or target symbol.)  This makes the case
above complete in 5 seconds.  And it even seems to do the right thing :)


Obvious points of possible improvements:

- A better hash function (sym_hash()).
- A better choice of hash table sizes.
- A better algorithm for when to resize the hash table.


Note: I'm off for christmas vacation now, so I may not be responding to
replies to this mail until next year.

eirik

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Replace-symbol-redefinition-list-with-a-hash-table.patch
Type: text/x-diff
Size: 7292 bytes
Desc: not available
URL: <https://sourceware.org/pipermail/binutils/attachments/20091218/5e3db973/attachment.bin>