Use libxxhash for hashing, if present
XXHash is faster than htab_hash_string:
------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------
BM_xxh3 11 ns 11 ns
65887249
BM_xxh32 19 ns 19 ns
36511877
BM_xxh64 16 ns 16 ns
42964585
BM_hash_string 182 ns 182 ns
3853125
BM_iterative_hash 77 ns 77 ns
9087638
Unfortunately, XXH3 is still experimental (see
https://github.com/Cyan4973/xxHash#user-content-new-experimental-hash-algorithm)
However, regular XXH64 is still a lot faster than
htab_hash_string per my benchmark above. I used the
following string for the benchmark:
static constexpr char str[] = "_ZZZL13make_gdb_typeP7gdbarchP10tdesc_typeEN16gdb_type_creator19make_gdb_type_flagsEPK22tdesc_type_with_fieldsE19__PRETTY_FUNCTION__";
htab_hash_string is currently 4.35% + 7.98% (rehashing) of gdb
startup when attaching to Chrome's content_shell.
An additional 5.21% is spent in msymbol_hash, which does not use
this hash function. Unfortunately, since it has to lowercase the
string, it can't use this hash function.
BM_msymbol_hash 52 ns 52 ns
13281495
It may be worth investigating if strlen+XXHash is still faster than
htab_hash_string, which would make it easier to use in more places.
Debian ships xxhash as libxxhash{0,-dev}. Fedora ships it as xxhash-devel.
gdb/ChangeLog:
2019-10-22 Christian Biesinger <cbiesinger@google.com>
* Makefile.in: Link with libxxhash.
* config.in: Regenerate.
* configure: Regenerate.
* configure.ac: Search for libxxhash.
* utils.c (fast_hash): Use xxhash if present.
Change-Id: Icab218388b9f829522ed3977f04301ae6d4fc4ca