When incremental computation beats recomputing everything
Code that recomputes everything when the input barely changed is everywhere. Edit one line in a file and the whole project gets type-checked again. Change one cell and the entire report is rebuilt. The fix looks obvious. Record what depends on what, then rerun only the parts that changed.
The catch is that the recording costs something too. You build and maintain a dependency graph, and you walk it on every change. Incremental computation is therefore not a technique that makes things faster by being applied. It is a trade with a definite break-even point. This piece looks at where that point sits, using numbers the implementations themselves published.
What graph propagation saves, and what it charges
Jane Street’s Incremental documents this trade unusually candidly. The library builds a directed acyclic graph out of input variables (Var.create), combinators (map2, bind) and observers (observe). Changing a value does not immediately run a computation. Var.set updates only the input, and actual recomputation happens when you call stabilize(), over the affected subgraph alone. Because change and computation are decoupled, several inputs can change within one tick and recomputation still happens once.
The cost sits in the same document. Processing a single node runs about 30ns (blog.janestreet.com). That figure sets the break-even. Either the work a node performs has to be far heavier than 30ns, or the portion of the graph that genuinely needs recomputing has to be very small, before there is anything left over.
Turn it around: if each node does roughly one addition and most of the graph is touched whenever an input changes, recomputing from scratch wins. The same post shows an example that groups an array into a binary tree so the update cost falls to log(n). That works not because the technique is clever but because the dependency structure was deliberately kept shallow. Graph depth and fan-out are decided by the designer, not the library.
The real savings come from early cutoff
A naive implementation that only follows dependencies does unnecessary work more often than you would expect. When an input changes it invalidates everything downstream, yet intermediate results frequently come out identical. Add a single whitespace character to a file and the parse result may differ while the type signatures do not. Whether propagation can stop right there is what separates fast from slow.
The red-green algorithm that Salsa inherited from rustc tackles this head-on. The database tracks a current revision and bumps it whenever an input is set. Each input records the revision in which its value last changed. A tracked function also stores the other tracked functions it depended on and the revision in which each of those last changed. When it is called again and no dependency has changed, it returns the cached value and skips execution.
The key idea is backdating. Even if an input changed and the function re-executed, when the output matches the previous one the system records the output as effectively unchanged (salsa-rs.github.io). Invalidation then stops spreading to downstream computations.
That is early cutoff, and it is the reason incremental computation pays off in practice. Dependency tracking only narrows the range you have to re-examine. What reduces actual work is the ability to judge cheaply whether a recomputed result matches the old one. Where comparing results is expensive, this advantage disappears.
A second axis that removes validation cost too
Early cutoff has a limit of its own. Even when nothing is recomputed, confirming that the cache is still valid means walking the graph. Recomputation cost goes to zero; validation cost remains.
rust-analyzer felt this acutely. Every keystroke changes project code, while the standard library typically stays fixed for the whole session. Editing src/lib.rs once nevertheless meant validating every query related to the standard library, and that alone took roughly 300ms (rust-analyzer.github.io). It was pure checking, not recomputation. Adding 300ms to a completion response is fatal.
The fix was to split a single global version number into a version vector with one component per durability tier. Standard library inputs are marked durable, user code volatile. A derived query automatically inherits the lowest durability among the inputs it directly depends on, and lower-durability components rise whenever higher-durability ones do.
Validation then compares only the component matching the query’s durability tier. If that component has not changed, the entire subgraph can be skipped without walking individual dependency edges. The lesson is unambiguous. Group inputs with different change frequencies into the same tier and the most frequently changing input sets the validation cost for all of them.
Demand-driven and update-driven are not the same
Implementations split into two broad styles. Update-driven systems propagate changes downward the moment an input changes. Demand-driven systems defer computation until someone asks for a result.
Adapton makes the latter an explicit design principle. Only computations an observer demanded are re-executed, and changes are recorded hierarchically in a demanded computation graph (cs.umd.edu). Intermediate results nobody uses are not refreshed. They are computed later, against the newest inputs, when someone actually asks. Incremental’s observe behaves similarly: unobserved nodes are not stabilized.
The difference plays out differently in a UI than on a server. Demand-driven works well in a UI where only visible results matter. There is no reason to compute ten thousand rows scrolled off screen.
For systems like alerting or monitoring, where a condition must not be missed even when nobody is watching, demand-driven can be dangerous. No observer means no computation. Such systems need a resident observer, which effectively makes them update-driven. Decide when the result is needed before picking a library.
Signals that you should not adopt it
Read the numbers above in reverse and the conditions against adoption emerge.
If per-node work sits around 30ns and the graph is small, bookkeeping eats the gain. In areas where the result changes nearly every time an input changes, early cutoff never fires. You recompute everything and pay graph maintenance on top.
Expensive or imprecise equality comparison on results also erodes backdating. Deeply comparing a large struct every time is the classic case. Group inputs of differing change frequency into one undifferentiated tier and you can land on the same pure validation cost, the 300ms that rust-analyzer hit.
The opposite conditions make it worth considering: only a small fraction of inputs need recomputing, intermediate results often stay identical, computing one node is expensive, and the same computation repeats several times a second. Compiler front ends, live dashboards and derived metrics in trading systems cluster here for a reason.
Finally, budget the implementation cost. Jane Street reimplemented Incremental seven times (janestreet.com). They did not merely change the interface; they kept revising graph maintenance, execution ordering and memory reclamation. If you plan to build an incremental computation system yourself, price in the likelihood that your first implementation is not your last.
References
[1] Jane Street. Introducing Incremental. Jane Street Tech Blog.
[2] Jane Street. Seven Implementations of Incremental. Jane Street Tech Talks.
[3] Salsa. The “red-green” algorithm. Salsa Reference.
[4] rust-analyzer. Durable Incrementality. 2023-07-24.
[5] Hammer, M. et al. Adapton: Composable, Demand-Driven Incremental Computation. PLDI 2014.
[6] Jane Street. janestreet/incremental. GitHub.