lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Thu, Oct 18, 2018 at 9:42 AM Dirk Laurie <dirk.laurie@gmail.com> wrote:
>
> An array subtype would solve that problem.
>
> 1. Own __len, implicit in the subtype, if you set your own __len it is
> no longer an array.
> 2. ipairs iterates from 1 to __len, table functions use __len.
> 3. Value returned by __len is fixed when the table is created and
> can't be changed by assignment, only by functions in the table library
> (insert, remove, setlen).
>

Some questions.

- Are you trying to address the problems stated in
http://lua-users.org/lists/lua-l/2018-03/msg00239.html with this
proposal? If yes, can you clarify the  mechanim to solve them?

- Why do you use the "Array subtype" semantic? It seems to me that
your proposal can be applied to ANY table, like a sort of "Protected
.n field". [1]

- At my understanding, your proposal implies that
`atable[1+getlen(atable)] = [[new content]]`, does not allow to
iterate over the 'new contents' in subsequent loops (with iparis or
__len). Is this right?

Note:

[1] I attach a thoughtless-patch that does something similar:
- A length is kept in a new field of the table struct (intialized to 0)
- Len-operator/opcode return it
- The length is updated every time something is written in a positive
integer key (nil also). The maximum index of all the writings is
stored.
- ipairs loops from 1 to this length, also if there are holes
- The table.setlen function can be used to set the value of the new
field. It does not change anything else.
The execution time increases  by ~3% (when updating the len) while the
memory size increases by ~7% (when storing empty tables). I think both
can be improved with more conscientious changes.

Left base folder: C:\WIP\tmp\lua-5.4.0-work2
Right base folder: C:\WIP\tmp\lua-5.4.0-work2-PATCH
--- src\lapi.c 2018-10-23 16:39:34.000000000 +0200
+++ src\lapi.c 2018-10-23 16:39:37.000000000 +0200
@@ -390,13 +390,13 @@
 LUA_API lua_Unsigned lua_rawlen (lua_State *L, int idx) {
   const TValue *o = index2value(L, idx);
   switch (ttypetag(o)) {
     case LUA_TSHRSTR: return tsvalue(o)->shrlen;
     case LUA_TLNGSTR: return tsvalue(o)->u.lnglen;
     case LUA_TUSERDATA: return uvalue(o)->len;
-    case LUA_TTABLE: return luaH_getn(hvalue(o));
+    case LUA_TTABLE: return hvalue(o)->LENPATCH;
     default: return 0;
   }
 }


 LUA_API lua_CFunction lua_tocfunction (lua_State *L, int idx) {
@@ -831,20 +831,20 @@
 LUA_API void lua_rawset (lua_State *L, int idx) {
   Table *t;
   TValue *slot;
   lua_lock(L);
   api_checknelems(L, 2);
   t = gettable(L, idx);
+  if (ttisinteger(s2v(L->top - 2))) LENPATCH_UPDATE(t,
ivalue(s2v(L->top - 2)));
   slot = luaH_set(L, t, s2v(L->top - 2));
   setobj2t(L, slot, s2v(L->top - 1));
   invalidateTMcache(t);
   luaC_barrierback(L, obj2gco(t), s2v(L->top - 1));
   L->top -= 2;
   lua_unlock(L);
 }
-

 LUA_API void lua_rawseti (lua_State *L, int idx, lua_Integer n) {
   Table *t;
   lua_lock(L);
   api_checknelems(L, 1);
   t = gettable(L, idx);
--- src\lbaselib.c 2018-10-23 16:39:34.000000000 +0200
+++ src\lbaselib.c 2018-10-23 16:39:37.000000000 +0200
@@ -260,20 +260,22 @@
     lua_pushvalue(L, 1);  /* argument 'self' to metamethod */
     lua_call(L, 1, 3);  /* get 3 values from metamethod */
   }
   return 3;
 }

+#include "lstate.h"

 /*
 ** Traversal function for 'ipairs'
 */
 static int ipairsaux (lua_State *L) {
   lua_Integer i = luaL_checkinteger(L, 2) + 1;
   lua_pushinteger(L, i);
-  return (lua_geti(L, 1, i) == LUA_TNIL) ? 1 : 2;
+  lua_geti(L, 1, i);
+  return (i > hvalue(s2v(L->ci->func + 1))->LENPATCH ? 1 : 2 );
 }


 /*
 ** 'ipairs' function. Returns 'ipairsaux', given "table", 0.
 ** (The given "table" may not be a table.)
--- src\lobject.h 2018-10-23 16:39:34.000000000 +0200
+++ src\lobject.h 2018-10-23 16:39:37.000000000 +0200
@@ -686,12 +686,13 @@
   unsigned int alimit;  /* "limit" of 'array' array */
   TValue *array;  /* array part */
   Node *node;
   Node *lastfree;  /* any free position is before this position */
   struct Table *metatable;
   GCObject *gclist;
+  unsigned int LENPATCH;
 } Table;


 /*
 ** Macros to manipulate keys inserted in nodes
 */
