Potentially easy chest-behavior performance optimization

[ssilk]

This morning I woke up and my first thought was “but we have already discussed this subject..”, and I searched a little bit and found it indeed.

So I merged it, because both subjects are really similar.

I point to Rsedings post: viewtopic.php?p=351657#p351657

Where he explains why this makes no sense.

But I had another idea. There is a special case, where changes to a chest can be made really much faster. These are the preconditions:

- only one item type in chest
- no gaps between the slots (in/out happens only on the “last”) slot.

This state can be replaced with a single integer. So instead of complex slot-handling, the chests content is represented as one simple integer.

Until the above preconditions change. I think this might be a really simple change, because only the internal representation of the chest changes. But I’m far away from knowing exactly.

[robot256]

After reading Rseding's post and the FFF, I've got a few observations to contribute.

For a chest with simple items only, the current state uses a statically allocated array of item-id + count for each stack in the container, which it iterated over to find empty slots. Since it is statically allocated and contains (I guess) 4 bytes per stack, it normally fits nicely in a single cache block and the iteration is extremely fast.

To add a special behavior for when the chest contains all of the same simple item and stored compactly, you would need to add (in my estimation):

1. A 2-byte field with the index of the first non-full slot, or 0 if the chest is not uniform and compact.
2. A test of this field every time anything is added to the container, even if the container is small or not compact or uniform.
3. A test of the item to be added every time anything is added to the container, to see if it will break uniformity.
4. Recompute and write to this field every time an item is added.
5. A test of this field every time anything is removed from the container to see where to start.
6. A test on the kind of removal operation taking place to see if it might have made the container non-uniform and non-compact.
7. Recompute and write to the field if it was a "simple" operation.
8. If it was a "complex" operation, perform the normal iteration and also check every slot to see if it is still uniform and compact. (This will take about 2x longer than the current iteration.)

In some cases, these steps will be able to replace the existing iteration. In others cases, they will be performed *every time* in addition to the existing iteration. Based on Rseding's post, I think it is likely that unless your entire base is made up of full 500-slot chests, the total penalty you add to smaller and mostly-empty chests will outweigh the total gain you receive on large full ones.

In general, memory caching and CPU pipelining mean that a fixed algorithm like iteration will be faster than multiple IF/ELSE checks. This is why so many optimizations actually involve removing special case handling with clever math tricks, rather than adding more cases. The human mind is good at finding shortcuts for special cases because we process raw information slowly, but computers are kind of the opposite.


IMO, an interesting test would be to see exactly what size of chest starts to add noticeable delay, and if this size varies based on what CPU cache size and memory setup is used. It's possible there is some number, like 350, that is still large but just as performant as a 48-slot chest.

[aka13]

used the windows snipping tool for screenshots, and Gimp to add the lines.

If you are willing to have a microsoft acc, their whiteboard app is an incredible companion to the snipping tool.

[buggy123]

Going to break this up a bit so I can respond more easily without a wall of text.

To add a special behavior for when the chest contains all of the same simple item and stored compactly, you would need to add (in my estimation):

1. A 2-byte field with the index of the first non-full slot, or 0 if the chest is not uniform and compact.
2. A test of this field every time anything is added to the container, even if the container is small or not compact or uniform.
3. A test of the item to be added every time anything is added to the container, to see if it will break uniformity.
4. Recompute and write to this field every time an item is added.
5. A test of this field every time anything is removed from the container to see where to start.
6. A test on the kind of removal operation taking place to see if it might have made the container non-uniform and non-compact.
7. Recompute and write to the field if it was a "simple" operation.
8. If it was a "complex" operation, perform the normal iteration and also check every slot to see if it is still uniform and compact. (This will take about 2x longer than the current iteration.)

There are a lot of checks, but my thinking was that there are also a lot of checks involved in iteration. With insertion as a example, every time it goes over a slot, it checks:

