const patch to reduce GC cycle

[paul@...]

Here is a quick hack to save some GC cycle with Lua 4.0. It
may only be meaningful for those who have HUGE table of numbers
and strings.

To compile the patch

	cd lua; make clean; patch -p1 < lua-const.patch; make

To use the patch

 	setconstant( table )

It will mark a table of strings or numbers as constant,
so that the content of this table will never be garbage
collected. Note that the table can be nested, and anything
other than number and string will be *garbage collected*
even if the table isn't modified (and probably cause
serious segfault?)

The idea behind the hack is to add a constant string pool and 
constant table pool, avoid constant values during mark, move 
constant values to constant pools during sweep. So eventually,
all constants are avoided in both mark & sweep. 

It reduces average GC cycle from 90ms to 42ms in my own 
program. An interesting note is, avoiding marking constants
saved me much more than avoiding sweeping constants. Not sure
why, but it could be that my constant table has 5 levels of 
nested structure.

Anyway, it was really a hack done in 4 hours, and I've not test
it extensively, but thought it might be useful for someone
out there. 

If you spot any bug caused by the patch, please let me 
know, thanks!

Regards,
.paul.

diff -urN lua/include/lua.h lua-hack/include/lua.h
--- lua/include/lua.h	Tue Oct 31 20:44:07 2000
+++ lua-hack/include/lua.h	Sun Mar 10 19:32:45 2002
@@ -166,6 +166,11 @@
 LUA_API int   lua_getgcthreshold (lua_State *L);
 LUA_API int   lua_getgccount (lua_State *L);
 LUA_API void  lua_setgcthreshold (lua_State *L, int newthreshold);
+/* 
+    to avoid any garbage collection, only applicable to tables containing
+    string & number
+*/    
+LUA_API void  lua_setconstant (lua_State *L);	
 
 /*
 ** miscellaneous functions
diff -urN lua/src/lapi.c lua-hack/src/lapi.c
--- lua/src/lapi.c	Mon Oct 30 20:50:09 2000
+++ lua-hack/src/lapi.c	Sun Mar 10 19:32:19 2002
@@ -492,3 +492,9 @@
   return ts->u.d.value;
 }
 
+LUA_API void  lua_setconstant (lua_State *L) {
+    Hash *h = hvalue(luaA_index(L, -1));
+    if (h) {
+    	h->constant = FIXMARK;
+    }
+}
diff -urN lua/src/lgc.c lua-hack/src/lgc.c
--- lua/src/lgc.c	Thu Oct 26 20:47:05 2000
+++ lua-hack/src/lgc.c	Sun Mar 10 21:54:52 2002
@@ -22,13 +22,13 @@
   Closure *cmark;  /* list of marked closures to be visited */
 } GCState;
 
+extern void newentry (lua_State *L, stringtable *tb, TString *ts, int h);
 
-
-static void markobject (GCState *st, TObject *o);
+static void markobject (GCState *st, TObject *o, int constant);
 
 
 /* mark a string; marks larger than 1 cannot be changed */
-#define strmark(s)    {if ((s)->marked == 0) (s)->marked = 1;}
+#define strmark(s, c)    {if ((s)->marked == 0) (s)->marked = c ? c : 1;}
 
 
 
@@ -36,13 +36,13 @@
   if (!f->marked) {
     int i;
     f->marked = 1;
-    strmark(f->source);
+    strmark(f->source, 1);
     for (i=0; i<f->nkstr; i++)
-      strmark(f->kstr[i]);
+      strmark(f->kstr[i], 1);
     for (i=0; i<f->nkproto; i++)
       protomark(f->kproto[i]);
     for (i=0; i<f->nlocvars; i++)  /* mark local-variable names */
-      strmark(f->locvars[i].varname);
+      strmark(f->locvars[i].varname, 1);
   }
 }
 
@@ -50,7 +50,7 @@
 static void markstack (lua_State *L, GCState *st) {
   StkId o;
   for (o=L->stack; o<L->top; o++)
-    markobject(st, o);
+    markobject(st, o, 0);
 }
 
 
