7 files changed, 146 insertions, 249 deletions

diff --git a/lgc.c b/lgc.c
index e4130bd5..3cdfd006 100644
--- a/lgc.c
+++ b/lgc.c
@@ -486,7 +486,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->alimit > 0);
+  int hasclears = (h->asize > 0);
   for (n = gnode(h, 0); n < limit; n++) {  /* traverse hash part */
     if (isempty(gval(n)))  /* entry is empty? */
       clearkey(n);  /* clear its key */
@@ -508,7 +508,7 @@ static void traverseweakvalue (global_State *g, Table *h) {
 ** Traverse the array part of a table.
 */
 static int traversearray (global_State *g, Table *h) {
-  unsigned asize = luaH_realasize(h);
+  unsigned asize = h->asize;
   int marked = 0;  /* true if some object is marked in this traversal */
   unsigned i;
   for (i = 0; i < asize; i++) {
@@ -604,7 +604,7 @@ static l_mem traversetable (global_State *g, Table *h) {
   }
   else  /* not weak */
     traversestrongtable(g, h);
-  return 1 + 2*sizenode(h) + h->alimit;
+  return 1 + 2*sizenode(h) + h->asize;
 }
 
 
@@ -790,7 +790,7 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
     Table *h = gco2t(l);
     Node *n, *limit = gnodelast(h);
     unsigned int i;
-    unsigned int asize = luaH_realasize(h);
+    unsigned int asize = h->asize;
     for (i = 0; i < asize; i++) {
       GCObject *o = gcvalarr(h, i);
       if (iscleared(g, o))  /* value was collected? */
diff --git a/lobject.h b/lobject.h
index b1407b77..4a0835a8 100644
--- a/lobject.h
+++ b/lobject.h
@@ -763,24 +763,12 @@ typedef union Node {
           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)->flags & BITRAS))
-#define setrealasize(t)         ((t)->flags &= cast_byte(~BITRAS))
-#define setnorealasize(t)       ((t)->flags |= 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 alimit;  /* "limit" of 'array' array */
+  lu_byte lsizenode;  /* log2 of number of slots of 'node' array */
+  unsigned int asize;  /* number of slots in 'array' array */
   Value *array;  /* array part */
   Node *node;
   struct Table *metatable;
diff --git a/ltable.c b/ltable.c
index 71a6f30d..6ea382a1 100644
--- a/ltable.c
+++ b/ltable.c
@@ -41,12 +41,12 @@
 
 
 /*
-** Only tables with hash parts larger than 2^LIMFORLAST has a 'lastfree'
-** field that optimizes finding a free slot. That field is stored just
-** before the array of nodes, in the same block. Smaller tables do a
-** complete search when looking for a free slot.
+** Only hash parts with at least 2^LIMFORLAST have a 'lastfree' field
+** that optimizes finding a free slot. That field is stored just before
+** the array of nodes, in the same block. Smaller tables do a complete
+** search when looking for a free slot.
 */
-#define LIMFORLAST    2  /* log2 of real limit */
+#define LIMFORLAST    3  /* log2 of real limit (8) */
 
 /*
 ** The union 'Limbox' stores 'lastfree' and ensures that what follows it
@@ -59,7 +59,7 @@ typedef union {
   char padding[offsetof(Limbox_aux, follows_pNode)];
 } Limbox;
 
-#define haslastfree(t)     ((t)->lsizenode > LIMFORLAST)
+#define haslastfree(t)     ((t)->lsizenode >= LIMFORLAST)
 #define getlastfree(t)     ((cast(Limbox *, (t)->node) - 1)->lastfree)
 
 
@@ -274,61 +274,6 @@ static int equalkey (const TValue *k1, const Node *n2, int deadok) {
 
 
 /*
-** 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
-*/
-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 'size' */
-    size |= (size >> 1);
-    size |= (size >> 2);
-    size |= (size >> 4);
-    size |= (size >> 8);
-#if (UINT_MAX >> 14) > 3  /* unsigned int has more than 16 bits */
-    size |= (size >> 16);
-#if (UINT_MAX >> 30) > 3
-    size |= (size >> 32);  /* unsigned int has more than 32 bits */
-#endif
-#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.)
 ** See explanation about 'deadok' in function 'equalkey'.
@@ -384,7 +329,7 @@ static unsigned findindex (lua_State *L, Table *t, TValue *key,
 
 
 int luaH_next (lua_State *L, Table *t, StkId key) {
-  unsigned int asize = luaH_realasize(t);
+  unsigned int asize = t->asize;
   unsigned int i = findindex(L, t, s2v(key), asize);  /* find original key */
   for (; i < asize; i++) {  /* try first array part */
     lu_byte tag = *getArrTag(t, i);
@@ -425,38 +370,10 @@ static void freehash (lua_State *L, Table *t) {
 
 
 /*
-** Check whether an integer key is in the array part. If 'alimit' is
-** not the real size of the array, the key still can be in the array
-** part.  In this case, do the "Xmilia trick" to check whether 'key-1'
-** is smaller than the real size.
-** The trick works as follow: let 'p' be the integer such that
-** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'.  That is,
-** 'p' is the highest 1-bit in 'alimit-1', and 2^(p+1) is the real size
-** of the array. What we have to check becomes 'key-1 < 2^(p+1)'.  We
-** compute '(key-1) & ~(alimit-1)', which we call 'res'; it will have
-** the 'p' bit cleared. (It may also clear other bits smaller than 'p',
-** but no bit higher than 'p'.) If the key is outside the array, that
-** is, 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than
-** 'p', therefore it will be larger or equal to 'alimit', and the check
-** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than
-** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller
-** than 2^p, therefore smaller than 'alimit', and the check succeeds.
-** As special cases, when 'alimit' is 0 the condition is trivially false,
-** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'.
-** If key is 0 or negative, 'res' will have its higher bit on, so that
-** it cannot be smaller than 'alimit'.
+** Check whether an integer key is in the array part of a table.
 */
-static int keyinarray (Table *t, lua_Integer key) {
-  lua_Unsigned alimit = t->alimit;
-  if (l_castS2U(key) - 1u < alimit)  /* 'key' in [1, t->alimit]? */
-    return 1;
-  else if (!isrealasize(t) &&  /* key still may be in the array part? */
-           (((l_castS2U(key) - 1u) & ~(alimit - 1u)) < alimit)) {
-    t->alimit = cast_uint(key);  /* probably '#t' is here now */
-    return 1;
-  }
-  else
-    return 0;
+l_sinline int keyinarray (Table *t, lua_Integer key) {
+  return (l_castS2U(key) - 1u < t->asize);  /* 'key' in [1, t->asize]? */
 }
 
 
@@ -466,7 +383,6 @@ static int keyinarray (Table *t, lua_Integer key) {
 ** ==============================================================
 */
 
-
 /*
 ** Structure to count the keys in a table.
 ** 'total' is the total number of keys in the table.
@@ -534,7 +450,7 @@ static void countint (lua_Integer key, Counters *ct) {
 }
 
 
-l_sinline int arraykeyisempty (const Table *t, lua_Unsigned key) {
+l_sinline int arraykeyisempty (const Table *t, unsigned key) {
   int tag = *getArrTag(t, key - 1);
   return tagisempty(tag);
 }
@@ -548,7 +464,7 @@ static void numusearray (const Table *t, Counters *ct) {
   unsigned int ttlg;  /* 2^lg */
   unsigned int ause = 0;  /* summation of 'nums' */
   unsigned int i = 1;  /* index to traverse all array keys */
-  unsigned int asize = limitasasize(t);  /* real array size */
+  unsigned int asize = t->asize;
   /* traverse each slice */
   for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
     unsigned int lc = 0;  /* counter */
@@ -600,7 +516,10 @@ static void numusehash (const Table *t, Counters *ct) {
 ** "concrete size" (number of bytes in the array).
 */
 static size_t concretesize (unsigned int size) {
-  return size * sizeof(Value) + size;  /* space for the two arrays */
+  if (size == 0)
+    return 0;
+  else  /* space for the two arrays plus an unsigned in between */
+    return size * (sizeof(Value) + 1) + sizeof(unsigned);
 }
 
 
@@ -631,17 +550,18 @@ static Value *resizearray (lua_State *L , Table *t,
                   luaM_reallocvector(L, NULL, 0, newasizeb, lu_byte));
     if (np == NULL)  /* allocation error? */
       return NULL;
+    np += newasize;  /* shift pointer to the end of value segment */
     if (oldasize > 0) {
-      size_t oldasizeb = concretesize(oldasize);
       /* move common elements to new position */
-      Value *op = t->array - oldasize;  /* real original array */
+      size_t oldasizeb = concretesize(oldasize);
+      Value *op = t->array;  /* original array */
       unsigned tomove = (oldasize < newasize) ? oldasize : newasize;
       size_t tomoveb = (oldasize < newasize) ? oldasizeb : newasizeb;
       lua_assert(tomoveb > 0);
-      memcpy(np + newasize - tomove, op + oldasize - tomove, tomoveb);
-      luaM_freemem(L, op, oldasizeb);
+      memcpy(np - tomove, op - tomove, tomoveb);
+      luaM_freemem(L, op - oldasize, oldasizeb);  /* free old block */
     }
-    return np + newasize;  /* shift pointer to the end of value segment */
+    return np;
   }
 }
 
@@ -665,7 +585,7 @@ static void setnodevector (lua_State *L, Table *t, unsigned size) {
     if (lsize > MAXHBITS || (1u << lsize) > MAXHSIZE)
       luaG_runerror(L, "table overflow");
     size = twoto(lsize);
-    if (lsize <= LIMFORLAST)  /* no 'lastfree' field? */
+    if (lsize < LIMFORLAST)  /* no 'lastfree' field? */
       t->node = luaM_newvector(L, size, Node);
     else {
       size_t bsize = size * sizeof(Node) + sizeof(Limbox);
@@ -730,7 +650,7 @@ static void exchangehashpart (Table *t1, Table *t2) {
 static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize,
                                             unsigned newasize) {
   unsigned i;
-  t->alimit = newasize;  /* pretend array has new size... */
+  t->asize = newasize;  /* pretend array has new size... */
   for (i = newasize; i < oldasize; i++) {  /* traverse vanishing slice */
     lu_byte tag = *getArrTag(t, i);
     if (!tagisempty(tag)) {  /* a non-empty entry? */
@@ -740,7 +660,7 @@ static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize,
       luaH_setint(L, t, cast_int(i) + 1, &aux);
     }
   }
-  t->alimit = oldasize;  /* restore current size... */
+  t->asize = oldasize;  /* restore current size... */
 }
 
 
@@ -772,7 +692,7 @@ static void clearNewSlice (Table *t, unsigned oldasize, unsigned newasize) {
 void luaH_resize (lua_State *L, Table *t, unsigned newasize,
                                           unsigned nhsize) {
   Table newt;  /* to keep the new hash part */
-  unsigned int oldasize = setlimittosize(t);
+  unsigned oldasize = t->asize;
   Value *newarray;
   if (newasize > MAXASIZE)
     luaG_runerror(L, "table overflow");
@@ -794,7 +714,9 @@ void luaH_resize (lua_State *L, Table *t, unsigned 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->alimit = newasize;
+  t->asize = newasize;
+  if (newarray != NULL)
+    *lenhint(t) = newasize / 2u;  /* set an initial hint */
   clearNewSlice(t, oldasize, newasize);
   /* re-insert elements from old hash part into new parts */
   reinsert(L, &newt, t);  /* 'newt' now has the old hash */
@@ -818,7 +740,6 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) {
   Counters ct;
   unsigned i;
   unsigned nsize;  /* size for the hash part */
-  setlimittosize(t);
   /* reset counts */
   for (i = 0; i <= MAXABITS; i++) ct.nums[i] = 0;
   ct.na = 0;
@@ -829,7 +750,7 @@ static void rehash (lua_State *L, Table *t, const TValue *ek) {
   numusehash(t, &ct);  /* count keys in hash part */
   if (ct.na == 0) {
     /* no new keys to enter array part; keep it with the same size */
-    asize = luaH_realasize(t);
+    asize = t->asize;
   }
   else {  /* compute best size for array part */
     numusearray(t, &ct);  /* count keys in array part */
@@ -857,15 +778,14 @@ Table *luaH_new (lua_State *L) {
   t->metatable = NULL;
   t->flags = maskflags;  /* table has no metamethod fields */
   t->array = NULL;
-  t->alimit = 0;
+  t->asize = 0;
   setnodevector(L, t, 0);
   return t;
 }
 
 
 lu_mem luaH_size (Table *t) {
-  lu_mem sz = cast(lu_mem, sizeof(Table))
-            + luaH_realasize(t) * (sizeof(Value) + 1);
+  lu_mem sz = cast(lu_mem, sizeof(Table)) + concretesize(t->asize);
   if (!isdummy(t))
     sz += sizehash(t);
   return sz;
@@ -876,9 +796,8 @@ lu_mem luaH_size (Table *t) {
 ** Frees a table.
 */
 void luaH_free (lua_State *L, Table *t) {
-  unsigned int realsize = luaH_realasize(t);
   freehash(L, t);
-  resizearray(L, t, realsize, 0);
+  resizearray(L, t, t->asize, 0);
   luaM_free(L, t);
 }
 
@@ -972,7 +891,7 @@ static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
 
 static const TValue *getintfromhash (Table *t, lua_Integer key) {
   Node *n = hashint(t, key);
-  lua_assert(l_castS2U(key) - 1u >= luaH_realasize(t));
+  lua_assert(!keyinarray(t, key));
   for (;;) {  /* check whether 'key' is somewhere in the chain */
     if (keyisinteger(n) && keyival(n) == key)
       return gval(n);  /* that's it */
@@ -1112,17 +1031,15 @@ static int rawfinishnodeset (const TValue *slot, TValue *val) {
 
 
 int luaH_psetint (Table *t, lua_Integer key, TValue *val) {
-  if (keyinarray(t, key)) {
-    lu_byte *tag = getArrTag(t, key - 1);
-    if (!tagisempty(*tag) || checknoTM(t->metatable, TM_NEWINDEX)) {
-      fval2arr(t, cast_uint(key) - 1, tag, val);
-      return HOK;  /* success */
-    }
-    else
-      return ~cast_int(key - 1);  /* empty slot in the array part */
-  }
-  else
-    return finishnodeset(t, getintfromhash(t, key), val);
+  lua_assert(!keyinarray(t, key));
+  return finishnodeset(t, getintfromhash(t, key), val);
+}
+
+
+static int psetint (Table *t, lua_Integer key, TValue *val) {
+  int hres;
+  luaH_fastseti(t, key, val, hres);
+  return hres;
 }
 
 
@@ -1139,12 +1056,12 @@ int luaH_psetstr (Table *t, TString *key, TValue *val) {
 int luaH_pset (Table *t, const TValue *key, TValue *val) {
   switch (ttypetag(key)) {
     case LUA_VSHRSTR: return luaH_psetshortstr(t, tsvalue(key), val);
-    case LUA_VNUMINT: return luaH_psetint(t, ivalue(key), val);
+    case LUA_VNUMINT: return psetint(t, ivalue(key), val);
     case LUA_VNIL: return HNOTFOUND;
     case LUA_VNUMFLT: {
       lua_Integer k;
       if (luaV_flttointeger(fltvalue(key), &k, F2Ieq)) /* integral index? */
-        return luaH_psetint(t, k, val);  /* use specialized version */
+        return psetint(t, k, val);  /* use specialized version */
       /* else... */
     }  /* FALLTHROUGH */
     default:
@@ -1244,6 +1161,7 @@ static lua_Unsigned hash_search (Table *t, lua_Unsigned j) {
 
 
 static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) {
+  lua_assert(i <= j);
   while (j - i > 1u) {  /* binary search */
     unsigned int m = (i + j) / 2;
     if (arraykeyisempty(array, m)) j = m;
@@ -1253,90 +1171,74 @@ static unsigned int binsearch (Table *array, unsigned int i, unsigned int j) {
 }
 
 
+/* return a border, saving it as a hint for next call */
+static lua_Unsigned newhint (Table *t, unsigned hint) {
+  lua_assert(hint <= t->asize);
+  *lenhint(t) = hint;
+  return hint;
+}
+
+
 /*
-** 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.)
-** (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 = t->alimit', 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 'limit-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 'alimit', 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. If it is empty, there must be a
-** boundary between the old limit (present) and the last element
-** (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
-** or 'limit+1' is absent, 'limit' is a boundary.  Otherwise, 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.)
+** Try to find a border in table 't'. (A 'border' is an integer index
+** such that t[i] is present and t[i+1] is absent, or 0 if t[1] is absent,
+** or 'maxinteger' if t[maxinteger] is present.)
+** If there is an array part, try to find a border there. First try
+** to find it in the vicinity of the previous result (hint), to handle
+** cases like 't[#t + 1] = val' or 't[#t] = nil', that move the border
+** by one entry. Otherwise, do a binary search to find the border.
+** If there is no array part, or its last element is non empty, the
+** border may be in the hash part.
 */
 lua_Unsigned luaH_getn (Table *t) {
-  unsigned int limit = t->alimit;
-  if (limit > 0 && arraykeyisempty(t, limit)) {  /* (1)? */
-    /* there must be a boundary before 'limit' */
-    if (limit >= 2 && !arraykeyisempty(t, limit - 1)) {
-      /* 'limit - 1' is a boundary; can it be a new limit? */
-      if (ispow2realasize(t) && !ispow2(limit - 1)) {
-        t->alimit = limit - 1;
-        setnorealasize(t);  /* now 'alimit' is not the real size */
+  unsigned asize = t->asize;
+  if (asize > 0) {  /* is there an array part? */
+    const unsigned maxvicinity = 4;
+    unsigned limit = *lenhint(t);  /* start with the hint */
+    if (limit == 0)
+      limit = 1;  /* make limit a valid index in the array */
+    if (arraykeyisempty(t, limit)) {  /* t[limit] empty? */
+      /* there must be a border before 'limit' */
+      unsigned i;
+      /* look for a border in the vicinity of the hint */
+      for (i = 0; i < maxvicinity && limit > 1; i++) {
+        limit--;
+        if (!arraykeyisempty(t, limit))
+          return newhint(t, limit);  /* 'limit' is a border */
       }
-      return limit - 1;
+      /* t[limit] still empty; search for a border in [0, limit) */
+      return newhint(t, binsearch(t, 0, limit));
     }
-    else {  /* must search for a boundary in [0, limit] */
-      unsigned int boundary = binsearch(t, 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);
+    else {  /* 'limit' is present in table; look for a border after it */
+      unsigned i;
+      /* look for a border in the vicinity of the hint */
+      for (i = 0; i < maxvicinity && limit < asize; i++) {
+        limit++;
+        if (arraykeyisempty(t, limit))
+          return newhint(t, limit - 1);  /* 'limit - 1' is a border */
+      }
+      if (arraykeyisempty(t, asize)) {  /* last element empty? */
+        /* t[limit] not empty; search for a border in [limit, asize) */
+        return newhint(t, binsearch(t, limit, asize));
       }
-      return boundary;
-    }
-  }
-  /* 'limit' is zero or present in table */
-  if (!limitequalsasize(t)) {  /* (2)? */
-    /* 'limit' > 0 and array has more elements after 'limit' */
-    if (arraykeyisempty(t, limit + 1))  /* 'limit + 1' is empty? */
-      return limit;  /* this is the boundary */
-    /* else, try last element in the array */
-    limit = luaH_realasize(t);
-    if (arraykeyisempty(t, limit)) {  /* 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, t->alimit, limit);
-      t->alimit = boundary;
-      return boundary;
     }
-    /* else, new limit is present in the table; check the hash part */
+    /* last element non empty; set a hint to speed up findind that again */
+    /* (keys in the hash part cannot be hints) */
+    *lenhint(t) = asize;
   }
-  /* (3) 'limit' is the last element and either is zero or present in table */
-  lua_assert(limit == luaH_realasize(t) &&
-             (limit == 0 || !arraykeyisempty(t, limit)));
-  if (isdummy(t) || hashkeyisempty(t, limit + 1))
-    return limit;  /* 'limit + 1' is absent */
-  else  /* 'limit + 1' is also present */
-    return hash_search(t, limit);
+  /* no array part or t[asize] is not empty; check the hash part */
+  lua_assert(asize == 0 || !arraykeyisempty(t, asize));
+  if (isdummy(t) || hashkeyisempty(t, asize + 1))
+    return asize;  /* 'asize + 1' is empty */
+  else  /* 'asize + 1' is also non empty */
+    return hash_search(t, asize);
 }
 
 
 
 #if defined(LUA_DEBUG)
 
-/* export these functions for the test library */
+/* export this function for the test library */
 
 Node *luaH_mainposition (const Table *t, const TValue *key) {
   return mainpositionTV(t, key);
diff --git a/ltable.h b/ltable.h
index 17e4fb4a..9c4eb937 100644
--- a/ltable.h
+++ b/ltable.h
@@ -48,7 +48,7 @@
 
 #define luaH_fastgeti(t,k,res,tag) \
   { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \
-    if ((u < h->alimit)) { \
+    if ((u < h->asize)) { \
       tag = *getArrTag(h, u); \
       if (!tagisempty(tag)) { farr2val(h, u, tag, res); }} \
     else { tag = luaH_getint(h, (k), res); }}
@@ -56,10 +56,11 @@
 
 #define luaH_fastseti(t,k,val,hres) \
   { Table *h = t; lua_Unsigned u = l_castS2U(k) - 1u; \
-    if ((u < h->alimit)) { \
+    if ((u < h->asize)) { \
       lu_byte *tag = getArrTag(h, u); \
-      if (tagisempty(*tag)) hres = ~cast_int(u); \
-      else { fval2arr(h, u, tag, val); hres = HOK; }} \
+      if (h->metatable == NULL || !tagisempty(*tag)) \
+        { fval2arr(h, u, tag, val); hres = HOK; } \
+      else hres = ~cast_int(u); } \
     else { hres = luaH_psetint(h, k, val); }}
 
 
@@ -94,28 +95,36 @@
 /*
 ** The array part of a table is represented by an inverted array of
 ** values followed by an array of tags, to avoid wasting space with
-** padding.  The 'array' pointer points to the junction of the two
-** arrays, so that values are indexed with negative indices and tags
-** with non-negative indices.
+** padding. In between them there is an unsigned int, explained later.
+** The 'array' pointer points between the two arrays, so that values are
+** indexed with negative indices and tags with non-negative indices.
 
-                     Values                      Tags
-        --------------------------------------------------------
-         ...  |   Value 1     |   Value 0     |0|1|...
-        --------------------------------------------------------
-                                               ^ t->array
+             Values                              Tags
+  --------------------------------------------------------
+  ...  |   Value 1     |   Value 0     |unsigned|0|1|...
+  --------------------------------------------------------
+                                       ^ t->array
 
 ** All accesses to 't->array' should be through the macros 'getArrTag'
 ** and 'getArrVal'.
 */
 
 /* Computes the address of the tag for the abstract C-index 'k' */
-#define getArrTag(t,k)  (cast(lu_byte*, (t)->array) + (k))
+#define getArrTag(t,k)  (cast(lu_byte*, (t)->array) + sizeof(unsigned) + (k))
 
 /* Computes the address of the value for the abstract C-index 'k' */
 #define getArrVal(t,k)  ((t)->array - 1 - (k))
 
 
 /*
+** The unsigned between the two arrays is used as a hint for #t;
+** see luaH_getn. It is stored there to avoid wasting space in
+** the structure Table for tables with no array part.
+*/
+#define lenhint(t)      cast(unsigned*, (t)->array)
+
+
+/*
 ** Move TValues to/from arrays, using C indices
 */
 #define arr2obj(h,k,val)  \
@@ -167,7 +176,6 @@ LUAI_FUNC lu_mem luaH_size (Table *t);
 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 luaH_realasize (const Table *t);
 
 
 #if defined(LUA_DEBUG)
diff --git a/ltests.c b/ltests.c
index 3edf805e..44ed7bcc 100644
--- a/ltests.c
+++ b/ltests.c
@@ -359,7 +359,7 @@ 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);
+  unsigned int asize = h->asize;
   Node *n, *limit = gnode(h, sizenode(h));
   GCObject *hgc = obj2gco(h);
   checkobjrefN(g, hgc, h->metatable);
@@ -1034,11 +1034,11 @@ static int table_query (lua_State *L) {
   unsigned int asize;
   luaL_checktype(L, 1, LUA_TTABLE);
   t = hvalue(obj_at(L, 1));
-  asize = luaH_realasize(t);
+  asize = t->asize;
   if (i == -1) {
     lua_pushinteger(L, cast(lua_Integer, asize));
     lua_pushinteger(L, cast(lua_Integer, allocsizenode(t)));
-    lua_pushinteger(L, cast(lua_Integer, t->alimit));
+    lua_pushinteger(L, cast(lua_Integer, asize > 0 ? *lenhint(t) : 0));
     return 3;
   }
   else if (cast_uint(i) < asize) {
diff --git a/lvm.c b/lvm.c
index 33da5609..1c564a71 100644
--- a/lvm.c
+++ b/lvm.c
@@ -1865,7 +1865,7 @@ void luaV_execute (lua_State *L, CallInfo *ci) {
           pc++;
         }
         /* when 'n' is known, table should have proper size */
-        if (last > luaH_realasize(h)) {  /* needs more space? */
+        if (last > h->asize) {  /* needs more space? */
           /* fixed-size sets should have space preallocated */
           lua_assert(GETARG_vB(i) == 0);
           luaH_resizearray(L, h, last);  /* preallocate it at once */
diff --git a/testes/nextvar.lua b/testes/nextvar.lua
index 00e509f8..d1da3cee 100644
--- a/testes/nextvar.lua
+++ b/testes/nextvar.lua
@@ -316,21 +316,6 @@ end
 local a = {}
 for i=1,lim do a[i] = true; foo(i, table.unpack(a)) end
 
-
--- Table length with limit smaller than maximum value at array
-local a = {}
-for i = 1,64 do a[i] = true end    -- make its array size 64
-for i = 1,64 do a[i] = nil end     -- erase all elements
-assert(T.querytab(a) == 64)    -- array part has 64 elements
-a[32] = true; a[48] = true;    -- binary search will find these ones
-a[51] = true                   -- binary search will miss this one
-assert(#a == 48)               -- this will set the limit
-assert(select(3, T.querytab(a)) == 48)  -- this is the limit now
-a[50] = true                   -- this will set a new limit
-assert(select(3, T.querytab(a)) == 50)  -- this is the limit now
--- but the size is larger (and still inside the array part)
-assert(#a == 51)
-
 end  --]
 
 
@@ -344,6 +329,20 @@ assert(#{1, 2, 3, nil, nil} == 3)
 print'+'
 
 
+do
+  local s1, s2 = math.randomseed()
+  print(string.format(
+    "testing length for some random tables (seeds 0X%x:%x)", s1, s2))
+  local N = 130
+  for i = 1, 1e3 do   -- create that many random tables
+    local a = table.create(math.random(N))   -- initiate with random size
+    for j = 1, math.random(N) do   -- add random number of random entries
+      a[math.random(N)] = true
+    end
+    assert(#a == 0 or a[#a] and not a[#a + 1])
+  end
+end
+
 local nofind = {}
 
 a,b,c = 1,2,3