Stephen Dolan 谈内存管理、垃圾回收与 OCaml

Ron Minsky 介绍 Jane Street 工具与编译器团队的 Stephen Dolan。Dolan 创建了 jq，研究过代数子类型，并参与 OCaml 多核垃圾回收器及让程序员更好控制内存的语言特性开发。

Dolan 从基本需求讲起：数据需要存放在内存中，同时不同的值不能在同一时刻占据同一位置。固定的内存映射或许足以满足微型嵌入式程序，但更一般的程序需要随着数据变化分配和回收空间。

栈适合生命周期遵循函数调用的值。函数获得一个栈帧和局部存储；函数返回后，存储空间可以以后进先出的顺序弹出。生命周期不那么容易预测的数据则需要堆分配，以及判断空间何时可以重用的方法。

在 C 中，malloc 和 free 把责任交给程序员。重复释放内存或在释放后继续使用它都可能造成安全漏洞。安全语言则使用垃圾回收或对所有权和借用进行静态验证等机制来防止这些错误。

Dolan 说，OCaml 传统上高度依赖垃圾回收，尽管这并不总是性能上的最佳取舍。团队正在探索让程序员更好控制生命周期、同时保持安全的方法。Minsky 将回收概括为近似判断哪些内容仍然需要保留：至少保留所有可达数据，也可能多保留一些。

Dolan 指出自动回收主要有两大类。追踪式回收器从存活的局部变量和全局变量等根出发，沿引用遍历。没有在遍历中到达的对象无法通过这些根使用，其内存便可以回收。

引用计数则为每个对象维护引用数量。创建和销毁引用会调整计数，计数为零时对象就可以回收。Minsky 指出其经典弱点：循环引用即使不再被外界访问，也可能保持正的计数。

Dolan 给出一个有用的对比：追踪回收遍历对象图中存活的一侧，引用计数则沿正在失效的对象传播。为处理循环，引用计数系统可以像 Python 那样定期追踪，也可以使用不会让对象保持存活的弱引用；后者需要程序员配合。

Dolan 说，认为引用计数就是更快的常见说法具有误导性。比较很困难，而维护计数可能成本高昂，尤其是在多线程更新需要原子操作时。它的优势通常是及时重用：失效内存可能立即可用，而不用等待下一个追踪阶段。

粗略概括，引用计数可能使用更少内存，追踪回收可能运行得更快，但追踪提供的是一个连续的取舍范围。更频繁的回收可以减少内存使用，却需要更多工作；较少回收可以提高吞吐量，但会占用更多内存。Dolan 说，OCaml 回收器提供了相对简单的调节方式。

在暂停时间上，两种方法也不能简单分出胜负。释放大型树结构的最后一个引用，可能迫使引用计数系统遍历整棵树。OCaml 等追踪回收器可以将标记和清扫拆成短小的增量切片，而不是暂停程序进行完整遍历。

惰性销毁或延迟传播计数也能分散引用计数的工作，但可能牺牲及时终结，同时保留计数开销。Dolan 指出普通引用计数特别适合一个场景：没有外部引用的大缓冲区可以迅速释放和重用，无须遍历对象图。

基准测试结果高度依赖工作负载。追踪回收器可能在下一轮回收前保留许多这样的缓冲区，因此垃圾回收语言的 API 常要求调用者提供可重用缓冲区。Minsky 指出，程序会逐渐采用其现有内存管理器的高效惯用法，这使比较更加复杂。

及时终结有助于管理稀缺 GPU 内存等非内存资源，但 Dolan 提醒说，引用计数并不能证明正在丢弃的引用就是最后一个。其他组件可能保留了引用。所有权或唯一性可以让释放位置更容易在局部确定。

Dolan 区分未经检查的 C 风格手动管理和 Rust 等安全系统。静态检查可以强制执行规范的手动管理方式，防止释放后使用；但对于类型检查器中的高度互连结构，向编译器解释生命周期可能很费力。此时追踪回收器可能更省事。

精确控制的好处是性能，但所有权也有助于防止意外别名。如果一个函数拥有某个值唯一的可变引用，修改它就不会通过共享别名意外改变程序的另一部分。这使高效修改与模块化能够兼得。

Dolan 指出，程序员经常为了避免共享修改错误而防御性复制可变结构，即使后来发现复制并无必要。两种替代方案分别是 Rust 的类型级所有权和借用，以及许多 OCaml 程序中由回收器管理的不可变数据结构。他希望能在同一门语言中同时使用这两种方法。

Minsky 观察到，Rust 和 OCaml 虽然不同，但设计思路有相通之处：共享修改是核心问题，一种方法限制共享，另一种限制修改。两位讲者随后转向如何加快自动垃圾回收，包括 Dolan 对 OCaml 回收器所做的工作。

OCaml 的回收器采用分代设计。Dolan 首先介绍主回收器：它定期从根出发，沿引用标记可达对象，然后清扫未标记对象，将空间交还分配器。这是一种标记—清扫设计。

