If i have an array with numbered indices in lua and need to go through every entry at least once, is it faster to use a numeric for loop or a generic for loop?
If i have an array with numbered indices in lua and need to go through every entry at least once, is it faster to use a numeric for loop or a generic for loop?
for i = 1, #t do end
is not the same as
for i, v in ipairs(t) do end
the latter does not rely on #t and respects the __ipairs metamethod (although this is deprecated and the __index and __newindex metamethods should be used instead).
Assuming no metamethods are set, ipairs will simply loop until it encounters a nil value. It is thus roughly equivalent to the following loop:
local i, v = 1, t[v]
while v ~= nil do --[[loop body here]] i = i + 1; v = t[i] end
This means there are two things it doesn't have to do:
__len metamethod if set. This might theoretically result in a better performance for lists which reside in the hash part (where Lua has to determine the length through a search). It could also improve performance in cases where the __len metamethod does costly counting.nil values. The numeric for loop on the other hand might loop over arbitrarily many nil values due to how the length operator is defined: For a table {[1] = 1, [1e9] = 1}, both 1 and 1e9 are valid values for the length. This also means it's unclear what it does, as the exact length value is unspecified.The latter point in particular means that in pathological cases, the numeric for loop could be arbitrarily slower. It also allows for mistakes, such as looping over (possibly long) strings instead of tables, and won't trigger an error:
local str = "hello world"
for i = 1, #str do local v = str[i] end
will loop over only nil values (as it indexes the string metatable) but throw no error.
I also consider ipairs to be more readable as it makes the intent clear.
For non-pathological cases (lists residing in the list part, no "holes" (nil values), no odd metatables), the numeric for loop can be expected to run marginally faster, as it does not incur the call overhead of the for generic loop you'd be using with ipairs. This ought to be benchmarked on different Lua implementations though:
In practice, the costs of looping will often be negligible compared to the cost of the operations performed within the loop body. Results may vary depending on other factors such as operating system or hardware.
print(jit and jit.version or _VERSION)
-- Fill list with 100 million consecutive integer values
a = {}
for i = 1, 1e8 do a[i] = i end
local function bench(name, func)
func() -- "warmup"
local t = os.clock()
for _ = 1, 10 do func() end
print(name, os.clock() - t, "s")
end
bench("numeric", function()
for i = 1, #a do
local v = a[i]
end
end)
bench("ipairs", function()
for i, v in ipairs(a) do end
end)
Conducted on a Linux machine.
Lua 5.1
numeric 54.312082 s
ipairs 63.579478 s
Lua 5.2
numeric 20.482682 s
ipairs 32.757554 s
Lua 5.3
numeric 14.81573 s
ipairs 23.121844 s
Lua 5.4
numeric 11.684143 s
ipairs 24.455616 s
Finally, LuaJIT:
LuaJIT 2.1.0-beta3
numeric 0.567874 s
ipairs 0.70047 s
Conclusion: Use LuaJIT if possible and stop worrying about micro-optimizations such as ipairs vs. numeric for (even though the latter may be slightly faster). Something as simple as an assert(i == v) will already cost as much as the loop itself (even if assert is local).
In this exact case it would be faster to use a numeric for loop. But not by much and in my testing it is more prone to load differences on my system.
Numeric Loop
a = {} -- new array
for i = 1, 10000000 do
a[i] = 10000000 + i
end
local startNumLoop = os.time(os.date("!*t"))
for i = 1, #a, 1 do
local value = a[i]
end
local stopNumLoop = os.time(os.date("!*t"))
local numloop = stopNumLoop - startNumLoop
print(os.clock())
Result: 1.379 - 1.499
Generic Loop
a = {} -- new array
for i = 1, 10000000 do
a[i] = 10000000 + i
end
local startGenLoop = os.time(os.date("!*t"))
for index, value in ipairs(a) do
end
local stopGenLoop = os.time(os.date("!*t"))
local genLoop = stopGenLoop- startGenLoop
print(os.clock())
Result: 1.568 - 1.662
Tested with lua 5.3.6 win32 binarys from lua.org
This was just a question i had where i didn't find the answer fast enough. If it is in fact a duplicate feel free to mark it so. :)
Especially for loops where is necessary to remove/change the current key/value pair i prefer the fast countdown method...
for i = #tab, 1, -1 do
if (tab[i].x > x) then
table.remove(tab, i) -- See comments
end
end
...for example in LÖVE [love2d] between two frames.