[PATCH v11 5/6] nss: Optimize nss_hash in nss_hash.c

[Noah Goldstein <goldstein.w.n@gmail.com>]

The prior unrolling didn't really do much as it left the dependency
chain between iterations. Unrolled the loop for 4 so 4x multiplies
could be pipelined in out-of-order machines.

Results for __nss_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.845
  type, length, New Time, Old Time, New Time / Old Time
 fixed,      0,    4.019,    3.729,               1.078
 fixed,      1,     4.95,    5.707,               0.867
 fixed,      2,    5.152,    5.657,               0.911
 fixed,      3,    4.641,    5.721,               0.811
 fixed,      4,    5.551,     5.81,               0.955
 fixed,      5,    6.525,    6.552,               0.996
 fixed,      6,    6.711,    6.561,               1.023
 fixed,      7,    6.715,    6.767,               0.992
 fixed,      8,    7.874,    7.915,               0.995
 fixed,      9,    8.888,    9.767,                0.91
 fixed,     10,    8.959,    9.762,               0.918
 fixed,     11,    9.188,    9.987,                0.92
 fixed,     12,    9.708,   10.618,               0.914
 fixed,     13,   10.393,    11.14,               0.933
 fixed,     14,   10.628,   12.097,               0.879
 fixed,     15,   10.982,   12.965,               0.847
 fixed,     16,   11.851,   14.429,               0.821
 fixed,     32,   24.334,   34.414,               0.707
 fixed,     64,   55.618,   86.688,               0.642
 fixed,    128,  118.261,   224.36,               0.527
 fixed,    256,  256.183,  538.629,               0.476
random,      2,   11.194,   11.556,               0.969
random,      4,   17.516,   17.205,               1.018
random,      8,   23.501,   20.985,                1.12
random,     16,   28.131,   29.212,               0.963
random,     32,   35.436,   38.662,               0.917
random,     64,    45.74,   58.868,               0.777
random,    128,   75.394,  121.963,               0.618
random,    256,  139.524,  260.726,               0.535
---
 nss/nss_hash.c | 79 +++++++++++++++++++++++++++-----------------------
 1 file changed, 42 insertions(+), 37 deletions(-)

diff --git a/nss/nss_hash.c b/nss/nss_hash.c
index 3d8e4cf37e..1d3787e675 100644
--- a/nss/nss_hash.c
+++ b/nss/nss_hash.c
@@ -19,58 +19,63 @@
 
 /* This is from libc/db/hash/hash_func.c, hash3 is static there */
 /*
- * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
+ * This is INCREDIBLY ugly, but fast.  We break the string up into 4 byte
  * units.  On the first time through the loop we get the "leftover bytes"
- * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
- * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
- * this routine is heavily used enough, it's worth the ugly coding.
+ * (len % 4).  On every other iteration, we perform a 4x unrolled version
+ * HASHC. Further unrolling does not appear to help.
  *
  * OZ's original sdbm hash
  */
 uint32_t
 __nss_hash (const void *keyarg, size_t len)
 {
+  enum
+  {
+    HASH_CONST_P0 = 1,	       /* (uint32_t)(65599 ^ 0).  */
+    HASH_CONST_P1 = 65599,     /* (uint32_t)(65599 ^ 1).  */
+    HASH_CONST_P2 = 8261505,   /* (uint32_t)(65599 ^ 2).  */
+    HASH_CONST_P3 = 780587199, /* (uint32_t)(65599 ^ 3).  */
+    HASH_CONST_P4 = 1139564289 /* (uint32_t)(65599 ^ 4).  */
+  };
+
   const unsigned char *key;
-  size_t loop;
   uint32_t h;
 
-#define HASHC   h = *key++ + 65599 * h
+#define HASHC	h = *key++ + HASH_CONST_P1 * h
 
   h = 0;
   key = keyarg;
   if (len > 0)
     {
-      loop = (len + 8 - 1) >> 3;
-      switch (len & (8 - 1))
-        {
-        case 0:
-          do
-            {
-              HASHC;
-              /* FALLTHROUGH */
-            case 7:
-              HASHC;
-              /* FALLTHROUGH */
-            case 6:
-              HASHC;
-              /* FALLTHROUGH */
-            case 5:
-              HASHC;
-              /* FALLTHROUGH */
-            case 4:
-              HASHC;
-              /* FALLTHROUGH */
-            case 3:
-              HASHC;
-              /* FALLTHROUGH */
-            case 2:
-              HASHC;
-              /* FALLTHROUGH */
-            case 1:
-              HASHC;
-            }
-	  while (--loop);
-        }
+      switch ((len & (4 - 1)))
+	{
+	case 0:
+	  /* h starts out as zero so no need to include the multiply. */
+	  h = *key++;
+	  /* FALLTHROUGH */
+	case 3:
+	  HASHC;
+	  /* FALLTHROUGH */
+	case 2:
+	  HASHC;
+	  /* FALLTHROUGH */
+	case 1:
+	  HASHC;
+	  /* FALLTHROUGH */
+	}
+
+      uint32_t c0, c1, c2, c3;
+      for (--len; len >= 4; len -= 4)
+	{
+	  c0 = (unsigned char) *(key + 0);
+	  c1 = (unsigned char) *(key + 1);
+	  c2 = (unsigned char) *(key + 2);
+	  c3 = (unsigned char) *(key + 3);
+	  h = HASH_CONST_P4 * h + HASH_CONST_P3 * c0 + HASH_CONST_P2 * c1
+	      + HASH_CONST_P1 * c2 + HASH_CONST_P0 * c3;
+
+	  key += 4;
+	}
     }
   return h;
 }
-- 
2.34.1