diff mbox series

[v1,6/6] elf: Optimize __dl_new_hash in dl-hash.h

Message ID 20220414041231.926415-6-goldstein.w.n@gmail.com
State Superseded
Headers
Series [v1,1/6] elf: Refactor dl_new_hash so it can be tested / benchmarked |

Checks

Context Check Description
dj/TryBot-apply_patch success Patch applied to master at the time it was sent
dj/TryBot-32bit success Build for i686

Commit Message

Noah Goldstein April 14, 2022, 4:12 a.m. UTC 
  Unroll slightly so some of the multiples can be pipelined on out-order
machines. Unrolling further started to induce slowdowns for sizes
[0, 4] but can help the loop so if larger sizes are the target
further unrolling can be beneficial.

Results for __dl_new_hash
Benchmarked on Tigerlake: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz

Time as Geometric Mean of N=25 runs
Geometric of all benchmark New / Old: 0.791
  type, length, New Time, Old Time, New Time / Old Time
 fixed,      0,    0.641,    0.658,               0.974
 fixed,      1,    1.888,    1.883,               1.003
 fixed,      2,    2.712,    2.833,               0.957
 fixed,      3,    3.314,    3.739,               0.886
 fixed,      4,    4.316,    4.866,               0.887
 fixed,      5,     5.16,    5.966,               0.865
 fixed,      6,    5.986,    7.241,               0.827
 fixed,      7,    7.264,    8.435,               0.861
 fixed,      8,    8.052,    9.846,               0.818
 fixed,      9,    9.369,   11.316,               0.828
 fixed,     10,   10.256,   12.925,               0.794
 fixed,     11,   12.191,   14.546,               0.838
 fixed,     12,   12.667,    15.92,               0.796
 fixed,     13,   14.442,   17.465,               0.827
 fixed,     14,   14.808,   18.981,                0.78
 fixed,     15,   16.244,   20.565,                0.79
 fixed,     16,   17.166,   22.044,               0.779
 fixed,     32,   35.447,   50.558,               0.701
 fixed,     64,   86.479,  134.529,               0.643
 fixed,    128,  155.453,  287.527,               0.541
 fixed,    256,   302.57,   593.64,                0.51
random,      2,   11.168,    10.61,               1.053
random,      4,   13.308,    13.53,               0.984
random,      8,   16.579,   19.437,               0.853
random,     16,   21.292,   24.776,               0.859
random,     32,    30.56,   35.906,               0.851
random,     64,   49.249,   68.577,               0.718
random,    128,   81.845,  140.664,               0.582
random,    256,  152.517,  292.204,               0.522
---
 sysdeps/generic/dl-hash.h | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)
diff mbox series

Patch

diff --git a/sysdeps/generic/dl-hash.h b/sysdeps/generic/dl-hash.h
index c041074352..425ab0876e 100644
--- a/sysdeps/generic/dl-hash.h
+++ b/sysdeps/generic/dl-hash.h
@@ -21,6 +21,9 @@ 
 
 #include <stdint.h>
 
+/* For __glibc_unlikely.  */
+#include <sys/cdefs.h>
+
 #ifndef __HAS_DL_ELF_HASH
 /* This is the hashing function specified by the ELF ABI.  In the
    first five operations no overflow is possible so we optimized it a
@@ -76,12 +79,29 @@  _dl_elf_hash (const char *name_arg)
 #endif /* !__HAS_DL_ELF_HASH */
 
 static uint32_t
+__attribute__ ((unused))
 __dl_new_hash (const char *s)
 {
-  uint32_t h = 5381;
-  for (unsigned char c = *s; c != '\0'; c = *++s)
-    h = h * 33 + c;
-  return h;
+  unsigned int h = 5381;
+  unsigned char c0, c1;
+  for (;;)
+    {
+      c0 = *s;
+      /* Unlikely length zero string so evens will be slightly less
+         common.  */
+      if (__glibc_unlikely (c0 == 0))
+	{
+	  return h;
+	}
+
+      c1 = *(s + 1);
+      if (c1 == 0)
+	{
+	  return h * 33 + c0;
+	}
+      h = 33 * 33 * h + 33 * c0 + c1;
+      s += 2;
+    }
 }