Yaron Minsky on Incremental: From Research Idea to Production Library

I want to explain Incremental, a library we use at Jane Street, and then trace the long route from our first implementation to the one we eventually used. Its ideas come from research on functional programming and self-adjusting computation. Our experience contains mistakes the academic work had already avoided, but also practical concerns the research had not emphasized.

The goal is to build large computations over substantial amounts of data and refresh them efficiently when only a small part of the input changes. The result should be a clean updated output without repeating all the work. A spreadsheet offers a useful analogy for this computational model.

A spreadsheet is a kind of functional language: a cell contains an expression calculated from other inputs. It reverses the usual emphasis of programming, making data prominent while hiding much of the logic inside cells. Each formula also creates dependencies on other cells.

Excel uses that dependency structure to avoid recomputing an entire large sheet after a few cells change. It also makes intermediate results easy to display: a monitoring sheet can reference points throughout a calculation. Incremental brings a version of this model into OCaml.

The early interface defines a parameterized incremental value, which can contain an integer, string or other type. The return operator turns an ordinary value into a constant incremental computation. Map takes an incremental and a function, producing a new incremental whose value changes when its input changes.

Map lets us grow a graph outward, but branching alone cannot bring results back together. Map2 accepts two incremental inputs and a function combining their values. Repeated combinations give us map3 and higher arities, allowing many branches to merge.

With return, map and map2, we can construct essentially arbitrary static directed acyclic dependency graphs. We can add nodes or have multiple inputs, but changing an input does not itself change the graph’s structure. That limitation matters for computations whose dependencies vary with the data.

Bind adds that dynamism. It takes an incremental input and a function that returns another incremental. The bind node can select a different right-hand dependency as its left-hand input changes; the small type difference from map gives the system substantial new expressive power.

Consider implementing a conditional with map3. It takes the condition, then branch and else branch as inputs and returns the appropriate value. Its graph remains connected to all three, so even a change in the currently irrelevant branch causes the conditional node to recompute.

A bind-based conditional instead selects the then or else incremental according to the condition. Only the selected branch is wired in at a time. Both implementations produce the same value, but they have different dependency graphs and therefore different performance behavior.

That conditional understates bind’s power. Its function can construct new incremental nodes, not merely select between two existing ones. Given a description of a configuration, for example, it can build a whole subgraph for the particular computation now required.

Map is generally simpler to use, understand and implement; bind is more powerful but adds complexity and often allocates nodes. For a tiny if statement, incrementalizing it at all may be unnecessary. These choices matter more for large computations and have to be assessed at their actual scale.

To understand an incremental program’s meaning, you can mentally remove the maps and binds and ask what the all-at-once computation does. To understand its performance, you must look closely at where incremental boundaries lie and how map and bind shape the graph.

The discussion mostly concerns functional computations without side effects. Another essential feature is a cutoff: a change may reach a node but leave its result unchanged, so there is no reason to propagate further. For floating-point results, an application might even choose a tolerance for insignificant changes.

The interface also needs a way to run the graph. Build the computation, modify inputs, then call stabilize to propagate changes. The early interface exposes a value operation for reading an incremental and an on-update callback for reacting when a watched value changes.

Inputs come from variables: create one with an initial value, set it when new data arrives and read its corresponding incremental. Together, variables and combinators let the programmer construct a graph, while stabilization and callbacks supply updated results.

An audience member asks about cycles. Pure functional construction largely prevents them, but practical optimizations such as memoizing and reusing subcomputations can introduce cycles or back edges. Handling those cases became a significant difference among the implementations.

The first version was written by Stephen Weeks and Milan Stanojevic. It represents the dependency graph using allocated OCaml objects and pointers. The direction of those pointers matters: changes arrive at the input leaves, so the implementation needs upward links to find the computations affected by changed inputs.

A naive depth-first propagation can recompute a node more than once when branches fan out and later merge. Stack such diamond-shaped graphs and one update can become two, four, eight and so on. Simply switching to breadth-first search does not solve the problem when branches have different lengths.

The first algorithm uses two passes. It marks the reachable affected nodes dirty and counts each node’s dirty inputs. During the second pass, a node waits until all its dirty inputs have been cleaned before recomputing, so converging branches do not repeatedly trigger it.

