Optimization Stuff

[Felix_Maxwell]

Hello All,

As my project grows, I wonder more and more how fast stuff is under the hood, and how I should write it to run as fast as possible.

My first question is: do tables get slower the bigger they get, or does it not matter because they're just C arrays and hash tables under the hood? To Phrase it another way, can I trade memory for speed and put whatever methods I want on every entity in the game (let's say for example, 100 methods on every entity), or will that cause a performance hit because it's searching through these huge tables (mostly associative, not numerically indexed)? Not counting constructors/rehashes, which are done during level generation in this 'hypothetical' case.

Question #2 : Since I'm using the standard class module for Lua, I think I'm creating a new metable every time I derive a new class from a base class, rather than just having one metatable that all of the derived classes set themselves to. Does searching six or seven metatables down on a regular basis to find methods and properties drag down the speed? I suspect the answer could be "Not really, as long as the functions searching through these metatables are JIT-friendly". I've heard that searching in metatables is one of the fastest ways to do it but am still a little curious about it as the Lua book and Reference manual don't go into a ton of detail as they have a lot to cover.

To rephrase more briefly:

1) Big tables bad?
2) Stacks of metatables: not cool?

Thank you for indulging my ramblings

[ivan]

do tables get slower the bigger they get,

Yes, but it's non-linear so the difference in performance is insignificant in most practical cases.

or will that cause a performance hit because it's searching through these huge tables (mostly associative, not numerically indexed)

It will be slightly slower, but with LuaJIT it will be hard to tell the difference.
With plain Lua it's a little more noticable, but still nothing to worry about.
The most realistic optimization in this respect is trying to keep the _G table clean and uncluttered.

2) Stacks of metatables: not cool?

metatables do have a tiny amount of overhead although with LuaJIT this is rarely an issue.
If it makes your code cleaner and easier to maintain than go with the stacks of metatables.

And use my profiler instead of trying to predict what is slowing down your game. 99.99% of the time the bottleneck is love.draw
https://github.com/2dengine/profile.lua

[pgimeno]

