Move free node pos to t->node[0].freetop. Saves 4 bytes in GCtab.

3 files changed, 38 insertions, 55 deletions

diff --git a/src/lj_obj.h b/src/lj_obj.h
index a37c0882..048a74f9 100644
--- a/src/lj_obj.h
+++ b/src/lj_obj.h
@@ -453,7 +453,7 @@ typedef struct Node {
   TValue val;           /* Value object. Must be first field. */
   TValue key;           /* Key object. */
   MRef next;            /* Hash chain. */
-  int32_t unused;       /* For consistent alignment. */
+  MRef freetop;         /* Top of free elements (stored in t->node[0]). */
 } Node;
 
 LJ_STATIC_ASSERT(offsetof(Node, val) == 0);
@@ -468,7 +468,6 @@ typedef struct GCtab {
   MRef node;            /* Hash part. */
   uint32_t asize;       /* Size of array part (keys [0, asize-1]). */
   uint32_t hmask;       /* Hash part mask (size of hash part - 1). */
-  MRef lastfree;        /* Any free position is before this position. */
 } GCtab;
 
 #define sizetabcolo(n)  ((n)*sizeof(TValue) + sizeof(GCtab))
diff --git a/src/lj_state.c b/src/lj_state.c
index 1e490b28..e90359ef 100644
--- a/src/lj_state.c
+++ b/src/lj_state.c
@@ -200,6 +200,7 @@ LUA_API lua_State *lua_newstate(lua_Alloc f, void *ud)
   setnilV(registry(L));
   setnilV(&g->nilnode.val);
   setnilV(&g->nilnode.key);
+  setmref(g->nilnode.freetop, &g->nilnode);
   lj_str_initbuf(L, &g->tmpbuf);
   g->gc.state = GCSpause;
   setgcref(g->gc.root, obj2gco(L));
diff --git a/src/lj_tab.c b/src/lj_tab.c
index fc44fdb4..be26bdda 100644
--- a/src/lj_tab.c
+++ b/src/lj_tab.c
@@ -60,9 +60,9 @@ static LJ_AINLINE void newhpart(lua_State *L, GCtab *t, uint32_t hbits)
     lj_err_msg(L, LJ_ERR_TABOV);
   hsize = 1u << hbits;
   node = lj_mem_newvec(L, hsize, Node);
+  setmref(node->freetop, &node[hsize]);
   setmref(t->node, node);
   t->hmask = hsize-1;
-  setmref(t->lastfree, &node[hsize]);
 }
 
 /*
@@ -116,7 +116,6 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
     t->asize = asize;
     t->hmask = 0;
     setmref(t->node, &g->nilnode);
-    setmref(t->lastfree, &g->nilnode);
   } else {  /* Otherwise separately allocate the array part. */
     t = lj_mem_newobj(L, GCtab);
     t->gct = ~LJ_TTAB;
@@ -128,7 +127,6 @@ static GCtab *newtab(lua_State *L, uint32_t asize, uint32_t hbits)
     t->hmask = 0;
     g = G(L);
     setmref(t->node, &g->nilnode);
