N-lane Tick Balancer (Lua library)

[doc]

TickBalancer 1.0.0

Not 100% sure which board to post this in ... please move as appropriate!

I've seen a lot of mods (in fact, pretty much almost every mod) using the following code pattern:

Code: Select all

script.on_event(defines.events.on_tick, function(event)
  if event.tick % 20 == 0 then
    -- Process all your entities here
  end
end)

What's the problem here? Well, handling ticks like this certainly reduces your load to 1/20th. But we still have a problem. 3 times per second we are processing all our entities, and this simply does not scale well. In fact it scales exactly as badly as processing all your entities every frame; in other words, when we have thousands of entities, the player is going to suffer performance problems whether you are checking those entities one tick in 60 or every tick in 60. Arguably the lag is even more jarring when it only happens on some frames rather than every frame!

There's an additional (and slightly hidden) problem; this doesn't play nicely with other mods. If another mod author has used the same pattern (and with any convenient multiple such as 5, 10, 30, 40, 60...) then both your mod and the other mod will both be processing all their entities on the same tick.

So, what is the solution? Well, what you need there is the N-lane Tick Balancer. This will increase your throughput by a factor of 20, assuming the above code.

What this does is spread your tick handlers evenly across every available tick. I think the lane balancer is the most appropriate analogy for this function.

To use this, firstly copy the TickBalancer.lua file into a /lib directory in your mod. Now, just add the following to your control.lua:

Code: Select all

require "lib.TickBalancer"

local balancer = nil

function onInit()
  balancer = TickBalancer.setupForEntity("my-entity-type", "myDataProperty", 20, function(data)
    -- Process data.entity here
  end)
end

script.on_init(onInit)
script.on_load(onInit)

For a default setup (i.e. a global table storing some data against an entity, where the table is called "global.myDataProperty") this is all you need. If you are converting an existing mod to use the balancer then you can use the following in your control.lua to perform a migration. Unfortunately it doesn't seem possible to use a standard migration script as the global data is not yet present (correct me if I'm wrong).

Code: Select all

function onConfigurationChanged(data)
  if data.mod_changes ~= nil and data.mod_changes["my-mod-name"] ~= nil and (data.mod_changes["my-mod-name"].old_version == "0.0.1") then -- Or another version comparison that makes sense
    balancer:migrateEntityData(global.myOldDataProperty)
    global.myOldDataProperty = nil
  end
end

