commit d015f1fc02e03864b0ed3ad668a6e0660417a718
parent 790690a2236ab0ad0cce35551c17e62064b4c85b
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Fri, 26 Nov 1999 16:58:58 -0200
table sizes don't need to be primes; power of 2 gives the same performance.
Diffstat:
6 files changed, 37 insertions(+), 40 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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;
