Try out a "Recently Used" queue

[year6b7a]

This idea might not work. Extensive testing is needed before merging.

Right now, all chests/tanks in the network update from the same FIFO queue. This is fair and works reasonably well, but in a standard factory there are usually a handful of high-throughput chests and a large number of unused chests.

My guess is that the "handful of high-throughput chests" should have higher priority than the unused chests. This could be done by adding a new "Recently Used" FIFO queue just for entities that have been updated in the last 10? seconds. Since the mod updates 20 entities each tick, maybe min(recently_used_queue.size, 15) can come from the recently used queue and the remaining from the normal queue

In preparation for this, update_entity functions return UPDATE_STATUS.UPDATED if the update operation transferred any items.

A few things to keep track of:

• track number of "active" vs "inactive" chests and use to tune the active duration.
• add a case to handle high-throughput factories where every chest updates each tick
• figure out where to store last_updated_tick for each entity.
• This should probably have a unit test or two.

[bengardner]

I implemented something like this, but I don't know how to test if it helps much.

The easiest implementation that seems effective is to add a second queue and push entities that didn't request anything (NOT_UPDATED) on the "slow" queue and put entities that did (UPDATED) on the normal queue.
No tracking tick or any other extra data.

I called the queues "active" and "inactive".
I restructured the "get next" logic to eliminate the need for "ALREADY_UPDATED".

The queues are processed, with 50% of the entities coming from each queue. The same number (20) are processed on each tick.
The "active" queue is shorter, so the entities are processed more often.

I'll see if I can isolate this change and create a pull request.
I've changed so many thing in my fork that it is getting difficult to pull out just one feature.

[year6b7a]

don't know how to test if it helps much

I'm mainly looking to test if the scheduler change improves throughput compared to before under a variety of different factory setups such as:

• A small factory with just a few chests
• A factory where almost every chest is active
• A factory where almost every chest is inactive

As for how to measure, I was planning on just watching different factories run with the changes to see how they work. This might be easiest by creating a factory with throughput issues and to see if the change helps. It might be useful to lower the new setting to lower the number of entities to update per tick to make throughput issues more obvious.

The queues are processed, with 50% of the entities coming from each queue

I was thinking of using queue sizes to get a weighted proportion, where active entities have double the weight of inactive entities:

local n_active = global.mod.scan_queue.size
local n_inactive = global.mod.inactive_queue.size
local n_active_weighted = 2 * n_active
local n_inactive_weighted = n_inactive
local total_weighted = n_active_weighted + n_inactive_weighted
local n_inactive_to_update = math.ceil(ENTITIES_TO_UPDATE * n_inactive_weighted / total_weighted)
local n_active_to_update = ENTITIES_TO_UPDATE - n_inactive_to_update

assert n_inactive_to_update > 0
assert n_active_to_update > 0

That code will have to be improved, but that's the kind of code that's super easy to unit test so not too worried about maintaining that.

Using a weighted proportion will make it super easy to adjust how many active items update per tick.

[year6b7a]

For the branch you implemented, what's your gut sense on your implementation? Does it seem to help?

[year6b7a]

I'm going to try to implement the weighted proportion for the second queue.

[bengardner]

In my testing of a fairly large end-game network (~1900 chest), I see around 50 active and ~1850 inactive. That means the active queue is processed every ~5 (50/10) ticks and the inactive around ~3 seconds (1850/10/60).
Chests jump back and forth a lot, as each time something is moved, the chest is promoted to the active queue. So the number of active chests varies quite a bit.

I did a 50-50 split because I wanted the boost to be entirely from the shorter queue length.
Weighted pulls increase the complexity a bit and I didn't want to give too much preference to the active chests.
For example, in the above, a 13/7 split would change the times to 3.8 ticks (active) and 4.4 seconds (inactive). Not much gain on the active queue and a big penalty on the inactive queue.

As you mentioned, there are 4 basic categories for chests.

• Low capacity providers (direct output from assemblers)
• Low capacity request chests (direct input to assemblers)
• High capacity providers (many assemblers/furnaces/drills feeding via a few loaders/belts)
• High capacity request chest (feed loader/belt for large furnace ops)

The low capacity providers don't need to be processed all that often. Once every 5 seconds would be enough.

Likewise for the low capacity request chests. 1 Hz is more than enough. The buffer size can be automatically tuned to match the rate of consumption. The amount to buffer relates to the inserter stack size. There are a few recipes that are real fast (copper wire), but most aren't all that fast.

The high capacity provider only needs to be serviced often enough to empty the chest. Once every 5 seconds would still be enough in most cases. A larger number of stacks might help in some cases.

The high capacity request chest might need to be serviced most out of all of them. Again, a larger chest might help reduce the required rate.

I played with detecting the category and using several (4) queues, but it looked like a lot of work for minimal gain.

The one simple thing I tried was to count how many "services" in a row the chest moved something. If it moved 2 in a row, then it would go to the active queue. If it didn't move anything 3 in a row, then it would be demoted to the inactive queue.
It was basically a count incremented if something move and decremented if not. The number as bound to the range (0 .. 3). If it was >=2 then add to the active queue. Otherwise, the inactive queue.

I expect that most chests will send/request items sporadically. High capacity might move something every service.

That might actually be worth it, but I didn't do a performance test before abandoning it, so I don't know if it would help much.

[year6b7a]

These findings are really cool. Thanks for the detailed write-up.

The ratio of 50 active / 1850 inactive for a late game factory is good to know. I like the way you measured the average update frequency and that seems like a really useful way to determine if a setup works or not.

Agree that trying to detect the category with 4 queues sounds like a lot of work, especially since players might be able to manually choose a different chest for each category in the future.

The idea of counting sequential "services" sounds interesting. A variation on that idea that could also work is to keep track of the "running average" where a[n+1] = (a[n] + was_serviced) / 2. That measurement should be better able to represent chests that update every other update with a running average of 0.5.

Based on these findings, my thought is to pause work on dual queues and focus just on adding new high volume chest variants that update more frequently than normal Network Chests. Once that work lands we can revisit the dual queue setup and go from there.

Does that sound like a good plan? Anything else you want to do?

[bengardner]

That all sounds good to me.