Spatial (resolution-aware) caching

[Keavon]

Spatial, and likely temporal, caching needs to with based on storing cached data at different zoom levels, areas in space (forming a patchwork quilt of cache hit areas within surroundings of cache miss areas), and different times in the animation timeline. All this will be needed to make Cache nodes relation-aware to work with footprint data.

[0HyperCube]

@Keavon I'm not really sure how we can do this. If we have f(Footprint) = disk sampled points and want to avoid doing the disk sampling many times, then how can we be sure that changing the footprint won't impact the result?

If we actually implemented the cull node, then changing the footprint by panning around would certainly impact the result - so if the shape was initially outside the viewport and we cached the empty result, then that would not be ideal.

[TrueDoctor]

If we actually implemented the cull node, then changing the footprint by panning around would certainly impact the result - so if the shape was initially outside the viewport and we cached the empty result, then that would not be ideal.

The idea of resolution aware caching would be that we only reuse the cached result if the outcome would be the same and otherwise recompute. The click targets are a bit more tricky to update but that's the basic idea

[0HyperCube]

@TrueDoctor How do we know if the "outcome would be the same" without computing the outcome?

[Keavon]

@TrueDoctor wrote in Discord:

There are basically two possible ways of going about this:

1. Fix the performance and actually make everything fast enough to be executed in real time
2. Change how click targets are propagated:
   If instead of just storing the click targets in the monitor nodes, we instead attach the click targets to the data type, we can modify the click target in the cache node.
   When the user then pans around in the viewport and we know that the data we have cached is basically still correct, we could modify the click target in the cache node to reflect the proper location.

But I honestly think that we really should not need to rely on caching for purely vector data. There are a bunch of potential optimizations we can do which should could speed this up (e.g. eliminating unnecessary clones etc.)

[0HyperCube]

@TrueDoctor / @Keavon

For 1, this is quite challenging given that poisson disk sampling inherently requires quite a lot of allocation and computation. A popular algorithm for fast poisson disk sampling is https://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf. I have also noticed that the code for sampling based on Euclidean distance is very inefficient and I might try and improve that sometime. However even with the current total caching currently we get a frame time of 80ms or ~12fps which doesn't really give a lot of room for these algorithms to run in real time.

For 2, I'm not sure how this is relevant as click targets are stored in document space so don't change as the user pans around the document.

[0HyperCube]

Caching based on the Context

Graph executions will rarely have the same context, since things like the current time are prone to varying. Therefore it is necessary to check if a cached value is still valid.

Time

The current time will only change the output if node that reads the time is executed. Therefore when evaluating the node to populate the cache, we must check if a time reading node is evaluated. We could do this by storing a bool (possibly atomic?) inside the ContextImpl that would be set when the time is accessed.

When the cache node sees that the time has changed, it should check to see if the last execution depended on the time. If it didn't, the cache doesn't need to be invalidated.

Fields

Fields consist of running the same lambda many times, with a different varargs in the Context. For example the position might change when creating instances. However you could also just pass in a constant value into a field, in which case it is desirable to just run the lambda once.

It is possible to avoid running a field many times if the evaluation does not depend on the specific part of the Context that is changing. To do this, a flag similar to the time can be used.

Footprint

For a simple implementation, we could use an approach similar to the time; whereby a flag is set when the footprint is read. This would allow us to properly cache nodes that don't depend on the footprint.

This strategy is very conservative with nodes that do depend on the Footprint, as it is likely that changes to the footprint will not usually give a different output. However I'm not really sure how to do any better. This was the problem I identified in my earlier comments above.

Propagating the flag

I proposed putting this flag into the ContextImpl struct as an atomic bool.

If a node has two inputs, then evaluating the first input might depend on the time, however the second input might not. Therefore it is necessary to reset the flags back to false before evaluating each input. If any of the inputs have set a flag to be true, we must then set the flag to be true before returning from the node.

I think we could possibly integrate this functionality into the node macro @TrueDoctor?

[TrueDoctor]

@0HyperCube
My plan for implementing this is by leveraging the compiler support and the different Extract* annotations. Each node which uses a footprint has to explicitly ask for the footprint and we can thus track usages throughout the node graph.
After an analysis of which context information is needed in which branch of the graph, we can inserts special nodes which modify the context. E.g. if the global time is not used anywhere in the graph, we can add a node at the root of the evaluation tree, which sets the global time to 0. We are allowed to do this, because we know that none of it's childeren depend on the global time. This approach allows us to reuse our existing caching without modification and only induces a minimal constant runtime overhead.

[TrueDoctor]

We will still need to implement the things described in this issue but I think the Context thing is orthogonal to the challanges described here and at least conceptually a solved problem. Currently, we only update the time if the user explicitly enables real time mode so I think that this should currently not cause any major problem until we get around to implementing the system described above. But thanks for brining this up, it is definitely an issue I have thought about, I just haven't properly documented the reason for the design choices as part of the context pr

[Keavon]

#2500