[PATCH v2 0/3] Speed up hashing in demangled_names_hash

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[PATCH v2 0/3] Speed up hashing in demangled_names_hash

Sourceware - gdb-patches mailing list
Use a faster hash function (via an optional dependency) and makes
equality comparison slightly faster (by comparing the length first).

Changes from v1:
- Rebased
- fast_hash now does not require nulltermination
- Updated commit message & benchmark data for patch 3/3

Christian Biesinger (3):
  Store the mangled name as a string_view
  Add a fast_hash function in common-utils
  Use libxxhash for hashing, if present

 gdb/Makefile.in  |   8 +-
 gdb/config.in    |   3 +
 gdb/configure    | 493 +++++++++++++++++++++++++++++++++++++++++++++++
 gdb/configure.ac |  19 ++
 gdb/symtab.c     |  16 +-
 gdb/utils.c      |  14 ++
 gdb/utils.h      |   2 +
 7 files changed, 546 insertions(+), 9 deletions(-)

--
2.23.0.581.g78d2f28ef7-goog

Reply | Threaded
Open this post in threaded view
|

[PATCH v2 1/3] Store the mangled name as a string_view

Sourceware - gdb-patches mailing list
This should be a bit faster (because we can compare the size first),
but it is also a dependency for the next patch.

(3.47% of gdb startup time is spent in eq_demangled_name_entry when
attaching to Chrome's content_shell binary)

gdb/ChangeLog:

2019-09-27  Christian Biesinger  <[hidden email]>

        * symtab.c (struct demangled_name_entry): Change type of mangled
        to gdb::string_view.
        (hash_demangled_name_entry): Update.
        (eq_demangled_name_entry): Update.
        (symbol_set_names): Update.
---
 gdb/symtab.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/gdb/symtab.c b/gdb/symtab.c
index 8a551f1575..0724110d12 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -68,6 +68,7 @@
 #include "filename-seen-cache.h"
 #include "arch-utils.h"
 #include <algorithm>
+#include "gdbsupport/gdb_string_view.h"
 #include "gdbsupport/pathstuff.h"
 
 /* Forward declarations for local functions.  */
@@ -713,7 +714,7 @@ symbol_set_language (struct general_symbol_info *gsymbol,
 /* Objects of this type are stored in the demangled name hash table.  */
 struct demangled_name_entry
 {
-  const char *mangled;
+  gdb::string_view mangled;
   ENUM_BITFIELD(language) language : LANGUAGE_BITS;
   char demangled[1];
 };
@@ -726,7 +727,7 @@ hash_demangled_name_entry (const void *data)
   const struct demangled_name_entry *e
     = (const struct demangled_name_entry *) data;
 
-  return htab_hash_string (e->mangled);
+  return iterative_hash (e->mangled.data (), e->mangled.length (), 0);
 }
 
 /* Equality function for the demangled name hash.  */
@@ -739,7 +740,7 @@ eq_demangled_name_entry (const void *a, const void *b)
   const struct demangled_name_entry *db
     = (const struct demangled_name_entry *) b;
 
-  return strcmp (da->mangled, db->mangled) == 0;
+  return da->mangled == db->mangled;
 }
 
 /* Create the hash table used for demangled names.  Each hash entry is
@@ -855,7 +856,7 @@ symbol_set_names (struct general_symbol_info *gsymbol,
   else
     linkage_name_copy = linkage_name;
 
-  entry.mangled = linkage_name_copy;
+  entry.mangled = gdb::string_view (linkage_name_copy, len);
   slot = ((struct demangled_name_entry **)
   htab_find_slot (per_bfd->demangled_names_hash.get (),
   &entry, INSERT));
@@ -888,7 +889,7 @@ symbol_set_names (struct general_symbol_info *gsymbol,
        obstack_alloc (&per_bfd->storage_obstack,
       offsetof (struct demangled_name_entry, demangled)
       + demangled_len + 1));
-  (*slot)->mangled = linkage_name;
+  (*slot)->mangled = gdb::string_view (linkage_name, len);
  }
       else
  {
@@ -904,7 +905,7 @@ symbol_set_names (struct general_symbol_info *gsymbol,
       + len + demangled_len + 2));
   mangled_ptr = &((*slot)->demangled[demangled_len + 1]);
   strcpy (mangled_ptr, linkage_name_copy);
-  (*slot)->mangled = mangled_ptr;
+  (*slot)->mangled = gdb::string_view (mangled_ptr, len);
  }
       (*slot)->language = gsymbol->language;
 
@@ -917,7 +918,7 @@ symbol_set_names (struct general_symbol_info *gsymbol,
    || gsymbol->language == language_auto)
     gsymbol->language = (*slot)->language;
 
-  gsymbol->name = (*slot)->mangled;
+  gsymbol->name = (*slot)->mangled.data ();
   if ((*slot)->demangled[0] != '\0')
     symbol_set_demangled_name (gsymbol, (*slot)->demangled,
        &per_bfd->storage_obstack);
--
2.23.0.581.g78d2f28ef7-goog

Reply | Threaded
Open this post in threaded view
|

[PATCH v2 2/3] Add a fast_hash function in common-utils

Sourceware - gdb-patches mailing list
In reply to this post by Sourceware - gdb-patches mailing list
Also updates a caller in symtab.c. For now this just calls htab_hash_string
but the next patch will change it to xxhash, if available.

gdb/ChangeLog:

2019-09-27  Christian Biesinger  <[hidden email]>

        * utils.c (fast_hash): New function.
        * utils.h (fast_hash): New function.
        * symtab.c (hash_demangled_name_entry): Call new function
        fast_hash.
---
 gdb/symtab.c | 3 ++-
 gdb/utils.c  | 6 ++++++
 gdb/utils.h  | 2 ++
 3 files changed, 10 insertions(+), 1 deletion(-)

diff --git a/gdb/symtab.c b/gdb/symtab.c
index 0724110d12..2577f3909a 100644
--- a/gdb/symtab.c
+++ b/gdb/symtab.c
@@ -70,6 +70,7 @@
 #include <algorithm>
 #include "gdbsupport/gdb_string_view.h"
 #include "gdbsupport/pathstuff.h"
+#include "gdbsupport/common-utils.h"
 
 /* Forward declarations for local functions.  */
 