-    setmref(t->lastfree, &g->nilnode);
     if (asize > 0) {
       if (asize > LJ_MAX_ASIZE)
         lj_err_msg(L, LJ_ERR_TABOV);
@@ -196,7 +194,7 @@ GCtab * LJ_FASTCALL lj_tab_dup(lua_State *L, const GCtab *kt)
     Node *node = noderef(t->node);
     Node *knode = noderef(kt->node);
     ptrdiff_t d = (char *)node - (char *)knode;
-    setmref(t->lastfree, (Node *)((char *)noderef(kt->lastfree) + d));
+    setmref(node->freetop, (Node *)((char *)noderef(knode->freetop) + d));
     for (i = 0; i <= hmask; i++) {
       Node *kn = &knode[i];
       Node *n = &node[i];
@@ -263,7 +261,6 @@ static void resizetab(lua_State *L, GCtab *t, uint32_t asize, uint32_t hbits)
   } else {
     global_State *g = G(L);
     setmref(t->node, &g->nilnode);
-    setmref(t->lastfree, &g->nilnode);
     t->hmask = 0;
   }
   if (asize < oldasize) {  /* Array part shrinks? */
@@ -427,59 +424,45 @@ cTValue *lj_tab_get(lua_State *L, GCtab *t, cTValue *key)
 
 /* -- Table setters ------------------------------------------------------- */
 
-static Node *getfreepos(GCtab *t)
-{
-  Node *node = noderef(t->node);
-  Node *lastfree = noderef(t->lastfree);
-  while (lastfree > node) {
-    lastfree--;
-    setmref(t->lastfree, lastfree);
-    if (tvisnil(&lastfree->key))
-      return lastfree;
-  }
-  return NULL;  /* could not find a free place */
-}
-
-/*
-** inserts a new key into a hash table; first, check whether key's main
-** position is free. If not, check whether colliding node is in its main
-** position or not: if it is not, move colliding node to an empty place and
-** put new key in its main position; otherwise (colliding node is in its main
-** position), new key goes to an empty position.
-*/
+/* Insert new key. Use Brent's variation to optimize the chain length. */
 TValue *lj_tab_newkey(lua_State *L, GCtab *t, cTValue *key)
 {
-  Node *mp = hashkey(t, key);
-  if (!tvisnil(&mp->val) || t->hmask == 0) {
-    Node *othern;
-    Node *n = getfreepos(t);  /* get a free place */
-    if (n == NULL) {  /* cannot find a free place? */
-      rehashtab(L, t, key);  /* grow table */
-      return lj_tab_set(L, t, key);  /* re-insert key into grown table */
-    }
-    lua_assert(n != &G(L)->nilnode);
-    othern = hashkey(t, &mp->key);
-    if (othern != mp) {  /* is colliding node out of its main position? */
-      /* yes; move colliding node into free position */
-      while (noderef(othern->next) != mp)
-        othern = nextnode(othern);  /* find previous */
-      setmref(othern->next, n);  /* redo the chain with `n' in place of `mp' */
-      *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
-      setmref(mp->next, NULL);  /* now `mp' is free */
-      setnilV(&mp->val);
-    } else {  /* colliding node is in its own main position */
-      /* new node will go into free position */
-      setmrefr(n->next, mp->next);  /* chain new position */
-      setmref(mp->next, n);
-      mp = n;
+  Node *n = hashkey(t, key);
+  if (!tvisnil(&n->val) || t->hmask == 0) {
+    Node *nodebase = noderef(t->node);
+    Node *collide, *freenode = noderef(nodebase->freetop);
+    lua_assert(freenode >= nodebase && freenode <= nodebase+t->hmask+1);
+    do {
+      if (freenode == nodebase) {  /* No free node found? */
+        rehashtab(L, t, key);  /* Rehash table. */
+        return lj_tab_set(L, t, key);  /* Retry key insertion. */
+      }
+    } while (!tvisnil(&(--freenode)->key));
+    setmref(nodebase->freetop, freenode);
+    lua_assert(freenode != &G(L)->nilnode);
+    collide = hashkey(t, &n->key);
+    if (collide != n) {  /* Colliding node not the main node? */
+      while (noderef(collide->next) != n)  /* Find predecessor. */
+        collide = nextnode(collide);
+      setmref(collide->next, freenode);  /* Relink chain. */
+      /* Copy colliding node into free node and free main node. */
+      freenode->val = n->val;
+      freenode->key = n->key;
+      freenode->next = n->next;
+      setmref(n->next, NULL);
+      setnilV(&n->val);
+    } else {  /* Otherwise use free node. */
+      setmrefr(freenode->next, n->next);  /* Insert into chain. */
+      setmref(n->next, freenode);
+      n = freenode;
     }
   }
-  mp->key.u64 = key->u64;
-  if (LJ_UNLIKELY(tvismzero(&mp->key)))
-    mp->key.u64 = 0;
+  n->key.u64 = key->u64;
+  if (LJ_UNLIKELY(tvismzero(&n->key)))
+    n->key.u64 = 0;
   lj_gc_barriert(L, t, key);
-  lua_assert(tvisnil(&mp->val));
-  return &mp->val;
+  lua_assert(tvisnil(&n->val));
+  return &n->val;
 }
 
 TValue *lj_tab_setinth(lua_State *L, GCtab *t, int32_t key)