@@ -58,7 +58,7 @@
   int i;
   for (i=0; i<L->refSize; i++) {
     if (L->refArray[i].st == LOCK)
-      markobject(st, &L->refArray[i].o);
+      markobject(st, &L->refArray[i].o, 0);
   }
 }
 
@@ -85,10 +85,10 @@
 }
 
 
-static void markobject (GCState *st, TObject *o) {
+static void markobject (GCState *st, TObject *o, int constant) {
   switch (ttype(o)) {
     case LUA_TUSERDATA:  case LUA_TSTRING:
-      strmark(tsvalue(o));
+      strmark(tsvalue(o), constant);
       break;
     case LUA_TMARK:
       markclosure(st, infovalue(o)->func);
@@ -100,6 +100,9 @@
       if (!ismarked(hvalue(o))) {
         hvalue(o)->mark = st->tmark;  /* chain it in list of marked */
         st->tmark = hvalue(o);
+        if (!hvalue(o)->constant) {
+            hvalue(o)->constant = constant;
+        }
       }
       break;
     }
@@ -122,21 +125,23 @@
       Closure *f = st.cmark;  /* get first closure from list */
       st.cmark = f->mark;  /* remove it from list */
       for (i=0; i<f->nupvalues; i++)  /* mark its upvalues */
-        markobject(&st, &f->upvalue[i]);
+        markobject(&st, &f->upvalue[i], 0);
     }
     else if (st.tmark) {
       int i;
       Hash *h = st.tmark;  /* get first table from list */
       st.tmark = h->mark;  /* remove it from list */
+      if (h->constant == 1) continue;  /* skip marking constant table */
       for (i=0; i<h->size; i++) {
         Node *n = node(h, i);
         if (ttype(key(n)) != LUA_TNIL) {
           if (ttype(val(n)) == LUA_TNIL)
             luaH_remove(h, key(n));  /* dead element; try to remove it */
-          markobject(&st, &n->key);
-          markobject(&st, &n->val);
+          markobject(&st, &n->key, h->constant);
+          markobject(&st, &n->val, h->constant);
         }
       }
+      if (h->constant) h->constant = 1;
     }
     else break;  /* nothing else to mark */
   }
@@ -212,19 +217,34 @@
 }
 
 
-static void collecttable (lua_State *L) {
+static void collecttable (lua_State *L, int all) {
   Hash **p = &L->roottable;
   Hash *next;
+  int n = 0;
   while ((next = *p) != NULL) {
-    if (ismarked(next)) {
+    n++;
+    if (ismarked(next) && !next->constant) {
       next->mark = next;  /* unmark */
       p = &next->next;
     }
     else {
       *p = next->next;
-      luaH_free(L, next);
+      if (!all && next->constant) {  /* move to constant table */
+          next->next = L->cnsttable;
+	  L->cnsttable = next;
+      }
+      else {
+        luaH_free(L, next);
+      }
     }
   }
+  if (all) {  /* if for all, shall collect all constant tables */
+      p = &L->cnsttable;
+      while ((next = *p) != NULL) {
+          *p = next->next;
+          luaH_free(L, next);
+      }
+  }
 }
 
 
@@ -240,20 +260,37 @@
     TString **p = &L->strt.hash[i];
     TString *next;
     while ((next = *p) != NULL) {
-      if (next->marked && !all) {  /* preserve? */
-        if (next->marked < FIXMARK)  /* does not change FIXMARKs */
-          next->marked = 0;
+      if (next->marked < FIXMARK && !all) {  /* preserve? */
+        next->marked = 0;
         p = &next->nexthash;
       } 
       else {  /* collect */
         *p = next->nexthash;
         L->strt.nuse--;
         L->nblocks -= sizestring(next->len);
-        luaM_free(L, next);
+        if (next->marked >= FIXMARK && !all) {  /* shall move to constant pool */
+            newentry(L, &L->cstt, next, next->u.s.hash & (L->cstt.size-1));
+        }
+	else {
+	  luaM_free(L, next);
+	}
       }
     }
   }
   checktab(L, &L->strt);
+  if (all) {  /* if for all, shall free all constant strings */
+    for (i=0; i<L->cstt.size; i++) {  /* for each list */
+      TString **p = &L->cstt.hash[i];
+      TString *next;
+      while ((next = *p) != NULL) {
+        *p = next->nexthash;
+        L->cstt.nuse--;
+        L->nblocks -= sizestring(next->len);
+	luaM_free(L, next);
+      }
+    }
+    checktab(L, &L->cstt);
+  }
 }
 
 
@@ -330,7 +367,7 @@
   collectudata(L, all);
   callgcTMudata(L);
   collectstrings(L, all);
-  collecttable(L);
+  collecttable(L, all);
   collectproto(L);
   collectclosure(L);
 }
