ld uses small fixed-size hash table

[Jeff Prothero]

There appears to be a general problem throughout binutils of
unscalability -- assumptions are made in the implementation
which break badly on programs of 1-10 million lines of code.

This is one such:  'ld' uses a hashtable of fixed size 4000
which on our images results in linearly searching bucket
chains HUNDREDS of entries long.

The idea behind hash table implementation is to avoid such
linear searches. :)

Expanding this table from 4K to 64K entries cut our link time from 3.5
minutes down to 1.5 minutes -- over a 50% saving, over 2 minutes of
CPU time shaved off every debug cycle.

I've attached our diff, but a bigger fixed hashtable size
isn't really a good fix, obviously.

Would it be impossibly difficult for hash tables to
expand in size when overload reaches some level such
as 32 * bucket-count?  Or else to implement an overflow
binary tree to cut in at that point?

Many thanks for all the good work!

 -- Jeff
    address@hidden