[PATCH v2 3/3] lib: Avoid the hash-lookup division if possible

Josh Stone jistone at redhat.com
Fri Dec 13 02:32:12 UTC 2013


For Dwarf_Abbrev codes, the most common case is that they're packed at
the low end, saving uleb128 encoding size.  Since the hash table is
always resized to be no more than 90% full, those codes are always less
than the table size, and dividing for the remainder is unnecessary.

Dwarf_Dies are frequently created anew, and need to find abbrev each
time, so even that one division becomes a noticeable hotspot.  This
patch adds a branch to avoid it, which is very predictable for the CPU.

Signed-off-by: Josh Stone <jistone at redhat.com>
---
 lib/ChangeLog         | 4 ++++
 lib/dynamicsizehash.c | 5 +++--
 2 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/lib/ChangeLog b/lib/ChangeLog
index 6ce3168f0ae6..9b8899e2ca5c 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,7 @@
+2013-12-12  Josh Stone  <jistone at redhat.com>
+
+	* dynamicsizehash.c (lookup): Add a shortcut around division.
+
 2013-04-30  Jan Kratochvil  <jan.kratochvil at redhat.com>
 
 	* eu-config.h (COMPAT_VERSION_NEWPROTO): New.  Twice.
diff --git a/lib/dynamicsizehash.c b/lib/dynamicsizehash.c
index 40f48d5ed119..acb360030376 100644
--- a/lib/dynamicsizehash.c
+++ b/lib/dynamicsizehash.c
@@ -49,8 +49,9 @@ lookup (htab, hval, val)
      HASHTYPE hval;
      TYPE val __attribute__ ((unused));
 {
-  /* First hash function: simply take the modul but prevent zero.  */
-  size_t idx = 1 + hval % htab->size;
+  /* First hash function: simply take the modul but prevent zero.  Small values
+   * can skip the division, which helps performance when this is common.  */
+  size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
 
   if (htab->table[idx].hashval != 0)
     {
-- 
1.8.4.2



More information about the elfutils-devel mailing list