This is the mail archive of the
binutils@sourceware.org
mailing list for the binutils project.
Re: [Commited] Extend BFD hash size table
- From: Nick Clifton <nickc at redhat dot com>
- To: Dave Korn <dave dot korn at artimi dot com>
- Cc: binutils at sourceware dot org
- Date: Mon, 09 Jan 2006 16:02:05 +0000
- Subject: Re: [Commited] Extend BFD hash size table
- References: <SERRANO3cFBjAUlygJk000001f9@SERRANO.CAM.ARTIMI.COM>
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