aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-13 13:37:24 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-13 13:37:24 -0300
commit2491b87c10db530eac2f3d81cd39f95875d16cd5 (patch)
tree56c066e5e2ccc3eb7b10bea1ba6c60d2b834a8f9
parent0de81911525bc62bc2a8fc52a368102afed7022b (diff)
downloadlua-2491b87c10db530eac2f3d81cd39f95875d16cd5.tar.gz
lua-2491b87c10db530eac2f3d81cd39f95875d16cd5.tar.bz2
lua-2491b87c10db530eac2f3d81cd39f95875d16cd5.zip
New rule for size of array part
Array part needs 1/3 of its elements filled, instead of 1/2. Array entries use ~1/3 the memory of hash entries, so this new rule still ensures that array parts do not use more memory than keeping the values in the hash, while allowing more uses of the array part, which is more efficient than the hash.
-rw-r--r--ltable.c27
-rw-r--r--ltests.c11
-rw-r--r--testes/nextvar.lua72
3 files changed, 81 insertions, 29 deletions
diff --git a/ltable.c b/ltable.c
index 3451445c..923f3eaa 100644
--- a/ltable.c
+++ b/ltable.c
@@ -471,12 +471,23 @@ typedef struct {
471 unsigned nums[MAXABITS + 1]; 471 unsigned nums[MAXABITS + 1];
472} Counters; 472} Counters;
473 473
474
475/*
476** Check whether it is worth to use 'na' array entries instead of 'nh'
477** hash nodes. (A hash node uses ~3 times more memory than an array
478** entry: Two values plus 'next' versus one value.) Evaluate with size_t
479** to avoid overflows.
480*/
481#define arrayXhash(na,nh) (cast_sizet(na) <= cast_sizet(nh) * 3)
482
474/* 483/*
475** Compute the optimal size for the array part of table 't'. 484** Compute the optimal size for the array part of table 't'.
485** This size maximizes the number of elements going to the array part
486** while satisfying the condition 'arrayXhash' with the use of memory if
487** all those elements went to the hash part.
476** 'ct->na' enters with the total number of array indices in the table 488** 'ct->na' enters with the total number of array indices in the table
477** and leaves with the number of keys that will go to the array part; 489** and leaves with the number of keys that will go to the array part;
478** return the optimal size. (The condition 'twotoi > 0' in the for loop 490** return the optimal size for the array part.
479** stops the loop if 'twotoi' overflows.)
480*/ 491*/
481static unsigned computesizes (Counters *ct) { 492static unsigned computesizes (Counters *ct) {
482 int i; 493 int i;
@@ -484,17 +495,19 @@ static unsigned computesizes (Counters *ct) {
484 unsigned int a = 0; /* number of elements smaller than 2^i */ 495 unsigned int a = 0; /* number of elements smaller than 2^i */
485 unsigned int na = 0; /* number of elements to go to array part */ 496 unsigned int na = 0; /* number of elements to go to array part */
486 unsigned int optimal = 0; /* optimal size for array part */ 497 unsigned int optimal = 0; /* optimal size for array part */
487 /* loop while keys can fill more than half of total size */ 498 /* traverse slices while 'twotoi' does not overflow and total of array
499 indices still can satisfy 'arrayXhash' against the array size */
488 for (i = 0, twotoi = 1; 500 for (i = 0, twotoi = 1;
489 twotoi > 0 && ct->na > twotoi / 2; 501 twotoi > 0 && arrayXhash(twotoi, ct->na);
490 i++, twotoi *= 2) { 502 i++, twotoi *= 2) {
491 a += ct->nums[i]; 503 unsigned nums = ct->nums[i];
492 if (a > twotoi/2) { /* more than half elements present? */ 504 a += nums;
505 if (nums > 0 && /* grows array only if it gets more elements... */
506 arrayXhash(twotoi, a)) { /* ...while using "less memory" */
493 optimal = twotoi; /* optimal size (till now) */ 507 optimal = twotoi; /* optimal size (till now) */
494 na = a; /* all elements up to 'optimal' will go to array part */ 508 na = a; /* all elements up to 'optimal' will go to array part */
495 } 509 }
496 } 510 }
497 lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
498 ct->na = na; 511 ct->na = na;
499 return optimal; 512 return optimal;
500} 513}
diff --git a/ltests.c b/ltests.c
index 2dafbee5..8191f14a 100644
--- a/ltests.c
+++ b/ltests.c
@@ -1043,7 +1043,10 @@ static int table_query (lua_State *L) {
1043 } 1043 }
1044 else if (cast_uint(i) < asize) { 1044 else if (cast_uint(i) < asize) {
1045 lua_pushinteger(L, i); 1045 lua_pushinteger(L, i);
1046 arr2obj(t, cast_uint(i), s2v(L->top.p)); 1046 if (!tagisempty(*getArrTag(t, i)))
1047 arr2obj(t, cast_uint(i), s2v(L->top.p));
1048 else
1049 setnilvalue(s2v(L->top.p));
1047 api_incr_top(L); 1050 api_incr_top(L);
1048 lua_pushnil(L); 1051 lua_pushnil(L);
1049 } 1052 }
@@ -1057,11 +1060,11 @@ static int table_query (lua_State *L) {
1057 } 1060 }
1058 else 1061 else
1059 lua_pushliteral(L, "<undef>"); 1062 lua_pushliteral(L, "<undef>");
1060 pushobject(L, gval(gnode(t, i))); 1063 if (!isempty(gval(gnode(t, i))))
1061 if (gnext(&t->node[i]) != 0) 1064 pushobject(L, gval(gnode(t, i)));
1062 lua_pushinteger(L, gnext(&t->node[i]));
1063 else 1065 else
1064 lua_pushnil(L); 1066 lua_pushnil(L);
1067 lua_pushinteger(L, gnext(&t->node[i]));
1065 } 1068 }
1066 return 3; 1069 return 3;
1067} 1070}
diff --git a/testes/nextvar.lua b/testes/nextvar.lua
index cee77f76..85c9ff6b 100644
--- a/testes/nextvar.lua
+++ b/testes/nextvar.lua
@@ -9,6 +9,22 @@ local function checkerror (msg, f, ...)
9end 9end
10 10
11 11
12
13----------------------------------------------------------------
14local function printTable (t)
15 local a, h = T.querytab(t)
16 print("array:")
17 for i = 1, a do
18 print("", T.querytab(t, i - 1))
19 end
20 print("hash:")
21 for i = 1, h do
22 print("", T.querytab(t, a + i - 1))
23 end
24end
25----------------------------------------------------------------
26
27
12local function check (t, na, nh) 28local function check (t, na, nh)
13 if not T then return end 29 if not T then return end
14 local a, h = T.querytab(t) 30 local a, h = T.querytab(t)
@@ -106,9 +122,10 @@ else --[
106-- testing table sizes 122-- testing table sizes
107 123
108 124
109local function mp2 (n) -- minimum power of 2 >= n 125-- minimum power of 2 (or zero) >= n
126local function mp2 (n)
110 local mp = 2^math.ceil(math.log(n, 2)) 127 local mp = 2^math.ceil(math.log(n, 2))
111 assert(n == 0 or (mp/2 < n and n <= mp)) 128 assert((mp == 0 or mp/2 < n) and n <= mp)
112 return mp 129 return mp
113end 130end
114 131
@@ -123,7 +140,7 @@ end
123 140
124-- testing constructor sizes 141-- testing constructor sizes
125local sizes = {0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 142local sizes = {0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17,
126 30, 31, 32, 33, 34, 254, 255, 256, 500, 1000} 143 30, 31, 32, 33, 34, 254, 255, 256, 257, 500, 1001}
127 144
128for _, sa in ipairs(sizes) do -- 'sa' is size of the array part 145for _, sa in ipairs(sizes) do -- 'sa' is size of the array part
129 local arr = {"return {"} 146 local arr = {"return {"}
@@ -167,8 +184,9 @@ end
167 184
168-- testing tables dynamically built 185-- testing tables dynamically built
169local lim = 130 186local lim = 130
170local a = {}; a[2] = 1; check(a, 0, 1) 187local a = {}; a[2] = 1; check(a, 2, 0)
171a = {}; a[0] = 1; check(a, 0, 1); a[2] = 1; check(a, 0, 2) 188a = {}; a[0] = 1; check(a, 0, 1);
189a[2] = 1; check(a, 2, 1)
172a = {}; a[0] = 1; a[1] = 1; check(a, 1, 1) 190a = {}; a[0] = 1; a[1] = 1; check(a, 1, 1)
173a = {} 191a = {}
174for i = 1,lim do 192for i = 1,lim do
@@ -184,28 +202,46 @@ for i = 1,lim do
184 check(a, 0, mp2(i)) 202 check(a, 0, mp2(i))
185end 203end
186 204
187a = {}
188for i=1,16 do a[i] = i end
189check(a, 16, 0)
190do 205do
206 local a = {}
207 for i=1,16 do a[i] = i end
208 check(a, 16, 0)
191 for i=1,11 do a[i] = undef end 209 for i=1,11 do a[i] = undef end
192 for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash (?) 210 check(a, 16, 0)
193 check(a, 0, 8) -- 5 elements in the table 211 a[30] = true -- force a rehash
212 a[30] = undef
213 check(a, 0, 8) -- 5 elements in the hash part: [12]-[16]
194 a[10] = 1 214 a[10] = 1
195 for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash (?) 215 for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash
196 check(a, 0, 8) -- only 6 elements in the table 216 check(a, 16, 1)
197 for i=1,14 do a[i] = true; a[i] = undef end 217 for i=1,14 do a[i] = true; a[i] = undef end
198 for i=18,50 do a[i] = true; a[i] = undef end -- force a rehash (?) 218 check(a, 16, 1) -- no rehash...
199 check(a, 0, 4) -- only 2 elements ([15] and [16]) 219 a[31] = true; a[32] = true -- force a rehash
220 check(a, 0, 4) -- [15], [16], [31], [32]
200end 221end
201 222
202-- reverse filling 223-- reverse filling
203for i=1,lim do 224do
225 local N = 2^10
204 local a = {} 226 local a = {}
205 for i=i,1,-1 do a[i] = i end -- fill in reverse 227 for i = N, 1, -1 do a[i] = i end -- fill in reverse
206 check(a, mp2(i), 0) 228 check(a, mp2(N), 0)
207end 229end
208 230
231
232do -- "almost sparse" arrays
233 -- create table with holes in 1/3 of its entries; all its
234 -- elements are always in the array part
235 local a = {}
236 for i = 1, 257 do
237 if i % 3 ~= 1 then
238 a[i] = true
239 check(a, mp2(i), 0)
240 end
241 end
242end
243
244
209-- size tests for vararg 245-- size tests for vararg
210lim = 35 246lim = 35
211local function foo (n, ...) 247local function foo (n, ...)
@@ -840,7 +876,7 @@ do
840 co() -- start coroutine 876 co() -- start coroutine
841 co(1) -- continue after yield 877 co(1) -- continue after yield
842 assert(res[1] == 30 and res[2] == 20 and res[3] == 10 and #res == 3) 878 assert(res[1] == 30 and res[2] == 20 and res[3] == 10 and #res == 3)
843 879
844end 880end
845 881
846print"OK" 882print"OK"