Altering the algorithm of the update cycle of Factorio

[BenSeidel]

The current behaviour:
Entities are either “Active” or “Inactive”. Active entities are processed each tick, updating various aspects of the entity. Inactive entities are not processed each tick, but are woken up by other entities.

Changing the processing scheme to be an event based processing system with queues coupled to the electric networks will reduce the amount of processing required each tick by a significant amount (easily 5x faster for most entities).

The algorithm is based upon a neural network message propagation system and when you think about it abstractly, factorio is a neural network.

Neural network algorithm:

All entities that are currently classed as inactive, are still inactive.

All entities that require power that are not attached to an electric network and whose buffer is depleted are inactive. When an entity is detached from an electric network and its buffer becomes depleted, it becomes inactive. When an entity is attached to an electric network, it becomes active.

So, that's the simple parts out of the way.

Active entities becoming more passive: event based updates

All entities within Factorio should only be processed when they have some discrete change in their behaviour. For example, an assembler finishes producing an item, or an inserter drops an item. So for the 5 seconds that an assembler is producing a red science pack, the assembler should not be given any processing time.

To achieve this, each entity must be able to calculate a time stamp for their next event. If this calculation is done based on a fully powered entity, then the absolute ordering of the event list for a particular electric network will always remain correct, even when the electric network is running at less than 100%. The main game loop then loops through each electric network, calling each entity's “update” function only if enough time has passed for the entity to have completed its task.

Because Factorio has electricity priorities, each electric network is then split into sub-groups, each with their own event queue. It is trivial to calculate the amount of power supplied to each sub-group and then to process the required amount of the group's event queue.

Rendering:
If each entity keeps their time stamp for their last update, then all that needs to be done is to calculate how far through the process the entity is currently, rendering the result.

Notes:
Anything that is a “burner” exists on the “burner” electric network.
A timestamp is not a wall-clock or tick count. It is an orderable series of events. A good system for this would be the number of watts produced by the electric network.
This is not a complete algorithm because I don't know how Wube want their software to run. Corner cases exist such as an entity that is connected to two networks.
Although I mainly used assemblers as my example, it can be applied to all entities, including belts, trains, bots, etc.
Changes to other systems may be required as this represents a change from a pull based system to a push based system and is usually a difficult transition.
If Wube is serious about making Factorio multi-threaded then this, or something similar, will have to be done as there need to be synchronise-able points in the code, aka “events”

Anyway, its just an idea. If it has merit please let me know, I am happy to discuss it in far more detail with anyone that is interested.

[ssilk]

What if the power fails? The assembly doesn't always take X seconds, sometimes it takes much longer. Same with nearly anything else.

[Rseding91]

The scheduling of each entity if they ran based off power flow would cost more time than just running update() on each active entity each tick. There's also the power draw portion that would change the power usage graph from a steady amount to spikes up/down as things tick over time. Additionally power is almost always available to the entities so they would run update regardless each tick.

The main slowdown in Factorio now is not CPU speed but the amount of RAM that has to be touched each tick to update all entities needing updating. Waiting for the CPU to load some bit of information from system memory is incredibly slow compared to how fast the CPU can work.

[Vegemeister]

It sounds to me like the idea is that powered entities *don't* have to update on each tick. They'd only have to update when something happens. So an assembler that takes 8 seconds to produce it's output would only need to update once every 8 seconds under non-brownout conditions.

The way you'd make it work with brownouts, is that each electrical network knows the total energy it has generated since the beginning of time. When updating an entity, calculate the energy it needs to perform its next action, add it with the current network energy, and schedule the entity for updating again whenever the network energy reaches that value. For animations, you could interpolate based on the current network energy.

The thing I anticipate being difficult is interactions between different networks, and interactions between on-network entities whose speed depends on available power and off-network entities like belts and trains. Perhaps you could allow entities to schedule other entities for immediate update. So for example items becoming available on a belt could schedule any pickers in reach.

[BenSeidel]

Hmmm... I think that the main idea of the algorithm was missed. Or a better description, the coupling to the power network was misinterpreted.

