diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-01-12 15:50:51 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-01-12 15:50:51 -0300 |
commit | d862da6d04111ce7e5b225040fbe7e526761f478 (patch) | |
tree | 5fec8b142e05a5e5c97d61161ad7053fb86a3cdb /ltable.c | |
parent | 7827c40c49d841daca2a40463b8a60f9a113f77e (diff) | |
download | lua-d862da6d04111ce7e5b225040fbe7e526761f478.tar.gz lua-d862da6d04111ce7e5b225040fbe7e526761f478.tar.bz2 lua-d862da6d04111ce7e5b225040fbe7e526761f478.zip |
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'.
Diffstat (limited to 'ltable.c')
-rw-r--r-- | ltable.c | 55 |
1 files changed, 37 insertions, 18 deletions
@@ -408,21 +408,22 @@ static void freehash (lua_State *L, Table *t) { | |||
408 | ** not the real size of the array, the key still can be in the array | 408 | ** not the real size of the array, the key still can be in the array |
409 | ** part. In this case, do the "Xmilia trick" to check whether 'key-1' | 409 | ** part. In this case, do the "Xmilia trick" to check whether 'key-1' |
410 | ** is smaller than the real size. | 410 | ** is smaller than the real size. |
411 | ** The trick works as follow: let 'p' be an integer such that | 411 | ** The trick works as follow: let 'p' be the integer such that |
412 | ** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. | 412 | ** '2^(p+1) >= alimit > 2^p', or '2^(p+1) > alimit-1 >= 2^p'. That is, |
413 | ** That is, 2^(p+1) is the real size of the array, and 'p' is the highest | 413 | ** 'p' is the highest 1-bit in 'alimit-1', and 2^(p+1) is the real size |
414 | ** bit on in 'alimit-1'. What we have to check becomes 'key-1 < 2^(p+1)'. | 414 | ** of the array. What we have to check becomes 'key-1 < 2^(p+1)'. We |
415 | ** We compute '(key-1) & ~(alimit-1)', which we call 'res'; it will | 415 | ** compute '(key-1) & ~(alimit-1)', which we call 'res'; it will have |
416 | ** have the 'p' bit cleared. If the key is outside the array, that is, | 416 | ** the 'p' bit cleared. (It may also clear other bits smaller than 'p', |
417 | ** 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than 'p', | 417 | ** but no bit higher than 'p'.) If the key is outside the array, that |
418 | ** therefore it will be larger or equal to 'alimit', and the check | 418 | ** is, 'key-1 >= 2^(p+1)', then 'res' will have some 1-bit higher than |
419 | ** 'p', therefore it will be larger or equal to 'alimit', and the check | ||
419 | ** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than | 420 | ** will fail. If 'key-1 < 2^(p+1)', then 'res' has no 1-bit higher than |
420 | ** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller | 421 | ** 'p', and as the bit 'p' itself was cleared, 'res' will be smaller |
421 | ** than 2^p, therefore smaller than 'alimit', and the check succeeds. | 422 | ** than 2^p, therefore smaller than 'alimit', and the check succeeds. |
422 | ** As special cases, when 'alimit' is 0 the condition is trivially false, | 423 | ** As special cases, when 'alimit' is 0 the condition is trivially false, |
423 | ** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'. | 424 | ** and when 'alimit' is 1 the condition simplifies to 'key-1 < alimit'. |
424 | ** If key is 0 or negative, 'res' will have its higher bit on, so that | 425 | ** If key is 0 or negative, 'res' will have its higher bit on, so that |
425 | ** if cannot be smaller than alimit. | 426 | ** it cannot be smaller than 'alimit'. |
426 | */ | 427 | */ |
427 | static int keyinarray (Table *t, lua_Integer key) { | 428 | static int keyinarray (Table *t, lua_Integer key) { |
428 | lua_Unsigned alimit = t->alimit; | 429 | lua_Unsigned alimit = t->alimit; |
@@ -788,11 +789,11 @@ static Node *getfreepos (Table *t) { | |||
788 | 789 | ||
789 | 790 | ||
790 | /* | 791 | /* |
791 | ** inserts a new key into a hash table; first, check whether key's main | 792 | ** Inserts a new key into a hash table; first, check whether key's main |
792 | ** position is free. If not, check whether colliding node is in its main | 793 | ** position is free. If not, check whether colliding node is in its main |
793 | ** position or not: if it is not, move colliding node to an empty place and | 794 | ** position or not: if it is not, move colliding node to an empty place |
794 | ** put new key in its main position; otherwise (colliding node is in its main | 795 | ** and put new key in its main position; otherwise (colliding node is in |
795 | ** position), new key goes to an empty position. | 796 | ** its main position), new key goes to an empty position. |
796 | */ | 797 | */ |
797 | static void luaH_newkey (lua_State *L, Table *t, const TValue *key, | 798 | static void luaH_newkey (lua_State *L, Table *t, const TValue *key, |
798 | TValue *value) { | 799 | TValue *value) { |
@@ -987,6 +988,16 @@ static int finishnodeset (Table *t, const TValue *slot, TValue *val) { | |||
987 | } | 988 | } |
988 | 989 | ||
989 | 990 | ||
991 | static int rawfinishnodeset (const TValue *slot, TValue *val) { | ||
992 | if (isabstkey(slot)) | ||
993 | return 0; /* no slot with that key */ | ||
994 | else { | ||
995 | setobj(((lua_State*)NULL), cast(TValue*, slot), val); | ||
996 | return 1; /* success */ | ||
997 | } | ||
998 | } | ||
999 | |||
1000 | |||
990 | int luaH_psetint (Table *t, lua_Integer key, TValue *val) { | 1001 | int luaH_psetint (Table *t, lua_Integer key, TValue *val) { |
991 | if (keyinarray(t, key)) { | 1002 | if (keyinarray(t, key)) { |
992 | lu_byte *tag = getArrTag(t, key - 1); | 1003 | lu_byte *tag = getArrTag(t, key - 1); |
@@ -1063,12 +1074,20 @@ void luaH_set (lua_State *L, Table *t, const TValue *key, TValue *value) { | |||
1063 | } | 1074 | } |
1064 | 1075 | ||
1065 | 1076 | ||
1077 | /* | ||
1078 | ** Ditto for a GC barrier. (No need to invalidate the TM cache, as | ||
1079 | ** integers cannot be keys to metamethods.) | ||
1080 | */ | ||
1066 | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { | 1081 | void luaH_setint (lua_State *L, Table *t, lua_Integer key, TValue *value) { |
1067 | int hres = luaH_psetint(t, key, value); | 1082 | if (keyinarray(t, key)) |
1068 | if (hres != HOK) { | 1083 | obj2arr(t, key, value); |
1069 | TValue k; | 1084 | else { |
1070 | setivalue(&k, key); | 1085 | int ok = rawfinishnodeset(getintfromhash(t, key), value); |
1071 | luaH_finishset(L, t, &k, value, hres); | 1086 | if (!ok) { |
1087 | TValue k; | ||
1088 | setivalue(&k, key); | ||
1089 | luaH_newkey(L, t, &k, value); | ||
1090 | } | ||
1072 | } | 1091 | } |
1073 | } | 1092 | } |
1074 | 1093 | ||