Yaron Minsky：Incremental 如何从研究概念走向生产库

我想介绍 Jane Street 使用的 Incremental 库，再回顾我们从第一版实现走到最终使用版本的漫长历程。它的思想来自函数式编程和自调整计算研究。我们的经历中既有学术研究已经避免的错误，也有研究没有重点强调的实际问题。

目标是在大量数据上构建大型计算，并在只有少部分输入改变时高效刷新。我们希望得到更新后的干净结果，而不必重复全部工作。电子表格是理解这种计算模型的一个好比喻。

电子表格可以看作一种函数式语言：单元格包含根据其他输入计算的表达式。它颠倒了通常编程的侧重点，让数据突出，而把许多逻辑藏在单元格中。每个公式还会对其他单元格形成依赖。

Excel 利用这种依赖结构，避免少量单元格变化后重新计算整个大表。它也让中间结果容易展示：监控表可以引用计算过程中的各个位置。Incremental 把这种模型的一种形式带进了 OCaml。

早期接口定义了带参数的增量值，可以包含整数、字符串或其他类型。return 把普通值变成常量增量计算。map 接收一个增量值和一个函数，产生一个新增量值；输入变化时，新值也会变化。

map 能让图向外生长，但只有分支还无法把结果重新汇合。map2 接收两个增量输入和一个合并其值的函数。继续组合就有 map3 和更高元数的版本，让许多分支汇合。

用 return、map 和 map2，我们基本可以构造任意静态有向无环依赖图。我们能增加节点，也能使用多个输入，但输入变化本身不会改变图的结构。对于依赖会随数据变化的计算，这就是一个限制。

bind 带来了动态性。它接收一个增量输入和一个返回另一个增量值的函数。当左侧输入变化时，bind 节点可以选择不同的右侧依赖。与 map 相比，类型上小小的差别赋予了系统强得多的表达能力。

考虑用 map3 实现条件表达式：它把条件、then 分支和 else 分支作为输入，返回相应的值。它的图始终连接着三者，因此即使当前无关的分支发生变化，条件节点也会重新计算。

基于 bind 的条件表达式则根据条件选择 then 或 else 增量值，一次只连接所选分支。两种实现产生相同的值，但依赖图不同，因此性能表现也不同。

这个条件例子还低估了 bind 的能力：它的函数不只是从两个已有增量值中选一个，还可以构造新的增量节点。例如，给定一份配置描述，它可以为当前所需的特定计算构建整个子图。

map 通常更容易使用、理解和实现；bind 更强大，但会增加复杂度，而且常常要分配节点。对于很小的 if 表达式，或许根本没必要做增量化。这些选择在大型计算中更重要，需要按实际规模评估。

要理解增量程序的含义，可以在脑中去掉 map 和 bind，看看一次性计算会做什么。要理解性能，则必须仔细观察增量边界在哪里，以及 map 和 bind 如何塑造依赖图。

这里讨论的主要是没有副作用的函数式计算。另一个关键功能是截断：变化可能传到某个节点，但其结果并未改变，这时就没有必要继续传播。对于浮点结果，应用甚至可以为微不足道的变化设定容差。

接口还需要运行图的方法：构建计算、修改输入，然后调用 stabilize 传播变化。早期接口提供 value 操作来读取增量值，以及 on-update 回调，在被关注的值变化时作出反应。

输入来自变量：先用初始值创建变量，新数据到来时设置它，再读取其对应的增量值。变量和组合器一起构建图，稳定化与回调则提供更新后的结果。

一位听众问到了环。纯函数式构造在很大程度上能防止环，但缓存和复用子计算等实际优化可能引入环或回边。如何处理这些情况，成为各版实现之间的一个重要区别。

第一版由 Stephen Weeks 和 Milan Stanojevic 编写。它用分配出的 OCaml 对象和指针表示依赖图。指针方向很重要：变化从输入叶节点进入，因此实现需要向上的链接，才能找到受影响的计算。

朴素的深度优先传播在分支展开后又汇合时，可能多次重算同一个节点。把这样的菱形图层层叠加，一次更新就可能变成两次、四次、八次，依此增长。分支长度不同时，简单改成广度优先搜索也无法解决。

第一个算法采用两遍处理：先把可达的受影响节点标记为脏，并统计每个节点有多少脏输入。第二遍中，节点要等所有脏输入清理完毕才重新计算，从而避免汇合分支反复触发它。

算法简单而快速，但图与垃圾回收的交互很困难。从仍存活的输入变量出发，向上的指针会让上方所有可达节点一直存活。我们真正想保留的内容，应该由输出端是否有人观察决定，而不只是看它是否连接到输入。

