From 43c8e5bded052801f54a7439d18933b83570eb82 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 30 Oct 2023 14:25:59 -0300 Subject: Full abstraction for representation of array values --- lobject.h | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'lobject.h') diff --git a/lobject.h b/lobject.h index 556608e4..e91bb0f8 100644 --- a/lobject.h +++ b/lobject.h @@ -736,12 +736,15 @@ typedef union Node { #define setnorealasize(t) ((t)->flags |= BITRAS) +typedef struct ArrayCell ArrayCell; + + typedef struct Table { CommonHeader; lu_byte flags; /* 1<

Date: Fri, 3 Nov 2023 15:26:13 -0300 Subject: Full implementation of new representation for arrays --- lgc.c | 8 ++++---- lobject.h | 4 +++- ltable.c | 46 +++++++++++++++++++++++++++++++++++++--------- ltable.h | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++------------- lvm.h | 4 ++-- 5 files changed, 96 insertions(+), 29 deletions(-) (limited to 'lobject.h') diff --git a/lgc.c b/lgc.c index 813b08d5..0f423282 100644 --- a/lgc.c +++ b/lgc.c @@ -493,7 +493,7 @@ static int traverseephemeron (global_State *g, Table *h, int inv) { unsigned int nsize = sizenode(h); /* traverse array part */ for (i = 0; i < asize; i++) { - GCObject *o = gcvalarr(h, i + 1); + GCObject *o = gcvalarr(h, i); if (o != NULL && iswhite(o)) { marked = 1; reallymarkobject(g, o); @@ -533,7 +533,7 @@ static void traversestrongtable (global_State *g, Table *h) { unsigned int i; unsigned int asize = luaH_realasize(h); for (i = 0; i < asize; i++) { /* traverse array part */ - GCObject *o = gcvalarr(h, i + 1); + GCObject *o = gcvalarr(h, i); if (o != NULL && iswhite(o)) reallymarkobject(g, o); } @@ -757,9 +757,9 @@ static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) { unsigned int i; unsigned int asize = luaH_realasize(h); for (i = 0; i < asize; i++) { - GCObject *o = gcvalarr(h, i + 1); + GCObject *o = gcvalarr(h, i); if (iscleared(g, o)) /* value was collected? */ - *getArrTag(h, i + 1) = LUA_VEMPTY; /* remove entry */ + *getArrTag(h, i) = LUA_VEMPTY; /* remove entry */ } for (n = gnode(h, 0); n < limit; n++) { if (iscleared(g, gcvalueN(gval(n)))) /* unmarked value? */ diff --git a/lobject.h b/lobject.h index e91bb0f8..25e268be 100644 --- a/lobject.h +++ b/lobject.h @@ -192,6 +192,8 @@ typedef union { /* macro to test for (any kind of) nil */ #define ttisnil(v) checktype((v), LUA_TNIL) +#define tagisempty(tag) (novariant(tag) == LUA_TNIL) + /* macro to test for a standard nil */ #define ttisstrictnil(o) checktag((o), LUA_VNIL) @@ -736,7 +738,7 @@ typedef union Node { #define setnorealasize(t) ((t)->flags |= BITRAS) -typedef struct ArrayCell ArrayCell; +typedef union ArrayCell ArrayCell; typedef struct Table { diff --git a/ltable.c b/ltable.c index ddda9a44..b7362a36 100644 --- a/ltable.c +++ b/ltable.c @@ -350,7 +350,7 @@ int luaH_next (lua_State *L, Table *t, StkId key) { 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 */ - int tag = *getArrTag(t, i + 1); + int tag = *getArrTag(t, i); if (!tagisempty(tag)) { /* a non-empty entry? */ setivalue(s2v(key), i + 1); farr2val(t, i + 1, tag, s2v(key + 1)); @@ -458,7 +458,7 @@ static int countint (lua_Integer key, unsigned int *nums) { l_sinline int arraykeyisempty (const Table *t, lua_Integer key) { - int tag = *getArrTag(t, key); + int tag = *getArrTag(t, key - 1); return tagisempty(tag); } @@ -512,6 +512,33 @@ static int numusehash (const Table *t, unsigned int *nums, unsigned int *pna) { } +/* +** Convert an "abstract size" (number of values in an array) to +** "concrete size" (number of cell elements in the array). Cells +** do not need to be full; we only must make sure it has the values +** needed and its 'tag' element. So, we compute the concrete tag index +** and the concrete value index of the last element, get their maximum +** and adds 1. +*/ +static unsigned int concretesize (unsigned int size) { + if (size == 0) return 0; + else { + unsigned int ts = TagIndex(size - 1); + unsigned int vs = ValueIndex(size - 1); + return ((ts >= vs) ? ts : vs) + 1; + } +} + + +static ArrayCell *resizearray (lua_State *L , Table *t, + unsigned int oldasize, + unsigned int newasize) { + oldasize = concretesize(oldasize); + newasize = concretesize(newasize); + return luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell); +} + + /* ** Creates an array for the hash part of a table with the given ** size, or reuses the dummy node if size is zero. @@ -605,7 +632,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, exchangehashpart(t, &newt); /* and new hash */ /* re-insert into the new hash the elements from vanishing slice */ for (i = newasize; i < oldasize; i++) { - int tag = *getArrTag(t, i + 1); + int tag = *getArrTag(t, i); if (!tagisempty(tag)) { /* a non-empty entry? */ TValue aux; farr2val(t, i + 1, tag, &aux); @@ -616,7 +643,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, exchangehashpart(t, &newt); /* and hash (in case of errors) */ } /* allocate new array */ - newarray = luaM_reallocvector(L, t->array, oldasize, newasize, ArrayCell); + newarray = resizearray(L, t, oldasize, newasize); if (l_unlikely(newarray == NULL && newasize > 0)) { /* allocation failed? */ freehash(L, &newt); /* release new hash part */ luaM_error(L); /* raise error (with array unchanged) */ @@ -626,7 +653,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize, t->array = newarray; /* set new array part */ t->alimit = newasize; for (i = oldasize; i < newasize; i++) /* clear new slice of the array */ - *getArrTag(t, i + 1) = LUA_VEMPTY; + *getArrTag(t, i) = LUA_VEMPTY; /* re-insert elements from old hash part into new parts */ reinsert(L, &newt, t); /* 'newt' now has the old hash */ freehash(L, &newt); /* free old hash part */ @@ -682,8 +709,9 @@ Table *luaH_new (lua_State *L) { void luaH_free (lua_State *L, Table *t) { + unsigned ps = concretesize(luaH_realasize(t)); freehash(L, t); - luaM_freearray(L, t->array, luaH_realasize(t)); + luaM_freearray(L, t->array, ps); luaM_free(L, t); } @@ -799,7 +827,7 @@ static int finishnodeget (const TValue *val, TValue *res) { int luaH_getint (Table *t, lua_Integer key, TValue *res) { if (keyinarray(t, key)) { - int tag = *getArrTag(t, key); + int tag = *getArrTag(t, key - 1); if (!tagisempty(tag)) { farr2val(t, key, tag, res); return HOK; /* success */ @@ -902,7 +930,7 @@ static int finishnodeset (Table *t, 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); + lu_byte *tag = getArrTag(t, key - 1); if (!tagisempty(*tag)) { fval2arr(t, key, tag, val); return HOK; /* success */ @@ -960,7 +988,7 @@ void luaH_finishset (lua_State *L, Table *t, const TValue *key, } else { /* array entry */ hres = ~hres; /* real index */ - fval2arr(t, hres, getArrTag(t, hres), value); + obj2arr(t, hres, value); } } diff --git a/ltable.h b/ltable.h index 371e721d..b401aba1 100644 --- a/ltable.h +++ b/ltable.h @@ -51,31 +51,68 @@ */ -struct ArrayCell { - lu_byte tt; +/* +** The array part of a table is represented by an array of cells. +** Each cell is composed of (NM + 1) elements, and each element has the +** type 'ArrayCell'. In each cell, only one element has the variant +** 'tag', while the other NM elements have the variant 'value'. The +** array in the 'tag' element holds the tags of the other elements in +** that cell. +*/ +#define NM ((unsigned int)sizeof(Value)) + +union ArrayCell { + unsigned char tag[NM]; Value value; }; -/* fast access to components of array values */ -#define getArrTag(t,k) (&(t)->array[k - 1].tt) -#define getArrVal(t,k) (&(t)->array[k - 1].value) +/* +** 'NMTag' defines which cell element has the tags; that could be any +** value between 0 (tags come before all values) and NM (tags come after +** all values). +*/ +#define NMTag 0 -#define tagisempty(tag) (novariant(tag) == LUA_TNIL) +/* +** Computes the concrete index that holds the tag of abstract index 'i' +*/ +#define TagIndex(i) (((i)/NM * (NM + 1u)) + NMTag) -#define farr2val(h,k,tag,res) \ - ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k)) +/* +** Computes the concrete index that holds the value of abstract index 'i' +*/ +#define ValueIndex(i) ((i) + (((i) + (NM - NMTag))/NM)) -#define fval2arr(h,k,tag,val) \ - (*tag = (val)->tt_, *getArrVal(h,k) = (val)->value_) +/* Computes the address of the tag for the abstract index 'k' */ +#define getArrTag(t,k) (&(t)->array[TagIndex(k)].tag[(k)%NM]) -#define obj2arr(h,k,val) \ - (*getArrTag(h,k) = (val)->tt_, *getArrVal(h,k) = (val)->value_) +/* Computes the address of the value for the abstract index 'k' */ +#define getArrVal(t,k) (&(t)->array[ValueIndex(k)].value) + +/* +** Move TValues to/from arrays, using Lua indices +*/ #define arr2obj(h,k,val) \ - ((val)->tt_ = *getArrTag(h,k), (val)->value_ = *getArrVal(h,k)) + ((val)->tt_ = *getArrTag(h,(k)-1u), (val)->value_ = *getArrVal(h,(k)-1u)) + +#define obj2arr(h,k,val) \ + (*getArrTag(h,(k)-1u) = (val)->tt_, *getArrVal(h,(k)-1u) = (val)->value_) + + +/* +** Often, we need to check the tag of a value before moving it. These +** macros also move TValues to/from arrays, but receive the precomputed +** tag value or address as an extra argument. +*/ +#define farr2val(h,k,tag,res) \ + ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,(k)-1u)) + +#define fval2arr(h,k,tag,val) \ + (*tag = (val)->tt_, *getArrVal(h,(k)-1u) = (val)->value_) LUAI_FUNC int luaH_getshortstr (Table *t, TString *key, TValue *res); diff --git a/lvm.h b/lvm.h index 32455fba..c74c81f8 100644 --- a/lvm.h +++ b/lvm.h @@ -90,7 +90,7 @@ typedef enum { if (!ttistable(t)) aux = HNOTATABLE; \ else { Table *h = hvalue(t); lua_Unsigned u = l_castS2U(k); \ if ((u - 1u < h->alimit)) { \ - int tag = *getArrTag(h,u); \ + int tag = *getArrTag(h,(u)-1u); \ if (tagisempty(tag)) aux = HNOTFOUND; \ else { farr2val(h, u, tag, res); aux = HOK; }} \ else { aux = luaH_getint(h, u, res); }} @@ -103,7 +103,7 @@ typedef enum { if (!ttistable(t)) aux = HNOTATABLE; \ else { Table *h = hvalue(t); lua_Unsigned u = l_castS2U(k); \ if ((u - 1u < h->alimit)) { \ - lu_byte *tag = getArrTag(h,u); \ + lu_byte *tag = getArrTag(h,(u)-1u); \ if (tagisempty(*tag)) aux = ~cast_int(u); \ else { fval2arr(h, u, tag, val); aux = HOK; }} \ else { aux = luaH_psetint(h, u, val); }} -- cgit v1.2.3-55-g6feb