Lua optimization tipps

[burli]

I found some interesting optimization tipps

http://lua-users.org/wiki/OptimisationTips

for example

t[#t+1] = 0 is faster than table.insert(t, 0)
Multiplication x*0.5 is faster than division x/2
x*x is faster than x^2

Another example from here

http://stackoverflow.com/questions/1546 ... ua-program

function ipairs

When iterating a table, the function overhead from ipairs does not justify it's use. To iterate a table, instead use

Code: Select all

for k=1, #tbl do local v = tbl[k];

It does exactly the same without the function call overhead (pairs actually returns another function which is then called for every element in the table while #tbl is only evaluated once). It's a lot faster, even if you need the value. And if you don't...

Also this PDF has some interesting tipps

http://www.lua.org/gems/sample.pdf

For example

Code: Select all

function foo (x)
  for i = 1, 1000000 do
   x = x + math.sin(i)
  end
  return x
end
print(foo(10))

We can optimize it by declaring sin once, outside function foo:

Code: Select all

local sin = math.sin
  function foo (x)
  for i = 1, 1000000 do
   x = x + sin(i)
  end
  return x
end
print(foo(10))

This second code runs 30% faster than the original one

some of this things I found in mods and I think, there is potential for optimization in many mods

[sfan5]

These micro-optimizations won't make any noticable different in mod speed.
Additionally most people run Minetest compiled with LuaJIT which these tips most likely do not apply to.

[burli]

These micro-optimizations won't make any noticable different in mod speed.
Additionally most people run Minetest compiled with LuaJIT which these tips most likely do not apply to.

I disagree. I tested a simple loop in two versions.

Version 1

Code: Select all

local start = os.clock()

for i=1,1000000 do
  x = math.max(math.random())
end

print(os.clock()-start)

Version 2

Code: Select all

local start = os.clock()

local max = math.max
local random = math.random()
for i=1,1000000 do
  x = max(random)
end

print(os.clock()-start)

Version 1
lua: 0.2 sec
luajit: 0.01 sec

Version 2
lua: 0.08 sec
luajit: 0.002 sec

Maybe not all tipps may have an effect with the jit, but this one has.

[Edit] I'm sorry, I can not reproduce this result myself. Something went obviously wrong.

[duane]

function ipairs

When iterating a table, the function overhead from ipairs does not justify it's use. To iterate a table, instead use

Code: Select all

for k=1, #tbl do local v = tbl[k];

It does exactly the same without the function call overhead (pairs actually returns another function which is then called for every element in the table while #tbl is only evaluated once). It's a lot faster, even if you need the value. And if you don't...

Of course this assumes you've got numeric keys, and you're not using a zero-based table. I might start doing it anyway -- pairs() isn't intuitive to me.

sfan5's right though. Probably 95% of your cpu time is spent on calls to the game, which will always be slower than doing the same thing in C. The actual lua runs pretty fast even unoptimized, unless you're doing something unusual.

I'd be more concerned about optimizing for luajit's tiny memory capacity.

[burli]

Ok, I stop trying to look for optimizations. Not because it wouldn't worth it, but the results are not consistent enough to compare. Some strange things going on here

Code: Select all

markus@neo:~/lua$ luajit bench2.lua 
0.001847
markus@neo:~/lua$ luajit bench2.lua 
0.002628
markus@neo:~/lua$ luajit bench2.lua 
0.00297
markus@neo:~/lua$ luajit bench2.lua 
0.001326
markus@neo:~/lua$ luajit bench2.lua 
0.002654
markus@neo:~/lua$ luajit bench2.lua 
0.000902

It is always the same code, but the results differ to much. The fastest is about 3 times faster than the slowest

[burli]

and you're not using a zero-based table.

I thought, lua tables are always start at 1?

[cheapie]

and you're not using a zero-based table.

I thought, lua tables are always start at 1?

They can start at whatever you want and essentially contain whatever indexes you want.

[duane]

and you're not using a zero-based table.

I thought, lua tables are always start at 1?

It's actually pretty easy to use zero-based tables. #table gives you the length less one, which is generally what you want. However, lots of little things will annoy you, like dump() listing your table as [1], [2], [3]... then [0].

[blert2112]

First... Please don't take anything I say personally. I have the utmost respect for all of you and if I mention a piece of code you wrote or worked on it is not meant as a personal attack.

These micro-optimizations won't make any noticable different in mod speed.
Additionally most people run Minetest compiled with LuaJIT which these tips most likely do not apply to.

Not necessarily, it depends on where they are being used. For instance, if you are just iterating through a table once before the game actually starts (registering nodes and such) or something that is only done every once in a while then, by all means, use the convenient way of doing it, that is what it is there for. But, if you are inside an on_generated, on_step, abm, lbm or a timer function then small speed tweaks can add up quick. On my system it takes between 30 and 40ms to receive and send VoxelManip data. Every millisecond I can shave off the rest of the code counts and it can be very noticeable especially in a complex on_generated function. I see the effect quite obviously when using my customized TNT mod (unreleased because it is totally incompatible with MineTest_Game), it is smoother and much more responsive compare to the default TNT mod (on my systems). It also uses only one global to function properly, but contain three others for use in other mods, and has more features.

I'd be more concerned about optimizing for luajit's tiny memory capacity.

This is key when dealing with LuaJIT!

Vanilla Lua is slow compared to LuaJIT. For Lua you want to optimize for CPU usage at the expense of memory because there is no memory limit. LuaJIT is fast already, for the most part, so optimizing for memory at the expense of CPU time is key because it has the darned memory limit. Working around using ipairs/pairs helps in both situations because both are relatively slow (compared to manual iteration) and also carry a memory overhead.

A simple fact is globals are very slow compared to locals. Globals are also not handled by the GarbageCollector. Any global function, table, var, object, etc stay in memory even if it will never be used again. Take for instance all the mods that have a global register_something() function. Nobody ever frees that function even though it will never be used in the game past an after(0). This is something that many Lua programmers forget about because they are used to Lua handling the memory for them unlike other languages that require you to remember to free your objects. Lua only manages LOCAL objects, the GarbageCollector does nothing with globals.

Reuse you local objects. Do this...

Code: Select all

local somevar
for i = 1,100 do
    somevar = something
end

...instead of...

Code: Select all

for i = 1,100 do
    local somevar = something
end

This will save the time needed to recreate the variable and helps to manage the amount of objects the GarbageCollector has to track. The more things the GC has to track the slower it becomes.

Faster still is using the FFI and CDEF to move large persistent objects outside the LuaJIT memory limit. In my experimentation, this is not helpful inside an on_generated or similar function that gets run many times per second. I have successfully moved VoxelManip data outside of the memory limit with relative ease but because of the nature of the GC and the memory required to call the functions to get the data it makes no difference. But it can be very useful for storing large tables of persistent data.

As far as localizing math.*() functions... Just about any seasoned Lua programmer will tell you to localize your math functions because it does make a difference. But again, it depends on how it is being used. If you only use it once in a while then why bother, save the memory and object count the GC has to deal with. But, if it is being called many times inside of a function that is getting called many times per second the savings can add up quickly.

There is undoubtedly more but within the above is a good start for mod devs to start managing memory better. If you want to see the code that moves the VM data outside the JIT memory limit just ask.

[oleastre]

I disagree. I tested a simple loop in two versions.
...

Code: Select all

for i=1,1000000 do

...

Do you really use that kind of loop in your mod code ?

Probably not, and you also said, you have problems reproducing the result.

When you are developing, "premature optimization is the root of all evil." (Donald Knuth).

If you really want to optimize your code:
- get stuff done, something that's useful and that works
- test it, a lot
- refactor your code so that it's easier to read, to maintain
- maybe, after a lot of corrections about getting your stuff working, you will find a performance problem
- at that time, try to find the hot points, what's the function that makes the code slow. Then, at that point, optimize that function, and only that one.

Micro optimization can be useful, but most of the time it makes the code hard to read for a really small performance benefit.

[burli]

Do you really use that kind of loop in your mod code ?

Well, not exactly, but nested loops with 80x80x80 iterations. Small optimizations can have a noticable effect

[cheapie]

Well, not exactly, but nested loops with 80x80x80 iterations. Small optimizations can have a noticable effect

Yep, they have quite the noticeable negative effect on the readability of the code.

[burli]

Well, not exactly, but nested loops with 80x80x80 iterations. Small optimizations can have a noticable effect

Yep, they have quite the noticeable negative effect on the readability of the code.

What is more important? Readable code or playable game?

[cheapie]

What is more important? Readable code or playable game?

Seeing as how bugs that nobody even tries to fix (because the code is near-unreadable) can be even worse than lag, it's possible that readability can often be more important then performance.

Besides, the (mostly) micro-optimizations suggested so far are not likely to make a large enough difference to turn unplayable into playable.

[duane]

What is more important? Readable code or playable game?

Readable code is entirely unnecessary, as long as you plan to maintain it, by yourself, forever or let your mod die off when you get worn out. Of course, you also deny others the opportunity to learn from your experience in the process.

When you are developing, "premature optimization is the root of all evil." (Donald Knuth).

+10

[burli]

Of course, you can optimize your code to death. That' not what I want to do. I just want to find out what is possible and where you have to keep an eye on

Yesterday I made a little experiment. I defined all local variables at the beginning of the file. The result: the garbage collector had lot of work. So this is baaad, burli. Don't do this

In another experiment I put three mapgens together in one file. The three single mapgens need around a second. Together in one file they only need 0.5 seconds, because the voxelmanip has to run only once instead of three times

[kaeza]

Do you really use that kind of loop in your mod code ?[...]

I see you didn't try to do mapgen stuff in Lua. These "microoptimizations" do wonders there, and in anything that requires heavy computation.

As blert said above:

t depends on where they are being used. For instance, if you are just iterating through a table once before the game actually starts [...] or something that is only done every once in a while then, by all means, use the convenient way of doing it, that is what it is there for. But, if you are inside an on_generated, on_step, abm, lbm or a timer function then small speed tweaks can add up quick.

[burli]

These "microoptimizations" do wonders there

I wouldn't say wonders, but they might help

[oleastre]

I see you didn't try to do mapgen stuff in Lua. These "microoptimizations" do wonders there, and in anything that requires heavy computation.

I never said micro-optimization is not useful and should not be used. What I said, is: first get it working, then benchmark your functions and then optimize what is really needed.

The whole point is: do not start by writing code that uses micro-optimization everywhere, start simple, get it working and then optimize.

[duane]

Yesterday I made a little experiment. I defined all local variables at the beginning of the file. The result: the garbage collector had lot of work. So this is baaad, burli. Don't do this

Are you sure about that? File variables shouldn't ever fall out of scope, so the garbage collector shouldn't ever collect them.

[duane]

I see you didn't try to do mapgen stuff in Lua. These "microoptimizations" do wonders there, and in anything that requires heavy computation.

Well, I've done a lot of mapgen profiling over the last year, and in my case, on my system, 75-90% of the cpu time went to producing noise tables, liquid handling, and lighting updates. That means that if I managed to shave 25% off the loops (not likely), I'd have sped the whole mapgen up by a whopping 2-6%. Not really worth worrying about, and certainly not worth making the code harder to follow.

At one point, we added an option to valleys lua to go with simpler caves, which resulted in something like a 30% speed increase overall by doing nothing but eliminating three of the five noises we needed. Five 3D noises were taking almost half of the cpu time. Now that's worth optimizing.

Of course your mileage may vary, and it's always worth knowing more about the system, so I really enjoy these discussions. Keep it up, Burli. : )

[burli]

Yesterday I made a little experiment. I defined all local variables at the beginning of the file. The result: the garbage collector had lot of work. So this is baaad, burli. Don't do this

Are you sure about that? File variables shouldn't ever fall out of scope, so the garbage collector shouldn't ever collect them.

I am shure. I moved all local var definitions from inside the functions to the beginning of the file. Then the garbage collector was called every few seconds. Moved everything back and everything was ok.

Well, I've done a lot of mapgen profiling over the last year, and in my case, on my system, 75-90% of the cpu time went to producing noise tables, liquid handling, and lighting updates. That means that if I managed to shave 25% off the loops (not likely), I'd have sped the whole mapgen up by a whopping 2-6%. Not really worth worrying about, and certainly not worth making the code harder to follow.

That's what I found too. I hacked the v6 cavegen and intersect light into your valleys helper mod. Stand alone these three mods need over one second of generation time, together in one file they need only around 0.5 seconds.

Of course your mileage may vary, and it's always worth knowing more about the system, so I really enjoy these discussions. Keep it up, Burli. : )

I want spend much time to optimization. As you said, the system needs more than the mod itself. If I try to optimize, I think I will try to put more code into one mapgen instead of seperate mods with their own register_on_generated()

[blert2112]

Reuse you local objects. Do this...

Code: Select all

local somevar
for i = 1,100 do
    somevar = something
end

...instead of...

Code: Select all

for i = 1,100 do
    local somevar = something
end

HybridDog brought some testing results to my attention. He proved that the above can be wrong. I needed to see for myself so... I recompiled MineTest, with and without LuaJIT. Here is the test function I used to see what was going on...

Code: Select all

core.register_on_generated(function(minp, maxp, seed)
	local m0 = collectgarbage("count")
	local t0 = os.clock()

	local a = {}
	for x = 1,112 do
		for y = 1,112 do
			for z = 1,112 do
				a = {x = x, y = y, z = z}
			end
		end
	end

	local t1 = os.clock()
	local m1 = collectgarbage("count")
	local t2 = os.clock()

	for x = 1,112 do
		for y = 1,112 do
			for z = 1,112 do
				local b = {x = x, y = y, z = z}
			end
		end
	end

	local t3 = os.clock()
	local m2 = collectgarbage("count")

	print("Results:")
	print("	first iteration:")
	print("time:", t1-t0)
	print("memory", m1-m0)
	print("	second iteration:")
	print("time:", t3-t2)
	print("memory", m2-m1)
end)

With LuaJIT:
The second loop is consistently much faster and less memory intensive.

Without LuaJIT:
The first loop is slightly faster (by about 0.0# miliseconds) and uses slightly less memory.

I suppose it all boils down to if JIT is used or not and what (and how much) you are trying to accomplish.
Since I spent the time to recompile with and without LuaJIT I may take the pairs/ipairs vs manual thing and see what kind of difference there really is. I would also like to see what happens if I swap the above table for a table the size of vm:get_data().

[burli]

With LuaJIT:
The second loop is consistently much faster and less memory intensive.

Without LuaJIT:
The first loop is slightly faster (by about 0.0# miliseconds) and uses slightly less memory.

I run your code from the command line and I am a little bit confused about the memory values if I run the code with normal lua interpreter. I got sometimes negative values.

I can confirm, that the second loop is much faster with LuaJIT

Code: Select all

markus@neo:~/lua$ lua bench1.lua 
Results:
   first iteration:
time:	0.470408
memory	23.9658203125
   second iteration:
time:	0.458614
memory	14.375
markus@neo:~/lua$ lua bench1.lua 
Results:
   first iteration:
time:	0.476296
memory	38.1845703125
   second iteration:
time:	0.468358
memory	-23.6875
markus@neo:~/lua$ lua bench1.lua 
Results:
   first iteration:
time:	0.481432
memory	20.0283203125
   second iteration:
time:	0.462899
memory	-9.6875
markus@neo:~/lua$ luajit bench1.lua 
Results:
   first iteration:
time:	0.236662
memory	30.1220703125
   second iteration:
time:	0.001136
memory	8.1484375
markus@neo:~/lua$ luajit bench1.lua 
Results:
   first iteration:
time:	0.236688
memory	30.1220703125
   second iteration:
time:	0.001136
memory	8.1484375
markus@neo:~/lua$ luajit bench1.lua 
Results:
   first iteration:
time:	0.235777
memory	30.1220703125
   second iteration:
time:	0.001135
memory	8.1484375

But what is better in this case?

Code: Select all

--****** version 1 ******
local data={}
local vm, emin, emax

local function caves()
  do_something_with(data)
end

function caves.generate(minp, maxp, seed)
  vm, emin, emax = minetest.get_mapgen_object("voxelmanip")
  vm:get_data(data)
  caves()
end


--****** version 2 ******

local function caves(data)
  do_something_with(data)
end

function caves.generate(minp, maxp, seed)
  local vm, emin, emax = minetest.get_mapgen_object("voxelmanip")
  local vm:get_data(data)
  caves(data)
end

Data is a larger variable. If I call "caves(data)", is "data" a reference to the original or a copy of the original?

[duane]

Data is a larger variable. If I call "caves(data)", is "data" a reference to the original or a copy of the original?

"data" is a variable containing a reference to a table. Any variable you set to data will be another reference to the same table. The data variable in mapgens should be passed as "vm:get_data(data)" to the game, which will then reuse the table and (I think) return a reference to it (which you don't actually need), so data should be file-local. However, that's an unusual case.