From ccb1ba62299edce72053dd567b9d384814e11885 Mon Sep 17 00:00:00 2001 From: Christian Biesinger Date: Fri, 27 Sep 2019 13:32:07 -0500 Subject: 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 * 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/utils.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'gdb/utils.h') diff --git a/gdb/utils.h b/gdb/utils.h index 478c485..a8ad9d9 100644 --- a/gdb/utils.h +++ b/gdb/utils.h @@ -574,7 +574,11 @@ extern void copy_bitwise (gdb_byte *dest, ULONGEST dest_offset, static inline unsigned int fast_hash (const char* str, size_t len) { +#ifdef HAVE_LIBXXHASH + return XXH64 (str, len, 0); +#else return iterative_hash (str, len, 0); +#endif } #endif /* UTILS_H */ -- cgit v1.1