Switch to fast string hash.

4 files changed, 25 insertions, 7 deletions

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)) {