Jane Street's Incremental Library Enables Efficient Self-Adjusting Computations
Jane Street: Incremental
I am excited to share Incremental, a library designed to build complex computations that update efficiently as inputs change. Inspired by self-adjusting computation research, it helps developers create dynamic spreadsheets, responsive GUI views, and synchronized derived data without redundant processing. This tool ensures your calculations stay perfectly in sync with source data while maximizing performance.
Incremental is a library that gives you a way of building complex computations that can update efficiently in response to their inputs changing.
- jitl
This style of reactive programming is quite popular in JavaScript UI frameworks these days under the moniker “signals”, with a proposal for standardization here: https://github.com/tc39/proposal-signals#-javascript-signals...
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/...
- fadesibert
Goldman took the same approach with instrument pricing ~30 years ago. I recall long discussions about "Node Purpling" in my ~13 year tenure there.
Computer Science has evolved, and AFAICT this is not a graph approach, but things like differentiation are computationally expensive, and therefore you want to minimize the number of times you do it to as close to the theoretical minimum.
Edit: Related HN discussion https://news.ycombinator.com/item?id=36006737
- ronfriedhaber
This is cool.
As far as I can tell, incremental the library aims to solve the problem of partially hydrating a computation graph when source data is altered. This approach is similar to the one pursued by (well designed) build systems and is common in the FP world. [2] This has many use cases and is very cool.
In addition, in the sphere of incremental computation, there exists Differential Dataflow, Timely Dataflow (adjacent), and DBSP. Systems like Feldera are built on DBSP. Materialize is lead by some DD guys.
Personally, I am pursuing an orthogonal approach specifically for the problem of financial data and financial workloads, There exists huge, very important problems to solve! [1]
[2] Signals And Threads episode on the subject https://signalsandthreads.com/build-systems/
- djtango
I was very curious about Dataflow programming years ago - I think a lot of people were coming at this problem from various angles. This specific library immediately reminded me of Javelin from Clojure [0]
- RandomBK
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 way to batch changes together before recomputing (but again, doable with observables too).
Is the delta primarily coming from introspection and automatically building the compute graph? Or is there something more fundamental that I'm missing?