Rolling Event Queue - Optimization

[Vegemeister]

It is my understanding that, with the way the game works now, a few very fast assemblers use less CPU time than a lot of slow assemblers for the same output, because all working assemblers have to be updated on every tick, no matter whether anything interesting happens on that tick or not. This is why most people use heavily beaconed configurations for megabases. But, I think, it doesn't have to be this way.

Suppose you have a length-300 circular buffer of lists of Event objects. That represents the next 5 seconds. The 0th list is the current tick, the 1st list is the next tick, and so on. On each tick, you process all the Events in the 0th list, and step the circular buffer forward by 1 tick.

Simplest case, recipes shorter than 5 seconds: On the current tick, an assembler's output/input buffer contents allow it to start working on a recipe that takes 2 seconds to complete. Record, in the assembler entity's state object, that it {is animating, starting from $frame_number, on $current_tickstamp}. Append an Event to the 120th list in the circular buffer that says the recipe finishes on that tick. Then put the assembler to sleep.

Recipes longer than 5 seconds: On the current tick, an assembler's output/input buffer contents allow it to start working on a recipe that takes 8 seconds to complete. Instead of making an Event to finish the recipe, make an Event to increment the recipe progress by 5/8, and append it to the list at the very end of the buffer. When that tick gets evaluated, you'll create another Event to finish the recipe.

Logistic/construction robots: On the current tick, a robot is dispatched for a job. Calculate how many ticks in the future it will reach its destination (distance/speed), and how many ticks until it runs out of power ( charge/(speed*energy_per_distance + energy_per_time) ), and depending on which will happen first, either create an Event for the robot to collect/deliver its cargo, or an Event for the robot to divert to a roboport for charging. If you want, you could actually determine which roboport that would be and divert the robot immediately. That way, robots on long journeys would travel from roboport to roboport until they were within battery-range of their destination, instead of doing that sawtooth thing they do now.

Inserters: Whenever an inserter starts moving, create an Event on the tick when it will reach the end of its swing.

But what about electricity? Create two numeric circular buffers, per-electric-network, for the next and previous 300 ticks. These are the demand and satisfaction buffers. Whenever you insert an Event into the rolling queue, increment every element of the demand buffer between now and the tick the Event comes due by the power draw of whatever entity it is. (I notice that requires doing per-tick work again, alas. But it's straight vector math.) On each tick, store the fraction of demand satisfied in the satisfaction buffer (should be 1 under non-brownout conditions). When you process an Event for an entity that slows down if insufficiently powered, average the values in the satisfaction buffer since the Event was created, and if the result is less than 1, advance the entity's progress of that fraction of the expected progress and schedule a new Event.

What this all achieves is that instead of updating a working assembler's state on every tick, you update it once when it starts a recipe, and once when it finishes, or once every 300 ticks if the recipe takes longer than that. (300 ticks is just a guess, actually selecting the buffer length would require benchmarking.) Unlike a traditional event-driven simulation with a priority queue, which is O(nlog(n)) IIRC, the rolling event queue makes the assumption that lots of events happen on every timestep, and is O(n*ceil(T/l)), where T is how long in advance events are scheduled and l is the length of the buffer.

[Tekky]

I really like this idea.

Whenever you insert an Event into the rolling queue, increment every element of the demand buffer between now and the tick the Event comes due by the power draw of whatever entity it is. (I notice that requires doing per-tick work again, alas. But it's straight vector math.)

This should not be a problem, because, according to this thread, the main bottleneck of the game is memory bandwidth. Since the memory page containing the circular buffer will already be in the Level 1 CPU Cache, incrementing all 300 elements of the buffer should be very fast. Using SIMD instructions could make this even faster.

What this all achieves is that instead of updating a working assembler's state on every tick, you update it once when it starts a recipe, and once when it finishes, or once every 300 ticks if the recipe takes longer than that.

If I understand your proposal correctly, this statement of yours is only correct when power statisfaction is 100%. When power satisfaction is below 100%, you will be constantly moving the "recipe finished" event in the event queue.

Why not have a seperate event queue for every electric network and only advance time in that queue by the percentage of power satisfaction in that electric network? For example, if power satisfaction is 50%, then only advance time by 50%. That way, events will no longer have to be moved, and you will no longer require power demand and satisfaction buffers. Only the rare cases of entities being supplied by multiple electric networks will have to be handled every tick (which could probably also be optimized, if necessary).

[Vegemeister]

Even when moving the recipe finished event due to brownout, there are still major savings. (A 100 tick recipe at 80% satisfaction is 80% complete in 1 event, 96% complete in 2 events, 99.2 % complete in 3 events, and finishes on the 4th event.)

But your suggestion (slowing the rate of time advance under brownout) is better. And there's a way to do it with my favorite tool of the week, integrator feedback.

Replace the power demand buffer with an energy demand buffer. On each tick, += the energy supplied by producers on that tick into an energy accumulator. If the value of the accumulator is greater than than the 0th element in the demand buffer, -= that demand from the accumulator and advance the event queue by 1 tick.

[Tekky]

Logistic/construction robots: On the current tick, a robot is dispatched for a job. Calculate how many ticks in the future it will reach its destination (distance/speed), and how many ticks until it runs out of power ( charge/(speed*energy_per_distance + energy_per_time) ), and depending on which will happen first, either create an Event for the robot to collect/deliver its cargo, or an Event for the robot to divert to a roboport for charging.

I don't think that this will be sufficient. I believe a new event will have to be created for every time a bot enters a new chunk (32x32 tiles), so that the bot becomes part of the llist of entities that are currently in that chunk. That way, when displaying the game on the monitor, it is easy for the game to determine which bots are nearby and must be displayed. All the game must do is look into the list of entities in all chunks that are visible.

Even if this increases the number of events significantly, it will still be a lot more efficient than having to update every bot every tick (which I guess is what is being done now).