hint Lua Performance: arrays

[Maris]

Variance: 0.01-0.2

http://pastebin.com/LQJtfFZw

 

Edited April 20, 2016 by Maris
info update

[Mobbstar]

Why is stuff faster when you make a local variable?

[bizziboi]

@Mobbstar

Because then lua doesn't have to lookup the index of variable 'a' in the global environment every iteration of the loop (twice even, once for the read and once for the write), it just addresses the array through the index of the local.

(running the code through luac will show you the difference - the innerloop with the global array has 5 opcodes, the one with the local array 3; 2 of which are getglobal which isn't the cheapest)

[bizziboi]

@Maris

Out of curiosity, what's your timing on test_a3 using pairs instead of ipairs?

Also, keep in mind that, while this is good to know, in normal code the array indexing mode will be of less impact as the code inside the loop is very likely to hit a cache miss (because it'll touch some variable on some lua-object that has no relation to the object in the iteration before it or after it) which is wayyyyyy more expensive than the lookup of the global variable (which will be much more likely to be in cache after the fist iteration)

[Maris]

1 hour ago, bizziboi said:

Out of curiosity, what's your timing on test_a3 using pairs instead of ipairs?

No difference. (Updated, see test_a5)

[simplex]

Aw, you didn't test table indexing! One of my favorite pieces of trivia about Lua is that table indexing with string keys is actually faster than indexing with numerical keys, even if that number falls in the array key range (though in this scenario the performance difference is very small).

 

1 hour ago, bizziboi said:

@Maris

Out of curiosity, what's your timing on test_a3 using pairs instead of ipairs?

They're virtually identical when a table has no hash part. In my system which one had the best average runtime changed between benchmarks, due to the performance being so close (the difference in runtime is of about 1%, one way or the other).

If you check their C implementations under Lua 5.1.5, you'll see that the operations performed by luaB_next (pair's generator) and ipairsaux (ipairs's generator) are basically the same. They are both defined in lbaselib.c, though reading luaB_next will take you to lua_next (lapi.c), which eventually will lead you to luaH_next (ltable.c).

 

And oh, @Maris, the cost of computing the length of a table (as in '#t') is roughly proportional to the logarithm of its size. Also note that the header of a for loop (such as 'for i = 1, #t do') is only evaluated once, so the cost of computing a table's length there is much smaller than the cost of actually running the loop, even if it's empty (for sufficiently large tables).

Edited April 20, 2016 by simplex
messages gluing together made for bad formatting

[bizziboi]

@simplex

My reason for asking was that I recalled a discussion from the LuaL mailing list a good while ago about pairs being marginally faster on large arrays, whereas reading the code as well as general reasoning would have led me to expect the opposite if anything.

I don't recall the specifics of that mailing list discussion and in general I don't care too much, as in most practical cases no loop (in Lua) is that tight that I need to consider the cost of the iterator itself, but since Maris had a benchmark ready to add the test to, I figured I'd ask :o)

[simplex]

2 hours ago, bizziboi said:

@simplex

My reason for asking was that I recalled a discussion from the LuaL mailing list a good while ago about pairs being marginally faster on large arrays, whereas reading the code as well as general reasoning would have led me to expect the opposite if anything.

I don't recall the specifics of that mailing list discussion and in general I don't care too much, as in most practical cases no loop (in Lua) is that tight that I need to consider the cost of the iterator itself, but since Maris had a benchmark ready to add the test to, I figured I'd ask :o)

Huh. Indeed it's rather strange that pairs could be faster than ipairs, even if marginally, over large arrays. If anything, since pairs performs checks to see if there are hash elements and since all of the luaX_next functions are in different compilation units (preventing inlining, thus hindering locality of reference), I'd expect pairs to be universally slower. But anyway, indeed this is only relevant as trivia.

Though I'm not sure I agree with the claim that "in most practical cases no loop (in Lua) is that tight that I need to consider the cost of the iterator itself", at least if this is to be taken as a general claim. If we're talking about pairs vs. ipairs then sure, it's irrelevant, but a numerical for can be significantly faster than ipairs iteration for simple "foldl" operations, such as summing an array, computing its minimum, etc. But ok, unless one's implementing a numerical linear algebra or scientific library in pure Lua (and why would they?), this kind of code shouldn't be a bottleneck. And you did say "in most practical cases" and "I need to", so I guess I'm needlessly nitpicking.

And oh, since we're talking about Lua performance: why doesn't Don't Starve/Don't Starve Together use LuaJIT?

Edited April 21, 2016 by simplex

[bizziboi]

@simplex

 

" But a numerical for can be significantly faster than ipairs iteration for simple "foldl" operations, such as summing an array, computing its minimum, etc. "

You're right. I see that while I was editing my post I dropped the original part saying something along the lines of 'except for extremely tight loops', since they are so rare in Lua. In general people iterate over a table of objects, dereferencing said object for even one variable will invariably lead to a cache miss. In a very tight loop, as the profiles show, the impact definitely can be quite significant. 

As for not using LuaJit, there's various reasons, one of them the changes that were made to Lua, making similar changes to LuaJit would be non-trivial and time consuming. There's still been the occasional bug with LuaJit. I need to keep in mind that we want to port. I have actually had to modify lua scripts for LuaJit to behave 100% identical. Taking all this (and some other things) into account, the risk and added complexity has outweighed the benefit.

 

[Maris]

Another test.

Let's say variable x can be only true or nil.

if x then --faster
if x ~= nil then --slower

but

if x == nil then --faster
if not x then --slower

 

[Muche]

2 hours ago, Maris said:

Another test.

Let's say variable x can be only true or nil.

if x then --faster
if x ~= nil then --slower

but

if x == nil then --faster
if not x then --slower

 

Where do

if not x == nil then
if x then else -- i.e. then block is empty

sit in this scenario?

 

[DarkXero]

16 hours ago, Maris said:

Another test.

I compared

local x = 0
for i = 0, 50000, 1 do
	if x == nil then
	end
end

with

local x = 0
for i = 0, 50000, 1 do
	if not x then
	end
end

and "not x" was the winner multiple times.

 

 

You should compare

local func1 = function(a,b,func) 
	return func(a+b) 
end

for i=1,50000 do
	local x = func1(1,2,function(a) return a*2 end)
end

versus

local func1 = function(a,b,func) 
	return func(a+b) 
end

local func2 = function(a) 
	return a*2 
end

for i=1,50000 do
	local x = func1(1,2,func2)
end

 

[simplex]

Checking whether a value evaluates to true (as in "if x then") is indeed marginally faster than an equality check, but whether or not throwing a negation (as in "not x") in the mix offsets that or not may very well depend on the phase of the moon and whether the gods have decided the day is in your favor.

 

When we get to *that* kind of minutiae and of such small differences, will it ever be at all relevant? You're more likely to get a different output due to hardware differences than due to any fundamental characteristic of the Lua virtual machine.