[PATCH 3/5] use jhash for STRING_N_HASH

[Paolo Bonzini]

The hottest hash table in Make is the variable hash, and it is
easy to apply a better function (that works on bigger chunks
than just one byte) because the length of its key is known.
This is about twice as fast as the current hash, and removes
the need for double hashing (improving locality of reference).
The hash function is based on Bob Jenkins' design.  It relies
on the compiler to optimize a memcpy to an unaligned load.

The resulting speedup on QEMU's noop build is 3.8% (from 13.8
seconds to 13.2).

* hash.c (rol32, jhash_mix, jhash_final, JHASH_INITVAL,
sum_get_unaligned_32, jhash): New.
* hash.h (STRING_N_HASH_1): Use jhash.
(STRING_N_HASH_2): Return a dummy value.
---
 hash.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 hash.h | 21 ++++++------------
 2 files changed, 89 insertions(+), 14 deletions(-)

diff --git a/hash.c b/hash.c
index 7b4b271..e6f4afc 100644
--- a/hash.c
+++ b/hash.c
@@ -328,3 +328,85 @@ round_up_2 (unsigned long n)
 
   return n + 1;
 }
+
+#define rol32(v, n) \
+       ((v) << (n) | ((v) >> (32 - (n))))
+
+/* jhash_mix -- mix 3 32-bit values reversibly. */
+#define jhash_mix(a, b, c)                      \
+{                                               \
+        a -= c;  a ^= rol32(c, 4);  c += b;     \
+        b -= a;  b ^= rol32(a, 6);  a += c;     \
+        c -= b;  c ^= rol32(b, 8);  b += a;     \
+        a -= c;  a ^= rol32(c, 16); c += b;     \
+        b -= a;  b ^= rol32(a, 19); a += c;     \
+        c -= b;  c ^= rol32(b, 4);  b += a;     \
+}
+
+/* jhash_final - final mixing of 3 32-bit values (a,b,c) into c */
+#define jhash_final(a, b, c)                    \
+{                                               \
+        c ^= b; c -= rol32(b, 14);              \
+        a ^= c; a -= rol32(c, 11);              \
+        b ^= a; b -= rol32(a, 25);              \
+        c ^= b; c -= rol32(b, 16);              \
+        a ^= c; a -= rol32(c, 4);               \
+        b ^= a; b -= rol32(a, 14);              \
+        c ^= b; c -= rol32(b, 24);              \
+}
+
+/* An arbitrary initial parameter */
+#define JHASH_INITVAL           0xdeadbeef
+
+#define sum_get_unaligned_32(r, p)              \
+  do {                                          \
+    unsigned int val;                           \
+    memcpy(&val, (p), 4);                       \
+    (r) += val;                                 \
+  } while(0);
+
+unsigned jhash(unsigned const char *k, int length)
+{
+  unsigned int a, b, c;
+
+  /* Set up the internal state */
+  a = b = c = JHASH_INITVAL + length;
+
+  /* All but the last block: affect some 32 bits of (a,b,c) */
+  while (length > 12)
+    {
+      sum_get_unaligned_32(a, k);
+      sum_get_unaligned_32(b, k + 4);
+      sum_get_unaligned_32(c, k + 8);
+      jhash_mix(a, b, c);
+      length -= 12;
+      k += 12;
+    }
+
+  if (!length)
+    return c;
+
+  if (length > 8)
+    {
+      sum_get_unaligned_32(a, k);
+      length -= 4;
+      k += 4;
+    }
+  if (length > 4)
+    {
+      sum_get_unaligned_32(b, k);
+      length -= 4;
+      k += 4;
+    }
+
+  if (length == 4)
+    c += (unsigned)k[3]<<24;
+  if (length >= 3)
+    c += (unsigned)k[2]<<16;
+  if (length >= 2)
+    c += (unsigned)k[1]<<8;
+  c += k[0];
+  jhash_final(a, b, c);
+  return c;
+}
diff --git a/hash.h b/hash.h
index 960cbd7..f01cf6a 100644
--- a/hash.h
+++ b/hash.h
@@ -73,6 +73,8 @@ void hash_map_arg __P((struct hash_table *ht, 
hash_map_arg_func_t map, void *arg
 void hash_print_stats __P((struct hash_table *ht, FILE *out_FILE));
 void **hash_dump __P((struct hash_table *ht, void **vector_0, qsort_cmp_t 
compare));
 
+extern unsigned jhash(unsigned char const *key, int n);
+
 extern void *hash_deleted_item;
 #define HASH_VACANT(item) ((item) == 0 || (void *) (item) == hash_deleted_item)
 
@@ -113,27 +115,18 @@ extern void *hash_deleted_item;
 
 
 #define STRING_N_HASH_1(KEY, N, RESULT) do { \
-  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
-  int _n_ = (N); \
-  if (_n_) \
-    while (--_n_ && *++_key_) \
-      (RESULT) += (*_key_ << (_key_[1] & 0xf)); \
-  (RESULT) += *++_key_; \
+  unsigned char const *_key_ = (unsigned char const *) (KEY); \
+  (RESULT) += jhash(_key_, N); \
 } while (0)
+
 #define return_STRING_N_HASH_1(KEY, N) do { \
   unsigned long _result_ = 0; \
   STRING_N_HASH_1 ((KEY), (N), _result_); \
   return _result_; \
 } while (0)
 
-#define STRING_N_HASH_2(KEY, N, RESULT) do { \
-  unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \
-  int _n_ = (N); \
-  if (_n_) \
-    while (--_n_ && *++_key_) \
-      (RESULT) += (*_key_ << (_key_[1] & 0x7)); \
-  (RESULT) += *++_key_; \
-} while (0)
+#define STRING_N_HASH_2(KEY, N, RESULT) do ; while (0)
+
 #define return_STRING_N_HASH_2(KEY, N) do { \
   unsigned long _result_ = 0; \
   STRING_N_HASH_2 ((KEY), (N), _result_); \
-- 
2.7.4