To Phrase it another way, can I trade memory for speed and put whatever methods I want on every entity in the game (let's say for example, 100 methods on every entity), or will that cause a performance hit because it's searching through these huge tables (mostly associative, not numerically indexed)? Not counting constructors/rehashes, which are done during level generation in this 'hypothetical' case.

Once the size of the table is stable, the cost will not vary noticeably. There's also a class library specifically designed to avoid rehashing, https://love2d.org/forums/viewtopic.php?t=83286 which might help if you need to create objects dynamically, but watch out for its limitations.

Question #2 : Does searching six or seven metatables down on a regular basis to find methods and properties drag down the speed? I suspect the answer could be "Not really, as long as the functions searching through these metatables are JIT-friendly".

Searching so many metatables in interpreted mode will be slow. In compiled mode, the execution flow is flattened (function calls are inlined) and then it doesn't really matter. However, you say that you're using pairs() to iterate. Take into account that LuaJIT only compiles loops, and it won't ever compile a pairs() loop because pairs() is NYI; therefore, no matter how LuaJIT-friendly the code is, it's quite likely that it will run in interpreted mode. Also, LuaJIT 2.1 is the first one to prevent C function calls from stopping traces, and that version won't be avaliable until Löve 12. Löve 11 uses LuaJIT 2.0.

[Felix_Maxwell]

Thanks for the detailed and reassuring answers. Maybe part of me was waiting for the other shoe to drop in terms of Love's performance, and it's nice to see it holding up as I continue to use it.

And use my profiler instead of trying to predict what is slowing down your game

I've already been using it for about a week. I didn't know it was yours, excellent work!

you're using pairs() to iterate

Thankfully I didn't find any pairs() uses, but after you linked me the NYI page I spent a few weeks refactoring out some unpack()'s and {...}'s, but mostly the {...}'s just because they came with the unpack()'s.

Optional project backstory/inquiry: It all started when I made this super convoluted system that 'tacked' functions onto entities imported from other files, sort of a single-table multi-file composition system that emulated inheritance, and suddenly the speed tanked to ~30%. The stack traces for errors got really long (bad sign?) and when I eventually profiled it, those 'tacked-on' methods were each being identified separately in the profiler, each one taking a tiny bit of CPU time, instead of seeing it as just one listing as Entity:update(). This made me suspect that the JIT compiler probably wasn't identifying these as the same function. Basically tried to fly too close to the sun and the compiler pushed back, and I have the profiler to thank for showing me what I was doing wrong. I don't know if this is a common mistake or if I bent the rules too far.

My main observation right now is that switching from that system to standard inheritance has raised the frame rate, and subjectively the game feels significantly smoother and buttery. Also the code is way cleaner.

In the NYI article, it says you have to 'write Lua least like Lua' or something like that to keep everything off the NYI list, but I think there's a different and equally 'sweet' Lua style that comes with ditching unpack(), {...}, and vararg functions, where you pass the arg you need as a single table, two tables, something static. Maybe it's 'Diet Lua' or something, makes it easy to keep things clean without long parameter lists. Fortuitously, Roberto recommends writing functions this way even though the Lua book never mentions LuaJIT.

Code: Select all

    
    local arg = {
        -- clear, easy to edit
        gun_name= "Uzi",
        proj_type= "bb",
        num_shots= 1,
        cooldown= 0.05,
        base_proj_speed= 2,
        inaccuracy= 0.2,
        automatic= true,
        kickback= 5,
        magnitude= 5  }
    local gun = GUN:new(arg)
 

Code: Select all

function GUN:new(arg)
	-- Easy to work with, no need to fiddle with parameter order
	self.gun_name = arg.gun_name or "no gun name!" 
	self.proj_type = arg.proj_type
	self.num_shots = arg.num_shots
	self.cooldown = arg.cooldown
	self.cooldown_timer = 0 -- zero for first shot
	self.cooling = false
	self.inaccuracy = arg.inaccuracy or 0
	self.base_proj_speed = arg.base_proj_speed
	self.automatic = arg.automatic or false
	self.kickback = arg.kickback or 0
	self.magnitude = arg.magnitude or 20
end

[Felix_Maxwell]

A few more questions if you'll indulge me -

The most realistic optimization in this respect is trying to keep the _G table clean and uncluttered.

Does the Interpreter always check if an identifer is a global before looking elsewhere for it? I just threw all of the data in the game into one global variable and it didn't seem to slow anything down. When I query the _G table, I get like 60 things, love and every built-in Lua function. So having 5-10 extra things put onto _G is probably not a big deal right?

#2: I am wondering if every time an entity in my project fires a bullet, I can just attach a field that points to who fired it? Since tables are always passed around by reference, does setting up a reference to a large object have significant cost, or is it just setting up a new identifier and pointer under the hood?

My last post was a little rambly, guess I got a little excited to get some answers.

[ivan]

Does the Interpreter always check if an identifer is a global before looking elsewhere for it?

If it's not local or on the stack it will be checked against the global table.

As long as you don't have hundreds or thousands of extra keys in the global table you'll be fine.

Assigning references is not an issue, it's accessing them that takes lookup time.

Also try to avoid cycles where table A points to B and B points to A. This puts a strain for the garbage collector.

[pgimeno]

Also try to avoid cycles where table A points to B and B points to A. This puts a strain for the garbage collector.

I know that affects CPython because it's reference counted, but it's the first time I hear it in relation to Lua, and I believe it's not reference counted. Do you have any further info about it?

[Felix_Maxwell]

This makes sense to me, because I see how the garbage collector could get caught in a loop while making sure a table has no remaining references. I actually do this a TON in my project, makes everything pretty easy, and I can spawn in a few thousand entities (each one containing about 9 circularly linked tables), and it seems to run ok. Perhaps I'm off the hook because all of the circular references are contained inside tables in my entity table/array, and when they're removed they're cleanly snipped/nil-ed out all at once - - - maybe the garbage collector isn't checking through them because it can see they they are already in the entities table, and therefore have at least one reference and shouldn't be cleaned out/investigated further?

[pgimeno]

This makes sense to me, because I see how the garbage collector could get caught in a loop while making sure a table has no remaining references.

From http://lua-users.org/wiki/GarbageCollectionTutorial :

This algorithm is called mark and sweep, i.e., we mark all the reachable objects and sweep away the ones remaining. Lua uses the mark and sweep garbage collection algorithm exclusively. This has the advantage that we don't have to reference count objects and so don't get cyclic referencing problems.

The LuaJIT author has plans for a more sophisticated garbage collector, which is not reference-counted either, but to the best of my knowledge, as of 2.1 it still uses the same as Lua. Also, the new GC does not seem to have much progress: https://github.com/LuaJIT/LuaJIT/issues/38

Perhaps I'm off the hook because all of the circular references are contained inside tables in my entity table/array, and when they're removed they're cleanly snipped/nil-ed out all at once - - - maybe the garbage collector isn't checking through them because it can see they they are already in the entities table, and therefore have at least one reference and shouldn't be cleaned out/investigated further?

I think that the biggest problem is not the reference loops, but the number of objects. The more live objects you have, the more objects need to be checked, and that does stress the GC.

Maybe ivan has some other information about reference loops being a problem.

[ivan]

I know that affects CPython because it's reference counted, but it's the first time I hear it in relation to Lua, and I believe it's not reference counted. Do you have any further info about it?

I remember reading about this before the days of LuaJIT so I may be completely wrong at this point.
From what I can remember the standard Lua garbage collector does handle cycles, but it may take a few extra collection steps to do so.
Like pgimeno said, creating and destroying a lot of intermediate tables is the main performance issue for the GC.