aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-12-05 17:34:08 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-12-05 17:34:08 -0300
commitb4b616bdf2beb161b89930cc71a06936e8531b2c (patch)
tree0b0842e358206fba5273821ac885e063eddd4537
parentbb93f04d87cfc093757dc712905e1fe3fbe65f58 (diff)
downloadlua-b4b616bdf2beb161b89930cc71a06936e8531b2c.tar.gz
lua-b4b616bdf2beb161b89930cc71a06936e8531b2c.tar.bz2
lua-b4b616bdf2beb161b89930cc71a06936e8531b2c.zip
Rehash reinserts elements with "lighter" functions
When reinserting elements into a table during a rehash, the code does not need to invoke all the complexity of a full 'luaH_set': - The table has space for all keys. - The key cannot exist in the new hash. - The keys are valid (not NaN nor nil). - The keys are normalized (1.0 -> 1). - The values cannot be nil. - No barrier needed (the table already pointed to the key and value).
-rw-r--r--ltable.c50
1 files changed, 33 insertions, 17 deletions
diff --git a/ltable.c b/ltable.c
index 735ae873..052e005e 100644
--- a/ltable.c
+++ b/ltable.c
@@ -395,6 +395,10 @@ static void freehash (lua_State *L, Table *t) {
395** ============================================================== 395** ==============================================================
396*/ 396*/
397 397
398static int insertkey (Table *t, const TValue *key, TValue *value);
399static void newcheckedkey (Table *t, const TValue *key, TValue *value);
400
401
398/* 402/*
399** Structure to count the keys in a table. 403** Structure to count the keys in a table.
400** 'total' is the total number of keys in the table. 404** 'total' is the total number of keys in the table.
@@ -620,7 +624,7 @@ static void setnodevector (lua_State *L, Table *t, unsigned size) {
620/* 624/*
621** (Re)insert all elements from the hash part of 'ot' into table 't'. 625** (Re)insert all elements from the hash part of 'ot' into table 't'.
622*/ 626*/
623static void reinsert (lua_State *L, Table *ot, Table *t) { 627static void reinserthash (lua_State *L, Table *ot, Table *t) {
624 unsigned j; 628 unsigned j;
625 unsigned size = sizenode(ot); 629 unsigned size = sizenode(ot);
626 for (j = 0; j < size; j++) { 630 for (j = 0; j < size; j++) {
@@ -630,7 +634,7 @@ static void reinsert (lua_State *L, Table *ot, Table *t) {
630 already present in the table */ 634 already present in the table */
631 TValue k; 635 TValue k;
632 getnodekey(L, &k, old); 636 getnodekey(L, &k, old);
633 luaH_set(L, t, &k, gval(old)); 637 newcheckedkey(t, &k, gval(old));
634 } 638 }
635 } 639 }
636} 640}
@@ -659,20 +663,18 @@ static void exchangehashpart (Table *t1, Table *t2) {
659** Re-insert into the new hash part of a table the elements from the 663** Re-insert into the new hash part of a table the elements from the
660** vanishing slice of the array part. 664** vanishing slice of the array part.
661*/ 665*/
662static void reinsertOldSlice (lua_State *L, Table *t, unsigned oldasize, 666static void reinsertOldSlice (Table *t, unsigned oldasize,
663 unsigned newasize) { 667 unsigned newasize) {
664 unsigned i; 668 unsigned i;
665 t->asize = newasize; /* pretend array has new size... */
666 for (i = newasize; i < oldasize; i++) { /* traverse vanishing slice */ 669 for (i = newasize; i < oldasize; i++) { /* traverse vanishing slice */
667 lu_byte tag = *getArrTag(t, i); 670 lu_byte tag = *getArrTag(t, i);
668 if (!tagisempty(tag)) { /* a non-empty entry? */ 671 if (!tagisempty(tag)) { /* a non-empty entry? */
669 TValue aux; 672 TValue key, aux;
670 farr2val(t, i, tag, &aux); /* copy entry into 'aux' */ 673 setivalue(&key, l_castU2S(i) + 1); /* make the key */
671 /* re-insert it into the table */ 674 farr2val(t, i, tag, &aux); /* copy value into 'aux' */
672 luaH_setint(L, t, cast_int(i) + 1, &aux); 675 insertkey(t, &key, &aux); /* insert entry into the hash part */
673 } 676 }
674 } 677 }
675 t->asize = oldasize; /* restore current size... */
676} 678}
677 679
678 680
@@ -714,7 +716,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned newasize,
714 if (newasize < oldasize) { /* will array shrink? */ 716 if (newasize < oldasize) { /* will array shrink? */
715 /* re-insert into the new hash the elements from vanishing slice */ 717 /* re-insert into the new hash the elements from vanishing slice */
716 exchangehashpart(t, &newt); /* pretend table has new hash */ 718 exchangehashpart(t, &newt); /* pretend table has new hash */
717 reinsertOldSlice(L, t, oldasize, newasize); 719 reinsertOldSlice(t, oldasize, newasize);
718 exchangehashpart(t, &newt); /* restore old hash (in case of errors) */ 720 exchangehashpart(t, &newt); /* restore old hash (in case of errors) */
719 } 721 }
720 /* allocate new array */ 722 /* allocate new array */
@@ -731,7 +733,7 @@ void luaH_resize (lua_State *L, Table *t, unsigned newasize,
731 *lenhint(t) = newasize / 2u; /* set an initial hint */ 733 *lenhint(t) = newasize / 2u; /* set an initial hint */
732 clearNewSlice(t, oldasize, newasize); 734 clearNewSlice(t, oldasize, newasize);
733 /* re-insert elements from old hash part into new parts */ 735 /* re-insert elements from old hash part into new parts */
734 reinsert(L, &newt, t); /* 'newt' now has the old hash */ 736 reinserthash(L, &newt, t); /* 'newt' now has the old hash */
735 freehash(L, &newt); /* free old hash part */ 737 freehash(L, &newt); /* free old hash part */
736} 738}
737 739
@@ -883,17 +885,31 @@ static int insertkey (Table *t, const TValue *key, TValue *value) {
883} 885}
884 886
885 887
888/*
889** Insert a key in a table where there is space for that key, the
890** key is valid, and the value is not nil.
891*/
892static void newcheckedkey (Table *t, const TValue *key, TValue *value) {
893 unsigned i = keyinarray(t, key);
894 if (i > 0) /* is key in the array part? */
895 obj2arr(t, i - 1, value); /* set value in the array */
896 else {
897 int done = insertkey(t, key, value); /* insert key in the hash part */
898 lua_assert(done); /* it cannot fail */
899 cast(void, done); /* to avoid warnings */
900 }
901}
902
903
886static void luaH_newkey (lua_State *L, Table *t, const TValue *key, 904static void luaH_newkey (lua_State *L, Table *t, const TValue *key,
887 TValue *value) { 905 TValue *value) {
888 if (!ttisnil(value)) { /* do not insert nil values */ 906 if (!ttisnil(value)) { /* do not insert nil values */
889 int done = insertkey(t, key, value); 907 int done = insertkey(t, key, value);
890 if (done) 908 if (!done) { /* could not find a free place? */
891 luaC_barrierback(L, obj2gco(t), key);
892 else { /* could not find a free place? */
893 rehash(L, t, key); /* grow table */ 909 rehash(L, t, key); /* grow table */
894 /* whatever called 'newkey' takes care of TM cache */ 910 newcheckedkey(t, key, value); /* insert key in grown table */
895 luaH_set(L, t, key, value); /* insert key into grown table */
896 } 911 }
912 luaC_barrierback(L, obj2gco(t), key);
897 } 913 }
898} 914}
899 915