--- src\ltable.c 2018-10-23 16:39:34.000000000 +0200
+++ src\ltable.c 2018-10-23 16:39:37.000000000 +0200
@@ -580,12 +580,13 @@
   GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
   Table *t = gco2t(o);
   t->metatable = NULL;
   t->flags = cast_byte(~0);
   t->array = NULL;
   t->alimit = 0;
+  t->LENPATCH = 0;
   setnodevector(L, t, 0);
   return t;
 }


 void luaH_free (lua_State *L, Table *t) {
--- src\ltable.h 2018-10-23 16:39:34.000000000 +0200
+++ src\ltable.h 2018-10-23 16:39:37.000000000 +0200
@@ -50,8 +50,9 @@

 #if defined(LUA_DEBUG)
 LUAI_FUNC Node *luaH_mainposition (const Table *t, const TValue *key);
 LUAI_FUNC int luaH_isdummy (const Table *t);
 #endif

+#define LENPATCH_UPDATE(v,k) (v->LENPATCH < k ? v->LENPATCH = k : 0)

 #endif
--- src\ltablib.c 2018-10-23 16:39:34.000000000 +0200
+++ src\ltablib.c 2018-10-23 16:39:37.000000000 +0200
@@ -399,26 +399,38 @@
     lua_settop(L, 2);  /* make sure there are two arguments */
     auxsort(L, 1, (IdxT)n, 0);
   }
   return 0;
 }

+#include "lstate.h"
+
+static int setlen (lua_State *L) {
+  if (!ttistable(s2v(L->ci->func + 1)))
+    return luaL_error(L, "argument #1 must be a table");
+  lua_Integer i = luaL_checkinteger(L, 2);
+  lua_pushinteger(L, i);
+  hvalue(s2v(L->ci->func + 1))->LENPATCH = i;
+  return 0;
+}
+
 /* }====================================================== */


 static const luaL_Reg tab_funcs[] = {
   {"concat", tconcat},
   {"insert", tinsert},
   {"pack", tpack},
   {"unpack", tunpack},
   {"remove", tremove},
   {"move", tmove},
   {"sort", sort},
+  {"setlen", setlen},
   {NULL, NULL}
 };


 LUAMOD_API int luaopen_table (lua_State *L) {
   luaL_newlib(L, tab_funcs);
   return 1;
 }

--- src\lvm.c 2018-10-23 16:39:34.000000000 +0200
+++ src\lvm.c 2018-10-23 16:39:37.000000000 +0200
@@ -589,13 +589,13 @@
   const TValue *tm;
   switch (ttypetag(rb)) {
     case LUA_TTABLE: {
       Table *h = hvalue(rb);
       tm = fasttm(L, h->metatable, TM_LEN);
       if (tm) break;  /* metamethod? break switch to call it */
-      setivalue(s2v(ra), luaH_getn(h));  /* else primitive len */
+      setivalue(s2v(ra), h->LENPATCH);  /* else primitive len */
       return;
     }
     case LUA_TSHRSTR: {
       setivalue(s2v(ra), tsvalue(rb)->shrlen);
       return;
     }
@@ -876,13 +876,12 @@
 }

 #define vmdispatch(o) switch(o)
 #define vmcase(l) case l:
 #define vmbreak break

-
 void luaV_execute (lua_State *L, CallInfo *ci) {
   LClosure *cl;
   TValue *k;
   StkId base;
   const Instruction *pc;
   int trap;
@@ -1034,12 +1033,13 @@
             ? (n = ivalue(rb), luaV_fastgeti(L, s2v(ra), n, slot))
             : luaV_fastget(L, s2v(ra), rb, slot, luaH_get)) {
           luaV_finishfastset(L, s2v(ra), slot, rc);
         }
         else
           Protect(luaV_finishset(L, s2v(ra), rb, rc, slot));
+        if (ttisinteger(rb)) LENPATCH_UPDATE(hvalue(s2v(ra)), ivalue(rb));
         vmbreak;
       }
       vmcase(OP_SETI) {
         const TValue *slot;
         int c = GETARG_B(i);
         TValue *rc = RKC(i);
@@ -1048,12 +1048,13 @@
         }
         else {
           TValue key;
           setivalue(&key, c);
           Protect(luaV_finishset(L, s2v(ra), &key, rc, slot));
         }
+        LENPATCH_UPDATE(hvalue(s2v(ra)), c);
         vmbreak;
       }
       vmcase(OP_SETFIELD) {
         const TValue *slot;
         TValue *rb = KB(i);
         TValue *rc = RKC(i);
@@ -1770,12 +1771,13 @@
           luaH_resizearray(L, h, last);  /* preallocate it at once */
         for (; n > 0; n--) {
           TValue *val = s2v(ra + n);
           setobj2t(L, &h->array[last - 1], val);
           last--;
+          LENPATCH_UPDATE(h, h->LENPATCH + 1);
           luaC_barrierback(L, obj2gco(h), val);
         }
         vmbreak;
       }
       vmcase(OP_CLOSURE) {
         Proto *p = cl->p->p[GETARG_Bx(i)];
         LClosure *ncl = getcached(p, cl->upvals, base);  /* cached closure */