Manual: balance load in on_tick

[Optera]

Since i couldn't find something similar and I guess most modders will use on_tick I'm going to start this thread as help to reduce load from on_tick events.
If you have a way to distribute load across multiple ticks, please add it to this thread.

single modulo

Code: Select all

if game.tick % update_interval then
  for k, sensor in pairs(global.Sensors ) do
     Worker(sensor)
  end				
end	

Added only for completion.
Con:

• no load distribution among ticks

modulo compare

Code: Select all

for k, sensor in pairs(global.Sensors ) do
  if k % update_interval == game.tick % update_interval then
     Worker(sensor)
  end				
end	

Pro:

• spreads load from Worker evenly across corresponding modulos

Con:

• works only with global.Sensors as array
  unordered sets will break this method

[Klonan]

With the modulo compare, you can rearrange it so you only need a single modulo:

Code: Select all

function on_tick(event)
  local tick = game.tick
  for k, v in pairs (global.table) do
    if (k + tick) % interval == 0 then
      do_something(v)
    end  
  end
end

[Optera]

With the modulo compare, you can rearrange it so you only need a single modulo:

That's smart.
Do you have something working for unordered sets by chance?

[Rseding91]

With the modulo compare, you can rearrange it so you only need a single modulo:

That's smart.
Do you have something working for unordered sets by chance?

Code: Select all

local i = 1

In your loop increment it by 1 and use it as the index.

[Mooncat]

After reading FFF-161, I have an idea but still haven't tried it yet (or maybe I did for the creative chests in CM unintentionally):

When you add items into the global table, separate them into sub-tables indexed by integer: for the first item, you add it into the table at [1], next at [2], and so on...

Code: Select all

function insert_sensor_at(i, sensor)
  if not global.Sensors[i] then global.Sensors[i] = {} end
  table.insert(global.Sensors[i], sensor)
end

1st sensor: insert_sensor_at(1, sensor)
2nd sensor: insert_sensor_at(2, sensor)
n-th sensor: insert_sensor_at(n % interval + 1, sensor)

Then, in on_tick, you only loop through the sub-table at particular index:

Code: Select all

function on_tick(event)
  local tick = game.tick
  local index = tick % interval + 1
  for k, sensor in pairs(global.Sensors[index])
    Worker(sensor)
  end
end

Although it is still O(n), but I guess it can improve UPS a little bit?

[Optera]

When you add items into the global table, separate them into sub-tables indexed by integer: for the first item, you add it into the table at [1], next at [2], and so on...

Code: Select all

function insert_sensor_at(i, sensor)
  if not global.Sensors[i] then global.Sensors[i] = {} end
  table.insert(global.Sensors[i], sensor)
end

Is there any advantage in having to add checks so it wont become an unordered set? When you can do this

Code: Select all

 table.insert(global.Sensors, sensor)

or if you want to add in the middle of a table. With insert taking care of moving all following indexes up 1.

Code: Select all

 table.insert(global.Sensors, index, sensor)

