Globally cached block evaluation

[kpreid]

While working on possibly switching to ECS data storage (#620), I hit a problem based on our current block evaluation strategy: evaluating a Block, such as for inserting into a Space, could require reading any other BlockDefs or Spaces, resulting in a borrow conflict that can only be resolved by run-time checking.

Another deficiency of the current system is that each Space caches block evaluations independently in its Palette; this makes sense as rigor from the perspective of Space as a single object, but when blocks appear in multiple spaces, it is wasted computation and memory.

Therefore, I think it would make sense to store block evaluations in a more widely shared cache. This cache should:

• Be either owned by the Universe or in a static item — I am not sure which.
  • Putting it in the Universe allows predictably scheduled updates like BlockDefs currently offer.
  • Making it global allows not-yet-inserted Spaces to use it without caveat, and to share some evaluations of simpler blocks between different universes — but there might be ambiguity about things like which ReadTicket to use.
  • Middle ground: We could have two caches, with the global cache used temporarily before insertion. But why, and what, if any would be the observable behavior difference?
• Probably, be interior mutable so that adding to it can be done at any time, and be reachable through ReadTicket.
  • (This means that the cache will not ever be made up of ECS entities.)
  • However, some of the circular-dependency cases will still be unable to be resolved except by iteration to a fixed point, so there is no magical "this makes things always succeed" here. The advantage of the cache in resolving such cases will be that if you insert into the cache, take a reevaluation step, then separately make use of a handle to the cache to insert the cached block into a Space, then that process will always succeed.
• In addition to caching evaluations, also offer interning of Block values — mapping equal blocks to a canonical instance to reduce duplicate representations of the same data.
• Have reference-counted cache entry handles owned by Palettes and possibly other places that would benefit, yet also keep some recently-used blocks by nothing more than recency. For example, a block animation that swaps out the block on a schedule should not end up repeatedly reevaluating, but hit the cache instead. (In fact, with the separation of cache from palette, we should become able to cache upcoming animation steps by inspecting the tick action.)

Once we have the cache, we can use it while executing SpaceTransactions by filling the cache during the check phase rather than the commit phase.

[kpreid]

Be either owned by the Universe or in a static item — I am not sure which.

Whoops; of course, if compiling without std, we need it to be somewhere it can be !Sync, i.e. not static.

[kpreid]

I was hoping that this block cache would straightforwardly replace all existing caching (that being the logic in space::Palette and BlockDef), but that leaves us no place to generally resolve the read/write conflicts during universe steps. The plausible way I see to do that is to keep the caching in those places, thus forming this 2-step update loop:

• Update the shared cache, reading from definitions in BlockDef and Space including their cached evaluations.
• Update BlockDef caches and Space state and cache, taking data from the shared cache.

However, if I do that, it would be nice not to now have 3 independent implementations of evaluation caching, which is a tricky business, particularly around ensuring the right notifications are received, and deciding what to do about newly-appearing evaluation errors. I'm thinking about whether the “cache entry” could be a thing that can be independent of the cache as a whole, and used in these 2 other applications, or whether they are too different in their requirements.

[kpreid]

Oh, I'm forgetting my previous thoughts. My earlier solution to the dependency cycle was for new blocks needing evaluation to be explicitly entered into the cache, typically during a transaction check phase, so that when the actual mutation happens, no evaluations are performed. Though, for cache updates during stepping, we'd need to make those internally to the cache two-phase (computing all the new evaluations, but only after all of them are done writing them to the cache) — which is simpler than having 3 different caches, but maybe not clearer to comprehend.

[kpreid]

I ended up doing the ECS migration (208bf3bb67b5b95f17b232bceb736c8bfa6a74a8) without making this change. It is probably still a good idea, but I’ll want to pursue it in context of the ECS architecture.

[kpreid]

As of c8579c9c84d89d95bf3ebd788fbdc6850e4be964, transactions evaluate blocks on check, and all borrow conflicts relevant to these matters have been eliminated (I think). It would still be nice to have shared evaluations that aren't strictly tied to palettes, but I think that’s now a pure performance matter and not tied to other work needing doing.