Incremental

Speaker Context & Scope

• Sebastian, a developer at Jane Street (the largest industrial user of OCaml), discusses the "Incremental" library for self-adjusting computations.
• The talk covers the library's features, real-world use cases (trading, risk models, UIs), and the eight-version evolution of its internal implementation.

Core Concept: Self-Adjusting Computations

• The library maintains a dependency graph where leaf nodes are inputs, internal nodes are computations, and outputs are results of user interest.
• Unlike Excel's static dependency graphs, Incremental supports dynamic graphs where the graph structure itself changes based on input values.
• The system performs the minimal work necessary to update computations only when dependencies actually change.
• Use cases include:
  • Trading Systems: Computing fair values and trading indicators based on live market events.
  • Risk Models: Real-time recalculation of complex, frequently changing dependency graphs.
  • User Interfaces: Efficiently updating only the subset of the UI affected by specific data changes (leveraging Js_of_ocaml for web apps).

API Design & Key Functions

• map / map2: Create static edges in the dependency graph; map fans out from a single input, while map2 allows combining two inputs.
• stabilize: A user-controlled function that triggers computation updates only when explicitly called.
  • Prevents exposure of inconsistent intermediate states to the user.
  • Enables efficient batching of updates (avoiding redundant recalculations for transient changes).
• bind: Enables dynamic graph topology by allowing the graph structure to change based on input values (e.g., effectively implementing conditional logic where branches are created or destroyed).
• Cut-offs: A mechanism to prevent propagation of changes if a node's value does not change significantly (e.g., ignoring statistically insignificant fluctuations in risk models).

Implementation Evolution & Challenges

• Version 1 (Naive Approach):
  • Used a two-pass algorithm (marking nodes dirty, then recomputing) with a counter for children.
  • Failure Mode 1 (Garbage Collection): Without reference counting or finalizers, the garbage collector could not collect obsolete graph nodes, leading to memory leaks.
  • Failure Mode 2 (Cut-offs): Could not efficiently handle cut-offs because the algorithm required knowing if a node changed before marking parents, forcing premature computation.
• Version 2 (Optimistic Cut-offs):
  • Assumed cut-offs wouldn't propagate; restarted the algorithm if the assumption proved false.
  • Resulted in poor performance for use cases where cut-offs did propagate.
• Version 3 (Topological Sorting):
  • Implemented topological sorting to ensure correct update ordering.
  • Performance Penalty: Used a heap for sorting, causing a 1.5x to 4x slowdown.
  • Exponential Garbage: The reliance on OCaml finalizers (which run late) led to exponential recomputation of dead nodes before collection occurred.
• Version 6 (Current Stable Baseline):
  • Replaced the heap with a partial order based on node "heights," utilizing an array of lists instead of a heap to eliminate the sorting overhead.
  • Implemented pseudo-heights to handle dynamic graph changes without constant re-sorting (increasing height only when necessary, "blowing up" if thresholds are exceeded).
  • Introduced explicit observer tracking and stop_observing to prevent exponential garbage accumulation.
  • Restored performance to baseline levels while supporting dynamic binds and cut-offs.

Optimization Techniques

• GADTs (Generalized Algebraic Data Types): Used to store heterogeneous types (ints, floats, strings) in a single list without heavy closure allocations, mimicking object-oriented polymorphism efficiently.
• Cache Optimization: Rotated record field orderings within the generic library to improve CPU cache locality, a technique feasible only because the library was built as a generic abstraction.

Future Directions

• The team is exploring explicit memory management and node collapsing.
• The library is open-sourced on GitHub with a documented interface (MLI).