Let me do a simple example using just assemblers. Assume that the player has put in maximum stacks of the items, or that the items magically appear. This is about the scheduling of the updates caused by the assembly machine, not about its interaction with the rest of the world. The figures for the electric network and all other numbers are completely made up and are used ONLY for demonstration purposes. I don't have the ability to check to find out what the in game figures are. Updates are not "game ticks" as they are now, ie 1/60th of a second, but could be interpreted as maybe 1 a second (too many updates at 60/second for the example to be readable). I also really hope that my numbers are correct, if you see any incorrect calculations let me know so I can fix the example.

Information about the numbers:
Electric networks produce Energy per update (E).
Copper cable takes 4 updates to create an item.
Green circuits takes 10 updates to create an item.
Assembly machines use 200 energy per update (200E).


update 1: player places an assembly machine to produce copper cable. It is not attached to an electric network. It is inactive.

update 2: player creates an electric network, producing 600E, and attaches it to the first assembly machine. The assembly machine uses 200E, so an "event" with a timestamp of 4 (4 ticks at full power) is created in the queue. A maximum power drain of 200E is set in the electric network.

update 3: The electric network produces 600E. Max drain is at 200E, so 400E is discarded (maybe into accumulators?). Queue is advanced to 1 (1 tick at 100%) so No events are processed because the first event is at 2.

update 4: see tick 3, but with a new queue value of 3.

update 5: queue value is now 4. First event is at 4, so assembly machine is processed producing one item and beginning the next item. A new event at 8 is placed in the electric network queue (current event of 4 + 4 more at 100%).

update 6: queue value is now 5, no events are processed. Player puts 2x speed modules into first assembly machine, increasing speed by 100% and power drain by 150%. Assembly machine is 25% through update, because its last "update stamp" is at 4 and the network is now at 5 with the next update queued at 8 ( (5 - 4) / 4) = 0.25. It now calculates a new power consumption of 500E, updating the network's max drain by 300E (initial drain - new drain). It also calculates the number of ticks at full power to complete the current action, placing the event it the queue at (5 + ( 0.75 * 2)) = 6.50.
(5 + ( 0.75 * 2)) -> Electric network current tick + remaining process %age * total duration.

update 7: The electric network produces 600E. Max drain is at 500E, so 100E is discarded (maybe into accumulators?). Queue is advanced to 6, so No events are processed because the first event is at 6.5.

update 8: The electric network is advanced to 7. Initial assembly machine is processed, creating a new event at 6.5 + 2 (completed time + time for new process) = 8.5. Player places 2 new assembly machines, one producing copper cable, one producing green circuits. A new event for the copper cable is created at 7 + 4 =11. A new event for green circuits is created at 7 + 10 =17. Max drain of the electric network is increased by 200E for each new assembly machine to 500E + 200E + 200E = 900E. It becomes night, reducing max power output to 100E. Electric network is now running at 11% capacity.

update 9: The electric network is advanced to 7.111, as it can only produce 100E of the required 900E. No events are processed because not enough power has been supplied to any of the attached assemblers.

update 10: The electric network is advanced to 7.2222, as it can only produce 100E. Note that IF the network was able to satisfy 100% of the power requirements then the initial copper wire assembler would have finished, but it has not.

As you can see, for most of the updates none of the entities were touched, only the initial event in the electric network was touched each tick to see if anything should be processed. All information about the electric network is updated continuously, there are no "power spikes" and the graph remains consistent. This is the essence of the algorithm, it is by no way complete. Before anyone says anything about the numbers, it's possible to do a sequence of numbers that wraps around itself without losing its ordering.

I hope that this example shows you why touching each entity is not required. I am still eager to discuss further.

Thanks.

*edit: realised that this it's actually a time dilation algorithm, not a time advancement algorithm, so updated it to be more inline with the requirements.

[BenSeidel]

I think my time advance algorithm in the example is incorrect as it advances too quickly, when I get time I will correct it.

edit: has now been corrected.

[ssilk]

Hm. This would be a very theoretical discussion.

