field 'sizearray' in struct 'Table' changed to 'alimit', which can

be used as a hint for '#t'

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<<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
index cc98f456..b0d3944d 100644
--- 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
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? */