Understand the change propagation model

[tsugabloom]

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)