@@ -727,7 +728,7 @@ hash_demangled_name_entry (const void *data)
   const struct demangled_name_entry *e
     = (const struct demangled_name_entry *) data;
 
-  return iterative_hash (e->mangled.data (), e->mangled.length (), 0);
+  return fast_hash (e->mangled.data (), e->mangled.length ());
 }
 
 /* Equality function for the demangled name hash.  */
diff --git a/gdb/utils.c b/gdb/utils.c
index e685cc2084..8615820c46 100644
--- a/gdb/utils.c
+++ b/gdb/utils.c
@@ -3436,6 +3436,12 @@ copy_bitwise (gdb_byte *dest, ULONGEST dest_offset,
     }
 }
 
+unsigned int
+fast_hash (const char* str, size_t len)
+{
+  return iterative_hash (str, len, 0);
+}
+
 void
 _initialize_utils (void)
 {
diff --git a/gdb/utils.h b/gdb/utils.h
index 76f0da69f7..7101add394 100644
--- a/gdb/utils.h
+++ b/gdb/utils.h
@@ -569,4 +569,6 @@ extern void copy_bitwise (gdb_byte *dest, ULONGEST dest_offset,
   const gdb_byte *source, ULONGEST source_offset,
   ULONGEST nbits, int bits_big_endian);
 
+extern unsigned int fast_hash (const char* str, size_t len);
+
 #endif /* UTILS_H */
--
2.23.0.581.g78d2f28ef7-goog

Reply | Threaded
Open this post in threaded view
|

[PATCH v2 3/3] Use libxxhash for hashing, if present

Sourceware - gdb-patches mailing list
In reply to this post by Sourceware - gdb-patches mailing list
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_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 XXH32 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-09-27  Christian Biesinger  <[hidden email]>

        * Makefile.in: Link with libxxhash.
        * config.in: Regenerate.
        * configure: Regenerate.
        * configure.ac: Search for libxxhash.
        * utils.c (fast_hash): Use xxhash if present.
---
 gdb/Makefile.in  |   8 +-
 gdb/config.in    |   3 +
 gdb/configure    | 493 +++++++++++++++++++++++++++++++++++++++++++++++
 gdb/configure.ac |  19 ++
 gdb/utils.c      |   8 +
 5 files changed, 529 insertions(+), 2 deletions(-)

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index 36650ad555..7b3c46cf8e 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -187,10 +187,14 @@ LIBEXPAT = @LIBEXPAT@
 # Where is lzma?  This will be empty if lzma was not available.
 LIBLZMA = @LIBLZMA@
 
-# Where is libbabeltrace? This will be empty if lbabeltrace was not
+# Where is libbabeltrace? This will be empty if libbabeltrace was not
 # available.
 LIBBABELTRACE = @LIBBABELTRACE@
 
+# Where is libxxhash? This will be empty if libxxhash was not
+# available.
+LIBXXHASH = @LIBXXHASH@
+
 # Where is libipt?  This will be empty if libipt was not available.
 LIBIPT = @LIBIPT@
 
@@ -597,7 +601,7 @@ CLIBS = $(SIM) $(READLINE) $(OPCODES) $(BFD) $(LIBCTF) $(ZLIB) \
  @LIBS@ @GUILE_LIBS@ @PYTHON_LIBS@ \
  $(LIBEXPAT) $(LIBLZMA) $(LIBBABELTRACE) $(LIBIPT) \
  $(LIBIBERTY) $(WIN32LIBS) $(LIBGNU) $(LIBICONV) $(LIBMPFR) \
- $(SRCHIGH_LIBS)
+ $(SRCHIGH_LIBS) $(LIBXXHASH)
 CDEPS = $(NAT_CDEPS) $(SIM) $(BFD) $(READLINE_DEPS) $(LIBCTF) \
  $(OPCODES) $(INTL_DEPS) $(LIBIBERTY) $(CONFIG_DEPS) $(LIBGNU)
 
diff --git a/gdb/config.in b/gdb/config.in
index 26ca02f6a3..da365a7fc8 100644
--- a/gdb/config.in
+++ b/gdb/config.in
@@ -255,6 +255,9 @@
 /* Define to 1 if you have the <libunwind-ia64.h> header file. */
 #undef HAVE_LIBUNWIND_IA64_H
 
+/* Define if you have the xxhash library. */
+#undef HAVE_LIBXXHASH
+
 /* Define to 1 if you have the <linux/elf.h> header file. */
 #undef HAVE_LINUX_ELF_H
 
diff --git a/gdb/configure b/gdb/configure
index 22a5f6051d..acad7acb5c 100755
--- a/gdb/configure
+++ b/gdb/configure
@@ -627,6 +627,9 @@ GCORE_TRANSFORM_NAME
 GDB_TRANSFORM_NAME
 XSLTPROC
 GDB_NM_FILE
+LTLIBXXHASH
+LIBXXHASH
+HAVE_LIBXXHASH
 LTLIBBABELTRACE
 LIBBABELTRACE
 HAVE_LIBBABELTRACE
@@ -897,6 +900,8 @@ enable_sim
 enable_gdbserver
 with_babeltrace
 with_libbabeltrace_prefix
+with_xxhash
+with_libxxhash_prefix
 enable_unit_tests
 '
       ac_precious_vars='build_alias
@@ -1627,6 +1632,9 @@ Optional Packages:
   --with-babeltrace       include babeltrace support (auto/yes/no)
   --with-libbabeltrace-prefix[=DIR]  search for libbabeltrace in DIR/include and DIR/lib
   --without-libbabeltrace-prefix     don't search for libbabeltrace in includedir and libdir
+  --with-xxhash           use libxxhash for hashing (faster) (auto/yes/no)
+  --with-libxxhash-prefix[=DIR]  search for libxxhash in DIR/include and DIR/lib
+  --without-libxxhash-prefix     don't search for libxxhash in includedir and libdir
 
 Some influential environment variables:
   CC          C compiler command
@@ -17556,6 +17564,491 @@ $as_echo "$as_me: WARNING: babeltrace is missing or unusable; GDB is unable to r
   fi
 fi
 
+# Check for xxhash
+
+# Check whether --with-xxhash was given.
+if test "${with_xxhash+set}" = set; then :
+  withval=$with_xxhash;
+else
+  with_xxhash=auto
+fi
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking whether to use xxhash" >&5
+$as_echo_n "checking whether to use xxhash... " >&6; }
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $with_xxhash" >&5
+$as_echo "$with_xxhash" >&6; }
+
+if test "x$with_xxhash" != "xno"; then
+
+
+
+
+
+
+
+
+    use_additional=yes
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+
+    eval additional_includedir=\"$includedir\"
+    eval additional_libdir=\"$libdir\"
+
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+
+# Check whether --with-libxxhash-prefix was given.
+if test "${with_libxxhash_prefix+set}" = set; then :
+  withval=$with_libxxhash_prefix;
+    if test "X$withval" = "Xno"; then
+      use_additional=no
+    else
+      if test "X$withval" = "X"; then
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+
+          eval additional_includedir=\"$includedir\"
+          eval additional_libdir=\"$libdir\"
+
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+      else
+        additional_includedir="$withval/include"
+        additional_libdir="$withval/lib"
+      fi
+    fi
+
+fi
+
+      LIBXXHASH=
+  LTLIBXXHASH=
+  INCXXHASH=
+  rpathdirs=
+  ltrpathdirs=
+  names_already_handled=
+  names_next_round='xxhash '
+  while test -n "$names_next_round"; do
+    names_this_round="$names_next_round"
+    names_next_round=
+    for name in $names_this_round; do
+      already_handled=
+      for n in $names_already_handled; do
+        if test "$n" = "$name"; then
+          already_handled=yes
+          break
+        fi
+      done
+      if test -z "$already_handled"; then
+        names_already_handled="$names_already_handled $name"
+                        uppername=`echo "$name" | sed -e 'y|abcdefghijklmnopqrstuvwxyz./-|ABCDEFGHIJKLMNOPQRSTUVWXYZ___|'`
+        eval value=\"\$HAVE_LIB$uppername\"
+        if test -n "$value"; then
+          if test "$value" = yes; then
+            eval value=\"\$LIB$uppername\"
+            test -z "$value" || LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$value"
+            eval value=\"\$LTLIB$uppername\"
+            test -z "$value" || LTLIBXXHASH="${LTLIBXXHASH}${LTLIBXXHASH:+ }$value"
+          else
+                                    :
+          fi
+        else
+                              found_dir=
+          found_la=
+          found_so=
+          found_a=
+          if test $use_additional = yes; then
+            if test -n "$shlibext" && test -f "$additional_libdir/lib$name.$shlibext"; then
+              found_dir="$additional_libdir"
+              found_so="$additional_libdir/lib$name.$shlibext"
+              if test -f "$additional_libdir/lib$name.la"; then
+                found_la="$additional_libdir/lib$name.la"
+              fi
+            else
+              if test -f "$additional_libdir/lib$name.$libext"; then
+                found_dir="$additional_libdir"
+                found_a="$additional_libdir/lib$name.$libext"
+                if test -f "$additional_libdir/lib$name.la"; then
+                  found_la="$additional_libdir/lib$name.la"
+                fi
+              fi
+            fi
+          fi
+          if test "X$found_dir" = "X"; then
+            for x in $LDFLAGS $LTLIBXXHASH; do
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+  eval x=\"$x\"
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+              case "$x" in
+                -L*)
+                  dir=`echo "X$x" | sed -e 's/^X-L//'`
+                  if test -n "$shlibext" && test -f "$dir/lib$name.$shlibext"; then
+                    found_dir="$dir"
+                    found_so="$dir/lib$name.$shlibext"
+                    if test -f "$dir/lib$name.la"; then
+                      found_la="$dir/lib$name.la"
+                    fi
+                  else
+                    if test -f "$dir/lib$name.$libext"; then
+                      found_dir="$dir"
+                      found_a="$dir/lib$name.$libext"
+                      if test -f "$dir/lib$name.la"; then
+                        found_la="$dir/lib$name.la"
+                      fi
+                    fi
+                  fi
+                  ;;
+              esac
+              if test "X$found_dir" != "X"; then
+                break
+              fi
+            done
+          fi
+          if test "X$found_dir" != "X"; then
+                        LTLIBXXHASH="${LTLIBXXHASH}${LTLIBXXHASH:+ }-L$found_dir -l$name"
+            if test "X$found_so" != "X"; then
+                                                        if test "$enable_rpath" = no || test "X$found_dir" = "X/usr/lib"; then
+                                LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$found_so"
+              else
+                                                                                haveit=
+                for x in $ltrpathdirs; do
+                  if test "X$x" = "X$found_dir"; then
+                    haveit=yes
+                    break
+                  fi
+                done
+                if test -z "$haveit"; then
+                  ltrpathdirs="$ltrpathdirs $found_dir"
+                fi
+                                if test "$hardcode_direct" = yes; then
+                                                      LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$found_so"
+                else
+                  if test -n "$hardcode_libdir_flag_spec" && test "$hardcode_minus_L" = no; then
+                                                            LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$found_so"
+                                                            haveit=
+                    for x in $rpathdirs; do
+                      if test "X$x" = "X$found_dir"; then
+                        haveit=yes
+                        break
+                      fi
+                    done
+                    if test -z "$haveit"; then
+                      rpathdirs="$rpathdirs $found_dir"
+                    fi
+                  else
+                                                                                haveit=
+                    for x in $LDFLAGS $LIBXXHASH; do
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+  eval x=\"$x\"
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+                      if test "X$x" = "X-L$found_dir"; then
+                        haveit=yes
+                        break
+                      fi
+                    done
+                    if test -z "$haveit"; then
+                      LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }-L$found_dir"
+                    fi
+                    if test "$hardcode_minus_L" != no; then
+                                                                                        LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$found_so"
+                    else
+                                                                                                                                                                                LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }-l$name"
+                    fi
+                  fi
+                fi
+              fi
+            else
+              if test "X$found_a" != "X"; then
+                                LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$found_a"
+              else
+                                                LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }-L$found_dir -l$name"
+              fi
+            fi
+                        additional_includedir=
+            case "$found_dir" in
+              */lib | */lib/)
+                basedir=`echo "X$found_dir" | sed -e 's,^X,,' -e 's,/lib/*$,,'`
+                additional_includedir="$basedir/include"
+                ;;
+            esac
+            if test "X$additional_includedir" != "X"; then
+                                                                                                                if test "X$additional_includedir" != "X/usr/include"; then
+                haveit=
+                if test "X$additional_includedir" = "X/usr/local/include"; then
+                  if test -n "$GCC"; then
+                    case $host_os in
+                      linux*) haveit=yes;;
+                    esac
+                  fi
+                fi
+                if test -z "$haveit"; then
+                  for x in $CPPFLAGS $INCXXHASH; do
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+  eval x=\"$x\"
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+                    if test "X$x" = "X-I$additional_includedir"; then
+                      haveit=yes
+                      break
+                    fi
+                  done
+                  if test -z "$haveit"; then
+                    if test -d "$additional_includedir"; then
+                                            INCXXHASH="${INCXXHASH}${INCXXHASH:+ }-I$additional_includedir"
+                    fi
+                  fi
+                fi
+              fi
+            fi
+                        if test -n "$found_la"; then
+                                                        save_libdir="$libdir"
+              case "$found_la" in
+                */* | *\\*) . "$found_la" ;;
+                *) . "./$found_la" ;;
+              esac
+              libdir="$save_libdir"
+                            for dep in $dependency_libs; do
+                case "$dep" in
+                  -L*)
+                    additional_libdir=`echo "X$dep" | sed -e 's/^X-L//'`
+                                                                                                                                                                if test "X$additional_libdir" != "X/usr/lib"; then
+                      haveit=
+                      if test "X$additional_libdir" = "X/usr/local/lib"; then
+                        if test -n "$GCC"; then
+                          case $host_os in
+                            linux*) haveit=yes;;
+                          esac
+                        fi
+                      fi
+                      if test -z "$haveit"; then
+                        haveit=
+                        for x in $LDFLAGS $LIBXXHASH; do
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+  eval x=\"$x\"
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+                          if test "X$x" = "X-L$additional_libdir"; then
+                            haveit=yes
+                            break
+                          fi
+                        done
+                        if test -z "$haveit"; then
+                          if test -d "$additional_libdir"; then
+                                                        LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }-L$additional_libdir"
+                          fi
+                        fi
+                        haveit=
+                        for x in $LDFLAGS $LTLIBXXHASH; do
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+  eval x=\"$x\"
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+                          if test "X$x" = "X-L$additional_libdir"; then
+                            haveit=yes
+                            break
+                          fi
+                        done
+                        if test -z "$haveit"; then
+                          if test -d "$additional_libdir"; then
+                                                        LTLIBXXHASH="${LTLIBXXHASH}${LTLIBXXHASH:+ }-L$additional_libdir"
+                          fi
+                        fi
+                      fi
+                    fi
+                    ;;
+                  -R*)
+                    dir=`echo "X$dep" | sed -e 's/^X-R//'`
+                    if test "$enable_rpath" != no; then
+                                                                  haveit=
+                      for x in $rpathdirs; do
+                        if test "X$x" = "X$dir"; then
+                          haveit=yes
+                          break
+                        fi
+                      done
+                      if test -z "$haveit"; then
+                        rpathdirs="$rpathdirs $dir"
+                      fi
+                                                                  haveit=
+                      for x in $ltrpathdirs; do
+                        if test "X$x" = "X$dir"; then
+                          haveit=yes
+                          break
+                        fi
+                      done
+                      if test -z "$haveit"; then
+                        ltrpathdirs="$ltrpathdirs $dir"
+                      fi
+                    fi
+                    ;;
+                  -l*)
+                                        names_next_round="$names_next_round "`echo "X$dep" | sed -e 's/^X-l//'`
+                    ;;
+                  *.la)
+                                                                                names_next_round="$names_next_round "`echo "X$dep" | sed -e 's,^X.*/,,' -e 's,^lib,,' -e 's,\.la$,,'`
+                    ;;
+                  *)
+                                        LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$dep"
+                    LTLIBXXHASH="${LTLIBXXHASH}${LTLIBXXHASH:+ }$dep"
+                    ;;
+                esac
+              done
+            fi
+          else
+                                                            LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }-l$name"
+            LTLIBXXHASH="${LTLIBXXHASH}${LTLIBXXHASH:+ }-l$name"
+          fi
+        fi
+      fi
+    done
+  done
+  if test "X$rpathdirs" != "X"; then
+    if test -n "$hardcode_libdir_separator"; then
+                        alldirs=
+      for found_dir in $rpathdirs; do
+        alldirs="${alldirs}${alldirs:+$hardcode_libdir_separator}$found_dir"
+      done
+            acl_save_libdir="$libdir"
+      libdir="$alldirs"
+      eval flag=\"$hardcode_libdir_flag_spec\"
+      libdir="$acl_save_libdir"
+      LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$flag"
+    else
+            for found_dir in $rpathdirs; do
+        acl_save_libdir="$libdir"
+        libdir="$found_dir"
+        eval flag=\"$hardcode_libdir_flag_spec\"
+        libdir="$acl_save_libdir"
+        LIBXXHASH="${LIBXXHASH}${LIBXXHASH:+ }$flag"
+      done
+    fi
+  fi
+  if test "X$ltrpathdirs" != "X"; then
+            for found_dir in $ltrpathdirs; do
+      LTLIBXXHASH="${LTLIBXXHASH}${LTLIBXXHASH:+ }-R$found_dir"
+    done
+  fi
+
+
+        ac_save_CPPFLAGS="$CPPFLAGS"
+
+  for element in $INCXXHASH; do
+    haveit=
+    for x in $CPPFLAGS; do
+
+  acl_save_prefix="$prefix"
+  prefix="$acl_final_prefix"
+  acl_save_exec_prefix="$exec_prefix"
+  exec_prefix="$acl_final_exec_prefix"
+  eval x=\"$x\"
+  exec_prefix="$acl_save_exec_prefix"
+  prefix="$acl_save_prefix"
+
+      if test "X$x" = "X$element"; then
+        haveit=yes
+        break
+      fi
+    done
+    if test -z "$haveit"; then
+      CPPFLAGS="${CPPFLAGS}${CPPFLAGS:+ }$element"
+    fi
+  done
+
+
+  { $as_echo "$as_me:${as_lineno-$LINENO}: checking for libxxhash" >&5
+$as_echo_n "checking for libxxhash... " >&6; }
+if ${ac_cv_libxxhash+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+
+    ac_save_LIBS="$LIBS"
+    LIBS="$LIBS $LIBXXHASH"
+    cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+#include <xxhash.h>
+int
+main ()
+{
+XXH32("foo", 3, 0);
+
+  ;
+  return 0;
+}
+_ACEOF
+if ac_fn_c_try_link "$LINENO"; then :
+  ac_cv_libxxhash=yes
+else
+  ac_cv_libxxhash=no
+fi
+rm -f core conftest.err conftest.$ac_objext \
+    conftest$ac_exeext conftest.$ac_ext
+    LIBS="$ac_save_LIBS"
+
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $ac_cv_libxxhash" >&5
+$as_echo "$ac_cv_libxxhash" >&6; }
+  if test "$ac_cv_libxxhash" = yes; then
+    HAVE_LIBXXHASH=yes
+
+$as_echo "#define HAVE_LIBXXHASH 1" >>confdefs.h
+
+    { $as_echo "$as_me:${as_lineno-$LINENO}: checking how to link with libxxhash" >&5
+$as_echo_n "checking how to link with libxxhash... " >&6; }
+    { $as_echo "$as_me:${as_lineno-$LINENO}: result: $LIBXXHASH" >&5
+$as_echo "$LIBXXHASH" >&6; }
+  else
+    HAVE_LIBXXHASH=no
+            CPPFLAGS="$ac_save_CPPFLAGS"
+    LIBXXHASH=
+    LTLIBXXHASH=
+  fi
+
+
+
+
+
+
+  if test "$HAVE_XXHASH" != yes; then
+     if test "$with_xxhash" = yes; then
+       as_fn_error $? "xxhash is missing or unusable" "$LINENO" 5
+     fi
+  fi
+fi
+
 # If nativefile (NAT_FILE) is not set in configure.nat, we link to an
 # empty version.
 
