commit 6e600695f8398843a156ce02023f731c6d687ae8
parent 06127927ffb4eb8459523f6c07bf8f22390c31b9
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Fri, 15 Jun 2018 11:13:53 -0300
field 'sizearray' in struct 'Table' changed to 'alimit', which can
be used as a hint for '#t'
Diffstat:
7 files changed, 201 insertions(+), 54 deletions(-)
diff --git 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
@@ -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<<p means tagmethod(p) is not present */
lu_byte lsizenode; /* log2 of size of 'node' array */
- unsigned int sizearray; /* size of 'array' array */
+ unsigned int alimit; /* "limit" of 'array' array */
TValue *array; /* array part */
Node *node;
Node *lastfree; /* any free position is before this position */
diff --git a/ltable.c b/ltable.c
@@ -1,5 +1,5 @@
/*
-** $Id: ltable.c,v 2.137 2018/05/30 14:25:52 roberto Exp roberto $
+** $Id: ltable.c,v 2.138 2018/06/01 16:51:34 roberto Exp roberto $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/
@@ -193,6 +193,59 @@ static int equalkey (const TValue *k1, const Node *n2) {
/*
+** True if value of 'alimit' is equal to the real size of the array
+** part of table 't'. (Otherwise, the array part must be larger than
+** 'alimit'.)
+*/
+#define limitequalsasize(t) (isrealasize(t) || ispow2((t)->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
@@ -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
@@ -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
@@ -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
@@ -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? */