diff -urN lua/src/lib/lbaselib.c lua-hack/src/lib/lbaselib.c
--- lua/src/lib/lbaselib.c	Mon Nov  6 21:45:18 2000
+++ lua-hack/src/lib/lbaselib.c	Sun Mar 10 19:36:48 2002
@@ -213,6 +213,12 @@
   return 0;
 }
 
+static int luaB_setconstant (lua_State *L) {
+  luaL_checktype(L, 1, LUA_TTABLE);
+  lua_setconstant(L);
+  return 0;
+}
+
 
 static int luaB_type (lua_State *L) {
   luaL_checkany(L, 1);
@@ -629,6 +635,7 @@
   {"setglobal", luaB_setglobal},
   {"settag", luaB_settag},
   {"settagmethod", luaB_settagmethod},
+  {"setconstant", luaB_setconstant},
   {"tag", luaB_tag},
   {"tonumber", luaB_tonumber},
   {"tostring", luaB_tostring},
diff -urN lua/src/lobject.h lua-hack/src/lobject.h
--- lua/src/lobject.h	Tue Oct 31 01:49:19 2000
+++ lua-hack/src/lobject.h	Sun Mar 10 19:21:03 2002
@@ -163,6 +163,7 @@
   Node *firstfree;  /* this position is free; all positions after it are full */
   struct Hash *next;
   struct Hash *mark;  /* marked tables (point to itself when not marked) */
+  int constant;
 } Hash;
 
 
diff -urN lua/src/lstate.c lua-hack/src/lstate.c
--- lua/src/lstate.c	Tue Oct 31 00:29:59 2000
+++ lua-hack/src/lstate.c	Sun Mar 10 21:23:18 2002
@@ -67,15 +67,16 @@
   lua_State *L = luaM_new(NULL, lua_State);
   if (L == NULL) return NULL;  /* memory allocation error */
   L->stack = NULL;
-  L->strt.size = L->udt.size = 0;
-  L->strt.nuse = L->udt.nuse = 0;
-  L->strt.hash = NULL;
+  L->strt.size = L->cstt.size = L->udt.size = 0;
+  L->strt.nuse = L->cstt.nuse = L->udt.nuse = 0;
+  L->strt.hash = L->cstt.hash = NULL;
   L->udt.hash = NULL;
   L->Mbuffer = NULL;
   L->Mbuffsize = 0;
   L->rootproto = NULL;
   L->rootcl = NULL;
   L->roottable = NULL;
+  L->cnsttable = NULL;
   L->TMtable = NULL;
   L->last_tag = -1;
   L->refArray = NULL;
@@ -103,6 +104,7 @@
   LUA_ASSERT(L->rootproto == NULL, "list should be empty");
   LUA_ASSERT(L->rootcl == NULL, "list should be empty");
   LUA_ASSERT(L->roottable == NULL, "list should be empty");
+  LUA_ASSERT(L->cnsttable == NULL, "list should be empty");
   luaS_freeall(L);
   if (L->stack)
     L->nblocks -= (L->stack_last - L->stack + 1)*sizeof(TObject);
diff -urN lua/src/lstate.h lua-hack/src/lstate.h
--- lua/src/lstate.h	Thu Oct  5 21:00:17 2000
+++ lua-hack/src/lstate.h	Sun Mar 10 21:22:59 2002
@@ -57,7 +57,9 @@
   Proto *rootproto;  /* list of all prototypes */
   Closure *rootcl;  /* list of all closures */
   Hash *roottable;  /* list of all tables */