I remembered a discussion with slpwnd in Prague, who said, that their first approach was fully object orientated but they need to change this completely due to performance reasons. And so also with my experience: I saw so many ideas. Simplest example: If database is too slow add another index. Of course. But at some point the updates to the index for one change takes longer than 1000 reads.

So theory is one thing, but practice only can show you, if it really works in all cases.

[BenSeidel]

Vegemeister, you seem to have it correct.

Hm. This would be a very theoretical discussion.

I don't believe this is a very theoretical discussion but an empirical one. A lg(n) algorithm is always superior to a linear algorithm, given a large enough set of data to process, and as the current linear time one is not cutting it very well, maybe some experiments with a lg(n) time one is worth it. It's well know how to do an ordered queue with lg(n) update time with constant time access, and that is essentially all the algorithm is.

Also, your examples about the database index and the object orientation change are only about altering the constant multiplier of the function. Relational database have a lg(n) amortised update time for an index. So, have two indexes that's 2xlg(n), three that's 3xlg(n). It's not changing the family of the function, only the constant.

Real object orientated code uses function pointers to resolve the function call, that is at least one additional cache miss to load the function pointer from the object, which really is only a constant cost per invocation. The issue is that these cache misses occur within tightly bound loops, so the constants propagate up in a multiplicative way into an N or what ever the function of the family is. Add an extra N to an already N function and you get a 2N function, again still linear but twice as slow.

Anyway, so far the optimisations in Factorio only seem to be focused on the constant factor, not on the functional family. I was offering a way of getting the functional family of the updates of some aspects of the game from a linear one to a logarithmic one. I also doubt that it is a one size fits all solution. Maybe inserters, when grabbing from a belt, would give better performance when run the way they are now because there is the continual "reaching" for the moving item. The beauty of this system is that you don't have to include all the entities. Maybe JUST inserters that move items from a box to box, get a performance increase.

[ssilk]

Hm. It sounds useful. On the other hand there are some optimizations possible in the current code, which might have a similar speed increase. So in the end it would be an economical decision in this case.

PS: You could prove that, if you ask the devs for the code to test your ideas.

[BenSeidel]

Haha, I could IF I could write C++.

[ssilk]

No, you can, if you will learn it.

De-facto: Good idea, maybe a dev will see this, maybe they already thought about this. We cannot know it here.

I will not hinder any longer to discuss this in theory; I just wanted to avoid a long discussion and disappointed faces.

[Vegemeister]

I don't believe this is a very theoretical discussion but an empirical one. A lg(n) algorithm is always superior to a linear algorithm, given a large enough set of data to process, and as the current linear time one is not cutting it very well, maybe some experiments with a lg(n) time one is worth it. It's well know how to do an ordered queue with lg(n) update time with constant time access, and that is essentially all the algorithm is.

I don't think that's quite right. Scheduling a single entity update would be O(log(n)), but you still have to handle all the entities, so the whole thing would be O(n*log(n)), which is worse than the current method (AFAIK) by a factor of log(n). But it would make a big improvement to the constant factor. An interesting difference in behavior would be that factories with huge numbers of assemblers would perform just as well as factories with a few assemblers working very fast due to beacons.

[BenSeidel]

I don't believe this is a very theoretical discussion but an empirical one. A lg(n) algorithm is always superior to a linear algorithm, given a large enough set of data to process, and as the current linear time one is not cutting it very well, maybe some experiments with a lg(n) time one is worth it. It's well know how to do an ordered queue with lg(n) update time with constant time access, and that is essentially all the algorithm is.

I don't think that's quite right. Scheduling a single entity update would be O(log(n)), but you still have to handle all the entities, so the whole thing would be O(n*log(n)), which is worse than the current method (AFAIK) by a factor of log(n). But it would make a big improvement to the constant factor. An interesting difference in behavior would be that factories with huge numbers of assemblers would perform just as well as factories with a few assemblers working very fast due to beacons.

Hmm, now its a theoretical discussion....

