11–20 of 83 posts
I do not understand what is the big deal with Increment. Is it more efficient because it is written in OCaml rather than C#?
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners. I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as…
The fundamental components here are laziness and weak connections between graph nodes. Node values are getting materialized only when you observe them, and the system is flexible for live structural changes.
Usually, you don't need to materialize the entire graph when you need to observe just some nodes. Additionally, you can halt computations at any point in time leaving the graph in semi-actualized state, make extra changes to the inputs, and continue materialization of the nodes of interest. The algorithm will sort out all changes for you.
Essentially, incremental computations is just a term covering these features. You can organize the same system in terms of observers and subscribers.
Perhaps, classical Excel spreadsheets is the best illustration of the idea. Also, see my article on the topic: https://medium.com/@eliah.lakhin/salsa-algorithm-explained-c...
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners. I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as…
Roughly, you subscribe and listen to an observable. Incrementals are more like a cache across some DAG of computation + state that lets you optimize by only recomputing what needs to be recomputed. There's a really good talk from Ron Minsky here: https://www.janestreet.com/tech-talks/seven-implementations-...
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners. I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as…
A naive observer approach will 1) compute that potentially exponential blow-up very inefficiently and 2) probably have "concurrency" issues. This library will be close to optimal and correct, even if you start dynamically changing the graph structure.
But yes, you can achieve the same thing with observers and other kinds of approaches. Most of them just a lot harder to get right while avoiding performance cliffs.
It’s used by frameworks Vue, SolidJS, Svelte, Ember, Angular, and there’s a few different implementations for React like Mobx and Jotai. There’s a few different algorithms for how to propagate changes and evaluate the DAG, I believe SolidJS2 uses a height-based algorithm similar to Incremental.
I’ve been fooling around with an implementation that uses an Int32Array arena to allocate nodes and link them together with linked lists without paying O(dependency edges) GC load: https://github.com/justjake/dalien-signals/tree/dalien-signa...
There are a few of these for Rust as well, Leptos is an example in UI frameworks, and Salsa is an example in general incremental computing, used in rust-analyzer.
Another way to look at this sort of thing is as a build system with automatically tracked dependencies. One such build system is tup, which instruments build jobs to detect what files they read to establish dependency relationships. Interesting reading from the author: https://gittup.org/tup/build_system_rules_and_algorithms.pdf, see also the classic Build Systems à la Carte https://www.microsoft.com/en-us/research/wp-content/uploads/...
One thing I've never fully grokked is how this differs from an observable pattern where one can publish new values to inputs, propagate that through the computation, and push newly computed values to listeners. I guess there's probably optimizations around change detection and stopping the propagation if there's no change (though observables can do that as well). The stabilize command also makes things interesting as…
It depends on how you define the observable pattern. The fundamental components here are laziness and weak connections between graph nodes. Node values are getting materialized only when you observe them, and the system is flexible for live structural changes. Usually, you don't need to materialize the entire graph when you need to observe just some nodes. Additionally, you can halt computations at any point in time…
However I'm not sure Excel is such a great illustration in that case, as it's neither lazy nor weakly connected; at least at the surface.