summaryrefslogtreecommitdiff
path: root/ext2fs
diff options
context:
space:
mode:
authorJustus Winter <4winter@informatik.uni-hamburg.de>2014-05-26 12:18:08 +0200
committerJustus Winter <4winter@informatik.uni-hamburg.de>2014-05-26 13:17:16 +0200
commit5b039a12bf5cfc9c65b8e169ed4503e306f971f3 (patch)
tree3d7d4a80647ea482b4ea8f5aaf7f5a86afb3f24c /ext2fs
parentb16f334192dbac002a33c31645e228d349de3c72 (diff)
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.
Diffstat (limited to 'ext2fs')
0 files changed, 0 insertions, 0 deletions