Filling array from offset can be slow

[XmiliaH]

When filling an array from a larger offset filling the array can become very slow.

The following code finished in PUC Lua and LuaJIT in under a second while Luau needs almost 3 minutes!

local t = {}
for i = 100000,400000 do
    t[i] = 1
end

However, when beginning from index 1 all implementations are comparable.

local t = {}
for i = 1,400000 do
    t[i] = 1
end

The following table shows the timings of the two cases for different Lua implementations.

Software	With Offset (Seconds)	From 1 (Seconds)
Luau (Debug)	179.0418060	0.0164390
Luau (Release)	72.4990020	0.0067836
Lua 5.1	0.0320840	0.0126690
Lua 5.4	0.0271857	0.0076240
LuaJIT	0.0068230	0.0026620

The problem seems to be that at some point the insertions start to hit the case https://github.com/Roblox/luau/blob/a934f742d81aefa53e8e45fa7eec0042d3fde7fc/VM/src/ltable.cpp#L530-L536 which rehashes the whole array every time the next index is inserted.

[zeux]

Yeah there's an edge case in the table invariant that we knew about, but didn't have a sufficiently motivating use case to fix. I think this only applies when the offset is large/comparable with the target array size, as is in this example.

(as an aside, your timings are a little surprising, on my system Lua 5.4 produces roughly comparable timings to Luau for the example that is starting from 1 - although if this is on macOS/M1 then yeah Lua 5.4 gets some benefits from first-class integers in programs like this, which we plan to address in the future)

[XmiliaH]

(as an aside, your timings are a little surprising, on my system Lua 5.4 produces roughly comparable timings to Luau for the example that is starting from 1 - although if this is on macOS/M1 then yeah Lua 5.4 gets some benefits from first-class integers in programs like this, which we plan to address in the future)

I use x86_64. This could be caused by building Luau with just make which should produce a debug build which ought to be slower. However, the timings were only included to show that in normal cases all timings are roughly the same.

[zeux]

Ah, gotcha - yeah, makes sense in this case. There's a few simple tweaks to table resize that eliminate this edge case, so we'll take a look - thanks!

[vegorov-rbx]

I have a few adjustments ready that will bring time back to 10s of milliseconds.

[vegorov-rbx]

Ok, it seems that it's harder to get right than I expected, so probably won't have a fix.

[vegorov-rbx]

Found the right fix, but unfortunately it will miss this weeks sync.