commit 3823fc6c814d20f2b2a0a1e3be8782084440040f
parent 52aa2b5d24c560fb4d7a642971571ff9cbeabfcd
Author: Roberto Ierusalimschy <roberto@inf.puc-rio.br>
Date: Fri, 15 Mar 2024 11:01:07 -0300
Added "bulk operations" to arrays
A few operations on arrays can be performed "in bulk", treating all
tags of a cell as a simple (or a few) word(s).
Diffstat:
| M | lgc.c | | | 59 | ++++++++++++++++++++++++++++++++++++++++++----------------- |
| M | ltable.c | | | 57 | ++++++++++++++++++++++++++++++++++++++++++--------------- |
| M | ltable.h | | | 18 | +++++++++++++++--- |
3 files changed, 99 insertions(+), 35 deletions(-)
diff --git a/lgc.c b/lgc.c
@@ -465,6 +465,46 @@ static void traverseweakvalue (global_State *g, Table *h) {
}
+#define BK2(x) cast(lua_Unsigned, ((x) << 8) | BIT_ISCOLLECTABLE)
+/*
+** Check whether some value in the cell starting at index 'i'
+** is collectable
+*/
+static int checkBulkCollectable (Table *h, unsigned i) {
+ const lua_Unsigned bitscoll = BK2(BK2(BK2(BK2(BK2(BK2(BK2(BK2(~0u))))))));
+ int j;
+ i /= NM;
+ for (j = 0; j < BKSZ; j++) {
+ if (h->array[i].u.bulk[j] & bitscoll)
+ return 1;
+ }
+ return 0;
+}
+
+
+/*
+** Traverse the array part of a table. The traversal is made by cells,
+** only traversing a cell if it has some collectable tag among its tags.
+*/
+static int traversearray (global_State *g, Table *h) {
+ unsigned asize = luaH_realasize(h);
+ int marked = 0; /* true if some object is marked in this traversal */
+ unsigned i;
+ for (i = 0; i < asize; i += NM) { /* traverse array in cells */
+ if (checkBulkCollectable(h, i)) { /* something to mark in this cell? */
+ unsigned j;
+ for (j = 0; j < NM && i + j < asize; j++) {
+ GCObject *o = gcvalarr(h, i + j);
+ if (o != NULL && iswhite(o)) {
+ marked = 1;
+ reallymarkobject(g, o);
+ }
+ }
+ }
+ }
+ return marked;
+}
+
/*
** Traverse an ephemeron table and link it to proper list. Returns true
** iff any object was marked during this traversal (which implies that
@@ -478,20 +518,11 @@ static void traverseweakvalue (global_State *g, Table *h) {
** by 'genlink'.
*/
static int traverseephemeron (global_State *g, Table *h, int inv) {
- int marked = 0; /* true if an object is marked in this traversal */
int hasclears = 0; /* true if table has white keys */
int hasww = 0; /* true if table has entry "white-key -> white-value" */
unsigned int i;
- unsigned int asize = luaH_realasize(h);
unsigned int nsize = sizenode(h);
- /* traverse array part */
- for (i = 0; i < asize; i++) {
- GCObject *o = gcvalarr(h, i);
- if (o != NULL && iswhite(o)) {
- marked = 1;
- reallymarkobject(g, o);
- }
- }
+ int marked = traversearray(g, h); /* traverse array part */
/* traverse hash part; if 'inv', traverse descending
(see 'convergeephemerons') */
for (i = 0; i < nsize; i++) {
@@ -523,13 +554,7 @@ static int traverseephemeron (global_State *g, Table *h, int inv) {
static void traversestrongtable (global_State *g, Table *h) {
Node *n, *limit = gnodelast(h);
- unsigned int i;
- unsigned int asize = luaH_realasize(h);
- for (i = 0; i < asize; i++) { /* traverse array part */
- GCObject *o = gcvalarr(h, i);
- if (o != NULL && iswhite(o))
- reallymarkobject(g, o);
- }
+ traversearray(g, h);
for (n = gnode(h, 0); n < limit; n++) { /* traverse hash part */
if (isempty(gval(n))) /* entry is empty? */
clearkey(n); /* clear its key */
diff --git a/ltable.c b/ltable.c
@@ -654,6 +654,44 @@ static void exchangehashpart (Table *t1, Table *t2) {
/*
+** Re-insert into the new hash part of a table the elements from the
+** vanishing slice of the array part.
+*/
+static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize,
+ unsigned newasize) {
+ unsigned i;
+ t->alimit = newasize; /* pretend array has new size... */
+ for (i = newasize; i < oldasize; i++) { /* traverse vanishing slice */
+ int tag = *getArrTag(t, i);
+ if (!tagisempty(tag)) { /* a non-empty entry? */
+ TValue aux;
+ farr2val(t, i + 1, tag, &aux);
+ luaH_setint(L, t, i + 1, &aux); /* re-insert it into the table */
+ }
+ }
+ t->alimit = oldasize; /* restore current size... */
+}
+
+
+#define BK1(x) cast(lua_Unsigned, ((x) << 8) | LUA_VEMPTY)
+
+/*
+** Clear new slice of the array, in bulk.
+*/
+static void clearNewSlice (Table *t, unsigned oldasize, unsigned newasize) {
+ int i, j;
+ int firstcell = (oldasize + NM - 1) / NM;
+ int lastcell = cast_int((newasize + NM - 1) / NM) - 1;
+ for (i = firstcell; i <= lastcell; i++) {
+ /* empty tag repeated for all tags in a word */
+ const lua_Unsigned empty = BK1(BK1(BK1(BK1(BK1(BK1(BK1(BK1(0))))))));
+ for (j = 0; j < BKSZ; j++)
+ t->array[i].u.bulk[j] = empty;
+ }
+}
+
+
+/*
** Resize table 't' for the new given sizes. Both allocations (for
** the hash part and for the array part) can fail, which creates some
** subtleties. If the first allocation, for the hash part, fails, an
@@ -668,7 +706,6 @@ static void exchangehashpart (Table *t1, Table *t2) {
*/
void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
unsigned int nhsize) {
- unsigned int i;
Table newt; /* to keep the new hash part */
unsigned int oldasize = setlimittosize(t);
ArrayCell *newarray;
@@ -678,19 +715,10 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
newt.flags = 0;
setnodevector(L, &newt, nhsize);
if (newasize < oldasize) { /* will array shrink? */
- t->alimit = newasize; /* pretend array has new size... */
- exchangehashpart(t, &newt); /* and new hash */
/* re-insert into the new hash the elements from vanishing slice */
- for (i = newasize; i < oldasize; i++) {
- int tag = *getArrTag(t, i);
- if (!tagisempty(tag)) { /* a non-empty entry? */
- TValue aux;
- farr2val(t, i + 1, tag, &aux);
- luaH_setint(L, t, i + 1, &aux);
- }
- }
- t->alimit = oldasize; /* restore current size... */
- exchangehashpart(t, &newt); /* and hash (in case of errors) */
+ exchangehashpart(t, &newt); /* pretend table has new hash */
+ reinsertOldSlice(L, t, oldasize, newasize);
+ exchangehashpart(t, &newt); /* restore old hash (in case of errors) */
}
/* allocate new array */
newarray = resizearray(L, t, oldasize, newasize);
@@ -702,8 +730,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned int newasize,
exchangehashpart(t, &newt); /* 't' has the new hash ('newt' has the old) */
t->array = newarray; /* set new array part */
t->alimit = newasize;
- for (i = oldasize; i < newasize; i++) /* clear new slice of the array */
- *getArrTag(t, i) = LUA_VEMPTY;
+ clearNewSlice(t, oldasize, newasize);
/* re-insert elements from old hash part into new parts */
reinsert(L, &newt, t); /* 'newt' now has the old hash */
freehash(L, &newt); /* free old hash part */
diff --git a/ltable.h b/ltable.h
@@ -87,20 +87,32 @@
/*
-** The array part of a table is represented by an array of cells.
+** 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.
*/
#define NM cast_uint(sizeof(Value))
+
+/*
+** A few operations on arrays can be performed "in bulk", treating all
+** tags of a cell as a simple (or a few) word(s). The next constant is
+** the number of words to cover the tags of a cell. (In conventional
+** architectures that will be 1 or 2.)
+*/
+#define BKSZ cast_int((NM - 1) / sizeof(lua_Unsigned) + 1)
+
struct ArrayCell {
- lu_byte tag[NM];
+ union {
+ lua_Unsigned bulk[BKSZ]; /* for "bulk" operations */
+ lu_byte tag[NM];
+ } u;
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) (&(t)->array[(k)/NM].u.tag[(k)%NM])
/* Computes the address of the value for the abstract index 'k' */
#define getArrVal(t,k) (&(t)->array[(k)/NM].value[(k)%NM])