So, based on the description I gave of the algorithm, yes the insertion is logarithmic, and yes you have to do one for each entity queued, giving N*lg(N) update, but that is based off a priority queue with an insertion time of lg(n). I would not use a priority queue but a linear time sorting algorithm for the insert, thereby taking the cost per queued entity down to a constant for an insertion. If you couple that with a priority queue containing buckets of sqrt(N) size, then you get a sqrt(N)*lg(sqrt(N)) function: Constant cost in ordering of sqrt(N) items with lg(sqrt(N)) bucket location cost. But as factorio does not have a uniform distribution of queued events (not much takes a long time), the exact bucket distribution will not allow for lg(n) size, but with a significantly large effort it could be close.

But it's also not the constant that is being altered giving the performance, but the N. N is no longer all the entities (or a specific type of entity), but the number of entities that need to be processed in a given tick. The algorithm is an adapted system synchronisation algorithm, and in its original use its a lg(n) vs the original linear, but there are different constraints and different N's on that system. All in all for longer running entities this algorithm will give a performance boost.

Ok, I know that it's not sqrt(N)*lg(sqrt(N)) for the general purpose queue, but for the life of me I can't remember what it is, nor can I see where I have gone wrong... Is it just lg(sqrt(N))?? hmm... maybe a cup or two of coffee will help...

Edit:
My original statement that it's a linear time algorithm vs a linear time algorithm is definitely incorrect and I apologize for it. It's a bad habit that I have developed. What I meant (but did not specify) is that you are saving linear time at the cost of a logarithmic overhead. I spend a lot of time discussing algorithm trade-off points, and unfortunately we have (never noticed till now) been using a comparison between the cost vs benefit portion of the function as if they were absolute costs. We also only use N, but no N is ever the same as another N. It's too confusing when you have P's, Q's, R's etc everywhere. So my original statement where I said that the lg(N) is always better than a linear one should be read as the extra cost of lg(N/duration) is always better when you save an N, so long as the N is larger than the N/duration where N is the number of items moved from the old to the new, hence the comment that the inserters picking up off the belt may not work.

Edit 2:
Changing my answer again. Vegemeister threw me right off with the whole N*lg(N) update time. The algorithm above is indeed logarithmic when compared to the current linear "update the world". The issue is, what are we measuring against. Its not a measure of work compared to the number of items, but the duration of the task. Currently each entity gets updated N times doing a task that takes N ticks. The algorithm above requires lg(N) update time for an entity doing a task that takes N ticks. If you want to compare the complete tick updates over the duration of a task then, as Vegemeister said, the algorithm above is N*lg(N) but then the current algorithm is N^2. To be more specific its N*lg(D) compared to N*D, with D being the duration of the task and N being the number of entities doing the task.

[BenSeidel]

Right, now for the actions of the entities that need to be updated every few ticks. Lets make an assumption that its a performance reduction if you use the above algorithm for tasks that take 5 or less ticks to complete. It may not be 5, could be more or less, but it's a magic number that needs to be empirically tested. It could also vary with the size of the factory. I am also assuming that it is possible to assign an integer to an entity denoting the order in which it needs to be updated. There are ways to create such systems if it's not already the case. The update order is also an assumption I made in the above algorithm, but never mentioned. Also, if there is interest, a change in the scheduling order system will give a way of safely multithreading.

Setup:
Create 5 buckets, one each for the next 5 ticks. Place each entity into their appropriate bucket. If it needs to be updated in the next tick, place it in the first bucket, second tick, in the second bucket, etc.
OnTick:
Grab the contents of the first bucket.
Integer sort the contents based on update order.
Create a new 5th tick bucket.
Loop through the sorted list of entities, updating them and placing them into their next update bucket.

The integer sort is a linear time algorithm, so it only adds a constant overhead to the processing of each item in the list.

The real question here is if the constant overhead of the sorting is worth the saving of not processing the entity every tick. This is quite obvious if the entity is being updated every tick, but in that case use the existing algorithm. Most of it comes down to reducing the cache misses. What is going to require more memory transfers? Loading the required entity's data or the int and the pointer used in the integer sort.

There are some special behaviours that can be made for the buckets as well that may remove the need for the integer sort and hence the original algorithm in the buckets, but it costs memory. Doing this for the first bucket may be worth while, and maybe even for the second bucket. Again empirical data is required, but it should be significantly faster than the current system.


