From 5edacafcfa36a1fa86a7b5316bacf8c6a2c47227 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 5 Apr 2024 15:35:11 -0300 Subject: Yet another representation for arrays This "linear" representation (see ltable.h for details) has worse locality than cells, but the simpler access code seems to compensate that. --- ltable.h | 37 ++++++++++++++++++++----------------- 1 file changed, 20 insertions(+), 17 deletions(-) (limited to 'ltable.h') diff --git a/ltable.h b/ltable.h index 4734bd50..6db197ba 100644 --- a/ltable.h +++ b/ltable.h @@ -71,7 +71,7 @@ /* ** 'luaH_get*' operations set 'res', unless the value is absent, and -** return the tag of the result, +** return the tag of the result. ** The 'luaH_pset*' (pre-set) operations set the given value and return ** HOK, unless the original value is absent. In that case, if the key ** is really absent, they return HNOTFOUND. Otherwise, if there is a @@ -86,24 +86,27 @@ /* -** The array part of a table is represented by an array of cells. -** Each cell is composed of NM tags followed by NM values, so that -** no space is wasted in padding. The last cell may be incomplete, -** that is, it may have fewer than NM values. +** 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. + + Values Tags + -------------------------------------------------------- + ... | Value 1 | Value 0 |0|1|... + -------------------------------------------------------- + ^ t->array + +** All accesses to 't->array' should be through the macros 'getArrTag' +** and 'getArrVal'. */ -#define NM cast_uint(sizeof(Value)) - -struct ArrayCell { - lu_byte tag[NM]; - Value value[NM]; -}; - /* Computes the address of the tag for the abstract index 'k' */ -#define getArrTag(t,k) (&(t)->array[(k)/NM].tag[(k)%NM]) +#define getArrTag(t,k) (cast(lu_byte*, (t)->array) + (k)) /* Computes the address of the value for the abstract index 'k' */ -#define getArrVal(t,k) (&(t)->array[(k)/NM].value[(k)%NM]) +#define getArrVal(t,k) ((t)->array - 1 - (k)) /* @@ -117,9 +120,9 @@ struct ArrayCell { /* -** 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. +** Often, we need to check the tag of a value before moving it. The +** following 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)) -- cgit v1.2.3-55-g6feb