TL;DR
Use a path decomposition for update order to optimize cache usage.What ?
I've been thinking for a while about how to improve cache usage for Factorio, and I'm pretty sure this is a path width problem.A vertex is a data/function object that needs to be moved into cache at some point.
An edge represents when two objects need to be in the cache at the same time for whatever reason, like if one needs access to the other.
The path decomposition provides the ideal update order that minimizes cache taken up by objects waiting for other objects to be transferred into cache (objects in the same node of the path). If there's enough cache to fit the largest node of the path, then objects would (ideally) be loaded into and out of cache at most once per update. Any remaining cache can then be filled with objects further along the path, right before they're needed, thus eliminating the latency bottleneck.
Finding the ideal path decomposition is an NP-complete problem, but would a relatively simple approximation algorithm be fast enough? Then there's the problem of the decomposition needing to be updated whenever things get built/destroyed, but perhaps there's a clever way to handle insertions/deletions. Or maybe the path decomposition can be calculated on save/load, but you'd then need to make sure cases like two inserters pulling from a chest with one item behave independently of update order to maintain determinism. That's probably a lot to ask for. This whole idea might be incompatible with some of the optimizations currently in place. Oh! How about slowly shifting things in memory around over time instead of all at once? Then you can have the ideal path decomposition without a lag spike whenever the player does anything, and save/load time is mostly unaffected.
Could this be used to optimize the overall structure of the Factorio program? Actually, compilers already do pretty much exactly this. They're just more strict about not changing the results, which doesn't quite matter for some cases here.
What do you think?