[Commited] Extend BFD hash size table

[Nick Clifton]

Hi Dave,

>   Do you happen to have any testcase handy that could be used to investigate
> the performance of the bfd hashing algorithm?

Not that I am allowed to distribute, no. :-(  I do have some quite large 
test cases but they contain files belonging to individual customers and 
they are covered by various NDA agreements.

> [Translation: the existing hashing function appears to be, at first glance,
> fairly poorly designed;

Actually in some tests I ran recently I found that the current hashing 
algorithm is actually pretty darn good.  I found one test case where a 
different algorithm had about a 2-3% speed up, but that same algorithm 
also created a 7-10% slow down in several other tests.

One idea I did try was to amalgamate all of the different places in the 
BFD library where the current hashing algorithm is used.  This allowed 
me to experiment with different algorithms more easily, but it did in 
fact introduce a speed penalty of its own.  (Due I assume to the cross 
compilation unit function call overhead that was introduced).

> if we had a better hashing function, we wouldn't need
> prime table sizes and could just use power-of-2 tables and replace all those
> modulo operations with bitwise ANDs.]

I have always thought that using prime numbers as the hash table size 
was necessary in order to get an efficient use of all the buckets.  Of 
course this may just be an urban myth, I do not know of any actual 
theoretical work to back this up.

Cheers
   Nick