diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-13 13:37:24 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2024-11-13 13:37:24 -0300 |
commit | 2491b87c10db530eac2f3d81cd39f95875d16cd5 (patch) | |
tree | 56c066e5e2ccc3eb7b10bea1ba6c60d2b834a8f9 /testes | |
parent | 0de81911525bc62bc2a8fc52a368102afed7022b (diff) | |
download | lua-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.
Diffstat (limited to 'testes')
-rw-r--r-- | testes/nextvar.lua | 72 |
1 files changed, 54 insertions, 18 deletions
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, ...) | |||
9 | end | 9 | end |
10 | 10 | ||
11 | 11 | ||
12 | |||
13 | ---------------------------------------------------------------- | ||
14 | local 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 | ||
24 | end | ||
25 | ---------------------------------------------------------------- | ||
26 | |||
27 | |||
12 | local function check (t, na, nh) | 28 | local 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 | ||
109 | local function mp2 (n) -- minimum power of 2 >= n | 125 | -- minimum power of 2 (or zero) >= n |
126 | local 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 |
113 | end | 130 | end |
114 | 131 | ||
@@ -123,7 +140,7 @@ end | |||
123 | 140 | ||
124 | -- testing constructor sizes | 141 | -- testing constructor sizes |
125 | local sizes = {0, 1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, | 142 | local 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 | ||
128 | for _, sa in ipairs(sizes) do -- 'sa' is size of the array part | 145 | for _, 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 |
169 | local lim = 130 | 186 | local lim = 130 |
170 | local a = {}; a[2] = 1; check(a, 0, 1) | 187 | local a = {}; a[2] = 1; check(a, 2, 0) |
171 | a = {}; a[0] = 1; check(a, 0, 1); a[2] = 1; check(a, 0, 2) | 188 | a = {}; a[0] = 1; check(a, 0, 1); |
189 | a[2] = 1; check(a, 2, 1) | ||
172 | a = {}; a[0] = 1; a[1] = 1; check(a, 1, 1) | 190 | a = {}; a[0] = 1; a[1] = 1; check(a, 1, 1) |
173 | a = {} | 191 | a = {} |
174 | for i = 1,lim do | 192 | for 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)) |
185 | end | 203 | end |
186 | 204 | ||
187 | a = {} | ||
188 | for i=1,16 do a[i] = i end | ||
189 | check(a, 16, 0) | ||
190 | do | 205 | do |
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] | ||
200 | end | 221 | end |
201 | 222 | ||
202 | -- reverse filling | 223 | -- reverse filling |
203 | for i=1,lim do | 224 | do |
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) |
207 | end | 229 | end |
208 | 230 | ||
231 | |||
232 | do -- "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 | ||
242 | end | ||
243 | |||
244 | |||
209 | -- size tests for vararg | 245 | -- size tests for vararg |
210 | lim = 35 | 246 | lim = 35 |
211 | local function foo (n, ...) | 247 | local 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 | ||
844 | end | 880 | end |
845 | 881 | ||
846 | print"OK" | 882 | print"OK" |