From 6e600695f8398843a156ce02023f731c6d687ae8 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 15 Jun 2018 11:14:20 -0300 Subject: field 'sizearray' in struct 'Table' changed to 'alimit', which can be used as a hint for '#t' --- lgc.c | 15 +++-- lobject.h | 17 +++++- ltable.c | 197 ++++++++++++++++++++++++++++++++++++++++++++++++++------------ ltable.h | 3 +- ltests.c | 15 +++-- lvm.c | 4 +- lvm.h | 4 +- 7 files changed, 201 insertions(+), 54 deletions(-) diff --git a/lgc.c b/lgc.c index 2e401cbd..b0e3c363 100644 --- a/lgc.c +++ b/lgc.c @@ -1,5 +1,5 @@ /* -** $Id: lgc.c,v 2.252 2018/02/26 13:35:03 roberto Exp roberto $ +** $Id: lgc.c,v 2.253 2018/03/16 14:22:09 roberto Exp roberto $ ** Garbage Collector ** See Copyright Notice in lua.h */ @@ -398,7 +398,7 @@ static void traverseweakvalue (global_State *g, Table *h) { Node *n, *limit = gnodelast(h); /* if there is array part, assume it may have white values (it is not worth traversing it now just to check) */ - int hasclears = (h->sizearray > 0); + int hasclears = (h->alimit > 0); for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ if (isempty(gval(n))) /* entry is empty? */ clearkey(n); /* clear its key */ @@ -433,8 +433,9 @@ static int traverseephemeron (global_State *g, Table *h) { int hasww = 0; /* true if table has entry "white-key -> white-value" */ Node *n, *limit = gnodelast(h); unsigned int i; + unsigned int asize = luaH_realasize(h); /* traverse array part */ - for (i = 0; i < h->sizearray; i++) { + for (i = 0; i < asize; i++) { if (valiswhite(&h->array[i])) { marked = 1; reallymarkobject(g, gcvalue(&h->array[i])); @@ -472,7 +473,8 @@ static int traverseephemeron (global_State *g, Table *h) { static void traversestrongtable (global_State *g, Table *h) { Node *n, *limit = gnodelast(h); unsigned int i; - for (i = 0; i < h->sizearray; i++) /* traverse array part */ + unsigned int asize = luaH_realasize(h); + for (i = 0; i < asize; i++) /* traverse array part */ markvalue(g, &h->array[i]); for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */ if (isempty(gval(n))) /* entry is empty? */ @@ -508,7 +510,7 @@ static lu_mem traversetable (global_State *g, Table *h) { } else /* not weak */ traversestrongtable(g, h); - return 1 + h->sizearray + 2 * allocsizenode(h); + return 1 + h->alimit + 2 * allocsizenode(h); } @@ -719,7 +721,8 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { Table *h = gco2t(l); Node *n, *limit = gnodelast(h); unsigned int i; - for (i = 0; i < h->sizearray; i++) { + unsigned int asize = luaH_realasize(h); + for (i = 0; i < asize; i++) { TValue *o = &h->array[i]; if (iscleared(g, gcvalueN(o))) /* value was collected? */ setempty(o); /* remove entry */ diff --git a/lobject.h b/lobject.h index da896662..7c2b3f84 100644 --- a/lobject.h +++ b/lobject.h @@ -1,5 +1,5 @@ /* -** $Id: lobject.h,v 2.143 2018/06/01 16:51:34 roberto Exp roberto $ +** $Id: lobject.h,v 2.144 2018/06/01 17:40:38 roberto Exp roberto $ ** Type definitions for Lua objects ** See Copyright Notice in lua.h */ @@ -669,11 +669,24 @@ typedef union Node { (void)L; checkliveness(L,io_); } +/* +** About 'alimit': if 'isrealasize(t)' is true, then 'alimit' is the +** real size of 'array'. Otherwise, the real size of 'array' is the +** smallest power of two not smaller than 'alimit' (or zero iff 'alimit' +** is zero); 'alimit' is then used as a hint for #t. +*/ + +#define BITRAS (1 << 7) +#define isrealasize(t) (!((t)->marked & BITRAS)) +#define setrealasize(t) ((t)->marked &= cast_byte(~BITRAS)) +#define setnorealasize(t) ((t)->marked |= BITRAS) + + typedef struct Table { CommonHeader; lu_byte flags; /* 1<

alimit)) + + +/* +** Returns the real size of the 'array' array +*/ +LUAI_FUNC unsigned int luaH_realasize (const Table *t) { + if (limitequalsasize(t)) + return t->alimit; /* this is the size */ + else { + unsigned int size = t->alimit; + /* compute the smallest power of 2 not smaller than 'n' */ + size |= (size >> 1); + size |= (size >> 2); + size |= (size >> 4); + size |= (size >> 8); + size |= (size >> 16); +#if (INT_MAX >> 30 >> 1) > 0 + size |= (size >> 32); /* int has more than 32 bits */ +#endif + size++; + lua_assert(ispow2(size) && size/2 < t->alimit && t->alimit < size); + return size; + } +} + + +/* +** Check whether real size of the array is a power of 2. +** (If it is not, 'alimit' cannot be changed to any other value +** without changing the real size.) +*/ +static int ispow2realasize (const Table *t) { + return (!isrealasize(t) || ispow2(t->alimit)); +} + + +static unsigned int setlimittosize (Table *t) { + t->alimit = luaH_realasize(t); + setrealasize(t); + return t->alimit; +} + + +#define limitasasize(t) check_exp(isrealasize(t), t->alimit) + + + /* ** "Generic" get version. (Not that generic: not valid for integers, ** which may be in array part, nor for floats with integral values.) @@ -228,11 +281,12 @@ static unsigned int arrayindex (lua_Integer k) { ** elements in the array part, then elements in the hash part. The ** beginning of a traversal is signaled by 0. */ -static unsigned int findindex (lua_State *L, Table *t, TValue *key) { +static unsigned int findindex (lua_State *L, Table *t, TValue *key, + unsigned int asize) { unsigned int i; if (ttisnil(key)) return 0; /* first iteration */ i = ttisinteger(key) ? arrayindex(ivalue(key)) : 0; - if (i != 0 && i <= t->sizearray) /* is 'key' inside array part? */ + if (i != 0 && i <= asize) /* is 'key' inside array part? */ return i; /* yes; that's the index */ else { const TValue *n = getgeneric(t, key); @@ -240,21 +294,22 @@ static unsigned int findindex (lua_State *L, Table *t, TValue *key) { luaG_runerror(L, "invalid key to 'next'"); /* key not found */ i = cast_int(nodefromval(n) - gnode(t, 0)); /* key index in hash table */ /* hash elements are numbered after array ones */ - return (i + 1) + t->sizearray; + return (i + 1) + asize; } } int luaH_next (lua_State *L, Table *t, StkId key) { - unsigned int i = findindex(L, t, s2v(key)); /* find original element */ - for (; i < t->sizearray; i++) { /* try first array part */ + unsigned int asize = luaH_realasize(t); + unsigned int i = findindex(L, t, s2v(key), asize); /* find original key */ + for (; i < asize; i++) { /* try first array part */ if (!isempty(&t->array[i])) { /* a non-empty entry? */ setivalue(s2v(key), i + 1); setobj2s(L, key + 1, &t->array[i]); return 1; } } - for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) { /* hash part */ + for (i -= asize; cast_int(i) < sizenode(t); i++) { /* hash part */ if (!isempty(gval(gnode(t, i)))) { /* a non-empty entry? */ Node *n = gnode(t, i); getnodekey(L, s2v(key), n); @@ -329,12 +384,13 @@ static unsigned int numusearray (const Table *t, unsigned int *nums) { unsigned int ttlg; /* 2^lg */ unsigned int ause = 0; /* summation of 'nums' */ unsigned int i = 1; /* count to traverse all array keys */ + unsigned int asize = limitasasize(t); /* real array size */ /* traverse each slice */ for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) { unsigned int lc = 0; /* counter */ unsigned int lim = ttlg; - if (lim > t->sizearray) { - lim = t->sizearray; /* adjust upper limit */ + if (lim > asize) { + lim = asize; /* adjust upper limit */ if (i > lim) break; /* no more elements to count */ } @@ -451,19 +507,19 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, unsigned int nhsize) { unsigned int i; Table newt; /* to keep the new hash part */ - unsigned int oldasize = t->sizearray; + unsigned int oldasize = setlimittosize(t); TValue *newarray; /* create new hash part with appropriate size into 'newt' */ setnodevector(L, &newt, nhsize); if (newasize < oldasize) { /* will array shrink? */ - t->sizearray = newasize; /* pretend array has new size... */ + t->alimit = newasize; /* pretend array has new size... */ exchangehashpart(t, &newt); /* and new hash */ /* re-insert into the new hash the elements from vanishing slice */ for (i = newasize; i < oldasize; i++) { if (!isempty(&t->array[i])) luaH_setint(L, t, i + 1, &t->array[i]); } - t->sizearray = oldasize; /* restore current size... */ + t->alimit = oldasize; /* restore current size... */ exchangehashpart(t, &newt); /* and hash (in case of errors) */ } /* allocate new array */ @@ -475,7 +531,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, /* allocation ok; initialize new part of the array */ exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */ t->array = newarray; /* set new array part */ - t->sizearray = newasize; + t->alimit = newasize; for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ setempty(&t->array[i]); /* re-insert elements from old hash part into new parts */ @@ -499,6 +555,7 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) { int i; int totaluse; for (i = 0; i <= MAXABITS; i++) nums[i] = 0; /* reset counts */ + setlimittosize(t); na = numusearray(t, nums); /* count keys in array part */ totaluse = na; /* all those keys are integer keys */ totaluse += numusehash(t, nums, &na); /* count keys in hash part */ @@ -525,7 +582,7 @@ Table *luaH_new (lua_State *L) { t->metatable = NULL; t->flags = cast_byte(~0); t->array = NULL; - t->sizearray = 0; + t->alimit = 0; setnodevector(L, t, 0); return t; } @@ -533,7 +590,7 @@ Table *luaH_new (lua_State *L) { void luaH_free (lua_State *L, Table *t) { freehash(L, t); - luaM_freearray(L, t->array, t->sizearray); + luaM_freearray(L, t->array, luaH_realasize(t)); luaM_free(L, t); } @@ -613,12 +670,21 @@ TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) { /* -** search function for integers +** Search function for integers. If integer is inside 'alimit', get it +** directly from the array part. Otherwise, if 'alimit' is not equal to +** the real size of the array, key still can be in the array part. In +** this case, try to avoid a call to 'luaH_realasize' when key is just +** one more than the limit (so that it can be incremented without +** changing the real size of the array). */ const TValue *luaH_getint (Table *t, lua_Integer key) { - /* (1 <= key && key <= t->sizearray) */ - if (l_castS2U(key) - 1u < t->sizearray) + if (l_castS2U(key) - 1u < t->alimit) /* (1 <= key && key <= t->alimit)? */ return &t->array[key - 1]; + else if (!limitequalsasize(t) && /* key still may be in the array part? */ + (key == t->alimit + 1 || l_castS2U(key) - 1u < luaH_realasize(t))) { + t->alimit = cast_uint(key); /* probably '#t' is here now */ + return &t->array[key - 1]; + } else { Node *n = hashint(t, key); for (;;) { /* check whether 'key' is somewhere in the chain */ @@ -749,33 +815,92 @@ static lua_Unsigned hash_search (Table *t, lua_Unsigned j) { } +static unsigned int binsearch (const TValue *array, unsigned int i, + unsigned int j) { + while (j - i > 1u) { /* binary search */ + unsigned int m = (i + j) / 2; + if (isempty(&array[m - 1])) j = m; + else i = m; + } + return i; +} + + /* ** Try to find a boundary in table 't'. (A 'boundary' is an integer index ** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent ** and 'maxinteger' if t[maxinteger] is present.) -** First, try the array part: if there is an array part and its last -** element is absent, there must be a boundary there; a binary search -** finds that boundary. Otherwise, if the hash part is empty or does not -** contain 'j + 1', 'j' is a boundary. Otherwize, call 'hash_search' -** to find a boundary in the hash part. +** (In the next explanation, we use Lua indices, that is, with base 1. +** The code itself uses base 0 when indexing the array part of the table.) +** The code starts with 'limit', a position in the array part that may +** be a boundary. +** (1) If 't[limit]' is empty, there must be a boundary before it. +** As a common case (e.g., after 't[#t]=nil'), check whether 'hint-1' +** is present. If so, it is a boundary. Otherwise, do a binary search +** between 0 and limit to find a boundary. In both cases, try to +** use this boundary as the new 'limit', as a hint for the next call. +** (2) If 't[limit]' is not empty and the array has more elements +** after 'limit', try to find a boundary there. Again, try first +** the special case (which should be quite frequent) where 'limit+1' +** is empty, so that 'limit' is a boundary. Otherwise, check the +** last element of the array part (set it as a new limit). If it is empty, +** there must be a boundary between the old limit (present) and the new +** limit (absent), which is found with a binary search. (This boundary +** always can be a new limit.) +** (3) The last case is when there are no elements in the array part +** (limit == 0) or its last element (the new limit) is present. +** In this case, must check the hash part. If there is no hash part, +** the boundary is 0. Otherwise, if 'limit+1' is absent, 'limit' is +** a boundary. Finally, if 'limit+1' is present, call 'hash_search' +** to find a boundary in the hash part of the table. (In those +** cases, the boundary is not inside the array part, and therefore +** cannot be used as a new limit.) */ lua_Unsigned luaH_getn (Table *t) { - unsigned int j = t->sizearray; - if (j > 0 && isempty(&t->array[j - 1])) { - unsigned int i = 0; - while (j - i > 1u) { /* binary search */ - unsigned int m = (i + j) / 2; - if (isempty(&t->array[m - 1])) j = m; - else i = m; + unsigned int limit = t->alimit; + if (limit > 0 && isempty(&t->array[limit - 1])) { + /* (1) there must be a boundary before 'limit' */ + if (limit >= 2 && !isempty(&t->array[limit - 2])) { + /* 'limit - 1' is a boundary; can it be a new limit? */ + if (ispow2realasize(t) && !ispow2(limit - 1)) { + t->alimit = limit - 1; + setnorealasize(t); + } + return limit - 1; + } + else { /* must search for a boundary in [0, limit] */ + unsigned int boundary = binsearch(t->array, 0, limit); + /* can this boundary represent the real size of the array? */ + if (ispow2realasize(t) && boundary > luaH_realasize(t) / 2) { + t->alimit = boundary; /* use it as the new limit */ + setnorealasize(t); + } + return boundary; } - return i; } - else { /* 'j' is zero or present in table */ - if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, j + 1)))) - return j; /* 'j + 1' is absent... */ - else /* 'j + 1' is also present */ - return hash_search(t, j); + /* 'limit' is zero or present in table */ + if (!limitequalsasize(t)) { + /* (2) 'limit' > 0 and array has more elements after 'limit' */ + if (isempty(&t->array[limit])) /* 'limit + 1' is empty? */ + return limit; /* this is the boundary */ + /* else, try last element in the array */ + limit = luaH_realasize(t); + if (isempty(&t->array[limit - 1])) { /* empty? */ + /* there must be a boundary in the array after old limit, + and it must be a valid new limit */ + unsigned int boundary = binsearch(t->array, t->alimit, limit); + t->alimit = boundary; + return boundary; + } + /* else, new limit is present in the table; check the hash part */ } + /* (3) 'limit' is the last element and either is zero or present in table */ + lua_assert(limit == luaH_realasize(t) && + (limit == 0 || !isempty(&t->array[limit - 1]))); + if (isdummy(t) || isempty(luaH_getint(t, cast(lua_Integer, limit + 1)))) + return limit; /* 'limit + 1' is absent... */ + else /* 'limit + 1' is also present */ + return hash_search(t, limit); } diff --git a/ltable.h b/ltable.h index 9b1a3464..ba2dddc8 100644 --- a/ltable.h +++ b/ltable.h @@ -1,5 +1,5 @@ /* -** $Id: ltable.h,v 2.26 2018/02/23 13:13:31 roberto Exp roberto $ +** $Id: ltable.h,v 2.27 2018/06/01 16:51:34 roberto Exp roberto $ ** Lua tables (hash) ** See Copyright Notice in lua.h */ @@ -45,6 +45,7 @@ LUAI_FUNC void luaH_resizearray (lua_State *L, Table *t, unsigned int nasize); LUAI_FUNC void luaH_free (lua_State *L, Table *t); LUAI_FUNC int luaH_next (lua_State *L, Table *t, StkId key); LUAI_FUNC lua_Unsigned luaH_getn (Table *t); +LUAI_FUNC unsigned int luaH_realasize (const Table *t); #if defined(LUA_DEBUG) diff --git a/ltests.c b/ltests.c index 452785c3..82d6463a 100644 --- a/ltests.c +++ b/ltests.c @@ -1,5 +1,5 @@ /* -** $Id: ltests.c,v 2.243 2018/03/09 19:24:45 roberto Exp roberto $ +** $Id: ltests.c,v 2.244 2018/06/11 14:19:50 roberto Exp roberto $ ** Internal Module for Debugging of the Lua Implementation ** See Copyright Notice in lua.h */ @@ -248,10 +248,11 @@ static void checkvalref (global_State *g, GCObject *f, const TValue *t) { static void checktable (global_State *g, Table *h) { unsigned int i; + unsigned int asize = luaH_realasize(h); Node *n, *limit = gnode(h, sizenode(h)); GCObject *hgc = obj2gco(h); checkobjref(g, hgc, h->metatable); - for (i = 0; i < h->sizearray; i++) + for (i = 0; i < asize; i++) checkvalref(g, hgc, &h->array[i]); for (n = gnode(h, 0); n < limit; n++) { if (!isempty(gval(n))) { @@ -810,19 +811,23 @@ static int stacklevel (lua_State *L) { static int table_query (lua_State *L) { const Table *t; int i = cast_int(luaL_optinteger(L, 2, -1)); + unsigned int asize; luaL_checktype(L, 1, LUA_TTABLE); t = hvalue(obj_at(L, 1)); + asize = luaH_realasize(t); if (i == -1) { - lua_pushinteger(L, t->sizearray); + lua_pushinteger(L, asize); lua_pushinteger(L, allocsizenode(t)); lua_pushinteger(L, isdummy(t) ? 0 : t->lastfree - t->node); + lua_pushinteger(L, t->alimit); + return 4; } - else if ((unsigned int)i < t->sizearray) { + else if ((unsigned int)i < asize) { lua_pushinteger(L, i); pushobject(L, &t->array[i]); lua_pushnil(L); } - else if ((i -= t->sizearray) < sizenode(t)) { + else if ((i -= asize) < sizenode(t)) { TValue k; getnodekey(L, &k, gnode(t, i)); if (!isempty(gval(gnode(t, i))) || diff --git a/lvm.c b/lvm.c index 3fed2a27..1e45e2ce 100644 --- a/lvm.c +++ b/lvm.c @@ -1,5 +1,5 @@ /* -** $Id: lvm.c,v 2.356 2018/05/30 14:25:52 roberto Exp roberto $ +** $Id: lvm.c,v 2.357 2018/06/01 16:51:34 roberto Exp roberto $ ** Lua virtual machine ** See Copyright Notice in lua.h */ @@ -1766,7 +1766,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) { } h = hvalue(s2v(ra)); last = ((c-1)*LFIELDS_PER_FLUSH) + n; - if (last > h->sizearray) /* needs more space? */ + if (last > luaH_realasize(h)) /* needs more space? */ luaH_resizearray(L, h, last); /* preallocate it at once */ for (; n > 0; n--) { TValue *val = s2v(ra + n); diff --git a/lvm.h b/lvm.h index c5d5206d..a789acc4 100644 --- a/lvm.h +++ b/lvm.h @@ -1,5 +1,5 @@ /* -** $Id: lvm.h,v 2.50 2018/02/21 12:54:26 roberto Exp roberto $ +** $Id: lvm.h,v 2.51 2018/02/23 13:13:31 roberto Exp roberto $ ** Lua virtual machine ** See Copyright Notice in lua.h */ @@ -84,7 +84,7 @@ #define luaV_fastgeti(L,t,k,slot) \ (!ttistable(t) \ ? (slot = NULL, 0) /* not a table; 'slot' is NULL and result is 0 */ \ - : (slot = (l_castS2U(k) - 1u < hvalue(t)->sizearray) \ + : (slot = (l_castS2U(k) - 1u < hvalue(t)->alimit) \ ? &hvalue(t)->array[k - 1] : luaH_getint(hvalue(t), k), \ !isempty(slot))) /* result not empty? */ -- cgit v1.2.3-55-g6feb