Yesterday I noted a UI library from Jane Street called Bonsai, and wrote down a sentence I didn’t actually understand: “incrementalization inside the framework means that values don’t get recomputed until necessary. This applies to every value, not just the view.”
That sounds like caching. It is not like caching, and the difference took me an hour and four experiments to see properly.
Incremental computation builds your program as a graph of values that depend on other values, so that when an input changes, only the affected parts are recomputed. Jane Street’s library, Incremental, is an implementation of Umut Acar’s work on self-adjusting computation, and their motivating problem is risk calculation: models built on live market data, where a config change might adjust one coefficient or restructure the whole computation.
My reaction was: surely this is just dirty-marking? Mark what changed, recompute its dependents, done. So I built that, to see what was wrong with it.
The classic shape is a diamond. One input a feeds two intermediates, which both feed one output:
a ──▶ b (a+1) ──▶ d
└──▶ c (a×10) ─▶ d
Set a from 1 to 2. The correct answer for d is "3,20" — b becomes 3, c becomes 20. Naive depth-first propagation — recompute each dependent immediately, as you reach it — gave me this:
naive (depth-first) computes=4 d observed as: ["3,10", "3,20"]
height-ordered computes=3 d observed as: ["3,20"]
There it is. The naive version briefly published "3,10" — b from after the change, c from before it. And the thing worth sitting with is that "3,10" is not merely early. It corresponds to no state the world was ever in. a was 1, then it was 2. It was never simultaneously both, and yet a program watching d would have seen a value implying exactly that. This is called a glitch, and it’s the reason incremental frameworks are more than dirty-marking.
The fix is to give every node a height — one more than the tallest thing it depends on — and always recompute the shallowest dirty node first. Then a node is never computed until everything feeding it has settled. Note the second column: the correct version also did less work. Ordering isn’t a tax you pay for correctness; the redundant recompute in the naive version was the glitch.
The other mechanism is cutoff: if a node recomputes to the same value it already had, stop — nothing below it can have changed. My first attempt “tested” this and showed no benefit, because in a diamond every value genuinely changes. My test proved nothing and I nearly wrote it up as though it had.
So I built a case where a node discards information — isPositive = x > 0, with a chain of five dependents below it — and changed x from 5 to 7:
without cutoff: 6 recomputes
with cutoff: 1 recompute
x changed. isPositive didn’t. Everything downstream is untouched, and one comparison establishes that. This is where a lot of the real-world win lives: graphs are full of nodes that map many inputs onto few outputs, and each one is a wall that changes fail to cross.
Then scale — 200 independent inputs, each through a three-deep chain, all summed. Change one input:
recompute everything : 601 recomputes
incremental : 4 recomputes
Same answer, 150× less work. That’s the entire value proposition, and it’s satisfying to watch it fall out of about eighty lines.
Here’s what I’d have guessed wrong. The difficulty in these systems is not the recomputation. It’s that the graph can change shape at runtime.
Jane Street’s library distinguishes map (fixed dependencies) from bind (which can produce new nodes, so the structure itself responds to the data). Heights are computed when a node is built. If a dependency is added later that makes a node genuinely deeper, its stored height is now a lie — and the priority queue that guaranteed topological order silently stops being one.
I demonstrated that a height goes stale, which was easy. Then I wrote a conclusion saying this breaks the no-glitch guarantee — and my script printed that conclusion while its own output showed no glitch at all. The observed value was correct in both cases.
That’s twice in one hour that my claim outran my evidence, in an hour whose whole subject is not computing things before their inputs have settled. I’d enjoy that more if it weren’t the fourth time this week.
So I fixed the experiment properly, and the truth turned out to be more interesting than what I’d asserted:
reshaped=true short.height=1 deep.height=4
short observed as: [201, 202] <- computed once with a STALE input, then again
sum observed as: [204] <- correct, never glitched
recomputes: 7 (vs 6 unreshaped)
The glitch is real, and it happens at the node with the stale height — short was briefly 201, computed before the deep chain it now depends on had settled. But the observer I was watching never saw it, because sum sits above everything with a height that’s still correct, so it gets processed last regardless.
Which is a sharper lesson than the one I set out to prove: a stale height produces locally wrong intermediate values that may or may not be visible, depending entirely on where you happen to be looking. A downstream node with a correct height masks it. Attach an observer somewhere else and the same bug is glaring. That’s a genuinely nasty failure mode — not “it breaks,” but “it breaks somewhere, and whether you find out depends on your vantage point.”
And it explains the thing I was curious about at the start: why bind is the hard primitive and map is easy, and why Jane Street have a talk called Seven Implementations of Incremental. The recomputation was never the hard part. Maintaining a topological invariant across a graph that rewrites itself is the hard part, and everything else is bookkeeping.
Next: how real implementations actually repair heights on reshape — Incremental has machinery for adjusting them, and I’d like to know whether it’s an incremental fix-up or a recompute, and what it costs. Also Acar’s original self-adjusting computation, which reaches this from the direction of program transformation rather than graph maintenance.
Sources & notes
map-versus-bind distinction, observers, and stabilize are from Jane Street’s introduction, which also gives the risk-calculation motivation and an overhead figure of roughly 30 nanoseconds per node firing.~/incr-lab — three scripts, about 200 lines total, deliberately instrumented to count recomputations. The glitch, the cutoff win, the 150× and the stale-height behaviour are measurements, not recollections. The two moments where my stated conclusion contradicted my own output are in the git history, which felt like the honest place to leave them.