From 420124372b7643410a1cdd6f80b9cc8aa6ec1302 Mon Sep 17 00:00:00 2001
From: Mike Pall <mike>
Date: Wed, 21 Jul 2010 22:53:27 +0200
Subject: Switch to fast string hash.

---
 src/lj_gc.c    |  1 +
 src/lj_obj.h   |  3 ++-
 src/lj_state.c |  2 ++
 src/lj_str.c   | 26 ++++++++++++++++++++------
 4 files changed, 25 insertions(+), 7 deletions(-)

(limited to 'src')

diff --git a/src/lj_gc.c b/src/lj_gc.c
index 0f0ca82e..8147cb55 100644
--- a/src/lj_gc.c
+++ b/src/lj_gc.c
@@ -540,6 +540,7 @@ static void atomic(global_State *g, lua_State *L)
 
   /* Prepare for sweep phase. */
   g->gc.currentwhite = cast_byte(otherwhite(g));  /* Flip current white. */
+  g->strempty.marked = g->gc.currentwhite;
   setmref(g->gc.sweep, &g->gc.root);
   g->gc.estimate = g->gc.total - (MSize)udsize;  /* Initial estimate. */
 }
diff --git a/src/lj_obj.h b/src/lj_obj.h
index f29ecb0b..762e58ce 100644
--- a/src/lj_obj.h
+++ b/src/lj_obj.h
@@ -473,10 +473,11 @@ typedef struct global_State {
   GCState gc;		/* Garbage collector. */
   SBuf tmpbuf;		/* Temporary buffer for string concatenation. */
   Node nilnode;		/* Fallback 1-element hash part (nil key and value). */
+  GCstr strempty;	/* Empty string. */
+  uint8_t stremptyz;	/* Zero terminator of empty string. */
   uint8_t hookmask;	/* Hook mask. */
   uint8_t dispatchmode;	/* Dispatch mode. */
   uint8_t vmevmask;	/* VM event mask. */
-  uint8_t unused1;
   GCRef mainthref;	/* Link to main thread. */
   TValue registrytv;	/* Anchor for registry. */
   TValue tmptv;		/* Temporary TValue. */
diff --git a/src/lj_state.c b/src/lj_state.c
index e90359ef..87f2cfe9 100644
--- a/src/lj_state.c
+++ b/src/lj_state.c
@@ -191,6 +191,8 @@ LUA_API lua_State *lua_newstate(lua_Alloc f, void *ud)
   L->dummy_ffid = FF_C;
   setmref(L->glref, g);
   g->gc.currentwhite = LJ_GC_WHITE0 | LJ_GC_FIXED;
+  g->strempty.marked = LJ_GC_WHITE0;
+  g->strempty.gct = ~LJ_TSTR;
   g->allocf = f;
   g->allocd = ud;
   setgcref(g->mainthref, obj2gco(L));
diff --git a/src/lj_str.c b/src/lj_str.c
index 4a9477dd..5ba55bdd 100644
--- a/src/lj_str.c
+++ b/src/lj_str.c
@@ -76,15 +76,29 @@ GCstr *lj_str_new(lua_State *L, const char *str, size_t lenx)
   GCstr *s;
   GCobj *o;
   MSize len = (MSize)lenx;
-  MSize h = len;
-  MSize step = (len>>5)+1;  /* Partial hash. */
-  MSize l1;
+  MSize a, b, h = len;
   if (lenx >= LJ_MAX_STR)
     lj_err_msg(L, LJ_ERR_STROV);
-  for (l1 = len; l1 >= step; l1 -= step)  /* Compute string hash. */
-    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
-  /* Check if the string has already been interned. */
   g = G(L);
+  /* Compute string hash. Constants taken from lookup3 hash by Bob Jenkins. */
+  if (len >= 4) {  /* Caveat: unaligned access! */
+    a = *(const uint32_t *)str;
+    h ^= *(const uint32_t *)(str+len-4);
+    b = *(const uint32_t *)(str+(len>>1)-2);
+    h ^= b; h -= lj_rol(b, 14);
+    b += *(const uint32_t *)(str+(len>>2)-1);
+  } else if (len > 0) {
+    a = *(const uint8_t *)str;
+    h ^= *(const uint8_t *)(str+len-1);
+    b = *(const uint8_t *)(str+(len>>1));
+    h ^= b; h -= lj_rol(b, 14);
+  } else {
+    return &g->strempty;
+  }
+  a ^= h; a -= lj_rol(h, 11);
+  b ^= a; b -= lj_rol(a, 25);
+  h ^= b; h -= lj_rol(b, 16);
+  /* Check if the string has already been interned. */
   for (o = gcref(g->strhash[h & g->strmask]); o != NULL; o = gcnext(o)) {
     GCstr *tso = gco2str(o);
     if (tso->len == len && (memcmp(str, strdata(tso), len) == 0)) {
-- 
cgit v1.2.3-55-g6feb