From 002beeebe79065e03dd9f531bee367e8459e3f64 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 29 Nov 2024 17:26:20 -0300 Subject: 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. --- ltable.h | 36 ++++++++++++++++++++++-------------- 1 file changed, 22 insertions(+), 14 deletions(-) (limited to 'ltable.h') 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,27 +95,35 @@ /* ** 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 */ @@ -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) -- cgit v1.2.3-55-g6feb