Self‑Adjusting Computations Made Practical: A Deep Dive into Jane Street’s Incremental Library

![Featured image]()

Thesis

The release of Incremental marks a turning point for OCaml programmers who need to keep large, interdependent calculations up to date without recomputing everything from scratch. By turning a program into a mutable directed‑acyclic graph (DAG) whose nodes automatically recompute only when their inputs change, the library provides a general‑purpose framework for what researchers call self‑adjusting computation (SAC). Unlike spreadsheets, which have a fixed dependency structure, Incremental allows the graph itself to evolve at runtime, opening the door to a host of applications that were previously the domain of hand‑crafted incremental algorithms.

---

Key Arguments

1. A clear conceptual model: variables, observers, and stabilization

Incremental structures a computation around three primitives:

• Variables (Inc.Var.create) represent mutable inputs.
• Incremental nodes (Inc.map, Inc.map2, Inc.bind, …) describe pure transformations of those inputs.
• Observers (Inc.observe) mark the results the program cares about.

The runtime does not recompute automatically; instead, the programmer calls Inc.stabilize to push changes through the graph. This explicit stabilization step makes the cost of updates predictable and gives developers fine‑grained control over when recomputation happens.

2. Dynamic graph topology distinguishes SAC from spreadsheets

In a spreadsheet, the dependency graph is fixed when the sheet is built. Incremental, by contrast, lets you re‑wire the graph on the fly. The bind combinator is the primary tool for this: it creates a new sub‑graph that depends on a changing input, and the framework discards the old sub‑graph when the input changes. This capability is essential for problems where the set of relevant data can grow or shrink, such as computing the average of a user‑specified prefix of an array.

3. Real‑world use cases illustrate the library’s versatility

Domain	How Incremental helps
Online combinatorial algorithms	By incrementalizing a batch algorithm, the library can match the asymptotic performance of bespoke online solutions while keeping the code simple and declarative.
GUI construction	Rendering a view from a model becomes a pure function; wrapping it in Incremental means only the parts of the UI that depend on changed model fields are redrawn, mirroring the goals of functional reactive programming but without the time‑centric semantics.
Configurable risk calculations	Risk models often combine market data with user‑defined configurations. Incremental lets a single computation react efficiently to both small market updates and large configuration changes (e.g., swapping out an entire factor list).

These examples show that the library is not a niche research artifact but a practical tool for everyday engineering problems.

4. Performance considerations and trade‑offs

The library’s overhead is measurable: a single node fires in roughly 30 ns on a typical laptop. Consequently, Incremental shines when each node encapsulates a non‑trivial amount of work or when the overall graph is large relative to the portion that needs updating. For tiny, cheap operations the cost of maintaining the graph can outweigh the benefits, so developers should profile their workloads and consider batching small calculations into larger nodes.

5. Implementation details that matter to the practitioner

• Generative functor – Incremental_lib.Incremental.Make () creates an isolated world with fresh types, preventing accidental mixing of values from different incremental contexts.
• Unordered array folds – Inc.unordered_array_fold ~f ~f_inverse exploits the existence of an inverse operation to achieve O(1) updates for sums, products, or other monoids with inverses, dramatically improving performance over a naïve binary‑tree merge.
• Binding for dynamic structure – Inc.bind is the only combinator that can introduce new nodes during recomputation, making it indispensable for workloads where the shape of the computation depends on runtime data.

---

Implications for the OCaml Ecosystem

Incremental brings a level of reactivity to OCaml that previously required external libraries or custom frameworks. Its design aligns with the language’s emphasis on pure functional core and controlled side effects, allowing developers to keep most of their code pure while still gaining the efficiency of incremental updates. The library also demonstrates that sophisticated research ideas—originally published by Umut Acar and colleagues—can be packaged into a production‑ready tool, encouraging further cross‑pollination between academia and industry.

---

Counter‑Perspectives

Critics may argue that the explicit stabilize call adds boilerplate compared to fully automatic systems like FRP libraries (e.g., react or sodium). However, this explicitness is intentional: it gives developers deterministic control over when recomputation occurs, which can be crucial in latency‑sensitive trading applications where unexpected background work could jeopardize performance guarantees.

Another concern is the learning curve associated with the generative functor pattern and the need to reason about graph topology. While the initial mental model is steeper than writing a straightforward loop, the payoff becomes apparent as the codebase grows; the same logic that would otherwise be scattered across ad‑hoc caches and manual invalidation becomes declarative and centrally managed.

---

Conclusion

Jane Street’s Incremental library transforms the abstract notion of self‑adjusting computation into a concrete, usable API for OCaml developers. By exposing variables, pure transformation nodes, and observers, and by allowing the dependency graph to evolve at runtime, it equips engineers with a powerful abstraction for a wide range of problems—from live algorithmic trading dashboards to configurable risk analytics. The library’s modest overhead means it is best applied to computations where each node does substantial work, but when used judiciously, it can replace brittle hand‑rolled caching mechanisms with a mathematically sound, automatically maintained system.

Developers interested in experimenting with the library can find the source and documentation on the Jane Street GitHub repository. The accompanying well‑commented .mli files provide a thorough guide to the API, and the blog post itself contains a compact set of examples that illustrate the core ideas.