[Bug libc/25924] Very poor choice of hash function in hsearch

["witold.baryluk+sourceware at gmail dot com" <sourceware-bugzilla@sourceware.org>]

https://sourceware.org/bugzilla/show_bug.cgi?id=25924

--- Comment #4 from Witold Baryluk <witold.baryluk+sourceware at gmail dot com> ---
I did a bit more of benchmarking on amd64, (AMD Threadripper TR 2950X), and
excluded the time for malloc / snprintf. I also instrumented the while loop in
hsearch_r to count collisions during insertion (ENTER). 20M insertions into
table of size 30M. Wall clock time - best of 5 runs.

old hash:
dec_keys  1.144s   6149640 collisions
hex_keys  3.319s  87011211 collisions

new hash, fasthash64:
dec_keys  1.146s   2313573 collisions
hex_keys  1.170s   2312409 collisions

It is just an example. But you can see new hash (or other good hash) has
significantly less collisions, and "%d" and "%x" style keys having essentially
same (and fast) performance and no collisions blow-up.

I did not measure the lookup (FIND), but considering number of collisions with
existing hash, I expect old hash to perform very bad.

-- 
You are receiving this mail because:
You are on the CC list for the bug.