+  Hash *cnsttable;  /* list of all constant tables */
   stringtable strt;  /* hash table for strings */
+  stringtable cstt;  /* hash table for constant strings */
   stringtable udt;   /* hash table for udata */
   Hash *gt;  /* table for globals */
   struct TM *TMtable;  /* table for tag methods */
diff -urN lua/src/lstring.c lua-hack/src/lstring.c
--- lua/src/lstring.c	Tue Oct 31 01:49:19 2000
+++ lua-hack/src/lstring.c	Sun Mar 10 20:59:45 2002
@@ -27,11 +27,12 @@
 
 void luaS_init (lua_State *L) {
   L->strt.hash = luaM_newvector(L, 1, TString *);
+  L->cstt.hash = luaM_newvector(L, 1, TString *);
   L->udt.hash = luaM_newvector(L, 1, TString *);
   L->nblocks += 2*sizeof(TString *);
-  L->strt.size = L->udt.size = 1;
-  L->strt.nuse = L->udt.nuse = 0;
-  L->strt.hash[0] = L->udt.hash[0] = NULL;
+  L->strt.size = L->cstt.size = L->udt.size = 1;
+  L->strt.nuse = L->cstt.nuse = L->udt.nuse = 0;
+  L->strt.hash[0] = L->cstt.hash[0] = L->udt.hash[0] = NULL;
 }
 
 
@@ -39,6 +40,9 @@
   LUA_ASSERT(L->strt.nuse==0, "non-empty string table");
   L->nblocks -= (L->strt.size + L->udt.size)*sizeof(TString *);
   luaM_free(L, L->strt.hash);
+  LUA_ASSERT(L->cstt.nuse==0, "non-empty string table");
+  L->nblocks -= (L->cstt.size + L->udt.size)*sizeof(TString *);
+  luaM_free(L, L->cstt.hash);
   LUA_ASSERT(L->udt.nuse==0, "non-empty udata table");
   luaM_free(L, L->udt.hash);
 }
@@ -62,7 +66,7 @@
     TString *p = tb->hash[i];
     while (p) {  /* for each node in the list */
       TString *next = p->nexthash;  /* save next */
-      unsigned long h = (tb == &L->strt) ? p->u.s.hash : IntPoint(p->u.d.value);
+      unsigned long h = (tb == &L->strt || tb == &L->cstt) ? p->u.s.hash : IntPoint(p->u.d.value);
       int h1 = h&(newsize-1);  /* new position */
       LUA_ASSERT(h%newsize == (h&(newsize-1)),
                     "a&(x-1) == a%x, for x power of 2");
@@ -78,7 +82,7 @@
 }
 
 
-static void newentry (lua_State *L, stringtable *tb, TString *ts, int h) {
+void newentry (lua_State *L, stringtable *tb, TString *ts, int h) {
   ts->nexthash = tb->hash[h];  /* chain new entry */
   tb->hash[h] = ts;
   tb->nuse++;
@@ -91,8 +95,13 @@
 TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
   unsigned long h = hash_s(str, l);
   int h1 = h & (L->strt.size-1);
+  int h2 = h & (L->cstt.size-1);
   TString *ts;
   for (ts = L->strt.hash[h1]; ts; ts = ts->nexthash) {
+    if (ts->len == l && (memcmp(str, ts->str, l) == 0))
+      return ts;
+  }
+  for (ts = L->cstt.hash[h2]; ts; ts = ts->nexthash) {
     if (ts->len == l && (memcmp(str, ts->str, l) == 0))
       return ts;
   }
diff -urN lua/src/ltable.c lua-hack/src/ltable.c
--- lua/src/ltable.c	Thu Oct 26 20:47:05 2000
+++ lua-hack/src/ltable.c	Sun Mar 10 19:21:06 2002
@@ -182,6 +182,7 @@
   t->size = 0;
   L->nblocks += gcsize(L, 0);
   t->node = NULL;
+  t->constant = 0;
   setnodevector(L, t, luaO_power2(size));
   return t;
 }