diff --git a/gdb/configure.ac b/gdb/configure.ac
index 9da8818fb5..7a2a5ca9d4 100644
--- a/gdb/configure.ac
+++ b/gdb/configure.ac
@@ -2217,6 +2217,25 @@ else
   fi
 fi
 
+# Check for xxhash
+AC_ARG_WITH(xxhash,
+  AC_HELP_STRING([--with-xxhash], [use libxxhash for hashing (faster) (auto/yes/no)]),
+  [], [with_xxhash=auto])
+AC_MSG_CHECKING([whether to use xxhash])
+AC_MSG_RESULT([$with_xxhash])
+
+if test "x$with_xxhash" != "xno"; then
+  AC_LIB_HAVE_LINKFLAGS([xxhash], [],
+ [#include <xxhash.h>],
+ [XXH32("foo", 3, 0);
+ ])
+  if test "$HAVE_XXHASH" != yes; then
+     if test "$with_xxhash" = yes; then
+       AC_MSG_ERROR([xxhash is missing or unusable])
+     fi
+  fi
+fi
+
 # If nativefile (NAT_FILE) is not set in configure.nat, we link to an
 # empty version.
 
diff --git a/gdb/utils.c b/gdb/utils.c
index 8615820c46..a0b546342b 100644
--- a/gdb/utils.c
+++ b/gdb/utils.c
@@ -36,6 +36,10 @@
 #include <pc.h>
 #endif
 
+#ifdef HAVE_LIBXXHASH
+#include <xxhash.h>
+#endif
+
 #include <signal.h>
 #include "gdbcmd.h"
 #include "serial.h"
@@ -3439,7 +3443,11 @@ copy_bitwise (gdb_byte *dest, ULONGEST dest_offset,
 unsigned int
 fast_hash (const char* str, size_t len)
 {
+#ifdef HAVE_LIBXXHASH
+  return XXH32(str, len, 0);
+#else
   return iterative_hash (str, len, 0);
+#endif
 }
 
 void
--
2.23.0.581.g78d2f28ef7-goog