From 351ccd733298e08c41937c1baf22a68e62bfeca9 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Mon, 15 May 2023 17:56:25 -0300 Subject: Towards a new implementation of arrays The array part of a table wastes too much space, due to padding. To avoid that, we need to store values in the array as something different from a TValue. Therefore, the API for table access should not assume that any value in a table lives in a *TValue. This commit is the first step to remove that assumption: functions luaH_get*, instead of returning a *TValue where the value lives, receive a *TValue where to put the value being accessed. (We still have to change the luaH_set* functions.) --- lapi.c | 32 ++++++++++++++----------------- ltable.c | 30 +++++++++++++++++++++++++++++ ltable.h | 21 ++++++++++++++++++++ lvm.c | 67 +++++++++++++++++++++++++++------------------------------------- lvm.h | 17 ++++++++++++++-- 5 files changed, 108 insertions(+), 59 deletions(-) diff --git a/lapi.c b/lapi.c index 34e64af1..2e27bc92 100644 --- a/lapi.c +++ b/lapi.c @@ -637,16 +637,16 @@ LUA_API int lua_pushthread (lua_State *L) { l_sinline int auxgetstr (lua_State *L, const TValue *t, const char *k) { - const TValue *slot; + int aux; TString *str = luaS_new(L, k); - if (luaV_fastget(L, t, str, slot, luaH_getstr)) { - setobj2s(L, L->top.p, slot); + luaV_fastget1(t, str, s2v(L->top.p), luaH_getstr1, aux); + if (aux == HOK) { api_incr_top(L); } else { setsvalue2s(L, L->top.p, str); api_incr_top(L); - luaV_finishget(L, t, s2v(L->top.p - 1), L->top.p - 1, slot); + luaV_finishget1(L, t, s2v(L->top.p - 1), L->top.p - 1, aux); } lua_unlock(L); return ttype(s2v(L->top.p - 1)); @@ -672,15 +672,13 @@ LUA_API int lua_getglobal (lua_State *L, const char *name) { LUA_API int lua_gettable (lua_State *L, int idx) { - const TValue *slot; + int aux; TValue *t; lua_lock(L); t = index2value(L, idx); - if (luaV_fastget(L, t, s2v(L->top.p - 1), slot, luaH_get)) { - setobj2s(L, L->top.p - 1, slot); - } - else - luaV_finishget(L, t, s2v(L->top.p - 1), L->top.p - 1, slot); + luaV_fastget1(t, s2v(L->top.p - 1), s2v(L->top.p - 1), luaH_get1, aux); + if (aux != HOK) + luaV_finishget1(L, t, s2v(L->top.p - 1), L->top.p - 1, aux); lua_unlock(L); return ttype(s2v(L->top.p - 1)); } @@ -694,16 +692,14 @@ LUA_API int lua_getfield (lua_State *L, int idx, const char *k) { LUA_API int lua_geti (lua_State *L, int idx, lua_Integer n) { TValue *t; - const TValue *slot; + int aux; lua_lock(L); t = index2value(L, idx); - if (luaV_fastgeti(L, t, n, slot)) { - setobj2s(L, L->top.p, slot); - } - else { - TValue aux; - setivalue(&aux, n); - luaV_finishget(L, t, &aux, L->top.p, slot); + luaV_fastgeti1(t, n, s2v(L->top.p), aux); + if (aux != HOK) { + TValue key; + setivalue(&key, n); + luaV_finishget1(L, t, &key, L->top.p, aux); } api_incr_top(L); lua_unlock(L); diff --git a/ltable.c b/ltable.c index 3c690c5f..8fd83fda 100644 --- a/ltable.c +++ b/ltable.c @@ -752,6 +752,21 @@ const TValue *luaH_getint (Table *t, lua_Integer key) { } +static int finishnodeget (const TValue *val, TValue *res) { + if (!ttisnil(val)) { + setobj(((lua_State*)NULL), res, val); + return HOK; /* success */ + } + else + return HNOTFOUND; /* could not get value */ +} + + +int luaH_getint1 (Table *t, lua_Integer key, TValue *res) { + return finishnodeget(luaH_getint(t, key), res); +} + + /* ** search function for short strings */ @@ -771,6 +786,11 @@ const TValue *luaH_getshortstr (Table *t, TString *key) { } +int luaH_getshortstr1 (Table *t, TString *key, TValue *res) { + return finishnodeget(luaH_getshortstr(t, key), res); +} + + const TValue *luaH_getstr (Table *t, TString *key) { if (key->tt == LUA_VSHRSTR) return luaH_getshortstr(t, key); @@ -782,6 +802,11 @@ const TValue *luaH_getstr (Table *t, TString *key) { } +int luaH_getstr1 (Table *t, TString *key, TValue *res) { + return finishnodeget(luaH_getstr(t, key), res); +} + + /* ** main search function */ @@ -802,6 +827,11 @@ const TValue *luaH_get (Table *t, const TValue *key) { } +int luaH_get1 (Table *t, const TValue *key, TValue *res) { + return finishnodeget(luaH_get(t, key), res); +} + + /* ** Finish a raw "set table" operation, where 'slot' is where the value ** should have been (the result of a previous "get table"). diff --git a/ltable.h b/ltable.h index 75dd9e26..c8a8c5e7 100644 --- a/ltable.h +++ b/ltable.h @@ -35,6 +35,27 @@ #define nodefromval(v) cast(Node *, (v)) +/* results from get/set */ +#define HOK 0 +#define HNOTFOUND 1 +#define HNOTATABLE 2 + + +/* 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_) + +#define tagisempty(tag) (novariant(tag) == LUA_TNIL) + +#define arr2val(h,k,tag,res) \ + ((res)->tt_ = tag, (res)->value_ = *getArrVal(h,k)) + + +LUAI_FUNC int luaH_getshortstr1 (Table *t, TString *key, TValue *res); +LUAI_FUNC int luaH_getstr1 (Table *t, TString *key, TValue *res); +LUAI_FUNC int luaH_get1 (Table *t, const TValue *key, TValue *res); +LUAI_FUNC int luaH_getint1 (Table *t, lua_Integer key, TValue *res); + LUAI_FUNC const TValue *luaH_getint (Table *t, lua_Integer key); LUAI_FUNC void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value); diff --git a/lvm.c b/lvm.c index 8493a770..ee386847 100644 --- a/lvm.c +++ b/lvm.c @@ -284,12 +284,12 @@ static int floatforloop (StkId ra) { ** if 'slot' is NULL, 't' is not a table; otherwise, 'slot' points to ** t[k] entry (which must be empty). */ -void luaV_finishget (lua_State *L, const TValue *t, TValue *key, StkId val, - const TValue *slot) { +void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, StkId val, + int aux) { int loop; /* counter to avoid infinite loops */ const TValue *tm; /* metamethod */ for (loop = 0; loop < MAXTAGLOOP; loop++) { - if (slot == NULL) { /* 't' is not a table? */ + if (aux == HNOTATABLE) { /* 't' is not a table? */ lua_assert(!ttistable(t)); tm = luaT_gettmbyobj(L, t, TM_INDEX); if (l_unlikely(notm(tm))) @@ -297,7 +297,6 @@ void luaV_finishget (lua_State *L, const TValue *t, TValue *key, StkId val, /* else will try the metamethod */ } else { /* 't' is a table */ - lua_assert(isempty(slot)); tm = fasttm(L, hvalue(t)->metatable, TM_INDEX); /* table's metamethod */ if (tm == NULL) { /* no metamethod? */ setnilvalue(s2v(val)); /* result is nil */ @@ -310,10 +309,9 @@ void luaV_finishget (lua_State *L, const TValue *t, TValue *key, StkId val, return; } t = tm; /* else try to access 'tm[key]' */ - if (luaV_fastget(L, t, key, slot, luaH_get)) { /* fast track? */ - setobj2s(L, val, slot); /* done */ - return; - } + luaV_fastget1(t, key, s2v(val), luaH_get1, aux); + if (aux == HOK) + return; /* done */ /* else repeat (tail call 'luaV_finishget') */ } luaG_runerror(L, "'__index' chain too long; possible loop"); @@ -1250,58 +1248,51 @@ void luaV_execute (lua_State *L, CallInfo *ci) { } vmcase(OP_GETTABUP) { StkId ra = RA(i); - const TValue *slot; TValue *upval = cl->upvals[GETARG_B(i)]->v.p; TValue *rc = KC(i); TString *key = tsvalue(rc); /* key must be a string */ - if (luaV_fastget(L, upval, key, slot, luaH_getshortstr)) { - setobj2s(L, ra, slot); - } - else - Protect(luaV_finishget(L, upval, rc, ra, slot)); + int aux; + luaV_fastget1(upval, key, s2v(ra), luaH_getshortstr1, aux); + if (aux != HOK) + Protect(luaV_finishget1(L, upval, rc, ra, aux)); vmbreak; } vmcase(OP_GETTABLE) { StkId ra = RA(i); - const TValue *slot; TValue *rb = vRB(i); TValue *rc = vRC(i); - lua_Unsigned n; - if (ttisinteger(rc) /* fast track for integers? */ - ? (cast_void(n = ivalue(rc)), luaV_fastgeti(L, rb, n, slot)) - : luaV_fastget(L, rb, rc, slot, luaH_get)) { - setobj2s(L, ra, slot); + int aux; + if (ttisinteger(rc)) { /* fast track for integers? */ + luaV_fastgeti1(rb, ivalue(rc), s2v(ra), aux); } else - Protect(luaV_finishget(L, rb, rc, ra, slot)); + luaV_fastget1(rb, rc, s2v(ra), luaH_get1, aux); + if (aux != HOK) /* fast track for integers? */ + Protect(luaV_finishget1(L, rb, rc, ra, aux)); vmbreak; } vmcase(OP_GETI) { StkId ra = RA(i); - const TValue *slot; TValue *rb = vRB(i); int c = GETARG_C(i); - if (luaV_fastgeti(L, rb, c, slot)) { - setobj2s(L, ra, slot); - } - else { + int aux; + luaV_fastgeti1(rb, c, s2v(ra), aux); + if (aux != HOK) { TValue key; setivalue(&key, c); - Protect(luaV_finishget(L, rb, &key, ra, slot)); + Protect(luaV_finishget1(L, rb, &key, ra, aux)); } vmbreak; } vmcase(OP_GETFIELD) { StkId ra = RA(i); - const TValue *slot; TValue *rb = vRB(i); TValue *rc = KC(i); TString *key = tsvalue(rc); /* key must be a string */ - if (luaV_fastget(L, rb, key, slot, luaH_getshortstr)) { - setobj2s(L, ra, slot); - } - else - Protect(luaV_finishget(L, rb, rc, ra, slot)); + int aux; + luaV_fastget1(rb, key, s2v(ra), luaH_getshortstr1, aux); + if (aux != HOK) + Protect(luaV_finishget1(L, rb, rc, ra, aux)); vmbreak; } vmcase(OP_SETTABUP) { @@ -1381,16 +1372,14 @@ void luaV_execute (lua_State *L, CallInfo *ci) { } vmcase(OP_SELF) { StkId ra = RA(i); - const TValue *slot; + int aux; TValue *rb = vRB(i); TValue *rc = RKC(i); TString *key = tsvalue(rc); /* key must be a string */ setobj2s(L, ra + 1, rb); - if (luaV_fastget(L, rb, key, slot, luaH_getstr)) { - setobj2s(L, ra, slot); - } - else - Protect(luaV_finishget(L, rb, rc, ra, slot)); + luaV_fastget1(rb, key, s2v(ra), luaH_getstr1, aux); + if (aux != HOK) + Protect(luaV_finishget1(L, rb, rc, ra, aux)); vmbreak; } vmcase(OP_ADDI) { diff --git a/lvm.h b/lvm.h index dba1ad27..704446c2 100644 --- a/lvm.h +++ b/lvm.h @@ -89,6 +89,10 @@ typedef enum { !isempty(slot))) /* result not empty? */ +#define luaV_fastget1(t,k,res,f, aux) \ + (aux = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, res))) + + /* ** Special case of 'luaV_fastget' for integers, inlining the fast case ** of 'luaH_getint'. @@ -100,6 +104,15 @@ typedef enum { ? &hvalue(t)->array[k - 1] : luaH_getint(hvalue(t), k), \ !isempty(slot))) /* result not empty? */ +#define luaV_fastgeti1(t,k,val,aux) \ + 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); \ + if (tagisempty(tag)) aux = HNOTFOUND; \ + else { arr2val(h, u, tag, val); aux = HOK; }} \ + else { aux = luaH_getint1(h, u, val); }} + /* ** Finish a fast set operation (when fast get succeeds). In that case, @@ -125,8 +138,8 @@ LUAI_FUNC int luaV_tointeger (const TValue *obj, lua_Integer *p, F2Imod mode); LUAI_FUNC int luaV_tointegerns (const TValue *obj, lua_Integer *p, F2Imod mode); LUAI_FUNC int luaV_flttointeger (lua_Number n, lua_Integer *p, F2Imod mode); -LUAI_FUNC void luaV_finishget (lua_State *L, const TValue *t, TValue *key, - StkId val, const TValue *slot); +LUAI_FUNC void luaV_finishget1 (lua_State *L, const TValue *t, TValue *key, + StkId val, int aux); LUAI_FUNC void luaV_finishset (lua_State *L, const TValue *t, TValue *key, TValue *val, const TValue *slot); LUAI_FUNC void luaV_finishOp (lua_State *L); -- cgit v1.2.3-55-g6feb