libihash: do not use an integer hash function by default

Recently libihash was changed to use an integer hash function on the
keys in an attempt to reduce the rate of collisions (2d898893), which
has long been assumed to be high.

Richard Braun was kind enough to run some benchmarks.  He observed:

"1/ Using an extremely simple microbenchmark [1] that merely inserts
keys, either random integers or sequential ones to match the way port
names are managed, it seems that the previous code, despite its
apparent flaws, did quite well.

[1] http://darnassus.sceen.net/gitweb/rbraun/ihtest.git

Using an integer hashing function actually reduces performance on the
sequential integer test case. It makes sense because, considering a
set of consecutive integers starting from 0, and a hash table that
always has more slots than items, a modulo is a perfect hash
function. Even when taking into account that only names for receive
rights are normally managed with libihash, i.e. that keys aren't
actually sequential, they are almost all equally distributed, leading
to very few collisions.

Therefore, as a third option, I've removed the hashing function,
leaving only a fast modulo (an AND) and this variant provided the best
raw results.

2/ I've also built hurd packages multiple times and got average build
times with each variant (previous, new, new without hash function) and
here are the results I obtained respectively : 52m59s, 52m31s, 52m22s."

Do not use the integer hash function on the keys by default.

* libihash/ihash.c (murmur3_mix32): Remove now unused function.
(find_index): Use the fast division method to derive the index.
(add_one): Likewise.  Also, update the comment to reflect the current
hashing method.

0 files changed, 0 insertions, 0 deletions