This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [Commited] Extend BFD hash size table


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



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]