Another thing I stumbled across:
According to this stackoverflow thread table[#table+1] = value is a little bit faster for appending at the end of tables than table.insert(table, value)

[Mooncat]

Did you mean the if check? It is just for ensuring the sub-table exists so it doesn't show error. It doesn't matter if you use sorted or unsorted set, the trick is to separate the whole big global.Sensors into smaller global.Sensors[1 ~ interval].

As stated in that FFF, the problem of having one global.Sensors is that you still need to loop through the whole set and check

Code: Select all

if (k + tick) % interval == 0 then

for each item. Maybe the problem is smaller than the FFF because the numbers are straightforward in our case. But still, my idea can reduce the number of modulo operations so, in theory, it can save some UPS.

Maybe we should carry out a test for them. Also for table[#table+1].

[Optera]

I meant checks to make sure i in function insert_sensor_at(i, sensor) is always continuous. If you happen to remove just the right sensors it might end up like this: global.Sensors[1], global.Sensors[2], global.Sensors[4] which behaves a bit odd. I think #global.Sensors would return 2 for example.

You'd have rebuild the array on every create/remove. Depending on how often you update vs rebuild the array it may not improve performance at all.

[Choumiko]

Maybe we should carry out a test for them. Also for table[#table+1].

Someone more or less already has: https://springrts.com/wiki/Lua_Performance

[Optera]

Maybe we should carry out a test for them. Also for table[#table+1].

Someone more or less already has: https://springrts.com/wiki/Lua_Performance

Thanks for linking this. I had no idea for loops in lua had such huge performance differences. Getting rid of for pair loops should yield a lot more than any other optimization.

[Mooncat]

I meant checks to make sure i in function insert_sensor_at(i, sensor) is always continuous. If you happen to remove just the right sensors it might end up like this: global.Sensors[1], global.Sensors[2], global.Sensors[4] which behaves a bit odd. I think #global.Sensors would return 2 for example.

You'd have rebuild the array on every create/remove. Depending on how often you update vs rebuild the array it may not improve performance at all.

hm... you don't need to make sure i is continuous. But I think some more works are needed in order to make the sensors to be evenly distributed. Like another array of indexes sorted by the array sizes.

And no, don't use #global.Sensors because they are arrays. #global.Sensors doesn't represent the number of sensors, but the number of sensor arrays.

Maybe we should carry out a test for them. Also for table[#table+1].

Someone more or less already has: https://springrts.com/wiki/Lua_Performance

That's a good article. Thanks for share.

[Supercheese]

Maybe we should carry out a test for them. Also for table[#table+1].

Someone more or less already has: https://springrts.com/wiki/Lua_Performance

Thanks for linking this. I had no idea for loops in lua had such huge performance differences. Getting rid of for pair loops should yield a lot more than any other optimization.

Pretty sure Factorio has a custom implementation of pairs(), which could make those performance tests invalid for Factorio applications.

[Optera]

It seems factorio performance behaves similar, but the effects are neglectably small.
For Inventory Sensor 1.1.3 i changed every possible for pairs to for i, #table and table.insert to table[#table+1] performance only went up by 0.06 UPS at best on my test map and oddly enough stayed exactly the same on some other maps.
in Numbers on the same save:
Inventory Sensor 1.1.1 ~0.28
Inventory Sensor 1.1.3 ~0.24

[bobingabout]

I was thinking of something along the lines of

Code: Select all

if tick % sizeof(global.table) == 0 then

but then it hit me.... how do you even get the size of a table?

[Optera]

I was thinking of something along the lines of

Code: Select all

if tick % sizeof(global.table) == 0 then

but then it hit me.... how do you even get the size of a table?

If it's an array you can use #table, if it's an unordered set you have to iterate through the entire thing with for pairs and count = count+1
For anything mostly run inside on_tick arrays seem the better storage strategy.

Using unordered sets does have advantages though.
If you store entities indexed by unit_number you don't have to use for loops when you get events triggered by entities and can access directly with global.entities[event.entity.unit_number].
Inventories are also unordered sets, with item name being the key which makes it a bit slower to read everything, but makes it very fast updating the count of a single item.

[bobingabout]

In that case, you'd probably end up with something like...

Code: Select all

-- Count tracker. would definitely be better to keep track of the size externally to on_tick
global.count = 0 
for k, sensor in pairs(global.Sensors) do
  global.count = global.count + 1 -- would be so much easier if we could do count++ like in C
end

--in on_tick
local count = 0
for k, sensor in pairs(global.Sensors) do
  count = count + 1
  if game.tick % global.count == count then
    --do stuff with sensor or global.Sensors[k]
  end
end

Alternatively, a slightly less safe but faster method, assuming you use an indexed table, and global.count is updated external to the tick routine:

Code: Select all

i = game.tick % global.count
--do stuff to global.Sensors[i]

[Macros]

I use a while loop during on_tick. This method iterates over 1/60th of the table each tick, starting over from the beginning once 60 ticks have passed:

Code: Select all

local TICK_INTERVAL = 60

script.on_event(defines.events.on_tick, function(event)
  local size = #global.ArrayOfThings
  local i = global.Counter -- global.Counter starts at 1, and increments by 1 every tick, resetting to 1 when global.Counter == TICK_INTERVAL
  while i <= size do
    local thing = global.ArrayOfThings[i]
    if thing ~= nil then
      <...do stuff...>
    end
    i = i + TICK_INTERVAL
  end
  global.Counter = (global.Counter % TICK_INTERVAL) + 1
end)

for is more efficient when iterating over an entire table, but my tests have indicated that while is more efficient when you only want a small fraction of the table on any given tick.

[DedlySpyder]

It seems factorio performance behaves similar, but the effects are neglectably small.
For Inventory Sensor 1.1.3 i changed every possible for pairs to for i, #table and table.insert to table[#table+1] performance only went up by 0.06 UPS at best on my test map and oddly enough stayed exactly the same on some other maps.
in Numbers on the same save:
Inventory Sensor 1.1.1 ~0.28
Inventory Sensor 1.1.3 ~0.24

I've had similarly small results from testing between the two. Powered entities had a big freeze (several seconds on a large map) and changing between the two had fairly inconclusive results (the minor variation in the search itself was about the same as what I might have saved).


As for this topic in general, I am going to need something like this soon, and here is my take on it:

Every time I add something to the global table I will recalculate a global variable (offset). This offset will be the number of items I need to check divided by how often (so 120 items divided by 60 ticks) rounded (not sure if I should floor or ceiling yet). Then, every tick take the modulo of the tick by the interval (60) times my offset, and check the offset in items. So if we're on tick 42 from above, we check 84 and 85.

I've yet to actually try this, but it seems to make sense in my head and written out.