Seven Implementations of Incremental

Core Concept and Goals

• Incremental is an internal OCaml library designed to efficiently refresh large, complex computations when only small subsets of input data change.
• The computational model mimics spreadsheets, where data is primary and logic is expressed as a dependency graph, allowing for efficient, localized updates rather than full recomputation.
• The system aims to reify intermediate computation results, enabling easy visualization and monitoring of partial states within the dependency graph.

Interface and Computational Model

• return (or const): Wraps a static value into an incremental computation that never changes.
• map: Applies a pure function f: a -> b to an incremental a, producing an incremental b that updates only when the input changes.
• map2: Combines two incrementals (incremental a and incremental b) via a function a -> b -> c, allowing the merging of parallel computation branches into a static Directed Acyclic Graph (DAG).
• bind: Introduces dynamism by allowing the dependency graph structure to change based on values; it takes an input and a function returning a new incremental, enabling conditional logic (e.g., if-else where branches are entirely different graphs) or dynamic graph construction.
• bind vs. map trade-off: map is simpler and faster for static structures, while bind adds significant complexity and allocation overhead but is necessary for dynamic behavior; confusing the two leads to performance catastrophes in nested scenarios.
• stabilize: The execution entry point that flushes the entire dirty computation graph, propagating changes from leaves to roots.
• onUpdate: Registers a callback to be triggered when a specific incremental value changes, allowing for reactive UI updates or side effects.
• Variable: The root data source; users create variables with initial values and read them to convert them into incrementals for the computation graph.

Evolutionary History and Technical Challenges

• Version 1 (Academic approach): Implemented a two-pass algorithm (marking dirty nodes, then recomputing) which suffered from exponential blowup in recombinant graphs (diamond patterns) if not handled with care, and could not support computation cutoffs.
• Garbage Collection Failure (V1): Reliance on GC to collect unobserved nodes led to exponential memory growth in nested bind scenarios; old nodes remained alive because upward pointers from inputs kept them referenced until GC ran.
• Cutoff Limitations (V2): The first attempt to support "cutoffs" (stopping propagation early based on value similarity) was inefficient, requiring repeated algorithm restarts and suffering from potential exponential re-firing.
• Time-based Topological Sort (V3): Introduced logical timestamps to ensure nodes fire only once in a specific order; however, dynamic graph restructuring caused timestamp ordering issues, and the implementation was 1.5x to 4x slower than V1.
• Explicit Observers (V4): Solved the exponential garbage problem by introducing "observers" (the dual of variables) to explicitly track the "observed" vs. "unobserved" parts of the graph, eagerly quiescing unobserved nodes to stop them from consuming resources.
• Dynamic Top Sort (V5): Attempted to handle cycles and back-edges introduced by memoization (common subexpression elimination) by adding a fallback topological sort, but performance remained poor due to the overhead of heap operations.
• Pseudo-Height Optimization (V6): Replaced the expensive heap-based scheduler with a partial order based on "pseudo-heights" (monotonically increasing depth metrics); this allowed using simple arrays instead of heaps, drastically improving performance while handling dynamic structures.
• Finalizer Elimination (V7): Reduced GC pressure by using observer reachability to enforce invariants, allowing the unobserved world to be garbage collected without needing finalizers on every sentinel node.
• Generalized Algebraic Data Types (GADTs) (V8): Switched from "poor man's objects" (records of closures) to GADTs to encode existentials natively; this eliminated closure allocation overhead, improved compiler optimization opportunities, and yielded a 3x speedup in end-user applications.

Current Status and Future Directions

• Production Impact: Migrating a trading system frontend from V3 to V8 transformed it from a performance bottleneck ("ruined my life") to the fastest application in the suite.
• JavaScript Compilation: The team is exploring using Incremental to incrementalize virtual DOM updates for OCaml-to-JavaScript compilation, aligning with React-like patterns.
• Functional Data Structure Diffing: Research is ongoing to add primitives that efficiently incrementalize changes in large functional data structures (e.g., maps) by leveraging efficient structural diffs (symmetric difference).
• Node Lowering: Potential future work involves "lowering" or inlining small incrementals into larger nodes based on usage statistics (trace-based optimization) to reduce overhead for programs where programmers lack granular control over node construction.
• Cycle Handling: The current implementation (V8) safely handles back-edges and cycles that previously caused infinite loops or exceptions in academic implementations.
• Semantic Safety: The team identified that nodes created in a bind are ephemeral; dependencies on "old" nodes from previous bind firings are unsafe and must be explicitly obsoleted.

Key Lessons

• Academic vs. Industrial Gap: Academic algorithms often assume perfect purity and static structures; real-world usage requires handling dynamic graphs, memoization, and GC constraints.
• Implementation Depth: Reaching production-ready performance required multiple iterative rewrites to address subtle issues like garbage collection timing, scheduler complexity, and data structure overhead.
• Incrementalization Limits: As the library becomes more optimized, the incremental framework itself becomes the primary performance bottleneck for the application, highlighting the high returns on continued framework refinement.