Performance-wise questions / good practices

[LotA]

Hello there, I have a question regarding script performance, more specifically i want to optimize as much as possible my on_tick event.

Basically i need delays/timers so I use an array like this : key= game.tick i want the code to perform, value= whatever data i need for the process

It's pretty handy to check on each tick if there's something to do

Code: Select all

script.on_event(defines.events.on_tick, function(event)	
	if global.timer_array[event.tick] then
		-- do stuff here using timer_array[event.tick]
	end
end)

Most of the time, the value will be nil as nothing happens at this tick.
my question is, is this technique efficient? I don't know how Lua works internally, does it need to iterate the whole array to find out this key is (un)used ?
Considering the table might have hundreds of elements with gaps of thousands of possible keys between each, should I test a simple boolean first? something like :

Code: Select all

script.on_event(defines.events.on_tick, function(event)
	if global.timer_state then
		if global.timer_array[event.tick] then
			-- do stuff here using timer_array[event.tick]
		end
	end
end)

I'm hesitating because reading from the global table seems to be quite expensive. In the end I don't know if using another variable is worth the trouble.
Does the size of the array matters?

[Nexela]

I'm hesitating because reading from the global table seems to be quite expensive. In the end I don't know if using another variable is worth the trouble.

(mostly unconfirmed assumptions ahead )
Reading from the global.table is just as expensive are reading from any other global variable in LUA. Basically LUA first looks to see if there is a local variable by that name, then goes on to look for a global variable. resulting in an extra look up call in everything regarding it.


Here is some info that may help you out.

viewtopic.php?f=25&t=39500&p=236764#p236764

[Adil]

Lua does hash tables. What you're describing is in fact the fastest way of doing what you want.
Reading from global tables cost some nanoseconds.
You can save a fraction of time by localizing the global table at first:

Code: Select all

local timers=global.time_array

Not that it will matter if then you query it only once.

I usually do try to write on_tick handlers in most unreadable manner in order to make them fast, but quite often it is calls to C++ api that take the most time anyway.

[orzelek]

Also please make sure that you actually remove the entries from that table so that it doesn't get longer and longer.

[LotA]

Lua does hash tables. What you're describing is in fact the fastest way of doing what you want.
Reading from global tables cost some nanoseconds.

So the way I do it is efficient enough? I the boolean var isn't worth it's cost no matter the array size?

You can save a fraction of time by localizing the global table at first:

Code: Select all

local timers=global.time_array

Not that it will matter if then you query it only once.

Where should I put it? before the check? then there will be a variable allocation that is 99% of time useless.
After the first check? then I still access the global table twice. (i guess that could do it if you need to access the data multiple times afterward)
thanks for the answer, but I must say that i'm still a bit confuse ^^

Also please make sure that you actually remove the entries from that table so that it doesn't get longer and longer.

Not removing the entry would actually be some obvious memory leak, moreover, I also wipe the whole array whenever i can

[Adil]

So the way I do it is efficient enough? I -the boolean var isn't worth it's cost no matter the array size?

Yes. Also for information, a lua table in general and lua table with non-continuous numeric indices are not arrays.
The boolean var isn't worth it's cost to talk about it.

You can save a fraction of time by localizing the global table at first:

Code: Select all

local timers=global.time_array

Not that it will matter if then you query it only once.

Where should I put it? before the check? then there will be a variable allocation that is 99% of time useless.
After the first check? then I still access the global table twice. (i guess that could do it if you need to access the data multiple times afterward)
thanks for the answer, but I must say that i'm still a bit confuse ^^

Not that it will matter if then you query it only once.

It was a general tip, since you're so obsessed with quickly accessing the global. It might trim a couple of nanoseconds if you had that before accessing the global table in a loop.

[LotA]

Ok, seems clear enough now.

Another question come to mind, i'll use an example as explanation :
Imagine I use many var but only a few simultaneously at any particular point.
What is the most efficient :
- Access everyone without much care, but only the needed ones

Code: Select all

return whatever_func(global.data1, global.data2, global.data3)

- Bundle all my var in a single table

