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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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:

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

local start = os.clock()

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

print(os.clock()-start)

Version 2

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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...

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

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


...instead of...

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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.
...

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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:

[I]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...

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

Code: Select all

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


...instead of...

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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...

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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?

Your phone or window isn't wide enough to display the code box. If it's a phone, try rotating it to landscape mode.

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.

[Sokomine]

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.

The last time I did some basic benchmarking on mg_villages, quite a lot of time was spent on reading the data via voxelmanip and afterwards writing it back. This took about the same time as the actual manipulation of the mapdata (flattening, adding the houses etc.). At least with luajit.

[Chiu ChunLing]

Readable code is relative.

If the code is so "readable" that people can think they know what it does when actually they haven't a clue, it is too readable. This is a common problem for me, I often find during writing code that making things "readable" keeps me from really looking at what the code actually does.

And you can always just go back and find/replace things if you need the code itself to be readable for others.

But really, comments are for making it so others can follow your code. If they aren't going to actually read the code itself (in which case optimized code, by virtue of relying on simpler, more basic functions, is FAR more readable), then all that matters is the comments.

Still, people work differently. For me, turning the kind of gibberish I find easier to understand properly (rather than misunderstand because it looks like English, which is an entirely different language with fundamentally different rules and syntax) into something 'more readable' is a simple matter, while avoiding misunderstanding of code that is written too much like an entirely different language I already know is very difficult. Not everyone has this problem, even most of the world's English speakers aren't particularly fluent to the degree where they interpret English-like code reflexively as if it were natural language (which it is not). There are also a lot of people whose experience of working in languages that are not particularly English-like leaves them with no patience for obfuscation on top of code...I suppose I understand that attitude, though I don't share it.

Habitual use of relatively optimized code practices results in such code being more readable to <i>you</i> than code that is written with a lot of dependence on complex functions even for simple tasks. Which is why the idea of a trade-off between readability and optimization is fundamentally flawed...readability is profoundly and intrinsically relative to a particular individual such that what is more readable to a person with one outlook may be far less readable to others, optimization is variable in degree of effect, but not in kind.

For me, quantity has a quality of it's own...the sheer number of characters used affects how well I'm able to understand them. I particularly hate having to scroll up and down...I'm well aware of what this does to the ability of other people to read the kind of code I prefer to write, and I care when I have some kind of reason to do so...which is to say if someone actually <i>indicates</i> an interest in maintaining my code without my continued involvement.

If that's the case, I'm more than happy to go back and edit for their idea of readability, even though it's completely different from mine. Because there's an actual benefit.

[paramat]

> The data variable in mapgens should be passed as "vm:get_data(data)" to the game, which will then reuse the table

This is an optimisation for reducing memory use, since the data table is so huge, 112^3 = 1,404,928 nodes.

[SegFault22]

Some of these optimizations will be very useful for a mod I will be making soon.

This mod won't just iterate through a table each time a new chunk is generated. It will be iterating every tenth of a second orso. And it won't just be iterating through one table - it will have to iterate through several tables, one for each of a few special types of nodes, that can exist anywhere in any loaded chunk. These nodes will be part of a power system, including producer nodes and consumer nodes - each producer node will have to keep a table of the attached consumer nodes which don't have a full power buffer, calculate losses over the conduits connecting them, and do something which changes the consumer node's metadata to increase the power stored in the buffer for however much has been transfered, each tenth of a second (orso).

And that's not everything, either - every time a "conduit" node is placed, or any producer or consumer, it initiates a "wave" of updating that moves outwards along all connected conduits, finding all attached producers and consumers, causing them to update their list of connected consumers and the associated conduit route distance to include any new connections if they exist.

I'm not exactly sure how it will all be implemented, and I can already see that it will probably cause unplayable lag if it isn't optimized good enough. Just imagine a network of one producer and 8 - every tenth of a second (or whatever, it will be configurable) the producer iterates through a table 8 entries long, and checks whether the buffer of each consumer is marked as "full"; then if the consumer has a buffer that isn't full, the producer calculates the conduit route distance loss, subtracts that from the producer's maximum packet size, determines if that packet's size will overfill the buffer and adjusts the packet size accordingly (if the buffer will be overfilled, adjust the packet size to the consumer's buffer maximum level minus the current level, and add the packet loss so that the consumer gets just enough to fill it up all of the way regardless of what the cable losses are), "sends the packet" (subtracts the packet's size from the producer storage buffer, and updates the consumer node metadata to increase the power stored in the buffer by the packet size minus the distance loss), and moves on to the next entry. If all of the consumer nodes start empty, all of those steps will have to be done for each consumer, every "tick" (1/10th second by default; maybe it should be 1/4th second though), which could generate lots of lag.

Thank you for giving us this information about optimizing Lua code, as it will be very useful for this project. I want my power system to transfer power quickly, so after placing a machine you don't have to wait 10 seconds or so for the network to start feeding power.

[Chiu ChunLing]

You need to check out how technic does this, they associate all the logic with the switching block and update it when a node is placed or removed from the wire nodes that connect to that switch. If you don't do something similar, no amount of other optimization is going to save you.