主回收器是增量式的：它将标记和清扫拆成小片工作，并在各片之间保存状态。Minsky 指出这对延迟敏感的应用很重要；Dolan 补充说，即使是交互程序，如果大型堆的完整回收让程序暂停数秒，也会影响体验。

分代假说指出，新近分配的对象尤其容易很快失效，而已经存活一段时间的对象往往会存活更久。Dolan 说，这种模式在许多语言和编程风格中都得到验证，因此单独设置年轻代很有用。

次堆在连续内存区域内使用碰撞指针分配对象，操作非常便宜。区域填满时，次回收会找出存活对象，将它们提升到主堆或以其他方式保留；其余对象可以一起丢弃。常常有 90% 甚至更多的分配在需要更昂贵的主分配器之前就消失了。

在这次讨论时，OCaml 现有回收器用一把锁保护共享堆；Dolan 也参与了正在向上游推进的多核设计。Minsky 转而介绍另一个令人惊讶的结果：Dolan 与 Will Hasenplaugh 的工作使标记阶段快了约两到三倍。

Dolan 解释了指针追踪为什么慢。处理器可以高带宽顺序读取数组，但遍历链表时，每个元素都需要一次新的、依赖前次结果的内存请求。在他的例子中，一次缓存未命中可能花费约 300 个周期，因此尽管可用带宽很高，延迟仍会占主导。

Minsky 将计算机的内存子系统比作分布式系统：带宽可能很高，但相互依赖的往返请求代价昂贵。垃圾回收标记尤其困难，因为它要沿指针访问分散的位置，可能花很多时间等待缓存未命中。

现代处理器可以同时处理多个尚未完成的缓存未命中。Dolan 的改动使用预取指令和一个小队列：回收器发现对象时提前请求其内存，随后先处理队列中的其他对象。由于标记顺序可以调整，多个请求就能重叠进行。

每次未命中仍有自身的延迟，但十个并发请求可以显著提高有效缓存行到达的速度。遍历庞大、分散的堆时，队列能更充分利用内存带宽。在一个成熟且受到认可的回收器上获得这样的提升，让两位讲者都感到惊讶。

Dolan 提出效果显著的两个可能原因：较新的处理器支持更多内存级并行，而 OCaml 的标签表示让回收器无须单独查询布局，就能低成本地区分整数和指针。他明确表示，与其他回收器的比较仍只是推测。

Minsky 问程序员是否应该更广泛地使用软件预取。Dolan 说预取可能有帮助，但时机很重要：请求太晚，使用时尚未完成；太早则可能在使用前被逐出缓存。垃圾回收特别适合这种优化，因为遍历顺序可以重新安排。

例如在 list.map 中，如果映射函数非常简单，预取下一个链表节点可能太晚；如果函数很慢，又可能太早而浪费资源。下一个元素本身还可能指向未预取的更多数据。库无法总是知道每个调用者的时序和数据布局。

Minsky 将其称为性能缺乏可组合性：优化在一个环境中有效，在另一个环境中却可能有害。Dolan 补充说缓存行为并非平滑变化。小改动可能让一次访问从缓存命中变为代价高得多的未命中，从而造成巨大的性能差异。

对话从改进回收器转向给程序员更多控制。Dolan 解释说，许多临时结构只存活很短时间，但普通 OCaml 会在次堆上分配它们。即使分配便宜，它们仍会占用空间，让下一次次回收更早发生。

类似栈的分配可以通过恢复指针回收，而不必等待垃圾回收。它还可以重用最近访问过、很可能仍在缓存中的内存。Minsky 对比了较大的次堆可以避免过早提升，而较小的次堆可以改善缓存局部性；局部分配有望同时获得两种好处。

Dolan 对比了 Go 主要采取尽力而为的逃逸分析，以及在接口中表达不逃逸的需求。安全问题在于把局部数据的引用传给另一个函数：如果被调用函数将它存入全局位置，而局部区域随后结束，保存的引用就会悬垂。

Rust 用附着在引用上的生命周期变量处理这个问题。能够接受任意生命周期引用的函数，不能把其中一个保存到要求静态生命周期的全局位置。类型系统检查生命周期之间的关系，让调用者能够安全传递栈上分配的数据。

高阶函数使问题更加复杂。传给函数的回调可能需要适用于该函数内部创建的任意生命周期，因此需要高阶类型。Rust 支持这些机制，但 Dolan 说它们需要相当多的类型系统机制，也可能限制类型推断，需要编写注解。

OCaml 用户习惯广泛的类型推断，因此提议中的局部设计直接表达函数不会捕获某个参数。常见情况下，调用者可以把局部数据传给这样的函数，无须生命周期变量或高阶多态。

这一选择不如 Rust 生命周期系统灵活，后者能够表达多个参数和结果之间复杂的关系。但 OCaml 会保留垃圾回收器来处理困难情况。两位讲者都希望默认方式易于使用，并在有价值时提供更多控制。