Notes:
The integer sorting, while linear time actually has a reasonably large constant factor. If you are able to keep the entire destination list in cache a binary sort is faster, if not then the number of cache misses per insert is the telling factor for when the swap should be made.
I am making some assumptions about the size and scope of the factories that the developers want people to be able to build. The current numbers of millions of entities may be enough for them.

[BenSeidel]

Is this idea been considered? If it has been dismissed then a reason would be nice to know. I only ask because I can continue to refine it further, but if I am just wasting my time I would like to know.

Thanks.

[bobingabout]

The main slowdown in Factorio now is not CPU speed but the amount of RAM that has to be touched each tick to update all entities needing updating. Waiting for the CPU to load some bit of information from system memory is incredibly slow compared to how fast the CPU can work.

That's one reason why I think the next big update for CPUs will be to have on board RAM. We already have multiple CPU cores in a CPU, and now it's harder to find a CPU without on board graphics than it is to find one with on board graphics. I see the future will have on board RAM too.

[Deadly-Bagel]

So a CPU will have processing, memory and display. Essentially, computers will be powered by another computer xD

[BenSeidel]

So a CPU will have processing, memory and display. Essentially, computers will be powered by another computer xD

They are called coprocessors. Your sound card is an example of this. The 386 (or 286/486? can't remember) had an optional floating point coprocessor.

That's one reason why I think the next big update for CPUs will be to have on board RAM

They already do. It's called cache. Ever since the MMX extension on the Pentium there is literally no difference between the level-X caches, main memory and the page file on the disk except the amount of time it takes to access. Programs don't have any idea where their data is stored because of the page table: a dictionary that contains virtual memory locations to physical memory locations. It's all really interesting the way it's done.

and now it's harder to find a CPU without on board graphics

I don't know of a CPU (modern) that has integrated graphics. I am going to assume that you meant a motherboard with onboard graphics. The main reason to have a motherboard with onboard graphics (in a desktop) is that it allows the chip manufacturers to clear out old stock. This issue won't really ever apply to RAM due to the longevity of each RAM iteration. It gives the RAM vendors many years to clear out old stock because of the timeframe that new RAM is being phased out, so a motherboard will probably never come with on-board RAM.

As for the future of CPU's. The number of cores will still increase, allowing for the continuation of Moore's law. However, the clock rates of them should decrease, eventually sitting at about 800 Mhz, as well as the complexity within each core. Things like branch prediction, loop unwinding, register aliasing, prefetching etc will all be removed from the core. Virtual threads (aka Intel's Hyperthreading) will become larger than the current two threads, probably sitting around 8, but instead of the current hardware context switch, will be an interleaving of instructions.

I believe the future will be an ARM chip capable of running 200,000 concurrent thread each at about 800Mhz. It will be an amazing future. Imagine playing factorio on that! ohh, nevermind.

[orzelek]

I'm not sure why you can't find modern CPU with graphics... most of intels and all AMD APU's have GPU. It's quality (esp on intel) might not be the best but they are there. AFAIK motherboards with GPU are not really made right now - it's either built in into CPU or separate. And it seems to be quite important for intel since there are rumors floating around that they might put AMD GPU into intel CPU's.

On die CPU RAM is currently something that might actually happen (And not the few MB's of cache that all of them have). They did that with GPU's (some AMD ones have HBM memory thats on the same die as GPU) and there is a chance that CPU's could also get it - it's a bit of an unknown still since that would tie your memory amount to CPU model.

Going into high amount of cores of ARM variety is a possibility (or x86/x64 variety too) but currently amount of cores rarely matters for games. Adoption of real multithreading is quite slow in this industry since it tends to be problematic (there are few exceptions like Ashes of Singularity). There was some nice info about this in FFF that talked about potential of multithreading inserters handling thats planned for 0.15.

[BenSeidel]

We are off topic now.

Edit: Wow, things have changed in the last 6 or so years. The onboard graphics processor used to be a pseudo-graphics processor, resembling a repurposed core or some other such thing, now they seem to take up half the dam chip! No wonder we are stuck with 4 core machines.

I weep inside now .