New way to keep hints for table length

Instead of using 'alimit' for keeping the size of the array and at
the same time being a hint for '#t', a table now keeps these two
values separate. The Table structure has a field 'asize' with the
size of the array, while the length hint is kept in the array itself.
That way, tables with no array part waste no space with that field.
Moreover, the space for the hint may have zero cost for small arrays,
if the array of tags plus the hint still fits in a single word.

1 files changed, 22 insertions, 14 deletions

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)