1. Check if the slot is empty. It keeps track of whether the slot is empty so that you can go back and insert a item in the lowest slot later if you don't find a appropriate stack. Several possible implementations depending on details but I think it will need a check here.
2. If not empty, check if it is the same as the item it is trying to insert (I can't off the top of my head think of a way to merge this with #1 as a single operation).
3. If #3 passes, also compare the stack size with the maximum stack size for that item.
4. If #4 also passes, do all the operations involved with adding the item and then probably stop iterating unless you couldn't fit all of the items you were trying to insert in that stack, inwhich case you continue.

In some cases, this is as low as 1-2 operations per slot you iterate over. But for chests with only one item type and most of the stacks are full, it could be as high as 3 per slot. That's potentially over a hundred operations for a filled steel chest.

In some cases, these steps will be able to replace the existing iteration. In others cases, they will be performed *every time* in addition to the existing iteration. Based on Rseding's post, I think it is likely that unless your entire base is made up of full 500-slot chests, the total penalty you add to smaller and mostly-empty chests will outweigh the total gain you receive on large full ones.

There are middle grounds, though. For example, i'm reasonably sure there's a performant way to only do this optimization on large containers such as warehouses. Wube wouldn't have too much motivation to do this aside from maybe altruism, since they don't use warehouse-sized containers and that's only a mod thing, but it would at least be a potential solution to the warehouse lag issue.

In general, memory caching and CPU pipelining mean that a fixed algorithm like iteration will be faster than multiple IF/ELSE checks. This is why so many optimizations actually involve removing special case handling with clever math tricks, rather than adding more cases. The human mind is good at finding shortcuts for special cases because we process raw information slowly, but computers are kind of the opposite.

That's fair. I'm aware of the fact that i'm looking at this in a strict count-the-steps-required sort of way, and it's possible that the finnicky details of implementation like that will mean that something unintuitive is faster.

IMO, an interesting test would be to see exactly what size of chest starts to add noticeable delay, and if this size varies based on what CPU cache size and memory setup is used. It's possible there is some number, like 350, that is still large but just as performant as a 48-slot chest.

That's a interesting point, there's probably some cutoff like that. But that'll vary per user, won't it? I don't think CPU cache sizes are completely standardized.



Also, on a related note, seeing how they implement itemstacks I wonder if you could do something where you 'merge' item stacks, so:
Seven slots of

Code: Select all

struct ItemStack
{
  ItemCountType 100;
  ItemID IRON_PLATES_ID;
};

becomes

Code: Select all

struct ItemStack
{
  ItemCountType 700;
  ItemID IRON_PLATES_ID;
  MergedStackCount 7;
};

It would be tricky to get performant, but it'd be sorta analogous of the belt optimization where they merged lines of belts into 'belt segments'.

[Nidan]

Since it is statically allocated and contains (I guess) 4 bytes per stack, it normally fits nicely in a single cache block and the iteration is extremely fast.

Small correction: Rseding explicitly said "An inventory is a vector of ItemStack (24 bytes each).". In the ItemStack structure definition from the FFF both count and id thus must be 64 bits each. Still reasonably compact, but only 2 2/3 stacks per cache line (usually 64 Byte).



My attempt at something general:
Replace an inventory's vector<ItemStack> with a sorted vector<struct{ItemStack without count, sorted vector<struct{slotId, count}>}> and a vector<uint64_t> as bitmap for listing free slots. In small inventories (where checking all slots is cheaper than maintaining order -- I'm thinking assemblers and alike) the vectors could be kept unsorted since:

In general, memory caching and CPU pipelining mean that a fixed algorithm like iteration will be faster than multiple IF/ELSE checks. This is why so many optimizations actually involve removing special case handling with clever math tricks, rather than adding more cases. The human mind is good at finding shortcuts for special cases because we process raw information slowly, but computers are kind of the opposite.

In terms of time complexity, worst case should be O(log(item types) + number of stacks of that type) for most operations, unless a free stack needs to be found, which is technically O(inventory size). But using 'count trailing zeros' and related instructions to scan for a free slot will still be fast. (With vanilla inventory sizes (48 slots) it's always a single instruction.).
In terms of space complexity, this solution would use (48 Bytes + 1 Bit per slot) statically, 40 Bytes per item type inside the inventory and 16 Bytes per slot used. In contrast, the current vector<ItemStack> uses (24 Bytes + 24 Bytes per slot) statically. Looking at these numbers, it seems like this would also reduce memory consumption, except for inventories containing a little bit for everything -- players and dump chests.
There's (obviously) also a drawback to this solution: I've introduced two additional indirections. Whether the theoretical gains outweigh these needs to be tested.

[robot256]

In theory sure, you could keep track of the items abstracted from the slots. Then when something accesses it in a way that breaks the uniform contents assumption, you have a burst of activity to re-allocate and populate the actual slots for the operation to use. And how often do you check if it's safe to collapse the items again? Going back and forth between the two representations introduces a lot of new places for bugs and corner cases. That's why I was thinking the only new information would be the index of the first non-full stack, and the actual slot data storage would remain the same.

[ssilk]

@robot256
I didn’t explain it good enough.

I meant this: a chest has 2 modes of operation: the current one and a new one, which is as long on, as the preconditions are fulfilled, which was a) only one item type, b) no gaps between the slots and what I forgot was c) in/outsertion by inserters/robots only.