The algorithm is simple and fast, but the graph’s interaction with garbage collection is difficult. Upward pointers from live input variables keep everything reachable above them alive. What we really want to retain is determined by what someone observes at the output, not merely by connection to an input.

A bind can create a new branch and stop referring to an old one. Yet the old nodes are still connected to live inputs. Without extra machinery those nodes cannot be collected, even though nobody needs their results.

The original solution maintains reference counts for external references and disconnects nodes when their count falls to zero. Instead of handing the internal node to a caller, it returns a separate sentinel. A garbage-collector finalizer on the sentinel signals when the external reference disappears and updates the count.

Cutoffs expose a separate flaw. The first pass marks the entire reachable closure before values have been recomputed, so it cannot know that an intermediate output will remain unchanged. It has already committed to recomputing everything beyond that point.

The workaround assumed a designated cutoff would usually stop propagation. It ran the algorithm under that assumption, recorded cutoff nodes, and restarted propagation from any that changed enough. This works, but nested cutoffs can again cause repeated, potentially exponential work. We limited their use to relatively simple edges of computations.

The delayed collection of abandoned bind branches was worse than a memory leak. Until their sentinels were collected, those nodes remained connected to inputs and continued to compute. Nested binds could repeatedly produce more obsolete branches and allocate an exponential amount of unnecessary work before the collector caught up.

Our earliest applications did not use many nested binds, so this problem was not initially obvious. User interfaces made them attractive and exposed long pauses. Within its limitations, version 1 was still useful and fast, but its cutoff and collection behavior required a different approach.

For version 2 we returned to the research and found an approach based on ordering the graph. A topological ordering respects dependencies: an input is processed before a node that depends on it. A heap of dirty nodes can then always take the next eligible node in order.

When a node is recomputed in topological order, its dependencies are already current, and it need not fire twice for the same stabilization. Crucially, its new value is available at that moment, so a cutoff can stop propagation without invalidating the algorithm.

For a static graph, allocation time itself supplies an order: every new node depends on older ones, so a counter can label them. Dynamic bind nodes complicate this. A new node created inside a bind must fit at the right point in the existing order, not simply at the end.

The idea is to assign logical timestamps between existing labels, placing nodes created within a bind before that bind and after the appropriate earlier nodes. Repeated insertion needs a data structure capable of making room without making every comparison expensive.

One simple approach spaces integer labels apart and inserts between them. When the gaps run out, a batch operation redistributes labels. Other solutions use trees; the tradeoff depends on how often labels are allocated versus compared. Cheap comparisons were valuable to us.

An intern implemented a version with these ideas. Its semantics improved, but performance was roughly 1.5 to 4 times worse than the original. We did not put that version into production. The result was a useful reminder that a better algorithmic story still has to meet the workload’s performance needs.

Version 3 attacked the other problem: obsolete bind branches continuing to run. It explicitly tracked which part of the graph was observed. An observer is a value created from an incremental; it exposes results and update callbacks and can be explicitly stopped.

When a bind changes from one branch to another, the old branch becomes unobserved immediately and the new one becomes observed. Only the observed portion is allowed to compute. The obsolete nodes may remain in memory until collection, but they no longer keep generating work.

Observers are in a sense the dual of input variables. A variable introduces data into the graph; an observer extracts information from it. A collected observer can be unobserved automatically, but relying on collection to happen soon repeats the earlier mistake, so in practice callers should stop observing when finished.

Version 3 supported many internal user interfaces. Version 4 was a closer reading of Umut Acar’s research, combining ideas from versions 2 and 3 and teaching us additional dependency invariants. It was more of a learning exercise than a practical final implementation.

One difference concerned map and bind. Acar’s original implementation could express map in terms of the more powerful bind. But that forces unnecessary allocation as a graph is rebuilt. Specializing map for static dependencies avoided that practical cost in our implementation.

Version 5 was a more practical combination of the ordering and observation ideas. It also addressed a problem caused by memoizing subgraphs: reused nodes can introduce edges that do not fit the original timestamp order. Real programs had many such edges even when their behavior was sensible.

Earlier versions dealt badly with those edges and cycles: the original could loop forever, while a simple timestamp approach could reject an ill-founded edge. Version 5 used a dynamic topological-sort fallback when it encountered a back edge. This was somewhat ad hoc but gave better behavior in practice.