Minsky 问到智能构造器：辅助函数分配局部值并将其返回给调用者。传统调用栈使这很棘手，因为被调用函数返回时自己的栈帧会消失，而调用者可能无法提前知道需要多大空间。

提议中的设计将调用栈与局部分配区域分开。通常二者的生命周期一致，但构造器可以在通过调用栈返回的同时，将分配留在局部区域供调用者使用。这避免了跨返回地址边界复制对象。

默认情况下，局部分配区域遵循函数调用。若函数创建的分配预期比自身栈帧活得更久，就需要注解。Dolan 说，团队放弃了自动将所有内容放在局部栈上的做法：值可能因此停留太久，使栈过度增长。

Minsky 转向堆。OCaml 的统一表示很简单，但数据可能分散在许多通过指针连接的分配中，小值也可能占据完整的机器字。提议中的无装箱类型旨在让程序员更好地控制表示方式。

Dolan 描述了将一个记录内联到另一个记录中，让字段相邻存放，而不用单独的块和指针。他还举例说明，OCaml 的 int32 通过指针指向更大的块来表示：统一性有利于运行时，但对处理大量 32 位整数的应用来说成本很高。

无装箱表示可以减少间接访问，有时甚至完全消除一次堆分配。在当时的 OCaml 中，用一个元组名称传递两个值可能需要堆块，而作为两个参数传递则不需要。目标特性将允许一个逻辑值包含多个机器级部分。

这与多态有关。泛型 List.map 可以取得未知类型的元素并传给函数，而不用为每种类型生成独立实现，因为普通 OCaml 值共享统一的调用表示。浮点数或多机器字结构可以装箱在一个指针后面，以适应该约定。

Minsky 问全程序特化能否解决问题。Dolan 说，特化或单态化在许多设计中有效，但遇到多态记录字段和一等模块时会更困难，因为多态函数可以先被存储，之后再以不同类型调用。它也会增加代码大小和编译工作量。

独立编译和增量构建在实践中很有价值。Dolan 还介绍即时特化作为设计空间中的另一个选择：它按需生成版本，但会在运行时引入编译暂停。他认为没有一种方法在所有情况下都更好，尤其是在涉及高级模块特性时。

他们提议的设计保留泛型实现和独立编译，同时增加一种表达方式，说明多态函数适用于具有特定布局的类型。函数可以支持所有适合整数寄存器的类型，或所有符合某种浮点布局的类型，而不必支持每一种可能的表示。

Minsky 认出这是一套 kind 系统：kind 按布局等属性对类型分类。Dolan 说，现有的统一表示对应一个名为 value 的 kind，而新 kind 可以描述立即值或特定宽度的无装箱元组。多态仍可在同一种布局内保持泛型。

包含两个整数的无装箱元组可以像两个局部机器级值一样工作，而不是通过一个指针指向堆对象。传递它会使用多个参数槽，返回时也能返回多个部分而不需要中间分配。Kind 有助于确定调用约定和寄存器需求。

Dolan 将这一想法与关于 kind 和调用约定的研究联系起来。兼容 kind 的函数可以使用统一约定，不同布局则可能需要不同寄存器。目标不仅是更紧凑地打包堆对象，还包括在不需要时避免堆表示。

需要堆对象时，无装箱数据可以装箱，但回收器会施加限制。在所讨论的设计中，回收器期望一个块要么包含它知道如何扫描的字段，要么完全不包含指针。混合指针和浮点数的元组可以无装箱传递，却不一定能一起存入堆块。

Minsky 指出，无装箱值没有一个稳定位置供修改。Dolan 解释说，可变的外层结构仍可支持看起来像修改内部字段的操作。当时某些组合会产生编译错误；放宽回收器限制则需要另行开发。

变体带来了更多问题。Dolan 认为，将一个变体内联到另一个相对直接；返回无装箱变体则更难，因为不同分支可能有不同大小，需要不同类型的寄存器。所讨论的编译器后端当时尚不支持随分支变化的结果布局。

这些困难促使团队考虑将局部分配作为某些情况的更简单替代方案。局部分配的变体保留普通表示，但回收成本低。Minsky 指出，局部分配可以重用现有类型和代码，而无装箱布局可能需要单独类型并限制多态。

对 option 而言，高效的可空表示很有吸引力：否则 Some 值需要额外的块。但嵌套 option 必须区分 None 和 Some None。Minsky 指出，这种嵌套可能自然地出现在抽象类型背后，所以合并这些情况会破坏有意义的区别。

Dolan 勾勒了一种提议中的可空类型：只有已知底层类型不可空时才能使用。非可空 kind 可以强制执行这一约束，拒绝专门可空表示的嵌套，避免歧义，同时让常见情况使用特殊值。

Minsky 说，如何高效表示 option 已经讨论了几十年。Dolan 描述了两种思路的取舍：为每种情况寻找紧凑表示，或调整类型系统让有问题的情况无法发生。对话最后回到一个主题：在同一门语言中安全结合自动化的便利与显式控制很困难。