aboutsummaryrefslogtreecommitdiff
path: root/testes
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-14 11:48:25 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2024-11-14 11:48:25 -0300
commit9a91fe1640ddbe5b55e7454541059372b971f400 (patch)
tree902589105ff77ee8f3000e80f7e0459cd21eb068 /testes
parent2491b87c10db530eac2f3d81cd39f95875d16cd5 (diff)
downloadlua-9a91fe1640ddbe5b55e7454541059372b971f400.tar.gz
lua-9a91fe1640ddbe5b55e7454541059372b971f400.tar.bz2
lua-9a91fe1640ddbe5b55e7454541059372b971f400.zip
Add extra size when resizing tables with deleted keys
Without this extra space, sequences of insertions/deletions (and some other uses) can have unpexpected low performances. See the added tests for an example, and *Mathematical Models to Analyze Lua Hybrid Tables and Why They Need a Fix* (Martínez, Nicaud, Rotondo; arXiv:2208.13602v2) for detais.
Diffstat (limited to 'testes')
-rw-r--r--testes/nextvar.lua62
1 files changed, 61 insertions, 1 deletions
diff --git a/testes/nextvar.lua b/testes/nextvar.lua
index 85c9ff6b..00e509f8 100644
--- a/testes/nextvar.lua
+++ b/testes/nextvar.lua
@@ -23,6 +23,12 @@ local function printTable (t)
23 end 23 end
24end 24end
25---------------------------------------------------------------- 25----------------------------------------------------------------
26local function countentries (t)
27 local e = 0
28 for _ in pairs(t) do e = e + 1 end
29 return e
30end
31----------------------------------------------------------------
26 32
27 33
28local function check (t, na, nh) 34local function check (t, na, nh)
@@ -115,6 +121,24 @@ do -- overflow (must wrap-around)
115 assert(k == nil) 121 assert(k == nil)
116end 122end
117 123
124
125do
126 -- alternate insertions and deletions in an almost full hash.
127 -- In versions pre-5.5, that causes constant rehashings and
128 -- takes a long time to complete.
129 local a = {}
130 for i = 1, 2^11 - 1 do
131 a[i .. ""] = true
132 end
133
134 for i = 1, 1e5 do
135 local key = i .. "."
136 a[key] = true
137 a[key] = nil
138 end
139 assert(countentries(a) == 2^11 - 1)
140end
141
118if not T then 142if not T then
119 (Message or print) 143 (Message or print)
120 ('\n >>> testC not active: skipping tests for table sizes <<<\n') 144 ('\n >>> testC not active: skipping tests for table sizes <<<\n')
@@ -202,6 +226,23 @@ for i = 1,lim do
202 check(a, 0, mp2(i)) 226 check(a, 0, mp2(i))
203end 227end
204 228
229
230-- insert and delete elements until a rehash occurr. Caller must ensure
231-- that a rehash will change the shape of the table. Must repeat because
232-- the insertion may collide with the deleted element, and then there is
233-- no rehash.
234local function forcerehash (t)
235 local na, nh = T.querytab(t)
236 local i = 10000
237 repeat
238 i = i + 1
239 t[i] = true
240 t[i] = undef
241 local nna, nnh = T.querytab(t)
242 until nna ~= na or nnh ~= nh
243end
244
245
205do 246do
206 local a = {} 247 local a = {}
207 for i=1,16 do a[i] = i end 248 for i=1,16 do a[i] = i end
@@ -212,7 +253,7 @@ do
212 a[30] = undef 253 a[30] = undef
213 check(a, 0, 8) -- 5 elements in the hash part: [12]-[16] 254 check(a, 0, 8) -- 5 elements in the hash part: [12]-[16]
214 a[10] = 1 255 a[10] = 1
215 for i=30,50 do a[i] = true; a[i] = undef end -- force a rehash 256 forcerehash(a)
216 check(a, 16, 1) 257 check(a, 16, 1)
217 for i=1,14 do a[i] = true; a[i] = undef end 258 for i=1,14 do a[i] = true; a[i] = undef end
218 check(a, 16, 1) -- no rehash... 259 check(a, 16, 1) -- no rehash...
@@ -242,6 +283,25 @@ do -- "almost sparse" arrays
242end 283end
243 284
244 285
286do
287 -- alternate insertions and deletions should give some extra
288 -- space for the hash part. Otherwise, a mix of insertions/deletions
289 -- could cause too many rehashes. (See the other test for "alternate
290 -- insertions and deletions" in this file.)
291 local a = {}
292 for i = 1, 256 do
293 a[i .. ""] = true
294 end
295 check(a, 0, 256) -- hash part is full
296 a["256"] = nil -- delete a key
297 forcerehash(a)
298 -- table has only 255 elements, but it got some extra space;
299 -- otherwise, almost each delete-insert would rehash the table again.
300 assert(countentries(a) == 255)
301 check(a, 0, 512)
302end
303
304
245-- size tests for vararg 305-- size tests for vararg
246lim = 35 306lim = 35
247local function foo (n, ...) 307local function foo (n, ...)