The state of that chest can be displayed with one simple integer! The number of occupied slots is direct proportional to the number of that integer.

E.g. you can have a chest full of 100 iron. Which can either be 2 stacks of iron or 100 iron that can be displayed as two stacks.

[robot256]

@robot256
I didn’t explain it good enough.

I meant this: a chest has 2 modes of operation: the current one and a new one, which is as long on, as the preconditions are fulfilled, which was a) only one item type, b) no gaps between the slots and what I forgot was c) in/outsertion by inserters/robots only.

The state of that chest can be displayed with one simple integer! The number of occupied slots is direct proportional to the number of that integer.

E.g. you can have a chest full of 100 iron. Which can either be 2 stacks of iron or 100 iron that can be displayed as two stacks.

I understood perfectly. It would be great if chests had only one slot per item--that's essentially what mods that increase stack size to 1000000 are for. My point was that the game would need reliable code to switch back and forth between the two modes, and have a comprehensive way of detecting every case where it needs to change modes in either direction, in order for the change of modes to be invisible to the user. That's where the opportunity for bugs and corner cases arises. Every time a player clicks on it, every time an inserter or bot arrives with a different item, every time a mod touches it, and undoubtedly many more cases that would be overlooked at first, the game would have to convert the item counts back to slots, do the operation, then check if it can be turned back to counts again. If it messed up the order of items at all, it would look like a glitch to the user.

[ssilk]

I don’t think this is complicated. It’s just the three rules I wrote. “Easy” to implement (compared to what you wrote). Nothing needs to be converted in this case, because the occupied slots are just a proportional function. The mode-change is hidden for the player. It’s just a change in the internal representation.

[Nidan]

The mode-change is hidden for the player. It’s just a change in the internal representation.

Of course it's hidden from the player. But it's not hidden from the programer who has to implement the mode change. And an implementation with less special cases tends to be easier to read, reducing cognitive load, reducing the likelihood of introducing bugs.

[Nosferatu]

Just one note about:
"Megabases avoid chest because they hurt performance"
No.

Avoiding a chest automatically means avoiding an inserter.
Inserters are bad and that's why you try to avoid chests

[SWeini]

Inserters inserting into or taking out of a chest virtually never shows up as being slow. The only time that has ever happened is when mods change an inventory size to something crazy (500 to 2000 slots) but no matter what you do at that scale it's going to be slow.

What?

Can we perhaps start with some easy optimization? Like storing an extra bit per container indicating whether the limited slots contain any items, or storing the index of the highest slot containing any items. If the game knows that these slots are empty there is no need to look for items in them when an inserter wants to grab items from it*.

Why?

When mods provide new containers, they often do so by increasing size and slot count. Sometimes I'm only interested in the increased size because it can act as an easy n-m splitter or because I actually have that much throughput. If I know what I'm doing and I care about performance, nowadays I must prevent these large containers if possible. However, if I could limit them to a few or even a single slot and they wouldn't tank performance I'd be happy.

UPS-sensitive vanilla megabases often use direct insertion, and sometimes have to use "assemblingmachine-stackinserter-chest-stackinserter-assemblingmachine" because of beacon placement and such. I haven't done performance comparisons (how could I), but I believe that even those will benefit slightly from being able to limit these chests to a single slot if that optimization has been implemented.

*In benchmarks I have seen (not performed by myself), wooden chests limited to 1 slot regularly perform better than steel chests limited to 1 slot, if I remember correctly.

[Koub]

Inserters inserting into or taking out of a chest virtually never shows up as being slow. The only time that has ever happened is when mods change an inventory size to something crazy (500 to 2000 slots) but no matter what you do at that scale it's going to be slow.

What?

Can we perhaps start with some easy optimization? Like storing an extra bit per container indicating whether the limited slots contain any items, or storing the index of the highest slot containing any items. If the game knows that these slots are empty there is no need to look for items in them when an inserter wants to grab items from it*.

I don't know if anything has been optimised ont that front, but bear in mind that a lot has been done by the devs since that post as of performance optimisation (this post is almost 5 years old, and while there hasn't been much on that front in the last 2 years, things might have changed before).

[mrvn]

There are also chests limited to a specific item. E.g. Angles warehouses have a Coal Silo that will only allow coal to be placed inside.

Re-reading this thread I'm thinking: Do we actually need and want slots in chest used in automation?

It's nice for a manually used chest to place random amounts of items into slots to keep things organized and make counting easier. But really a chest where you manually fiddle with the slots is rare compared to all the buffer chests a large game has that are completely used by inserters or loaders.

So for optimizations I could see chest being split into 3 groups:

1) single item chest

The chest has a item type either set by the prototype or when the first item is added (and cleared when the last item is removed). It also has a maximum size (set from the prototypes number of slots * item stack size) and item count. There really isn't much use for organizing the item into stacks in the container, the total count really is all you need.

2) sorted items chest

This is like the players inventory. All items of the same type are always combined into the smallest number of stacks. But instead of storing stacks and always having to find the right stack to manipulate I would just store the #slots, slots-used and pairs of item-type * count. The last could be a hashtable or simple list that you have to search through to find the right item-type to manipulate. slots-used is just a speedup to keep track of how many stacks (fully or partial) the chest holds if it would be using stacks. So it's fast to see if a chest is full without having to go through all items and compute the number of stacks each item count represents.

Note: A item type needs 4 bytes and the count is 4 bytes too. So 8 item types would fit into a cache line when stored as a vector. How many chests with <= 8 items does your factory use? How many single item chests? Even 2000 slot warehouses frequently have <= 8 item types in them.

3) legacy chests

Chest just like they are now with all the flexibility to arrange partial stacks of items and the cost of having to search for the stack to manipulate. Would probably have to remain in use for any container with filter support (e.g. cargo wagons).


Note: Case 1 might not even be a worthwhile optimization over case 2. A sorted items chest with just one item will always find the item on the first try. It's more about limiting the chest to one item so it's impossible to insert anything else, e.g. Coal Silo.

[vitharr]

Apologies if this is considered a necro or not, but I was about to suggest my own thread and found this one during searching. I would like to throw my vote in for removing 'slots' as a display concept in chests and instead start using it as a figure to show 'density', especially for the upcoming 2.0 addition of interplanetary logistics

Removing slots from chests and instead display only single 'slots' filled with the amount of item in that chest only

Add a new metric for items in the form of 'space' or 'size', for example:

Copper wire: 200 Stack, 1 'Size'
Meaning: Copper wire consumes 1 'slot' of a chest per every 200 count of items

Nuclear reactor: 10 Stack, 10 'Size'
Meaning: Nuclear reactor consumes 10 'slots' of a chest's 'volume' per 10 count of items

Removing the need for inserters to 'search' for slots in inventories is, imo, a very good change as I have not yet been able to imagine a gameplay use for how chests work as opposed to the player inventory at current, but to add to the gameplay that will be coming in 2.0, I believe using the 'slot' or 'size' mechanic would further gameify the interplanetary logistics in a way similar to other 'tetris' style inventory systems, where item sizes are taken into account, not just the raw, abstracted amount of them. This also opens up an avenue for a new class of chest, one with fewer max items per 'slot' and instead more 'slots', if the gameplay of it is worthwhile

[mrvn]

Apologies if this is considered a necro or not, but I was about to suggest my own thread and found this one during searching. I would like to throw my vote in for removing 'slots' as a display concept in chests and instead start using it as a figure to show 'density', especially for the upcoming 2.0 addition of interplanetary logistics

Removing slots from chests and instead display only single 'slots' filled with the amount of item in that chest only

Add a new metric for items in the form of 'space' or 'size', for example:

Copper wire: 200 Stack, 1 'Size'
Meaning: Copper wire consumes 1 'slot' of a chest per every 200 count of items

Nuclear reactor: 10 Stack, 10 'Size'
Meaning: Nuclear reactor consumes 10 'slots' of a chest's 'volume' per 10 count of items

Removing the need for inserters to 'search' for slots in inventories is, imo, a very good change as I have not yet been able to imagine a gameplay use for how chests work as opposed to the player inventory at current, but to add to the gameplay that will be coming in 2.0, I believe using the 'slot' or 'size' mechanic would further gameify the interplanetary logistics in a way similar to other 'tetris' style inventory systems, where item sizes are taken into account, not just the raw, abstracted amount of them. This also opens up an avenue for a new class of chest, one with fewer max items per 'slot' and instead more 'slots', if the gameplay of it is worthwhile

No need to invent anything new. The size of items is simply count / stack size rounded up.

The gameplay use of how stacks in chests work is when you want to reserve some slots. You place 1 iron plate in each slot where you want only iron plates to be filled in. That way you can make a slot filter for chests that don't allow filters (which are all chests or make a temporary filter for e.g. cargo wagons.

Having chests work tetris style would increase UPS costs significantly.

Note: You still would have to search the slots in a chest even if you just save the sum of each item. You just would have fewer slots filled because every item would only use one slot. This can use a hashtable though and be optimized for chests with < 4-8 items or whatever fits in a cacheline. Chests with many types of items are rather rare.