bind 可能创建新分支，并停止引用旧分支，但旧节点仍与存活的输入相连。没有额外机制时，即使没人需要结果，这些节点也无法回收。

最初的方案为外部引用维护引用计数，计数归零时断开节点。它不给调用者内部节点本身，而是返回单独的哨兵对象。哨兵上的垃圾回收终结器会在外部引用消失时发出信号并更新计数。

截断暴露出另一个缺陷。第一遍会在重新计算值之前，标记全部可达节点，因此无法知道某个中间输出会保持不变。系统此时已经决定重算该点之后的所有内容。

临时方案是假定指定截断通常会阻止传播：算法先按这个假设运行并记录截断节点，再从变化超过阈值的节点重新启动传播。它能工作，但嵌套截断仍可能造成反复甚至指数级的工作，因此我们把它限制在相对简单的计算边缘。

被弃用的 bind 分支延迟回收，比内存泄漏更糟。在哨兵被回收之前，这些节点仍连接输入并持续计算。嵌套 bind 可能反复产生更多旧分支，在垃圾回收赶上之前带来指数级的无用工作。

最早的应用没有大量嵌套 bind，所以这个问题起初并不明显。用户界面让嵌套 bind 变得有吸引力，也暴露出长时间停顿。在自身限制内，版本 1 仍然有用且快速，但其截断和回收行为需要另一种方案。

做版本 2 时，我们回到研究文献，找到一种基于图排序的方法。拓扑排序遵守依赖关系：先处理输入，再处理依赖它的节点。装有脏节点的堆于是可以按顺序取出下一个符合条件的节点。

按拓扑顺序重算节点时，它的依赖已经是最新的，同一次稳定化中不必重复触发。更关键的是，此时新值已经可用，所以截断可以停止传播而不破坏算法。

对于静态图，分配时间本身就提供一种顺序：每个新节点都依赖更旧的节点，因此可以用计数器标记。动态 bind 使事情复杂起来：bind 内新建的节点必须插入已有顺序的正确位置，而不能简单放在末尾。

思路是在已有标签之间分配逻辑时间戳，把 bind 内创建的节点放在该 bind 之前、适当的早期节点之后。反复插入需要一种数据结构，既能腾出空间，又不会让每次比较都很昂贵。

一种简单方法是让整数标签保持间隔，并在间隙插入。间隔用完时，通过批量操作重新分配标签。其他方案使用树；选择取决于标签分配与比较的频率。在我们的场景中，比较便宜很重要。

一位实习生据此实现了一个版本。它的语义更好，但性能比原版差约 1.5 到 4 倍，所以我们没有将它投入生产。这个结果提醒我们：算法思路更好，仍必须满足实际负载的性能要求。

版本 3 攻克了旧 bind 分支持续运行的问题：它显式跟踪图中被观察的部分。观察者由增量值创建，可以读取结果、接收更新回调，也可以显式停止。

当 bind 从一个分支切换到另一个分支时，旧分支立即变为未观察，新分支则变为被观察。只有被观察的部分允许运行。旧节点可能要等垃圾回收才从内存消失，但它们不会再持续产生工作。

从某种意义上说，观察者与输入变量相对：变量把数据引入图，观察者从中取出信息。观察者被回收后可以自动停止观察，但依赖垃圾回收及时发生会重蹈覆辙，所以调用者实际使用时应在结束后主动停止观察。

版本 3 支撑了许多内部用户界面。版本 4 更深入地阅读了 Umut Acar 的研究，结合版本 2 和 3 的思路，也让我们学到了更多依赖不变量。它更像是学习练习，而不是实用的最终实现。

一个区别涉及 map 和 bind。Acar 的原始实现可以用能力更强的 bind 表达 map，但这样会在图重建时强制产生不必要的分配。我们的实现为静态依赖专门处理 map，避免了这项实际成本。

版本 5 更实用地结合了排序和观察思路，也处理了缓存子图造成的问题：复用节点可能引入不符合原有时间戳顺序的边。真实程序中即使行为合理，也会出现很多这样的边。

早期版本处理这些边和环的方式不佳：原版可能永远循环，简单时间戳方案则可能拒绝不符合顺序的边。版本 5 遇到回边时回退到动态拓扑排序。这有些权宜之计的意味，但实际行为更好。

剩下的困难是速度。节点流经堆时，会产生不可忽视的常数开销和对数级删除成本。即使团队投入了大量工作，版本 5 的速度仍不足以让我们放心替换现有系统。

