From d015f1fc02e03864b0ed3ad668a6e0660417a718 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 26 Nov 1999 16:59:20 -0200 Subject: table sizes don't need to be primes; power of 2 gives the same performance. --- lgc.c | 4 ++-- lobject.c | 25 ++++++++----------------- lobject.h | 9 ++++++--- lstring.c | 21 +++++++++++---------- lstring.h | 4 ++-- ltable.c | 14 ++++++++------ 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] 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; isize; 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