Jane Street Incremental: A Library for Incremental Computations

Optimizing Computation via Incremental Updates

Incremental is an OCaml library designed to solve the problem of partially hydrating a computation graph when source data is altered. Instead of re-running an entire pipeline of calculations, the library tracks dependencies and only re-computes the specific nodes affected by a change, minimizing redundant work.

This approach is critical for performance-intensive applications where the cost of a full re-computation is prohibitive, such as in financial modeling, complex user interfaces, or large-scale build systems.

Core Mechanics and Implementation

Incremental functions by constructing a Directed Acyclic Graph (DAG) of computations. When an input value changes, the library propagates that change through the graph to update dependent nodes.

Key Technical Characteristics

• Dependency Tracking: The library automatically tracks which computations depend on others, allowing it to isolate the impact of a data change.
• Batching with Stabilize: The library provides a stabilize command, which allows developers to batch multiple changes together before triggering a re-computation, preventing unnecessary intermediate updates.
• Language Choice: Written in OCaml, the library leverages a strong type system to provide correctness guarantees that are often missing in dynamic implementations of similar patterns.

Relationship to Other Paradigms

Incremental computation is a recurring pattern across various domains of software engineering, often appearing under different names depending on the context.

Reactive Programming and "Signals"

In modern JavaScript UI frameworks (such as Vue, SolidJS, Svelte, Ember, and Angular), this pattern is known as "signals." These frameworks use similar DAG-based propagation to update only the parts of the DOM that depend on a specific piece of state. Some implementations, like SolidJS, use height-based algorithms for change propagation similar to those found in Incremental.

Build Systems

Well-designed build systems operate on the same principle: they detect which source files have changed and only re-run the specific compilation steps required to produce the final artifact. This is a form of incremental computation where the "graph" consists of file dependencies and build tasks.

Dataflow and Stream Processing

Incremental is conceptually related to several high-performance dataflow systems:

• Differential Dataflow (DD) and DBSP: Systems used for large-scale data processing that track changes (deltas) rather than re-processing entire datasets.
• IVM for SQL: Incremental View Maintenance (IVM) applies these principles to database views, ensuring that a view is updated incrementally as the underlying tables change.

Practical Applications and Ecosystem

UI Development with Bonsai

Jane Street has built a UI library called Bonsai on top of Incremental. While traditional Virtual DOM libraries (like React) skip some work by comparing trees, Bonsai makes the Virtual DOM itself incremental, reducing the overhead of constructing the tree in the first place.

Industry Precedents

Similar patterns have been used in high-stakes environments for decades. For example, some financial institutions implemented "node purpling" (a method of marking dirty nodes in a graph) for instrument pricing approximately 30 years ago to minimize the number of expensive differentiations required during pricing updates.

Comparative Perspectives from the Community

Community discussion highlights both the strengths and the conceptual overlaps of the Incremental library:

"One thing i have always linked about Jane street projects is that they tend to package ideas that have existed in research or niche system into something developers can actually use."

While some developers question the necessity of a dedicated library—noting that similar behavior can be achieved via observables or event-driven architectures in languages like C#—the primary advantage of Incremental lies in its automated graph construction and the efficiency of its change-propagation algorithms.