Code: Select all

local datas = global.my_data_package
return whatever_func(datas.data1, datas.data2, datas.data3)

resulting in only one global access at the cost of a potentially huge table with many/most useless data for this specific part of the script
Once again, does the table size matter?

I know I'm asking pretty specific questions that might not have huge impact after all... But I just can't accept the idea of having wrong/bad/unoptimized coding practices.

[Adil]

In lua a table is created with {}, this operator reserves a certain amount of memory in the ram for the table. That reserved space stays constant and unmovable, exceptions are implementation details that script writer should not concern himself with.
Any variable you assign table to

Code: Select all

a={}; 
b={ c={a} }

is just a pointer to the table in memory. A pointer takes up either 32 or 64 bits and that's it.
Whenever you pass table around only those 64 bits are copied.
Whenever you query a table in a table:

Code: Select all

return b.c[1]

computer follows the pointer stored in `b`, finds a table object in ram, queries it for key "c", takes pointer to another table, queries that for key "1" then returns the pointer to the table `a`. Just a simple pointer hopping, workload on par with arithmetic.

Every function has associated table `_ENV`, any variable lookup

Code: Select all

return a

is actually a query to that table

Code: Select all

return _ENV.a

If the variable is local, it is stored in `_ENV`.

If there's no variable in `_ENV` with the given name, then global variables are queried, those actually reside in top-level table, the `_ENV` of the root function of the script (it is `require` or `dofile` function that loads and executes the script).
Usually, a link to the global table is stored in any other `_ENV` as `_G`. So the access to a global variable

Code: Select all

return b

is actually something like

Code: Select all

return _ENV.b or _ENV._G.b

Thus it is about 3 pointer jumps instead of 1.
Here is convoluted example that should give you an insight on the amount of work that implies:

RUn it in standalone lua interpreter

Code: Select all

local depth=100--how many pointers will be in a chain
local  q={};--a table
local a={};--a start of pointer chain
local b=a;  -- intermediate variable
for i=1,depth do b.a={} b=b.a end;  --setup chain
local t=os.clock(); 
print(q)  
print(os.clock()-t);--time of previous line execution 
t=os.clock(); --start of pointer chain traversal
b=a 
while b.a do b=b.a end 
print(b) 
print(os.clock()-t)--time of pointer traversal

When a pointer chain is about 100 elements, system load fluctuations may actually cause the second time be smaller. The direct access gets notably faster only when you change `depth` to thousands and more intermediate pointers.

Note that, whenever you query uninitialized variable, all 3 jumps are taken.

That is all about Lua-global, now in factorio there is a table named `global`, that name is misnormer. It might be more appropriately named as `persistent` or `save_this` or somesuch. What it truly is is just `_G.global`. So in your examples

Code: Select all

return whatever_func(global.data1, global.data2, global.data3)

performs 3 jumps to get global, and does so 3 times, and a single jump to data1 or data2 or data3.

Code: Select all

local datas = global.my_data_package
return whatever_func(datas.data1, datas.data2, datas.data3)

Performs 3 jumps to initialize datas, then like before a single jump per actual data.
So, you've shaved off 6 jumps, 6 remain.
It's good but not to the point of being obsessed over it.
edit: actually it's 'about 6 jumps' since there may be more lookups in the encompassing environments of nested functions (upvalues), metatables and such.

There's article by the language creator on the matter of optimizations in lua, it does give insight on the workings of the language, but it's probably better to first get through the tutorial book itself as it also provides a few details on what and how is it done in lua.

[LotA]

