From 2491b87c10db530eac2f3d81cd39f95875d16cd5 Mon Sep 17 00:00:00 2001 From: Roberto Ierusalimschy Date: Wed, 13 Nov 2024 13:37:24 -0300 Subject: 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. --- testes/nextvar.lua | 72 ++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 54 insertions(+), 18 deletions(-) (limited to 'testes') 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, ...) end + +---------------------------------------------------------------- +local function printTable (t) + local a, h = T.querytab(t) + print("array:") + for i = 1, a do + print("", T.querytab(t, i - 1)) + end + print("hash:") + for i = 1, h do + print("", T.querytab(t, a + i - 1)) + end +end +---------------------------------------------------------------- + + local function check (t, na, nh) if not T then return end local a, h = T.querytab(t) @@ -106,9 +122,10 @@ else --[ -- testing table sizes -local function mp2 (n) -- minimum power of 2 >= n +-- minimum power of 2 (or zero) >= n +local function mp2 (n) local mp = 2^math.ceil(math.log(n, 2)) - assert(n == 0 or (mp/2 < n and n <= mp)) + assert((mp == 0 or mp/2 < n) and n <= mp) return mp end @@ -123,7 +140,7 @@ end -- testing constructor sizes local sizes = {0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, - 30, 31, 32, 33, 34, 254, 255, 256, 500, 1000} + 30, 31, 32, 33, 34, 254, 255, 256, 257, 500, 1001} for _, sa in ipairs(sizes) do -- 'sa' is size of the array part local arr = {"return {"} @@ -167,8 +184,9 @@ end -- testing tables dynamically built local lim = 130 -local a = {}; a[2] = 1; check(a, 0, 1) -a = {}; a[0] = 1; check(a, 0, 1); a[2] = 1; check(a, 0, 2) +local a = {}; a[2] = 1; check(a, 2, 0) +a = {}; a[0] = 1; check(a, 0, 1); +a[2] = 1; check(a, 2, 1) a = {}; a[0] = 1; a[1] = 1; check(a, 1, 1) a = {} for i = 1,lim do @@ -184,28 +202,46 @@ for i = 1,lim do check(a, 0, mp2(i)) end -a = {} -for i=1,16 do a[i] = i end -check(a, 16, 0) do + local a = {} + for i=1,16 do a[i] = i end + check(a, 16, 0) for i=1,11 do a[i] = undef end - for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash (?) - check(a, 0, 8) -- 5 elements in the table + check(a, 16, 0) + a[30] = true -- force a rehash + a[30] = undef + check(a, 0, 8) -- 5 elements in the hash part: [12]-[16] a[10] = 1 - for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash (?) - check(a, 0, 8) -- only 6 elements in the table + for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash + check(a, 16, 1) for i=1,14 do a[i] = true; a[i] = undef end - for i=18,50 do a[i] = true; a[i] = undef end -- force a rehash (?) - check(a, 0, 4) -- only 2 elements ([15] and [16]) + check(a, 16, 1) -- no rehash... + a[31] = true; a[32] = true -- force a rehash + check(a, 0, 4) -- [15], [16], [31], [32] end -- reverse filling -for i=1,lim do +do + local N = 2^10 local a = {} - for i=i,1,-1 do a[i] = i end -- fill in reverse - check(a, mp2(i), 0) + for i = N, 1, -1 do a[i] = i end -- fill in reverse + check(a, mp2(N), 0) end + +do -- "almost sparse" arrays + -- create table with holes in 1/3 of its entries; all its + -- elements are always in the array part + local a = {} + for i = 1, 257 do + if i % 3 ~= 1 then + a[i] = true + check(a, mp2(i), 0) + end + end +end + + -- size tests for vararg lim = 35 local function foo (n, ...) @@ -840,7 +876,7 @@ do co() -- start coroutine co(1) -- continue after yield assert(res[1] == 30 and res[2] == 20 and res[3] == 10 and #res == 3) - + end print"OK" -- cgit v1.2.3-55-g6feb