new cache for interning strings

6 files changed, 61 insertions, 15 deletions

diff --git a/lgc.c b/lgc.c
index 1695ea74..db4259e0 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 2.201 2014/12/20 13:58:15 roberto Exp roberto $
+** $Id: lgc.c,v 2.202 2015/01/16 16:54:37 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -967,6 +967,19 @@ void luaC_freeallobjects (lua_State *L) {
 }
 
 
+/*
+** Clear API string cache. (Entries cannot be empty, so fill them with
+** a non-collectable string.)
+*/
+static void clearapihash (global_State *g) {
+  int i;
+  for (i = 0; i < STRCACHE_SIZE; i++) {
+    if (iswhite(g->strcache[i]))  /* will entry be collected? */
+      g->strcache[i] = g->memerrmsg;  /* replace it with something fixed */
+  }
+}
+
+
 static l_mem atomic (lua_State *L) {
   global_State *g = G(L);
   l_mem work;
@@ -1007,6 +1020,7 @@ static l_mem atomic (lua_State *L) {
   /* clear values from resurrected weak tables */
   clearvalues(g, g->weak, origweak);
   clearvalues(g, g->allweak, origall);
+  clearapihash(g);
   g->currentwhite = cast_byte(otherwhite(g));  /* flip current white */
   work += g->GCmemtrav;  /* complete counting */
   return work;  /* estimate of memory marked by 'atomic' */
diff --git a/llimits.h b/llimits.h
index 961ff53b..7ff282ca 100644
--- a/llimits.h
+++ b/llimits.h
@@ -1,5 +1,5 @@
 /*
-** $Id: llimits.h,v 1.131 2015/02/09 15:41:56 roberto Exp roberto $
+** $Id: llimits.h,v 1.132 2015/03/03 19:53:13 roberto Exp roberto $
 ** Limits, basic types, and some other 'installation-dependent' definitions
 ** See Copyright Notice in lua.h
 */
@@ -187,6 +187,14 @@ typedef unsigned long Instruction;
 #endif
 
 
+/*
+** Size of cache for strings in the API (better be a prime)
+*/
+#if !defined(STRCACHE_SIZE)
+#define STRCACHE_SIZE           127
+#endif
+
+
 /* minimum size for string buffer */
 #if !defined(LUA_MINBUFFER)
 #define LUA_MINBUFFER   32
diff --git a/lstate.c b/lstate.c
index d42f0e82..3a9b8e98 100644
--- a/lstate.c
+++ b/lstate.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.c,v 2.126 2014/11/02 19:19:04 roberto Exp roberto $
+** $Id: lstate.c,v 2.127 2014/11/02 19:33:33 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -37,9 +37,6 @@
 #endif
 
 
-#define MEMERRMSG       "not enough memory"
-
-
 /*
 ** a macro to help the creation of a unique random seed when a state is
 ** created; the seed is used to randomize hashes.
@@ -200,12 +197,9 @@ static void f_luaopen (lua_State *L, void *ud) {
   UNUSED(ud);
   stack_init(L, L);  /* init stack */
   init_registry(L, g);
-  luaS_resize(L, MINSTRTABSIZE);  /* initial size of string table */
+  luaS_init(L);
   luaT_init(L);
   luaX_init(L);
-  /* pre-create memory-error message */
-  g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
-  luaC_fix(L, obj2gco(g->memerrmsg));  /* it should never be collected */
   g->gcrunning = 1;  /* allow gc */
   g->version = lua_version(NULL);
   luai_userstateopen(L);
diff --git a/lstate.h b/lstate.h
index fb2e91b4..285dfd82 100644
--- a/lstate.h
+++ b/lstate.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstate.h,v 2.118 2014/10/25 11:50:46 roberto Exp roberto $
+** $Id: lstate.h,v 2.119 2014/10/30 18:53:28 roberto Exp roberto $
 ** Global State
 ** See Copyright Notice in lua.h
 */
@@ -140,6 +140,7 @@ typedef struct global_State {
   TString *memerrmsg;  /* memory-error message */
   TString *tmname[TM_N];  /* array with tag-method names */
   struct Table *mt[LUA_NUMTAGS];  /* metatables for basic types */
+  TString *strcache[STRCACHE_SIZE];  /* cache for strings in API */
 } global_State;
 
 
diff --git a/lstring.c b/lstring.c
index 29e4630c..638f3dec 100644
--- a/lstring.c
+++ b/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 2.45 2014/11/02 19:19:04 roberto Exp roberto $
+** $Id: lstring.c,v 2.46 2015/01/16 16:54:37 roberto Exp roberto $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -22,6 +22,8 @@
 #include "lstring.h"
 
 
+#define MEMERRMSG       "not enough memory"
+
 
 /*
 ** Lua will use at most ~(2^LUAI_HASHLIMIT) bytes from a string to
@@ -85,6 +87,21 @@ void luaS_resize (lua_State *L, int newsize) {
 }
 
 
+/*
+** Initialize the string table and the string cache
+*/
+void luaS_init (lua_State *L) {
+  global_State *g = G(L);
+  int i;
+  luaS_resize(L, MINSTRTABSIZE);  /* initial size of string table */
+  /* pre-create memory-error message */
+  g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
+  luaC_fix(L, obj2gco(g->memerrmsg));  /* it should never be collected */
+  for (i = 0; i < STRCACHE_SIZE; i++)
+    g->strcache[i] = g->memerrmsg;  /* fill cache with valid strings */
+}
+
+
 
 /*
 ** creates a new string object
@@ -163,10 +180,21 @@ TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
 
 
 /*
-** new zero-terminated string
+** Create or reuse a zero-terminated string, first checking in the
+** cache (using the string address as a key). The cache can contain
+** only zero-terminated strings, so it is safe to use 'strcmp' to
+** check hits.
 */
 TString *luaS_new (lua_State *L, const char *str) {
-  return luaS_newlstr(L, str, strlen(str));
+  unsigned int i = point2uint(str) % STRCACHE_SIZE;  /* hash */
+  TString **p = &G(L)->strcache[i];
+  if (strcmp(str, getstr(*p)) == 0)  /* hit? */
+    return *p;  /* that it is */
+  else {  /* normal route */
+    TString *s = luaS_newlstr(L, str, strlen(str));
+    *p = s;
+    return s;
+  }
 }
 
 
diff --git a/lstring.h b/lstring.h
index 573daf9a..2b06afaf 100644
--- a/lstring.h
+++ b/lstring.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.h,v 1.56 2014/07/18 14:46:47 roberto Exp roberto $
+** $Id: lstring.h,v 1.57 2015/01/16 16:54:37 roberto Exp roberto $
 ** String table (keep all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -36,6 +36,7 @@
 LUAI_FUNC unsigned int luaS_hash (const char *str, size_t l, unsigned int seed);
 LUAI_FUNC int luaS_eqlngstr (TString *a, TString *b);
 LUAI_FUNC void luaS_resize (lua_State *L, int newsize);
+LUAI_FUNC void luaS_init (lua_State *L);
 LUAI_FUNC void luaS_remove (lua_State *L, TString *ts);
 LUAI_FUNC Udata *luaS_newudata (lua_State *L, size_t s);
 LUAI_FUNC TString *luaS_newlstr (lua_State *L, const char *str, size_t l);