Add 'local storage indexes' to significantly improve performance and enable efficient transport pipes.

This was mostly implemented via the new Inventory class in Stardew Valley 1.6, which is used by all chests and other item inventories.

Proposed implementation

Background

One of the difficulties for transport pipes (#61) and performance (#281) is efficiently finding items available to a machine. Hundreds of machines may need to perform multiple queries at once without causing visible stutter. Local storage indexes provide a way to do that.

Current implementation

Each machine group has a StorageManager which encapsulates access to the containers within the group. To search or list items, it essentially iterates through every item slot in every container. We can boil that down to this diagram (ignoring a few abstractions that don't matter here):

┌───────┐
│ chest │<──┐ find                       find
╞═══════╡   │ item X ┌─────────────────┐ item X ┌─────────┐
│ chest │<──┼────────┤ storage manager │<───────┤ machine │
╞═══════╡   │        └─────────────────┘        └─────────┘
│ chest │<──┘
└───────┘

That can impact performance in some cases: many machines might each perform multiple searches, which each iterate multiple containers, which each iterate multiple item slots. The problem gets significantly worse with transport pipes, which increases the number of potential containers, adds filtering logic, and adds complications like multiple in/out connections and multiple routes between machine groups (not to mention potential circular references).

Proposed implementation (local storage indexes)

A local storage index is an optimised view of the connected containers. It contains references to every item stack in those containers, and stacks added/removed in the containers get added/removed in the index (without rebuilding the rest of the index). It doesn't need to be updated when a stack size changes, since it holds references to the stacks.

For example (showing 3 slots for simplicity, but each container can have 36+ slots):

┌─────────────┐
│ chest       │<──┐
│  [3 item X] │   │ get
│  [empty]    │   │ all
│  [empty]    │   │ items  ┌─────────────┐
╞═════════════╡   │        │ local index │
│ chest       │<──┼────────┤  [3 item X] │
│  [5 item Y] │   │        │  [5 item Y] │
│  [empty]    │   │        │  [1 item Z] │
│  [empty]    │   │        └─────────────┘
╞═════════════╡   │
│ chest       │   │
│  [1 item Z] │<──┘
│  [empty]    │
│  [empty]    │
└─────────────┘

With the index in place, the previous example is now much simpler. Instead of checking every slot in every container (108+ checks per search in the above example), we can search the optimised index (3 checks per search):

           find                       find
┌───────┐  item X ┌─────────────────┐ item X ┌─────────┐
│ index │<────────┤ storage manager │<───────┤ machine │
└───────┘         └─────────────────┘        └─────────┘

Future development

The proposed implementation works fine for machine groups: every machine pulls items from every container, so we only need one index per group. Things get more tangled with transport pipes, which let players connect any number of machine groups and optionally add filters, uni-directional pipes, etc. The most likely solution is to have a separate input/output index for each pipe connection, and have index changes propagate across the network. That's beyond the scope of this implementation.

Prerequisites

For local storage indexes to work, they must be...

• atomic and consistent. If a container changes, that must be immediately reflected in every index (otherwise we get duplication bugs).
• highly efficient. With transport pipes, a change to one container can affect many indexes. If they all get rebuilt by querying all connected containers, performance would be hugely impacted.

Polling is prohibitively expensive; that could involve doing the original expensive query thousands of times per tick. To do this efficiently, we need a SMAPI event raised when values are added/removed to the chest.items NetList (Pathoschild/SMAPI#310), which in turn requires some changes to the game itself (requested here).

Nice work on the optimisation side, eager to see it implemented!