[naasking]

Not sure I like the mixed push/pull approach. If you're already traversing the tree to mark nodes as possibly dirty, you might as well recompute the node's value and store it while you're there. Otherwise on pull/lazy update, you're traversing the tree all over again! Terrible for cache locality, particularly for large graphs.

You might be tempted to say that the lazy approach might avoid some recomputations, but if a node isn't actually going to be accessed then that node is effectively no longer live and should be disposed of/garbage collected, and so it will no longer be in the update path anyway!

The mixed push/pull approach has only once nice property: it avoids "glitches" when updating values that have complex dependencies. The pull-based evaluation implicitly encodes the correct dependency path, but a naive push-based approach can update some nodes multiple times in non-dependency order. Thus a node can take on multiple incorrect values while a reaction is ongoing, only eventually settling on the correct value once the reaction is complete.

In other push-based reactive approaches, you have to explicitly schedule the updates in dependency order to avoid such glitches, so perhaps this push/pull approach was picked to keep things simple.

[Gehinnn]

I implemented the eager recomputation model for the observable utilities in vscode [1] and it quickly fell on my feet because of these glitches.

In particular this is problematic if you have observable optional state that has inner observable/derived state and someone reactively reads the outer state and then it's inner if the outer one is defined.

Then you clear and dispose the outer state and at the same time set some other observable value that the inner derived depends on. With eager recomputation, it can now happen that the inner derived is recomputed, even though the inner state is disposed.

[1] https://github.com/microsoft/vscode/blob/fe9154e791eafb4f18d...

[naasking]

Yes, if you want to better tolerate glitches you have to separate internal and external reactivity, and only run the external ones after the full reaction is complete. I think this would prevent the scenario you describe, assuming your operators are well-defined.

The other option is to use FrTime's approach and only update nodes in dependency order.

[Gehinnn]

With dependency order you mean dependants before dependencies? (and dependencies lazily when they are requested again by the dependant)

If you update dependencies before dependants, the dependant might not depend on all it's dependencies anymore (because a derived might depend on A only if the observable B is true) and you do too much work/run into glitches.

[naasking]

Dependency order = values are computed in the same order as they would be in a purely pull-based system, which is intrinsically glitch-free

Push-based systems permit better efficiency and minimal state changes, but they should endeavour to preserve the above property for external observers.

[KMag]

I spent 11+ years at Goldman, working in SecDb Core, and various SecDb-related infrastructure.

Goldman's Slang language has subsets of both lazily-evaluated backward-propagating dataflow graph ("The SecDb Graph") and forward-propagating strict-evaluating dataflow graph ("TSecDb"). They both have their use cases. The lazily evaluated graph is much more efficient in cases where you have DAG nodes close to the output that are only conditionally dependent upon large sub-graphs, especially in cases where you might be skipping some inputs, and so the next needed graph structure might not be known at invalidation time.

Ideally, you'd have some compile-time/load-time static strictness analysis to determine which nodes are always needed (similar to what GHC does to avoid a lot of needless thunk creation) along with some dynamic GC-like strictness analysis that works backward from output nodes to figure out which of the potentially-lazy nodes should be strictly evaluated. In the general case, the graph dependencies may depend upon the particular dynamic values of some graph nodes (the nodes whose values affected the graph structure used to be called "purple children" in SecDb, but that lead to Physics/Statistics PhDs coming to the core team confused by exceptions like "Purple children should not exist in subgraph being compiled to serializable lambda")

TSecDb already contains a similar analysis to prune dead code nodes from the dataflow DAG after the DAG structure is dynamically updated. (For instance, when a new stock order comes in, a big chunk of TSecDb subgraph is created to handle that one order, and the TSecDb garbage collector immediately runs and removes all of the graph nodes that can't possibly affect trading decisions for that order. This also means that developers new to TSecDb often get their logging code automatically pruned from the graph because they've forgotten to mark it as a GC root (TsDevNull(X))... and it's pretty bad logging code if it affects the trading decisions.)

Risk exposure calculations (basically calculating the partial derivatives of the value of everything on the books with respect to most of the inputs) are done mostly on the lazy graph, and real-time trading decisions are done mostly on the strict graph.

[naasking]

Sounds cool and quite intricate. Distributed reactive computations might indeed change the basic logic I described. Most reactive systems I've worked with and thought about are local.

[nyanpasu64]

In a push-based approach, can you bundle state changes into a transaction and recompute derived state when the transaction ends and all inputs have finished changing?

[naasking]

That's effectively what I suggest in the other replies. You separate internal from external callbacks, and run the internal ones first and enqueue the set of external ones, then run those at the end. All subsequent externally-driven changes should be enqueued until the next "turn", ie. after all changes have settled. This preserves transactional semantics.

[gnulinux]

Can one not just note the timestamp of last change with a monotonic clock. Then, dependencies check the timestamp of last computation, and pessimistically determine if recomputation is needed.

Seems like the trouble here is you'll have to traverse the tree every time to check timestamps but if the dependency is dirty that needs to happen anyway.

[naasking]

That's effectively a pull-based system, which works fine but is inefficient. With a binary dependency tree of depth N, you have to touch 2^N nodes in such a pull-based system every time you evaluate it, no matter how many nodes you may have updated.

If you only updated 1 node, a push-based system will only update nodes that have changed, which will be considerably less (likely linear in depth). For instance, consider:

    var evenSeconds = clock.Seconds.Where(x => x % 2 == 0);
    var countEvents = evenSeconds.Count();
    var minutes = clock.Seconds.Count(x => x / 60);
    var hours = minutes.Count(x => x / 60);

Even though evenSeconds and countEvents is only updated every other second, and minutes once every 60 seconds, your pull-based approach will have to check all nodes up to the root every time clock.Seconds changes.

In a push-based system, clock.Seconds would trigger seconds+1. If that's not even, propagation stops there, if it is even then this updates evenSeconds, which would then trigger an update for countEvents. Ditto logic for minutes and hours.

You can see the push-based system permits minimal state changes via early termination if downstream dependents won't see any changes.