[PATCH] Fast String Hash

[Mike Pall <mikelu-0712@...>]

This is an experimental patch for fast(er) string hashing. It's a
backport of the new string hash algorithm from LuaJIT 2.x.

I'm posting this as a follow-up to the recent thread about
speeding up string processing. My intention is to gather some
early feedback on the new hash algorithm (speed _and_ quality).

The attached patch applies cleanly to Lua 5.1.2 and LuaJIT 1.1.3.
You may want to try this patch in your applications, if you
suspect that string hashing is a bottleneck. Please post your
findings!

The new hash algorithm is a bastardized variant of Bob Jenkins'
fast rotate-and-mix hash. It hashes up to 12 chars from a string,
picked from the start, middle and end. The basic ideas are: less
fetches, more bit mixing, no loops and a constant hash time.

CAVEAT: this version relies on UNALIGNED access of 32 bit words
for speed. I.e. it probably only works on x86 and will certainly
crash on most other architectures. Sorry, I don't have the time
right now to add a (fast) replacement with aligned accesses. Feel
free to adapt the patch to your needs.

I've done some extensive tuning and profiling on it:

The hash quality is superior to Lua's standard string hash in all
my tests. It's a lot better for the kind of short strings
typically used for field names or method names. Hash quality does
not deteriorate noticeably for longer strings, except for
hand-crafted cases (but these exist for the Lua hash, too).

The hash speed is constant (wrt. string length). It's typically
2x-10x faster than Lua's standard string hash. It's much more
suitable for modern CPUs with out-of-order execution.

Note: this is just the isolated speedup for the hash calculcation
itself. It cannot be used to predict the performance of a complex
application. One has to take into account the relative time spent
on string hashing and the effect on hash collisions, too. I've
found a ~5-10% speedup in benchmarks which create huge amounts of
strings and (not suprisingly) no difference at all in other
benchmarks. YMMV.

--Mike

--- lua-5.1.2/src/lstring.c	2005-12-22 17:19:56 +0100
+++ lua-5.1.2-fasthash/src/lstring.c	2007-12-17 21:06:16 +0100
@@ -74,11 +74,28 @@
 
 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
   GCObject *o;
-  unsigned int h = cast(unsigned int, l);  /* seed */
-  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
-  size_t l1;
-  for (l1=l; l1>=step; l1-=step)  /* compute hash */
-    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
+  unsigned int a, b, h = cast(unsigned int, l);
+  /* Bastardized variant of Bob Jenkins' rotate-and-mix hash. */
+  if (l >= 4) {  /* Caveat: unaligned access! */
+    a = *(const unsigned int *)str;
+    h ^= *(const unsigned int *)(str+l-4);
+    b = *(const unsigned int *)(str+(l>>1)-2);
+  } else if (l > 0) {
+    a = *(const unsigned char *)str;
+    h ^= *(const unsigned char *)(str+l-1);
+    b = *(const unsigned char *)(str+(l>>1));
+  } else { 
+    goto empty;
+  }
+#define rotleft(a, b)		(((a)<<(b)) | ((a)>>(32-(b))))
+  h ^= b; h -= rotleft(b, 14);
+  a ^= h; a -= rotleft(h, 11);
+  b ^= a; b -= rotleft(a, 25);
+  h ^= b; h -= rotleft(b, 16);
+  a ^= h; a -= rotleft(h, 4);
+  b ^= a; b -= rotleft(a, 14);
+  h ^= b; h -= rotleft(b, 24);
+empty:
   for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
        o != NULL;
        o = o->gch.next) {