Understand the change propagation model

[nettybun]

Hi 3Shain,

I saw this short benchmark that compares how reactive libraries might avoid doing unnecessary computations:

https://github.com/3Shain/kairo/blob/6e1a3b87a5a0820cdf5a355008e5bde097aca8a4/benchmarks/cases/avoidable.ts

This kind of graph traversal is really interesting to me. I've tried comparing it to @lord's graph in this thread salsa-rs/salsa#41 (comment) which also deals with avoiding expensive work.

I've tried multiple times to map out your avoidable.ts but am having a hard time imagining the dirty marking of each cell and the decision of whether to propagate the change - possibly because the code is a generic wrapper around multiple reactive libraries, so I'm not always sure at what stages value-diffing is used (only some libraries do this by default; @ryansolid enabled diffing by default in https://github.com/solidjs/solid/releases/tag/v0.26.0 which might have drastically impacted these benchmarks?)

Would you be able to walk through what steps and checks Kairo makes to avoid work?

I understand that it resolves around computed5 not changing its value, because computed2 is always 0, but it can't possibly know it'll always be 0, since it depends on computed1, so it has to run every time to check, yes?... I think I'm confused about how much of the graph is marked as dirty each iteration of head.write(i), and in what order computeds are notified and re-executed. Are transitive dependencies (i.e head) passed up in Kairo? In the frameworks I've studied I'd see head "passed up" each time such that computed5 is notified/called directly by head, which in turn calls "down the tree" (which is great for conditional logic where you want to only execute necessary computeds but maybe not relevant in this code example).

Any insight and discussion would be helpful. Thanks!

[lord]

(not sure i have much to add here, but if you liked the graph in that thread, you may enjoy the follow up blog post i wrote with what i learned from that conversation)

[3Shain]

I understand that it resolves around computed5 not changing its value, because computed2 is always 0, but it can't possibly know it'll always be 0, since it depends on computed1, so it has to run every time to check, yes?

yes
if computed2 unchanged, then computed3 will be skipped, and so do computed4, computed5...

I think I'm confused about how much of the graph is marked as dirty each iteration of head.write(i), and in what order computeds are notified and re-executed.

all of affected downstream nodes
the optimization is: if dependencies not changed, the computation stay unchanged. in other word, the computation should be re-computed only if any of dependencies did change(then skip the computation if unchanged, but the propagation will continue) (so the expression of computation must be referential transparency)
the propagation order is topological (and there are 2 dfs passes, the first one finds the sorted routine (by inc .dc:dependency counter and dec it in second pass (propagate once it becomes zero)) and the second one do the real computation/optimization), and it's guaranteed that the depended (parent) nodes will be fresh (updated) before updating the children. but there is an exception, for example a:=b?c:d, given previous dependencies are {b,c} but later it changes to {b,d} ,d might be not fresh yet, then the computation will be deferred and re-computed when d is fresh (it's very sophisticated and I hadn't had time to break down the concepts)

Are transitive dependencies (i.e head) passed up in Kairo?

nope

[nettybun]

@lord Thanks yes I've read that blog post at least 5 times 😅

@3Shain I appreciated the explanation and links to Kairo's code! I'm familiar with the 2x DFS algorithm and have seen it used in the Incremental library as well: https://youtu.be/G6a5G5i4gQU?t=1340.

I understand Kairo stops propagation when dependencies are unchanged, and that's a "cutoff", but Incremental talks a lot about the importance of cutting off propagation if the value is "good enough" and I see Kairo does have this comparison as observer.cp = Object.is. However in propagate() it seems the propagation will continue regardless of the value comparison so the computation change is not cut off?

As a comparison then:

• In Kairo computed2 is always running and returning 0, propagating 0 to computed3. In the run of computed3, it skips recomputation because it identifies that the dependencies have not changed (and therefore cuts off propagation).
• In Incremental computed2 would cut off propagation internally at the compare step and computed3 is never run.

I believe it's a small difference in responsibility of propagation, and I think both options are right... but in the Incremental video they say this leads to exponential recalculations https://youtu.be/G6a5G5i4gQU?t=1667. I think Kairo isn't vulnerable to this due to your deferred execution that prevents double execution of nodes....

[3Shain]

it seems the propagation will continue regardless of the value comparison so the computation change is not cut off?

propagation will always happen, while computation will not.
and it's necessary to do full propagations, because in first pass I have no idea which node will not change but the state is mutated (as .dc increase), then in second pass, even I know a node is unchanged without re-compute it, I still need to reverse the mutation (dec .dc). I can't just say let's forget about the downstream nodes in second pass otherwise I get bad state left.

and I should rephrase it identifies that the dependencies have not changed as it sounds like there is a function identifying whether any dependency changed. in fact all downstream nodes are assumed not changed, however, because parent(s) is definitely visited (updated/freshed) before children, so it's a changed node marking its direct children (not all downstream) changed (and we have source data nodes, which are definitely the sources of changes), so that when a node is visited, the fact "whether any dependency changed" is certain.

it's true that computation nodes hold their dependencies (sources) but that's completely for managing subscription, and in propagations they are never used.

about exponential recalculations, i think it has nothing to do with deferred execution, but the design of .dc that makes sure a node is visited exactly once.