(Note, you must change the storage name, the balancer won't initialise correctly on top of the old table.)

I have attempted to implement this as optimally as possible, however some improvements are surely possible so please leave any suggestions!

You can see the balancer in use in my Blueprint Automated Deployment mod: viewtopic.php?f=93&t=24053

The source is hosted on GitHub, get the latest version and submit any bug reports or pull requests here:
https://github.com/chucksellick/factorio-tick-balancer

[Koub]

[Koub] Moved the topic to "Tools > Development-Tools, because I feel it's the right place for it. Feel free to suggest better place if you don't agree .
[Edit] I was hesitating with viewforum.php?f=96 (for the library thing).

[Klonan]

Code: Select all

script.on_event(defines.events.on_tick, function(event)
  if event.tick % 20 == 0 then
    -- Process all your entities here
  end
end)

This actually works fine for 95% of mods,
If you have less than say, 200 entities, or you're just doing stuff with player characters, it will be fine.

What i have found to work is a simple way of spreading the load over multiple ticks,

Code: Select all

script.on_event(defines.events.on_tick, function(event)
for k, entities in pairs (global.my_entities) --Iterates over all the entities i want to update
  if k % 500 == game.tick % 500 then --This means only 1 in 500 entities is updated every tick, this works well for maybe 10,000 entities
    update(entities)
  end
end
end

[Adil]

[Koub] Moved the topic to "Tools > Development-Tools, because I feel it's the right place for it. Feel free to suggest better place if you don't agree .
[Edit] I was hesitating with viewforum.php?f=96 (for the library thing).

I do believe this is a library rather than devtool as it is used by mod in runtime, not a by modder to output a mod unrelated to the presented code.

@doc:
Well, those are some l33t lua skills, way out of my understanding. What I notice though is:

Code: Select all

  
  script.on_event(defines.events.on_built_entity, onBuiltEntity)
  script.on_event(defines.events.on_robot_built_entity, onBuiltEntity)
  script.on_event(defines.events.on_player_mined_item, onMinedItem)
  script.on_event(defines.events.on_robot_mined, onMinedItem)
  script.on_event(defines.events.on_entity_died, onEntityDied)

  -- Handle ticks
  script.on_event(defines.events.on_tick, function(event)

I believe it is called for each entity modder tries to register.
You do know, that

Code: Select all

script.on_event({event_codes here}, handler) 

just takes the "handler" and plugs it instead of previously registered one, right?
Thus it seems that your library not only supports single type of entity, but also will be completelly disabled if the modder registers his own handlers of on_built and on_entity_died events. And while I see dataconstructor, I fail to notice datadestructor method being accepted.

You can see the balancer in use in my Blueprint Automated Deployment mod: viewtopic.php?f=93&t=24053

Also, I can't see it there

Also, need manual
I've also took liberty to notify the people in that thread about this release. Do you think the threads are related?

@Klonan

This actually works fine for 95% of mods,
If you have less than say, 200 entities, or you're just doing stuff with player characters, it will be fine.

Surely, this depends on the type of handling you perform. Say those artifact collectors spam find_entities() function like crazy and if you don't stagger even a dozen of those, the stuttering will become noticeable.

[doc]

[Koub] Moved the topic to "Tools > Development-Tools, because I feel it's the right place for it. Feel free to suggest better place if you don't agree .

Thanks, yes this seems appropriate.

This actually works fine for 95% of mods,
If you have less than say, 200 entities, or you're just doing stuff with player characters, it will be fine.

Yes certainly, many mods do not need this optimisation. But, if you have any player-buildable entity, do you know how many of them players might want to build in their megabase? And the problem is compounded if players are running multiple entity mods.

What i have found to work is a simple way of spreading the load over multiple ticks,

Code: Select all

script.on_event(defines.events.on_tick, function(event)
for k, entities in pairs (global.my_entities) --Iterates over all the entities i want to update
  if k % 500 == game.tick % 500 then --This means only 1 in 500 entities is updated every tick, this works well for maybe 10,000 entities
    update(entities)
  end
end
end

This is nice and simple and certainly better than the standard for most cases, however you are still looping over the entire list and calculating (k % 500) for each item every tick. As you say it's ok for a certain number of entities. But the TickBalancer sorts the entities into lists in advance so it only has to loop over the required entities and no more.

Code: Select all

  
  script.on_event(defines.events.on_tick, function(event)

I believe it is called for each entity modder tries to register.
You do know, that

Code: Select all

script.on_event({event_codes here}, handler) 

just takes the "handler" and plugs it instead of previously registered one, right?

Ah .... thanks for pointing that out. It's not entirely obvious from the API docs. And of course I didn't test it with more than one entity Still this isn't a total disaster, for the case of a single entity it's still useful, and I'll add some additional support for more complex cases.

Also, need manual

Yes, my documentation writing is terrible. Will fix this

I've also took liberty to notify the people in that thread about this release. Do you think the threads are related?

Thanks for bringing that thread to my attention, it's certainly a similar idea. I did consider releasing this as a standalone utility mod, providing hooks through the remote interface. However ... this would present its own challenges, and I am also not sure of the performance of remote interface calls (tho maybe I could pass a callback function through the interface?). Even a small overhead becomes significant in a megabase. And it's much easier for mod authors to manage a dependency when it's just a file in their mod (which they can adapt to suit). Maybe with the new mod portal it will be easier for players to install dependencies. Side note: I come from a Javascript and node.js world where packages tend to have many (sometimes 100s) small utility dependencies. This turned into something of a catastrophe recently when one developer pulled one tiny package (just 11 lines of Javascript!) from NPM over a naming dispute, completely breaking numerous high-profile projects which depended on it. Gory details here: http://www.theregister.co.uk/2016/03/23 ... pad_chaos/

[Adil]

I keep forgetting about this.
While Klonan's code from above contains silliness on many layers, what would be advantages of this library over something as simple as the following?

Code: Select all

global.count=1;
interval=60
function update()
    local entities=global.entities
    local count=global.count
    for i = count,#entities, interval do
         update(entities[i])
    end
    global.count= global.count % interval+1
end

[doc]

I keep forgetting about this.
While Klonan's code from above contains silliness on many layers, what would be advantages of this library over something as simple as the following?

Well, my library provides more functionality, such as storing a custom data object against each entity, and registering your entities for you when they are created or destroyed. In the latest version (which I haven't actually released ... will rectify this later) this is all done in a way that seems, from my research, to be as optimal as possible (including actually adding/removing entities which can be a slow operation on large tables).

That aside, for the very simple case where you just want to loop over some entities, yes your version is pretty optimal and I hadn't actually thought of doing it that way. I don't know without benchmarking, however, whether your entities lookup might cause this to be slower than my ipairs loop which gives a handle to the object directly.

Small bugfix, I think you need to change the last line to:

Code: Select all

global.count = (global.count + 1) % interval

Also there are some subtleties to beware of with this approach. What happens if you remove or add something to global.entities inside the loop? Results will be unpredicatable.

Anyway, in part the purpose of this thread was simply to encourage mod authors to think a bit more about this aspect of performance, and it's always good to have multiple solutions to fit different cases

[Adil]

Just to add to a discussion here a bit.

Small bugfix, I think you need to change the last line to:

Code: Select all

global.count = (global.count + 1) % interval

I don't think so, when

Code: Select all

global.count=intreval - 1

Your suggestion will result in

Code: Select all

global.count=0

and tables are usually indexed from 1.
I've used the code in a pair of mods.

Also there are some subtleties to beware of with this approach. What happens if you remove or add something to global.entities inside the loop? Results will be unpredicatable.

Yep, that's the idea. No safety, only speed. (it's a bit of ocd)
I remember seeing notion of numerical loops being faster than iterators somewhere on the internet. And I doubt ipairs could get a direct link to an object without doing entities lookup itself.
Additions to table don't cause problems, they're just ignored for the current run, and seeing how interval is reasonable to be 60 or more, that's a lot to add for this fact to matter.
Removal, well it's a known feature of the numeric loop.
Also, you can do it backwards:

Code: Select all

for i=#entities - count, 1, -1 do
...
end

[doc]

Your suggestion will result in

Code: Select all

global.count=0

and tables are usually indexed from 1.

Oh, you are right. For some reason (due to the spacing I think) I misinterpreted your code as:

Code: Select all

global.count= global.count % (interval+1)

It's probably a case where I'd use unnecessary brackets around (global.count % interval) just for readability, that's my own OCD right there

I remember seeing notion of numerical loops being faster than iterators somewhere on the internet. And I doubt ipairs could get a direct link to an object without doing entities lookup itself.

Yep, numerical loops are definitely faster, however there is something it you might not be aware of with tables. Any lua object can be used as a table key.

In other words:

Code: Select all

-- Add some data
function entityCreated(entity)
  local data = {foo=bar}
  global.entities[entity] = data
end

-- Look up the data
function getData(entity)
   return global.entities[entity]
end

-- Delete the data
function entityRemoved(entity)
  global.entities[entity] = nil
end

-- Loop through entities
function iterateEntities()
  for entity,data in pairs(global.entities)
     -- Do stuff
  end
end

Note use of pairs instead of ipairs.

So the data can be looked up for a given entity extremely quickly without having to loop through your entities list. Remove also becomes a very fast operation because keys no longer need updating in the table. Also the entity itself doesn't even need to be stored on the data object.

Not saying the above could necessarily be faster, but in a scenario where lots of lookups and delete operations tend to happen, it could end up being; anyway it's a useful property to be aware of!

In reality without running benchmarks it's almost certainly better to go with your simpler code

[ArderBlackard]

Code: Select all

-- Add some data
function entityCreated(entity)
  local data = {foo=bar}
  global.entities[entity] = data
end

-- Look up the data
function getData(entity)
   return global.entities[entity]
end
...

If it is intended that game entities will be used in this code - then it is not guaranteed to work across different events. Every time the event handler is raised - it may receive a completely different Lua-table for the same ingame entity. They have __eq() metamethod defined so they will be considered equal when compared using '==' operator, but as a table keys they will not match.

[doc]

If it is intended that game entities will be used in this code - then it is not guaranteed to work across different events. Every time the event handler is raised - it may receive a completely different Lua-table for the same ingame entity. They have __eq() metamethod defined so they will be considered equal when compared using '==' operator, but as a table keys they will not match.

Oh, that's unfortunate. I hadn't tested this yet but it sounds like things would have quickly broken.

What would be *really* nice in that case is if every entity had a unique Id assigned that was available in the API. This way data lookups could at least be easier than looping through a gigantic table.

Although, what would be even *nicer* is if the entity API actually provided an inbuilt system for modders to store custom data against an entity (and if this data would also be stored in blueprints...)

[ArderBlackard]

What would be *really* nice in that case is if every entity had a unique Id assigned that was available in the API. This way data lookups could at least be easier than looping through a gigantic table.

Totally agree. This idea was discussed here: viewtopic.php?f=28&t=13369. @Rseding91 stated that the IDs may be exposed for entities that actually have them (entities with force).

Although, what would be even *nicer* is if the entity API actually provided an inbuilt system for modders to store custom data against an entity (and if this data would also be stored in blueprints...)

Unfortunately I don't think it's possible. As far as I understand, the entity we get as a result of Lua API call or as event handler parameter is a Lua-table created on-the-fly from the underlying C++ object. As the source objects have a rigid structure - there is no way of attaching any additional information to it.

[doc]

Unfortunately I don't think it's possible. As far as I understand, the entity we get as a result of Lua API call or as event handler parameter is a Lua-table created on-the-fly from the underlying C++ object. As the source objects have a rigid structure - there is no way of attaching any additional information to it.

Well ... as a coder I can say that nothing is impossible But a lot of things are very hard or would have serious performance implications. What I would imagine is a special API that you'd access via entities exposing an entity.data object providing the functionality (not just arbitrary named fields directly on the entity, and preferably the data scoped to your mod). I can imagine this having performance consequences, so maybe it could only be enabled by modifying a bool on the entity prototype, and perhaps *only* allowed for custom entities, not any of the base entities - maybe even only on a special "custom-entity" base type allowing extended functionality. Some part of this would be by biggest wish for the modding API, as currently the entity system can feel extremely restrictive when trying to do anything more complex than, e.g. just creating a faster inserter or a longer underground belt... Anyway looking forward to what changes come in 0.13, hopefully there will be some cool new stuff to play with.

[ArderBlackard]

Well ... as a coder I can say that nothing is impossible

I'm a coder too and I know that But it can be just too expensive (in any sense) to implement.

What I would imagine is a special API that you'd access via entities exposing an entity.data object providing the functionality (not just arbitrary named fields directly on the entity, and preferably the data scoped to your mod). I can imagine this having performance consequences, so maybe it could only be enabled by modifying a bool on the entity prototype, and perhaps *only* allowed for custom entities, not any of the base entities - maybe even only on a special "custom-entity" base type allowing extended functionality.

I think the idea with exposing IDs can be more flexible - you will have a way of storing data for any entity in Lua, no changes would be required for the entities inner structure and the data can be truly arbitrary.

[doc]

I think the idea with exposing IDs can be more flexible - you will have a way of storing data for any entity in Lua, no changes would be required for the entities inner structure and the data can be truly arbitrary.

The big issue with the Id method (which isn't any different to current lookups) is blueprints. Your custom data can never be stored in a blueprint. This severely limits things if you have a custom settings GUI with your entity, those settings can't be copied in a blueprint, so you can't build really complex setups using modded entities then clone them in your factory or share them as blueprint strings. Edit: Just to clarify, I am talking about for instance a custom type of combinator or something else fancy that uses circuit networks with some custom options.

A custom data dictionary (just a simple key/value store only allowing simple types) could support the data being copied into the blueprint and also serialised in the blueprint string.

Also edit: I would also be fine with something like an on_blueprint_created hook that allowed you to scan the blueprint and inject additional data, and a corresponding hook for unpacking the data when the entities are deployed by the bots. But this seems way more complicated for the modder to implement than wrapping the whole thing up in the kind of data API described, and would to boot greatly simplify this very common case that a lot of mods are using where they are storing this data in global tables.