Use libxxhash for hashing, if present
authorChristian Biesinger <cbiesinger@google.com>
Fri, 27 Sep 2019 18:32:07 +0000 (13:32 -0500)
committerChristian Biesinger <cbiesinger@google.com>
Tue, 22 Oct 2019 16:47:24 +0000 (11:47 -0500)
commitccb1ba62299edce72053dd567b9d384814e11885
tree2bea3a6796df3af2f866e854bef525d7a4d18b79
parent1a6ff1a96b302283d517b3cdeae7310adecbe859
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
gdb/ChangeLog
gdb/Makefile.in
gdb/config.in
gdb/configure
gdb/configure.ac
gdb/utils.c
gdb/utils.h