The remaining difficulty was speed. Nodes flowing through a heap incur nontrivial constant costs and logarithmic removal. Even after a team invested substantial work, version 5 was not fast enough for us to replace the existing system confidently.

Version 6 eliminated the heap. A total order was stronger than we needed: it is enough to order dependencies correctly while allowing unrelated nodes to share a rank. One candidate rank is height, defined as zero for leaves and one plus the maximum height of a node’s children otherwise.

A graph with hundreds of thousands of nodes might have only dozens of distinct heights. Instead of a heap containing every pending node, an array of lists indexed by height can schedule work with much lower overhead. The dependency order is preserved even though many nodes share the same height.

Exact heights have a cost when a dynamic bind changes size. If a small node’s height repeatedly rises and falls, recomputing the heights above it can touch a large fraction of the graph. A change that should be local can become linear in the graph’s size.

Pseudo-height avoids that repeated downward adjustment: it starts like height but never decreases. There are pathological graphs whose nodes can force each other upward indefinitely, but Minsky says the team rarely saw that in real programs and would receive errors if a committed height limit was exceeded.

With version 6 the system had the improved semantics while performance had returned close to version 1. Version 7 then reduced the cost of finalizers. Earlier versions attached a finalizer to every sentinel so they could find and disconnect graph nodes that were no longer externally reachable.

The new approach uses observation information to maintain an invariant: no pointer runs from the observed part of the graph into the unobserved part. When observation changes, the system cuts or restores the relevant upward connection. Unobserved nodes then become collectible when nothing else retains them.

That change greatly reduced the number of finalizers. A 300,000-node graph with ten observed outputs could need about ten rather than 300,000. Version 7 also identified a bind-related semantic constraint: old nodes created by a prior firing can become obsolete and must not remain valid dependencies.

The team thought version 7 was the end, but review led to version 8. By then they understood allocation costs better and OCaml had gained generalized algebraic data types, or GADTs, which allow a more expressive representation of heterogeneous graph nodes.

The graph has nodes producing different types, yet they must live together in internal structures. The older solution packaged each underlying object behind a record of closures. Those functions hid the object’s type, allowing a common container and a limited set of operations.

That representation was expensive when many closures were allocated. It was also awkward to program against: every permitted operation needed its own wrapper, while the ordinary variants and records that reveal a structure were hidden. Minsky compares the experience to programming with oven mitts.

Existential packaging and GADTs let the implementation describe values whose precise type is hidden while still representing the different node cases directly. Removing unnecessary closures saved memory and made the code easier to understand. Seeing the graph’s actual structure also exposed opportunities for additional rewrites and optimizations.

The change produced a dramatic result. Minsky reports that some substantial, already tuned end-user applications became three times faster—not merely that the library itself gained a threefold speedup. Once incrementalization removes most of the original computation, the framework’s own overhead can dominate what remains.

One slow trading-system front end had remained on version 3. When the team finally moved it to version 8, users described a striking improvement. By this point Incremental supported both computational engines and user interfaces, with plans to expand its use for interfaces.

For browser interfaces, OCaml can compile to JavaScript, and incremental computation fits naturally with a virtual-DOM-style view: treat what a user sees as a function of data, then optimize updates to that function. At the time of the talk, the team was exploring this application.

A remaining difficulty is a large functional data structure arriving as a new whole value each time. Incremental works naturally when inputs are already separated into many small incremental values, but turning a changing large structure into efficient fine-grained dependencies needs additional primitives.

The proposed approach takes advantage of efficient differences between persistent structures. A map’s symmetric-difference operation can discover changes while stopping at physically identical shared subtrees. That can expose changed components without traversing the entire old and new structures.

Another possible optimization comes from the Father Time system for Scheme and Racket. If every small operation becomes an incremental node, overhead can overwhelm useful work. Its lowering optimization combines nodes into larger units, accepting less fine-grained incrementalization to improve overall efficiency.

Minsky suggests a trace-based approach that records costs and uses them to decide which nodes to combine. Jane Street’s programmers already choose where to introduce incremental nodes, so the optimization is less critical there, but it could let people write broadly incremental code and recover performance automatically.

The larger lesson is how far an idea may have to travel from a paper before it is comfortable in production. The team did not merely demand that the library be faster: it experimented with multiple representations and algorithms, learned their failure modes and built a better understanding of the problem through use.