Incremental: Self-Adjusting Computations in OCaml

I am Sebastian, a developer at Jane Street. We use OCaml across trading systems and infrastructure, and I want to introduce Incremental, our library for self-adjusting computations. I will explain its interface and then some of the implementation challenges we encountered across several versions.

The idea, based on work by Acar on self-adjusting computation, is to represent a complex calculation and its changing inputs as a dependency graph. When inputs change, the library does the necessary work to update the outputs that users care about, rather than rerunning every calculation.

A spreadsheet is a useful analogy: input cells feed calculations, and changing inputs updates their dependents. The crucial difference in this comparison is that Incremental’s graph can itself change with the inputs. Its dependencies are dynamic rather than fixed in advance.

Our first application was trading systems. Market events feed calculations of quantities such as fair value, which in turn inform trading decisions. We have also used the library to update complex risk models in real time and to construct user interfaces that update only the affected portions when data changes.

We have also been exploring dynamic web applications using js_of_ocaml, which compiles OCaml to JavaScript. The same idea of describing an output from changing data can apply in the browser.

The interface has a type for an incremental computation producing a value of some type, and a constant constructor for a value that never changes. Variables provide changing inputs. Map transforms an incremental value with a function, creating a new node dependent on the original.

Map2 combines two incremental inputs using a function. That matters because map alone can fan out from a node, but cannot bring two dependencies together into a single computation. Bind, which I will return to, supplies the more powerful dynamic part of the interface.

Stabilize has a unit-to-unit type, but it performs important work. Changing an input does not immediately recalculate the graph; the user explicitly calls stabilize to perform the necessary updates. This is a deliberate design choice.

Explicit stabilization lets us batch updates and avoid exposing intermediate, inconsistent states. In a trading system, several changes arising from one market event may need to be considered together before presenting an indicator; recalculating after each partial change could lead to an undesirable decision.

For a simple example, define height and width as variables and use map2 to multiply them into a rectangle’s area. Register a callback, set the inputs and stabilize to print the result. A subsequent change prints nothing until the next stabilization, which applies the accumulated changes.

Bind differs subtly from map in its type: its function returns another incremental computation. That lets the graph selected by the function change with its input. Map and map2 build static dependency structures; bind makes the dependency graph dynamic.

A conditional can be expressed with map3 over the condition and both branches, but then both branches remain dependencies. Changes to an inactive branch may still cause work. With bind, the selected branch becomes the dependency, so work underneath the unused branch need not propagate.

Cutoffs provide another way to avoid unnecessary work. A node can prevent an update from propagating if its value has not changed enough, for example by a specified percentage. That can be useful when a small numerical change is not significant enough to justify recomputing a large statistical model.

Implementing the library largely comes down to the stabilization algorithm. A first attempt uses two passes: starting at changed inputs, mark dependent nodes dirty and count children that must be recomputed; then recalculate from the leaves upward, waiting for each node’s dirty children.

A simple algorithm also has to cooperate with the garbage collector. If inputs remain live and point upward through the graph, old branches can remain reachable even when a bind changes the graph and users no longer need them. Without care, unused nodes accumulate.

One approach uses reference counts, pointers in both directions, and sentinels exposed to users as proxies for observed nodes. A finalizer on a collected sentinel can help clean up graph references when the corresponding output is no longer needed.

The two-pass algorithm has a separate problem with cutoffs. Its first pass marks parents dirty before it recomputes the cutoff node, so it cannot yet know whether a change should propagate. An optimistic workaround assumes it will not propagate and restarts if recomputation shows otherwise.

That workaround performed well in the original workload, where cutoffs often stopped propagation, but became painful under other usage patterns. A wrong optimistic assumption can force work to be repeated. We needed a better ordering for recomputation.

A topological order and a heap can ensure that children are updated before their parents. Dynamic binds complicate the ordering: recomputing a full topological sort whenever the graph changes would be expensive. Pseudo-timestamps allow a newly created node to be placed between existing nodes.

The labels need room for future insertions. A data structure can distribute them using heuristics and occasionally pay for an expensive redistribution when it runs out of space. This approach was relatively easy to implement, but in our measurements the heap made it roughly 1.5 to 4 times slower than the first version.

Another problem was garbage retained until finalizers ran. In the runtime behavior we observed, finalization could be delayed a long time. Until the collector recognizes that nodes are dead, input changes can keep triggering work in obsolete parts of the graph, with especially bad behavior when many binds are involved.

The interface needs an explicit notion of what is observed and when it stops being observed. An observer tracks outputs that users care about, and a stop-observing operation says that an output no longer needs computation. This avoids relying solely on delayed collection to stop obsolete work.

The heap still costs too much. In version six we took advantage of the fact that a total order is unnecessary: nodes at the same height cannot depend on one another, so they can be processed in either order. Many of our graphs have millions of nodes but heights of only around 20 or 30.

Instead of a heap, a small array of lists can group nodes by height. Dynamic graphs still create a problem: recalculating all heights on every bind would waste work. We use pseudo-heights, increasing a height when necessary but not decreasing it simply because a dependency moved.

A pathological graph that repeatedly alternates can make pseudo-heights grow indefinitely. Our practical safeguard is to fail when a configurable height limit is exceeded—128 in the example. In our workloads, this has not been a practical problem.

After six versions, we recovered performance comparable to the original baseline while making cutoffs work and binds efficient. It was frustrating to spend so much effort making the initial implementation slower before eventually getting back to its speed with correct behavior.

Further work yielded another two- to threefold improvement. A graph contains heterogeneous incrementals—integers, floats, strings and other types. One common way to hide those differences is to store closures that operate on nodes, but closures allocate memory and can be expensive.

Generalized algebraic data types, or GADTs, let the implementation represent and pattern-match over heterogeneous node kinds without relying on the same closure-heavy approach. The result greatly reduced allocation and sped up real applications. It is an example of a type-system feature proving useful for practical performance.

Applications using Incremental are often limited by time spent in the library itself. That is a reason to take on the sometimes painful work of building a reusable abstraction: a generic library can be profiled across many uses, making optimizations worthwhile that a one-off application might never receive.

For example, a node’s record contains the information needed by several use cases. We tried rearranging its fields to find an ordering that worked better for caches, and obtained an improvement. It is a simple optimization, but one that a developer writing only a single application might not consider.

There is still room for further work, such as explicit memory management or collapsing nodes, though neither is as trivial as it may sound. Incremental is open source on GitHub, and its documented interface is available for anyone who wants to explore it.