commit 351ccd733298e08c41937c1baf22a68e62bfeca9
parent 6443185167c77adcc8552a3fee7edab7895db1a9
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Mon, 15 May 2023 17:55:58 -0300
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.)
Diffstat:
| M | lapi.c | | | 32 | ++++++++++++++------------------ |
| M | ltable.c | | | 30 | ++++++++++++++++++++++++++++++ |
| M | ltable.h | | | 21 | +++++++++++++++++++++ |
| M | lvm.c | | | 67 | ++++++++++++++++++++++++++++--------------------------------------- |
| M | lvm.h | | | 17 | +++++++++++++++-- |
5 files changed, 108 insertions(+), 59 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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);