版本 6 去掉了堆。全序比我们需要的更强：只要依赖顺序正确，无关节点可以共享同一等级。高度是一种候选等级：叶节点高度为零，其他节点的高度等于其子节点最大高度加一。

一张有几十万个节点的图，可能只有几十种不同高度。系统可以用按高度索引的链表数组调度工作，而不必把所有待处理节点放进堆，大幅降低开销。尽管许多节点共享高度，依赖顺序仍然得到保证。

动态 bind 改变大小时，精确高度会有成本。如果一个小节点的高度反复升降，重新计算它上方的高度可能触及图的大部分区域。本该局部完成的变化，可能变成与整张图规模成正比的工作。

伪高度避免反复向下调整：它最初与高度相同，但永远不会降低。某些病态图的节点可能让彼此的高度无限上升，但 Minsky 说团队在真实程序中很少遇到，而且超过设定的高度限制时会得到错误。

到了版本 6，系统既有改进后的语义，性能也回到了接近版本 1 的水平。版本 7 随后降低了终结器的成本。早期版本给每个哨兵都附加终结器，以便找到并断开不再被外部引用的图节点。

新方法利用观察信息维持一个不变量：不存在从被观察部分指向未观察部分的指针。观察状态改变时，系统切断或恢复相关的向上连接。这样，只要没有其他东西保留未观察节点，它们就可以被回收。

这一变化大幅减少了终结器数量。一个有 30 万个节点、只有 10 个被观察输出的图，可能只需要约 10 个终结器，而不是 30 万个。版本 7 还发现一个与 bind 有关的语义约束：先前执行创建的旧节点可能过时，不能继续作为有效依赖。

团队以为版本 7 已经结束，但代码审查带来了版本 8。那时他们对分配成本有了更好的理解，而 OCaml 也有了广义代数数据类型，即 GADT，可以更有表达力地表示不同类型的图节点。

图中的节点产生不同类型的值，却必须共同存放在内部结构里。旧方案把每个底层对象包装在一组闭包记录之后。那些函数隐藏对象的类型，使它们可以放入共同容器，并只暴露有限操作。

需要分配大量闭包时，这种表示很昂贵，编程也不方便：每项允许的操作都需要自己的包装函数，而原本能揭示结构的普通变体和记录却隐藏起来。Minsky 把这种体验比作戴着隔热手套编程。

存在类型封装和 GADT 让实现可以描述精确类型被隐藏的值，同时直接表示不同节点情况。去掉不必要的闭包既节省内存，也让代码更易理解。能够看到图的实际结构，还暴露出进一步改写和优化的机会。

变化带来的效果非常显著。Minsky 报告，一些大型、已经调优过的终端用户应用提速三倍，而不只是库本身快了三倍。一旦增量化消除了大部分原始计算，框架自身的开销就可能主导剩余工作。

一个缓慢的交易系统前端一直停留在版本 3。团队最终将它迁到版本 8 后，用户描述了显著改善。此时 Incremental 同时支撑计算引擎和用户界面，团队也计划扩大它在界面中的应用。

在浏览器界面中，OCaml 可以编译成 JavaScript；增量计算也自然适合虚拟 DOM 风格的视图：把用户看到的内容视为数据的函数，再优化该函数的更新。演讲时团队正在探索这一用途。

一个尚存的难题是，每次都把大型函数式数据结构作为全新的整体值传入。输入已经拆成许多小增量值时，Incremental 很容易工作；但要把变化的大结构转化为高效的细粒度依赖，还需要额外原语。

提出的方案利用持久化结构之间高效的差异比较。map 的对称差操作可以找出变化，并在遇到物理上相同的共享子树时停止。这样就能暴露变化的部分，而不必遍历完整的新旧结构。

另一项可能优化来自 Scheme 和 Racket 的 Father Time 系统。如果每个小操作都变成增量节点，开销可能压过实际工作。它的 lowering 优化把节点组合成更大的单元，以较粗的增量粒度换取整体效率。

Minsky 提议一种基于追踪的方法：记录成本，再据此决定合并哪些节点。Jane Street 的程序员已经会选择在哪里引入增量节点，因此这项优化在那里没那么关键；但它可能让人们广泛编写增量代码，再自动恢复性能。

更大的启示是，一个想法从论文走到能舒适地用于生产，可能需要经历漫长过程。团队并没有只是要求库更快，而是尝试多种表示和算法，了解它们的失败模式，并通过实际使用加深了对问题的理解。