Incremental：OCaml 中的自调整计算

我是 Sebastian，Jane Street 的开发者。我们在交易系统和基础设施中使用 OCaml，我想介绍用于自调整计算的库 Incremental。我会先解释它的接口，再介绍我们在多个版本中遇到的一些实现挑战。

这个想法基于 Acar 对自调整计算的研究：把复杂计算及其变化的输入表示为依赖图。输入改变时，库只做必要的工作，更新用户关心的输出，而不是重新运行每一项计算。

电子表格是一个有用的类比：输入单元格为计算提供数据，输入变化会更新依赖它们的结果。这个比较中的关键区别是，Incremental 的图本身可以随输入改变；依赖关系是动态的，而不是预先固定的。

我们的第一个应用场景是交易系统。市场事件输入计算，产生公允价值等量，进而为交易决策提供依据。我们也用这个库实时更新复杂的风险模型，并构建用户界面，让数据变化时只更新受影响的部分。

我们还在探索利用 js_of_ocaml 构建动态 Web 应用；它可以把 OCaml 编译成 JavaScript。根据变化的数据描述输出的同一思想，也可以应用在浏览器中。

接口中有一种类型，表示产生某种类型值的增量计算；常量构造函数则用于创建永不变化的值。变量提供变化的输入。Map 用函数转换增量值，创建一个依赖原节点的新节点。

Map2 使用函数组合两个增量输入。这一点很重要，因为单靠 map 可以从节点向外展开，却不能把两个依赖合并到一次计算中。稍后介绍的 bind 则提供接口中更强大的动态部分。

Stabilize 的类型是 unit 到 unit，但它执行重要工作。输入变化时，图不会立即重新计算；用户需要显式调用 stabilize 才会进行必要的更新。这是一个刻意作出的设计选择。

显式稳定化让我们能批量处理更新，避免暴露不一致的中间状态。在交易系统中，展示指标之前可能需要综合考虑一个市场事件引发的多项变化；每次局部变化后都重新计算，可能导致不理想的决策。

举个简单例子：把高度和宽度定义为变量，用 map2 将它们相乘得到矩形面积。注册回调、设置输入并调用 stabilize，就会打印结果。之后再作一次修改，在下一次稳定化应用积累的变化之前不会打印任何内容。

Bind 与 map 的类型有一个细微差别：它的函数返回另一个增量计算。这使函数选择的图可以随输入变化。Map 和 map2 构建静态依赖结构；bind 则使依赖图变成动态的。

条件分支可以用 map3 表达，将条件和两个分支都作为输入，但这样两个分支都会保留为依赖。不活跃分支的变化仍可能引发工作。使用 bind 时，选中的分支才成为依赖，因此不必传播未使用分支下的工作。

截断提供了另一种避免不必要工作的方法。节点的值如果变化不够大，例如没有超过指定百分比，就可以阻止更新继续传播。当数值变化小到不值得重新计算大型统计模型时，这很有用。

实现这个库主要归结为稳定化算法。第一次尝试采用两遍处理：从变化的输入开始，将依赖节点标记为脏，并统计必须重新计算的子节点；然后从叶节点向上计算，每个节点都等待其脏子节点完成。

简单算法还必须与垃圾回收器协作。如果输入一直存活并沿图向上持有引用，即便 bind 改变了图、用户不再需要旧分支，这些分支仍可能可达。如果不加处理，未使用的节点就会积累。

一种方法使用引用计数、双向指针，以及向用户提供的哨兵，作为被观察节点的代理。当相应输出不再需要时，已回收哨兵上的终结器可以帮助清理图中的引用。

两遍算法在处理截断时还有一个独立问题。第一遍在重新计算截断节点之前就把父节点标记为脏，因此还不知道变化是否应该传播。一个乐观的变通办法是假定不会传播，如果重新计算发现并非如此，就重新开始。

这种方法在最初的工作负载下表现不错，因为截断经常阻止传播；但在其他使用模式下就变得痛苦。错误的乐观假设可能迫使工作重复执行。我们需要更好的重新计算顺序。

拓扑顺序和堆可以确保先更新子节点再更新父节点。动态 bind 让排序更复杂：图每次变化都重新计算完整拓扑排序会很昂贵。伪时间戳允许将新建节点放在现有节点之间。

标签需要为未来插入留出空间。数据结构可以用启发式方法分配标签，空间耗尽时偶尔付出一次昂贵的重新分配成本。这种方法相对容易实现，但我们的测量显示，堆让它比第一版慢约 1.5 到 4 倍。

另一个问题是垃圾在终结器运行前一直被保留。根据我们观察到的运行时行为，终结处理可能延迟很久。在回收器识别出节点已经失效之前，输入变化仍会触发对图中过时部分的计算；涉及大量 bind 时，情况尤其严重。

接口需要显式表示哪些内容正在被观察，以及何时停止观察。观察者追踪用户关心的输出，停止观察操作则表示不再需要计算某个输出。这样就无须仅仅依赖延迟的回收来停止过时工作。

堆的成本仍然太高。在第六版中，我们利用了一个事实：不需要全序。同一高度的节点不可能互相依赖，因此可以按任意顺序处理。我们的许多图有数百万节点，高度却只有大约 20 或 30。

可以用一个小型列表数组按高度分组节点，取代堆。动态图仍然带来问题：每次 bind 都重新计算所有高度会浪费工作。我们使用伪高度：必要时提高高度，但不会仅因依赖移动就降低高度。

一种反复交替的病态图可能让伪高度无限增长。实际的保护措施是超过可配置高度上限时直接报错——例子中为 128。在我们的工作负载中，这并不是实际问题。

经过六个版本，我们恢复了与最初基准相当的性能，同时让截断正常工作、bind 保持高效。花了这么多精力让初始实现先变慢，最终才在行为正确的情况下回到原来的速度，这令人沮丧。

进一步的工作又带来了 2 到 3 倍的性能提升。图中包含不同类型的增量节点：整数、浮点数、字符串等。隐藏这些差异的一种常见方式是存储操作节点的闭包，但闭包会分配内存，成本可能很高。

广义代数数据类型，即 GADT，让实现能够表示不同类型的节点并对其进行模式匹配，无须同样依赖大量闭包。结果大幅减少了内存分配，加快了实际应用的运行。这是类型系统特性有助于实际性能的一个例子。

使用 Incremental 的应用，性能往往受到库本身耗时的限制。这也是值得承担构建可复用抽象时那些有时令人痛苦的工作的原因：通用库可以跨多种用途进行性能分析，让一次性应用可能永远不会获得的优化变得值得。

例如，节点记录包含多种用途所需的信息。我们尝试重新排列其字段，寻找更适合缓存的顺序，并获得了性能提升。这是一个简单优化，但只编写单个应用的开发者可能不会考虑。

仍有进一步改进的空间，例如显式内存管理或合并节点，虽然两者都不像听起来那么简单。Incremental 已在 GitHub 开源，接口也有文档，欢迎有兴趣的人探索。