table sizes don't need to be primes; power of 2 gives the same performance.

6 files changed, 37 insertions, 40 deletions

diff --git a/lgc.c b/lgc.c
index fe55f3e7..c3259421 100644
--- a/lgc.c
+++ b/lgc.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lgc.c,v 1.32 1999/11/22 13:12:07 roberto Exp roberto $
+** $Id: lgc.c,v 1.33 1999/11/23 13:58:02 roberto Exp roberto $
 ** Garbage Collector
 ** See Copyright Notice in lua.h
 */
@@ -208,7 +208,7 @@ static void collectstring (lua_State *L, int limit) {
       }
     }
     if ((tb->nuse+1)*6 < tb->size)
-      luaS_grow(L, tb);  /* table is too big; `grow' it to a smaller size */
+      luaS_resize(L, tb, tb->size/2);  /* table is too big */
   }
 }
 
diff --git a/lobject.c b/lobject.c
index 1e9f99d3..e2845127 100644
--- a/lobject.c
+++ b/lobject.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.c,v 1.24 1999/10/04 17:51:04 roberto Exp roberto $
+** $Id: lobject.c,v 1.25 1999/11/22 13:12:07 roberto Exp roberto $
 ** Some generic functions over Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -22,22 +22,13 @@ const char *const luaO_typenames[] = { /* ORDER LUA_T */
 const TObject luaO_nilobject = {LUA_T_NIL, {NULL}};
 
 
-
-/* hash dimensions values */
-static const long dimensions[] =
- {5L, 11L, 23L, 47L, 97L, 197L, 397L, 797L, 1597L, 3203L, 6421L,
-  12853L, 25717L, 51437L, 102811L, 205619L, 411233L, 822433L,
-  1644817L, 3289613L, 6579211L, 13158023L, MAX_INT};
-
-
-int luaO_redimension (lua_State *L, int oldsize) {
-  int i;
-  for (i=0; dimensions[i]<MAX_INT; i++) {
-    if (dimensions[i] > oldsize)
-      return dimensions[i];
-  }
-  lua_error(L, "tableEM");
-  return 0;  /* to avoid warnings */
+/*
+** returns smaller power of 2 bigger than `n' (minimum is MINPOWER2) 
+*/
+unsigned long luaO_power2 (unsigned long n) {
+  unsigned long p = MINPOWER2;
+  while (p<=n) p<<=1;
+  return p;
 }
 
 
diff --git a/lobject.h b/lobject.h
index ea397620..d286095f 100644
--- a/lobject.h
+++ b/lobject.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lobject.h,v 1.36 1999/11/10 15:39:35 roberto Exp roberto $
+** $Id: lobject.h,v 1.37 1999/11/22 13:12:07 roberto Exp roberto $
 ** Type definitions for Lua objects
 ** See Copyright Notice in lua.h
 */
@@ -45,7 +45,8 @@ typedef unsigned char  Byte;  /* unsigned 8 bits */
 
 
 /* convertion of pointer to int (for hashing only) */
-#define IntPoint(L, p)  ((unsigned int)(p))
+/* (the shift removes bits that are usually 0 because of alignment) */
+#define IntPoint(L, p)  (((unsigned int)(p)) >> 3)
 
 
 /*
@@ -194,9 +195,11 @@ typedef struct Hash {
 
 extern const char *const luaO_typenames[];
 
-
 #define luaO_typename(L, o)        luaO_typenames[-ttype(o)]
 
+#define MINPOWER2       4       /* minimum size for "growing" vectors */
+
+unsigned long luaO_power2 (unsigned long n);
 
 extern const TObject luaO_nilobject;
 
diff --git a/lstring.c b/lstring.c
index dcfbe718..d8e83953 100644
--- a/lstring.c
+++ b/lstring.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.c,v 1.28 1999/11/22 13:12:07 roberto Exp roberto $
+** $Id: lstring.c,v 1.29 1999/11/22 18:24:50 roberto Exp roberto $
 ** String table (keeps all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -52,24 +52,25 @@ static unsigned long hash_s (const char *s, long l) {
 }
 
 
-void luaS_grow (lua_State *L, stringtable *tb) {
-  int ns = luaO_redimension(L, tb->nuse);  /* new size */
-  TaggedString **newhash = luaM_newvector(L, ns, TaggedString *);
+void luaS_resize (lua_State *L, stringtable *tb, int newsize) {
+  TaggedString **newhash = luaM_newvector(L, newsize, TaggedString *);
   int i;
-  for (i=0; i<ns; i++) newhash[i] = NULL;
+  for (i=0; i<newsize; i++) newhash[i] = NULL;
   /* rehash */
   for (i=0; i<tb->size; i++) {
     TaggedString *p = tb->hash[i];
     while (p) {  /* for each node in the list */
       TaggedString *next = p->nexthash;  /* save next */
-      int h = p->hash%ns;  /* new position */
+      int h = p->hash&(newsize-1);  /* new position */
+      LUA_ASSERT(L, p->hash%newsize == (p->hash&(newsize-1)),
+                    "a&(x-1) == a%x, for x power of 2");
       p->nexthash = newhash[h];  /* chain it in new position */
       newhash[h] = p;
       p = next;
     }
   }
   luaM_free(L, tb->hash);
-  tb->size = ns;
+  tb->size = newsize;
   tb->hash = newhash;
 }
 
@@ -113,14 +114,14 @@ static void newentry (lua_State *L, stringtable *tb, TaggedString *ts, int h) {
   tb->hash[h] = ts;
   tb->nuse++;
   if (tb->nuse > tb->size)  /* too crowded? */
-    luaS_grow(L, tb);
+    luaS_resize(L, tb, tb->size*2);
 }
 
 
 TaggedString *luaS_newlstr (lua_State *L, const char *str, long l) {
   unsigned long h = hash_s(str, l);
   stringtable *tb = &L->string_root[h%NUM_HASHSTR];
-  int h1 = h%tb->size;
+  int h1 = h&(tb->size-1);
   TaggedString *ts;
   for (ts = tb->hash[h1]; ts; ts = ts->nexthash) {
     if (ts->u.s.len == l && (memcmp(str, ts->str, l) == 0))
@@ -136,7 +137,7 @@ TaggedString *luaS_newlstr (lua_State *L, const char *str, long l) {
 TaggedString *luaS_createudata (lua_State *L, void *udata, int tag) {
   unsigned long h = IntPoint(L, udata);
   stringtable *tb = &L->string_root[(h%NUM_HASHUDATA)+NUM_HASHSTR];
-  int h1 = h%tb->size;
+  int h1 = h&(tb->size-1);
   TaggedString *ts;
   for (ts = tb->hash[h1]; ts; ts = ts->nexthash) {
     if (udata == ts->u.d.value && (tag == ts->u.d.tag || tag == LUA_ANYTAG))
diff --git a/lstring.h b/lstring.h
index be260b89..31feabdb 100644
--- a/lstring.h
+++ b/lstring.h
@@ -1,5 +1,5 @@
 /*
-** $Id: lstring.h,v 1.12 1999/11/04 17:22:26 roberto Exp roberto $
+** $Id: lstring.h,v 1.13 1999/11/22 13:12:07 roberto Exp roberto $
 ** String table (keep all strings handled by Lua)
 ** See Copyright Notice in lua.h
 */
@@ -26,7 +26,7 @@
 
 
 void luaS_init (lua_State *L);
-void luaS_grow (lua_State *L, stringtable *tb);
+void luaS_resize (lua_State *L, stringtable *tb, int newsize);
 TaggedString *luaS_createudata (lua_State *L, void *udata, int tag);
 void luaS_freeall (lua_State *L);
 void luaS_free (lua_State *L, TaggedString *ts);
diff --git a/ltable.c b/ltable.c
index 8a207b80..ea3ab4a9 100644
--- a/ltable.c
+++ b/ltable.c
@@ -1,5 +1,5 @@
 /*
-** $Id: ltable.c,v 1.29 1999/11/10 15:39:35 roberto Exp roberto $
+** $Id: ltable.c,v 1.30 1999/11/22 13:12:07 roberto Exp roberto $
 ** Lua tables (hash)
 ** See Copyright Notice in lua.h
 */
@@ -65,7 +65,9 @@ Node *luaH_mainposition (lua_State *L, const Hash *t, const TObject *key) {
       lua_error(L, "unexpected type to index table");
       h = 0;  /* to avoid warnings */
   }
-  return &t->node[h%(unsigned int)t->size];
+  LUA_ASSERT(L, h%(unsigned int)t->size == (h&((unsigned int)t->size-1)),
+            "a&(x-1) == a%x, for x power of 2");
+  return &t->node[h&((unsigned int)t->size-1)];
 }
 
 
@@ -109,7 +111,7 @@ static void setnodevector (lua_State *L, Hash *t, int size) {
 
 Hash *luaH_new (lua_State *L, int size) {
   Hash *t = luaM_new(L, Hash);
-  setnodevector(L, t, luaO_redimension(L, size+1));
+  setnodevector(L, t, luaO_power2(size));
   t->htag = TagDefault;
   t->next = L->roottable;
   L->roottable = t;
@@ -125,7 +127,7 @@ void luaH_free (lua_State *L, Hash *t) {
 }
 
 
-static int newsize (lua_State *L, const Hash *t) {
+static int newsize (const Hash *t) {
   Node *v = t->node;
   int size = t->size;
   int realuse = 0;
@@ -134,7 +136,7 @@ static int newsize (lua_State *L, const Hash *t) {
     if (ttype(&v[i].val) != LUA_T_NIL)
       realuse++;
   }
-  return luaO_redimension(L, realuse*2);
+  return luaO_power2(realuse+realuse/4+1);
 }
 
 
@@ -148,7 +150,7 @@ static void rehash (lua_State *L, Hash *t) {
   Node *nold = t->node;
   int i;
   L->nblocks -= gcsize(L, oldsize);
-  setnodevector(L, t, newsize(L, t));  /* create new array of nodes */
+  setnodevector(L, t, newsize(t));  /* create new array of nodes */
   /* first loop; set only elements that can go in their main positions */
   for (i=0; i<oldsize; i++) {
     Node *old = nold+i;