I've read the book, but I've missed that performance tips.. (haven't read it yet but will absolutely do)

you have very well explained how the Lua scope works : local / global.
I guess it's a bit misleading to have a table in factorio that is called global. "Persistent" could have been more logical, personally i think of it as the "serialized data" or, more simply "variable gets here or you end up with desync".

But my concern is not much about pointers or chain-pointers. Accessing/writing the factorio global table is expensive as the data gets serialized and my questions are more regarding this cost (so it's more determined by the factorio engine than the Lua internal I think)

I could rephrase my questions like this :
Is the expensiveness of accessing factorio's global table solely due to the Lua scope mechanics or is it this expensive because its somehow need to "unserialize" data and so does it affect/create "local" (not scope-wise but memory-wise) data for further processing. And if so, if I call the global table again, does it brainlessly redo all the "unserialize" process of is it smart enough with the "local allocation" so the next calls get faster?
I believe when you affect a local variable with data from the global table, it doesn't simply pass by a pointer but it somehow "duplicate" the data somewhere "local"
Why I believe that? - that's where my knowledge of lua internal lacks - But It seems to me that using a (factorio's) global var is hundreds maybe thousand times more expensive that accessing a local variable, It seems very big to me for "simply" accessing the parent element's variables / going upward in the scope. That's where I need a highlight I guess.

If i'm not mistaken (or even) and regarding what you're saying, I guess its worth to always (well, as long as you'll call more than twice the data) to affect the global table to a local variable before using the actual data.

[Adil]

`global` is just a table like any other. Serialization and unserialization occurs only during save\load process.
No data is ever duplicated, when you pass around pointer, that would just ruin the point of passing pointer in the first place.
A highlight of the running costs of lua scoping would require a quotation of several computer science articles by R. Ierusalimschy, if you insist, they are listed at the lua site in documentation page. A tldr version is: "it is cheap enough to not worry about it".
The only time a significant amount of extra work can happen is interacting with game api, for example

Code: Select all

entity.position.x 

infers data conversion and creation of a table `position`, which you can then index.

Localizing the global values is indeed reasonable practice, however gains are often negligible. If anything, the motivation for that should be giving a shorter or contextually appropriate name to a global variable for the sake of improving readability of the code.

[LotA]

When i first tried multiplayer scenarios, i naively created my vars directly within the control.lua. The scenario would cause desyncs whenever I changed the value of a variable. I resolved it by putting all my var in the global table so I assumed it also affect the network.

[prg]

When i first tried multiplayer scenarios, i naively created my vars directly within the control.lua. The scenario would cause desyncs whenever I changed the value of a variable. I resolved it by putting all my var in the global table so I assumed it also affect the network.

The contents of global affects the network insofar as it gets serialized and sent as part of the save game when a new player joins, so the new client starts simulating the game with the same state as existing clients. Apart from that, global is just a normal variable.

[dewiniaid]

Not an expert on Lua or Factorio modding, but I am a developer.

There's a variety of alternative solutions to this other than indexing a global table of events, depending on what your access pattern looks like.

If events are infrequently created, you can use a linked list and sort upon insertion. This makes it easy to see when the next event is (O(1)) -- it's always at the front of the list. The cost (O(n)) having to iterate over the list to find the event that is before yours but has it's next event after yours. If events are frequently in the same tick, you can replace "event" with "list of events all happening at the same time" and adjust logic accordingly.

To speed up insertion at the cost of complexity, you can maintain an index of N-tick-long "blocks", where each block points to the earliest item in the linked list belonging to that block. Insertion of events only needs to look up the block in a table and search the list belonging to that list's block -- still O(n) but a much smaller n. (This can actually still be one single linked list, with the block table simply containing the first entry in the block). Checking for the next event still only needs to examine the head of the list (O(1)), though processing that event needs to see if it's the first event of a new block so it can properly clean up the previous block (removing it from the table).

This modified solution is essentially a modified Calendar Queue if you want to read up on it. I'd be happy to write up some Python-esque pseudocode illustrating that concept if there is interest -- once I'm at a real keyboard.

Note: After researching this, it seems that your initial approach may actually be better in most cases (Hash table access is O(1) complexity on average), with one key exception: With this approach you can efficiently answer "when is the next event?" rather than simply "is the next event now?". The difference is small, but means that (again speaking generically and not Lua or Factorio modding) you can do things like "sleep for X amount of time" rather than checking every single tick, provided that your insertion algorithm is capable of waking up the executor when it inserts an event that is earlier than the earliest scheduled one. So, most of this post is probably unnecessary but it's probably still insightful so I'm clicking Submit anyways.