From d862da6d04111ce7e5b225040fbe7e526761f478 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Fri, 12 Jan 2024 15:50:51 -0300 Subject: Optimizations for 'lua_rawgeti' and 'lua_rawseti' 'lua_rawgeti' now uses "fast track"; 'lua_rawseti' still calls 'luaH_setint', but the latter was recoded to avoid extra overhead when writing to the array part after 'alimit'. --- lapi.c | 19 +++++++++++-------- ltable.c | 55 +++++++++++++++++++++++++++++++++++++------------------ ltable.h | 19 +++++++++++++++++++ lvm.h | 36 +++++++++++++----------------------- 4 files changed, 80 insertions(+), 49 deletions(-) diff --git a/lapi.c b/lapi.c index d18445e0..74f1d66b 100644 --- a/lapi.c +++ b/lapi.c @@ -102,7 +102,7 @@ static TValue *index2value (lua_State *L, int idx) { /* ** Convert a valid actual index (not a pseudo-index) to its address. */ -l_sinline StkId index2stack (lua_State *L, int idx) { +static StkId index2stack (lua_State *L, int idx) { CallInfo *ci = L->ci; if (idx > 0) { StkId o = ci->func.p + idx; @@ -234,7 +234,7 @@ LUA_API void lua_closeslot (lua_State *L, int idx) { ** Note that we move(copy) only the value inside the stack. ** (We do not move additional fields that may exist.) */ -l_sinline void reverse (lua_State *L, StkId from, StkId to) { +static void reverse (lua_State *L, StkId from, StkId to) { for (; from < to; from++, to--) { TValue temp; setobj(L, &temp, s2v(from)); @@ -664,7 +664,7 @@ LUA_API int lua_pushthread (lua_State *L) { */ -l_sinline int auxgetstr (lua_State *L, const TValue *t, const char *k) { +static int auxgetstr (lua_State *L, const TValue *t, const char *k) { int hres; TString *str = luaS_new(L, k); luaV_fastget(t, str, s2v(L->top.p), luaH_getstr, hres); @@ -683,7 +683,9 @@ l_sinline int auxgetstr (lua_State *L, const TValue *t, const char *k) { static void getGlobalTable (lua_State *L, TValue *gt) { Table *registry = hvalue(&G(L)->l_registry); - luaH_getint(registry, LUA_RIDX_GLOBALS, gt); + int hres = luaH_getint(registry, LUA_RIDX_GLOBALS, gt); + (void)hres; /* avoid warnings (not used) when checks are off */ + api_check(L, hres == HOK, "global table must exist"); } @@ -740,7 +742,7 @@ l_sinline int finishrawget (lua_State *L, int hres) { } -static Table *gettable (lua_State *L, int idx) { +l_sinline Table *gettable (lua_State *L, int idx) { TValue *t = index2value(L, idx); api_check(L, ttistable(t), "table expected"); return hvalue(t); @@ -761,9 +763,11 @@ LUA_API int lua_rawget (lua_State *L, int idx) { LUA_API int lua_rawgeti (lua_State *L, int idx, lua_Integer n) { Table *t; + int hres; lua_lock(L); t = gettable(L, idx); - return finishrawget(L, luaH_getint(t, n, s2v(L->top.p))); + luaH_fastgeti(t, n, s2v(L->top.p), hres); + return finishrawget(L, hres); } @@ -901,9 +905,8 @@ LUA_API void lua_seti (lua_State *L, int idx, lua_Integer n) { api_checknelems(L, 1); t = index2value(L, idx); luaV_fastseti(t, n, s2v(L->top.p - 1), hres); - if (hres == HOK) { + if (hres == HOK) luaV_finishfastset(L, t, s2v(L->top.p - 1)); - } else { TValue temp; setivalue(&temp, n); diff --git a/ltable.c b/ltable.c index d3e90696..21a54f81 100644 --- a/ltable.c +++ b/ltable.c @@ -408,21 +408,22 @@ static void freehash (lua_State *L, Table *t) { ** not the real size of the array, the key still can be in the array ** part. In this case, do the "Xmilia trick" to check whether 'key-1' ** is smaller than the real size. -** The trick works as follow: let 'p' be an integer such that -** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. -** That is, 2^(p+1) is the real size of the array, and 'p' is the highest -** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'. -** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will -** have the 'p' bit cleared. If the key is outside the array, that is, -** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p', -** therefore it will be larger or equal to 'alimit', and the check +** The trick works as follow: let 'p' be the integer such that +** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. That is, +** 'p' is the highest 1-bit in 'alimit-1', and 2^(p+1) is the real size +** of the array. What we have to check becomes 'key-1 < 2^(p+1)'. We +** compute '(key-1) & ~(alimit-1)', which we call 'res'; it will have +** the 'p' bit cleared. (It may also clear other bits smaller than 'p', +** but no bit higher than 'p'.) If the key is outside the array, that +** is, 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than +** 'p', therefore it will be larger or equal to 'alimit', and the check ** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than ** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller ** than 2^p, therefore smaller than 'alimit', and the check succeeds. ** As special cases, when 'alimit' is 0 the condition is trivially false, ** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'. ** If key is 0 or negative, 'res' will have its higher bit on, so that -** if cannot be smaller than alimit. +** it cannot be smaller than 'alimit'. */ static int keyinarray (Table *t, lua_Integer key) { lua_Unsigned alimit = t->alimit; @@ -788,11 +789,11 @@ static Node *getfreepos (Table *t) { /* -** inserts a new key into a hash table; first, check whether key's main +** Inserts a new key into a hash table; first, check whether key's main ** position is free. If not, check whether colliding node is in its main -** position or not: if it is not, move colliding node to an empty place and -** put new key in its main position; otherwise (colliding node is in its main -** position), new key goes to an empty position. +** position or not: if it is not, move colliding node to an empty place +** and put new key in its main position; otherwise (colliding node is in +** its main position), new key goes to an empty position. */ static void luaH_newkey (lua_State *L, Table *t, const TValue *key, TValue *value) { @@ -987,6 +988,16 @@ static int finishnodeset (Table *t, const TValue *slot, TValue *val) { } +static int rawfinishnodeset (const TValue *slot, TValue *val) { + if (isabstkey(slot)) + return 0; /* no slot with that key */ + else { + setobj(((lua_State*)NULL), cast(TValue*, slot), val); + return 1; /* success */ + } +} + + int luaH_psetint (Table *t, lua_Integer key, TValue *val) { if (keyinarray(t, key)) { lu_byte *tag = getArrTag(t, key - 1); @@ -1063,12 +1074,20 @@ void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { } +/* +** Ditto for a GC barrier. (No need to invalidate the TM cache, as +** integers cannot be keys to metamethods.) +*/ void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { - int hres = luaH_psetint(t, key, value); - if (hres != HOK) { - TValue k; - setivalue(&k, key); - luaH_finishset(L, t, &k, value, hres); + if (keyinarray(t, key)) + obj2arr(t, key, value); + else { + int ok = rawfinishnodeset(getintfromhash(t, key), value); + if (!ok) { + TValue k; + setivalue(&k, key); + luaH_newkey(L, t, &k, value); + } } } diff --git a/ltable.h b/ltable.h index 5581efb1..8b0340b5 100644 --- a/ltable.h +++ b/ltable.h @@ -45,6 +45,25 @@ #define nodefromval(v) cast(Node *, (v)) + +#define luaH_fastgeti(t,k,res,hres) \ + { Table *h = t; lua_Unsigned u = l_castS2U(k); \ + if ((u - 1u < h->alimit)) { \ + int tag = *getArrTag(h,(u)-1u); \ + if (tagisempty(tag)) hres = HNOTFOUND; \ + else { farr2val(h, u, tag, res); hres = HOK; }} \ + else { hres = luaH_getint(h, u, res); }} + + +#define luaH_fastseti(t,k,val,hres) \ + { Table *h = t; lua_Unsigned u = l_castS2U(k); \ + if ((u - 1u < h->alimit)) { \ + lu_byte *tag = getArrTag(h,(u)-1u); \ + if (tagisempty(*tag)) hres = ~cast_int(u); \ + else { fval2arr(h, u, tag, val); hres = HOK; }} \ + else { hres = luaH_psetint(h, u, val); }} + + /* results from get/pset */ #define HOK 0 #define HNOTFOUND 1 diff --git a/lvm.h b/lvm.h index c74c81f8..54ee5dd7 100644 --- a/lvm.h +++ b/lvm.h @@ -78,35 +78,25 @@ typedef enum { /* ** fast track for 'gettable' */ -#define luaV_fastget(t,k,res,f, aux) \ - (aux = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, res))) +#define luaV_fastget(t,k,res,f, hres) \ + (hres = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, res))) /* ** Special case of 'luaV_fastget' for integers, inlining the fast case ** of 'luaH_getint'. */ -#define luaV_fastgeti(t,k,res,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)-1u); \ - if (tagisempty(tag)) aux = HNOTFOUND; \ - else { farr2val(h, u, tag, res); aux = HOK; }} \ - else { aux = luaH_getint(h, u, res); }} - - -#define luaV_fastset(t,k,val,aux,f) \ - (aux = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, val))) - -#define luaV_fastseti(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)) { \ - 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); }} +#define luaV_fastgeti(t,k,res,hres) \ + if (!ttistable(t)) hres = HNOTATABLE; \ + else { luaH_fastgeti(hvalue(t), k, res, hres); } + + +#define luaV_fastset(t,k,val,hres,f) \ + (hres = (!ttistable(t) ? HNOTATABLE : f(hvalue(t), k, val))) + +#define luaV_fastseti(t,k,val,hres) \ + if (!ttistable(t)) hres = HNOTATABLE; \ + else { luaH_fastseti(hvalue(t), k, val, hres); } /* -- cgit v1.2.3-55-g6feb