gistfile1.txt

Problem: 

Some operations would like to work on past or potential future versions of a component storage. For instance, many fast multiplayer games try to extrapolate component states from the known past to the present while the packets carrying the actual current state are still in transit. Or a discrete event simulation system wants to avoid component order artefacts by not modifying components until the changes to all the components involved in an interaction are determined. Or an AI should be able to simulate possible outcomes of its actions. 

The normal fast way to do things like this is to mutate the associated structures in place to the states they had, have, or will have, as needed by the system operating on it, but this is tricky to get right, and can easily break if implementation details such as the order of systems changes. It coflates the different states that the storages had at different times together into one, and allows for multiple unrelated systems that do not work together to mutate the same structure without any separation of access. In other words, this is bad design. 

Solution: 

First, a CoWStorage trait is exposed. Like FlaggedStorage, it tracks additions, modifications, and removals, but with the modification and removal events, it maintains the original versions which can be retained. 

Second, a DeltaStorage trait is exposed. This DeltaStorage can be constructed on top of a CoWStorage, and initially looks the same as its underlying storage. Alternatively, it can be constructed on top of one storage, but with the diff such that it looks like a different storage, but this is much more computationally expensive, so the first will usually be preferred. 

When the original storage is modified, it generates events which have enough information for the DeltaStorage to act like it "undoes" them, thus keeping the DeltaStorage externally constant. However, this does require some synchronization, as if the original storage changes before the DeltaStorage can account for the changes, a data race and silent modification may be witnessed by the DeltaStorage. 

To avoid such a mess and minimize contention, the dispatcher can perform a few tricks. First, it can try to schedule the storage accesses so that the modification of the underlying storage does not occur simultaneously with the access to the DeltaStorage. Second, if this is impossible (say, due to a component unwittingly requesting both the DeltaStorage and the original at the same time) or the dispatcher finds that doing so would cause the code to not utilize multithreading efficiently, it can perform redirect-on-write for the modifying component as well as the accessing ones, and then commit the changes later when the system is far less contended. 

Different DeltaStorage implementations can have very different performance implications. A DeltaStorage based on a persistent tree, for example, will suffer from logarithmic update times on write, but is virtually unaffected by writes to the underlying storage provided that the underyling storage is based on the same kind of persistent tree, while a DeltaStorage based on a hash table of changes can be updated in constant time but has to wait if the underlying storage is updated. There is no one-size-fits-all solution here, so there should be multiple implementations, each with distinct strengths.