理解垃圾回收器

这是书籍Real World OCaml中章节理解垃圾回收器的改编版本，经许可在此转载。

本章包含 Stephen Weeks 和 Sadiq Jaffer 的贡献。

我们之前在值的内存表示中描述了单个 OCaml 变量的运行时格式。当您执行程序时，OCaml 通过定期扫描已分配的值并在不再需要时释放它们来管理这些变量的生命周期。这反过来意味着您的应用程序不需要手动实现内存管理，并且大大降低了内存泄漏潜入您代码的可能性。

OCaml 运行时是一个 C 库，它提供可以在运行的 OCaml 程序中调用的例程。运行时管理一个堆，它是一组从操作系统获取的内存区域。运行时使用此内存来保存堆块，它根据 OCaml 程序的分配请求用 OCaml 值填充这些堆块。

标记-清除垃圾回收

当没有足够的内存来满足来自已分配堆块池的分配请求时，运行时系统会调用垃圾回收器 (GC)。OCaml 程序在完成使用某个值时不能显式释放它。相反，GC 定期确定哪些值是存活的，哪些值是死亡的，即不再使用。收集死亡的值，并将其内存提供给应用程序重复使用。

GC 不会持续跟踪值的分配和使用情况。相反，它通过从应用程序始终可以访问的一组根值（例如堆栈）开始，定期扫描它们。GC维护一个有向图，其中堆块是节点，如果b1的某个字段是指向b2的指针，则从堆块b1到堆块b2有一条边。

通过沿着图中的边从根开始可以到达的所有块都必须保留，而无法到达的块可以由应用程序重复使用。OCaml 用于执行此堆遍历的算法通常称为标记-清除垃圾回收，我们现在将进一步解释它。

分代垃圾回收

通常的 OCaml 编程风格涉及分配许多短期使用然后不再访问的小值。OCaml 利用这一事实，通过使用分代 GC 来提高性能。

分代 GC 会根据块存活的时间长短，维护不同的内存区域来保存块。OCaml 的堆被分成两个这样的区域

• 一个小的、固定大小的次要堆，大多数块最初都在这里分配

• 一个更大的、可变大小的主要堆，用于存活时间更长的块

典型的函数式编程风格意味着年轻的块往往很快死亡，而旧的块往往比年轻的块存活更长时间。这通常被称为分代假设。

OCaml 使用不同的内存布局和垃圾回收算法来处理主要堆和次要堆之间的这种分代差异。接下来我们将更详细地解释它们的不同之处。

快速次要堆

次要堆是大多数短生命周期值存储的地方。它由一个连续的虚拟内存块组成，其中包含一系列 OCaml 块。如果有空间，分配一个新的块是一个快速、恒定时间的操作，只需要几个 CPU 指令。

为了垃圾回收次要堆，OCaml 使用复制收集将次要堆中所有存活的块移动到主要堆。这需要的工作量与次要堆中存活块的数量成正比，根据分代假设，这个数量通常很小。一般来说，垃圾收集器在运行时会停止世界（即暂停应用程序），因此快速完成它非常重要，以便应用程序能够在最小的中断下恢复运行。

在次要堆上分配

次要堆是一个连续的虚拟内存块，通常大小为几兆字节，以便可以快速扫描。

运行时将次要堆的边界存储在两个指针中，这两个指针限定了堆区域的起始和结束（caml_young_start 和 caml_young_end，但为了简洁起见，我们将省略 caml_young 前缀）。base 是系统 malloc 返回的内存地址，start 与从 base 开始的下一个最近的字边界对齐，以便更容易存储 OCaml 值。

在一个新的次要堆中，limit 等于 start，当前的 ptr 将等于 end。当分配块时，ptr 会减小，直到它到达 limit，此时会触发一次次要垃圾回收。

在次要堆中分配一个块只需要将 ptr 减去块的大小（包括头部）并检查它是否小于 limit。如果没有足够的空间容纳块而无需将 ptr 减小到超过 limit，则会触发一次次要垃圾回收。在大多数 CPU 架构上，这是一个非常快速的检查（没有分支）。

理解分配

您可能想知道为什么 limit 完全必要，因为它似乎总是等于 start。这是因为运行时安排次要堆收集的最简单方法是将 limit 设置为等于 end。完成此操作后，下一次分配将永远没有足够的空间，并且始终会触发垃圾回收。这样提前进行收集有各种内部原因，例如处理挂起的 UNIX 信号，但它们通常与应用程序代码无关。

可以编写循环或递归，使其分配（如果有的话）花费很长时间。为了确保需要中断正在运行的 OCaml 程序的 UNIX 信号和其他内部簿记仍然发生，编译器会在生成的原生代码中引入轮询点。

这些轮询点会检查 ptr 与 limit 的关系，开发人员应该预计它们会被放置在每个函数的开头和循环的后边沿。编译器包含一个数据流传递，它会移除除确保这些检查在有界时间内发生的最小点集之外的所有点。

# open Core;;
# let c = Gc.get ();;
val c : Gc.Control.t =
  {Core.Gc.Control.minor_heap_size = 262144; major_heap_increment = 15;
   space_overhead = 120; verbose = 0; max_overhead = 500;
   stack_limit = 1048576; allocation_policy = 2; window_size = 1;
   custom_major_ratio = 44; custom_minor_ratio = 100;
   custom_minor_max_size = 8192}
# Gc.tune ~minor_heap_size:(262144 * 2) ();;
- : unit = ()

长生命周期主要堆

主要堆是程序中大部分长生命周期和较大值存储的地方。它由任意数量的非连续虚拟内存块组成，每个块包含交错的存活块和空闲内存区域。运行时系统维护一个自由列表数据结构，该结构索引它已分配的所有空闲内存，并使用它来满足 OCaml 块的分配请求。

主要堆通常比次要堆大得多，并且可以扩展到千兆字节的大小。它通过一个分多个阶段运行的标记-清除垃圾回收算法进行清理。

• 标记阶段扫描块图并通过设置块头标签中的一个位（称为颜色标签）来标记所有存活块。

• 清除阶段依次扫描堆块并识别之前未标记的死块。

• 压缩阶段将存活块重新定位到新分配的堆中，以消除自由列表中的间隙。这可以防止长时间运行的程序中堆块碎片化，并且通常比标记和清除阶段发生得少得多。

主要垃圾回收也必须停止世界，以确保可以移动块而不会被活动应用程序观察到。标记和清除阶段会增量地跨堆的切片运行，以避免长时间暂停应用程序，并且还会在每个切片之前进行快速次要收集。只有压缩阶段会一次性处理所有内存，并且是一个相对较少的操作。

在主要堆上分配

主要堆由一个单链表组成，该链表包含按虚拟地址递增顺序排序的连续内存块。每个块都是通过malloc(3)分配的单个内存区域，并且包含一个头部和数据区域，其中包含 OCaml 堆块。堆块头部包含

• 包含该块的内存区域的malloced 虚拟地址

• 数据区域的大小（以字节为单位）

• 在堆压缩期间使用的分配大小（以字节为单位），用于合并小块以碎片化堆

• 指向列表中下一个堆块的链接

• 指向可能包含未检查字段并需要稍后扫描的块范围的开始和结束的指针。仅在标记堆栈溢出后使用。

每个块的数据区域从页面边界开始，其大小是页面大小（4 KB）的倍数。它包含一个连续的堆块序列，这些堆块可以小到一个或两个 4 KB 页面，但通常以 1 MB 块（或 32 位架构上的 512 KB）分配。

控制主要堆增量

Gc 模块使用 major_heap_increment 值来控制主要堆的增长。这定义了每次扩展时添加到主要堆的字数，并且是初始启动后操作系统从 OCaml 运行时观察到的唯一内存分配操作（因为次要堆的大小是固定的）。

在主要堆上分配 OCaml 值首先会检查块的自由列表以查找合适的区域来放置它。如果自由列表上没有足够的空间，运行时会通过分配一个足够大的新堆块来扩展主要堆。然后将该块添加到自由列表中，并再次检查自由列表（这次肯定成功）。

旧版本的 OCaml 需要为主要堆增量设置固定数量的字节。这是一个难以正确设置的值：太小的值会导致大量较小的堆块散布在虚拟内存的不同区域，需要 OCaml 运行时进行更多维护来跟踪它们；太大的值会浪费具有小堆的程序的内存。

您可以使用 Gc.tune 设置该值，但出于向后兼容性的原因，这些值有点违反直觉。小于 1000 的值被解释为百分比，默认值为 15%。1000 及以上的值被视为原始字节数。但是大多数时候，您根本不会设置该值。

内存分配策略

主要堆尽最大努力尽可能高效地管理内存分配，并依赖于堆压缩来确保内存保持连续且未碎片化。默认的分配策略通常适用于大多数应用程序，但值得记住的是，还有其他选项。

在主要堆中分配新块时，始终首先检查块的自由列表。默认的自由列表搜索称为最佳拟合分配，还提供下一个拟合和首次拟合算法作为替代。

最佳拟合分配

最佳拟合分配器是两种策略的组合。第一个，大小分隔的自由列表，基于这样的观察：OCaml 中几乎所有主要堆分配都很小（考虑列表元素和元组，它们只有几个机器字）。最佳拟合为最多 16 个字的大小保留单独的自由列表，这为大多数分配提供了快速路径。这些大小的分配可以从其分隔的自由列表中服务，或者如果它们为空，则从具有空间的下一个大小中服务。

第二种策略，用于较大分配，是使用一种称为伸展树的专门数据结构作为自由列表。这是一种自适应于最近访问模式的搜索树。对于我们的用途，这意味着最常请求的分配大小是最快访问的。

当分隔的自由列表中没有更大的大小可用时，小分配和大分配（大于 16 个字）将从主自由列表中服务。查询自由列表以获取最小块，该块至少与请求的分配一样大。

最佳拟合分配是默认的分配机制。它代表了分配成本（在 CPU 工作方面）和堆碎片化之间的良好权衡。

下一个拟合分配

下一个拟合分配会保留一个指向自由列表中最近用于满足请求的块的指针。当新的请求到来时，分配器从下一个块搜索到自由列表的末尾，然后从自由列表的开头搜索到该块。

下一个拟合分配是一种相当便宜的分配机制，因为相同的堆块可以在分配请求之间重复使用，直到它用完。这反过来意味着存在良好的内存局部性以更好地使用 CPU 缓存。下一个拟合的最大缺点是，由于大多数分配都很小，因此自由列表开头的较大部分会严重碎片化。

首次拟合分配

如果您的程序分配了各种大小的值，您有时可能会发现您的自由列表变得碎片化。在这种情况下，GC 被迫执行昂贵的压缩，尽管存在空闲块，因为没有一个块本身足够大以满足请求。

首次拟合分配侧重于减少内存碎片（从而减少压缩次数），但以牺牲更慢的内存分配为代价。每次分配都会从开头扫描自由列表以查找合适的空闲块，而不是像下一个拟合分配器那样重复使用最近的堆块。

对于某些需要在负载下具有更多实时行为的工作负载，堆压缩频率的减少将超过额外的分配成本。

控制堆分配策略

您可以通过调用 Gc.tune 设置堆分配策略。

# Gc.tune ~allocation_policy:First_fit ();;
- : unit = ()

可以通过环境变量控制相同行为，将 OCAMLRUNPARAM 设置为 a=0 表示下一个拟合，a=1 表示首次拟合，或 a=2 表示最佳拟合。

标记和扫描堆

标记过程可能需要很长时间才能遍历整个主堆，并且在运行时必须暂停主应用程序。因此，它通过分段标记堆来增量运行。堆中的每个值在其头中都有一个 2 位的颜色字段，用于存储有关该值是否已被标记的信息，以便 GC 可以轻松地在片段之间恢复。

• 蓝色：在空闲列表中，并且当前未使用
• 白色（标记期间）：尚未到达，但可能可达
• 白色（扫描期间）：不可达，可以释放
• 黑色：可达，并且其字段已被扫描

值头中的颜色标记存储了标记过程的大部分状态，允许它稍后暂停和恢复。在分配时，所有堆值最初都设置为白色，表示它们可能可达但尚未扫描。GC 和应用程序在标记主堆的一个片段以及实际执行程序逻辑之间交替进行。OCaml 运行时根据分配率和可用内存计算出每个主堆片段大小的合理值。

标记过程从一组始终处于活动状态的根值开始（例如应用程序栈和全局变量）。这些根值将其颜色设置为黑色，并被推入一个称为标记栈的专用数据结构中。标记通过从栈中弹出值并检查其字段来进行。任何包含白色块的字段都会更改为黑色并推入标记栈。

此过程重复进行，直到标记栈为空并且没有其他值需要标记。但是，在此过程中有一个重要的边缘情况。标记栈只能增长到一定大小，之后 GC 无法再递归进入中间值，因为它在跟随其字段时无处存储它们。这被称为标记栈溢出，并开始一个称为修剪的过程。修剪完全清空标记栈，将每个块的地址总结为每个堆块头中的起始和结束范围。

在标记过程的后期，当标记栈为空时，它会通过重新标记堆来补充。这从第一个（按地址）具有需要重新标记的块的堆块开始（即在修剪期间从标记栈中删除的块），并将重新标记范围中的条目添加到标记栈，直到它达到四分之一满。清空和补充循环持续进行，直到没有堆块剩下需要重新标记的范围。

控制主堆收集

您可以通过 major_slice 调用触发主 GC 的单个片段。这首先执行一次次要收集，然后执行一个片段。片段的大小通常由 GC 自动计算到一个适当的值，并返回此值，以便您在以后的调用中根据需要修改它。

# Gc.major_slice 0;;
- : int = 0
# Gc.full_major ();;
- : unit = ()

space_overhead 设置控制 GC 设置片段大小为大尺寸的积极程度。这表示用于活动数据的内存比例将被“浪费”，因为 GC 不会立即收集不可达的块。Core 将其默认为 100 以反映一个通常不受内存限制的典型系统。如果您有大量内存，请将此值设置得更高，或者将其设置得更低以使 GC 更努力地工作并更快地收集块，但代价是使用更多的 CPU 时间。

堆压缩

在完成一定数量的主 GC 周期后，由于值以与分配顺序不同的顺序被释放，堆可能会开始碎片化。这使得 GC 更难为新分配找到连续的内存块，这反过来又需要不必要地扩展堆。

堆压缩周期通过将主堆中的所有值重新定位到一个新的堆中来避免这种情况，该新堆将它们全部连续地放置在内存中。该算法的简单实现需要额外的内存来存储新堆，但 OCaml 在现有堆中就地执行压缩。

# Gc.tune ~max_overhead:0 ();;
- : unit = ()

代间指针

分代收集的一个复杂之处在于，次要堆扫描比主要堆收集频繁得多。为了知道次要堆中的哪些块是活动的，收集器必须跟踪哪些次要堆块被主要堆块直接指向。如果没有此信息，每次次要收集还需要扫描更大的主要堆。

OCaml 保持着一组这样的代间指针以避免主要和次要堆收集之间的这种依赖关系。编译器引入了一个写屏障，以便在修改主要堆块以指向次要堆块时更新这个所谓的记住集合。

可变写屏障

写屏障可能对代码的结构产生深远的影响。这是使用不可变数据结构并通过更改分配新副本有时比就地修改记录更快的原因之一。

OCaml 编译器跟踪任何可变类型，并在进行更改之前添加对运行时 caml_modify 函数的调用。这会检查目标写入的位置及其正在更改的值，并确保记住集合保持一致。虽然写屏障效率相当高，但它有时可能比在快速的次要堆上简单地分配一个新值并进行一些额外的次要收集要慢。

让我们用一个简单的测试程序自己看看。在编译此代码之前，您需要通过 opam install core_bench 安装 Core 基准测试套件。

open Core
open Core_bench

module Mutable = struct
  type t =
    { mutable iters : int
    ; mutable count : float
    }

  let rec test t =
    if t.iters = 0
    then ()
    else (
      t.iters <- t.iters - 1;
      t.count <- t.count +. 1.0;
      test t)
end

module Immutable = struct
  type t =
    { iters : int
    ; count : float
    }

  let rec test t =
    if t.iters = 0
    then ()
    else test { iters = t.iters - 1; count = t.count +. 1.0 }
end

let () =
  let iters = 1_000_000 in
  let count = 0.0 in
  let tests =
    [ Bench.Test.create ~name:"mutable" (fun () ->
          Mutable.test { iters; count })
    ; Bench.Test.create ~name:"immutable" (fun () ->
          Immutable.test { iters; count })
    ]
  in
  Bench.make_command tests |> Command_unix.run

此程序定义了一个类型 t1，它是可变的，t2 是不可变的。基准测试循环遍历这两个字段并递增一个计数器。使用一些额外的选项编译并执行此操作以显示发生的垃圾收集量。

$ opam exec -- dune exec -- ./barrier_bench.exe -ascii alloc -quota 1
Estimated testing time 2s (2 benchmarks x 1s). Change using '-quota'.

  Name        Time/Run   mWd/Run   mjWd/Run   Prom/Run   Percentage
 ----------- ---------- --------- ---------- ---------- ------------
  mutable       5.06ms    2.00Mw     20.61w     20.61w      100.00%
  immutable     3.95ms    5.00Mw     95.64w     95.64w       77.98%

这里存在一个空间/时间权衡。可变版本完成所需的时间比不可变版本长，但分配的次要堆字比不可变版本少得多。OCaml 中的次要分配非常快，因此通常最好使用不可变数据结构而不是更传统的可变版本。另一方面，如果您很少修改某个值，那么接受写屏障的命中而不进行分配可能会更快。

唯一确定方法是在真实场景下使用 Core_bench 对程序进行基准测试，并尝试权衡利弊。命令行基准测试二进制文件有一些有用的选项，这些选项会影响垃圾收集行为和输出格式。

$ opam exec -- dune exec -- ./barrier_bench.exe -help
Benchmark for mutable, immutable

  barrier_bench.exe [COLUMN ...]

Columns that can be specified are:
	time       - Number of nano secs taken.
	cycles     - Number of CPU cycles (RDTSC) taken.
	alloc      - Allocation of major, minor and promoted words.
	gc         - Show major and minor collections per 1000 runs.
	percentage - Relative execution time as a percentage.
	speedup    - Relative execution cost as a speedup.
	samples    - Number of samples collected for profiling.
...

将终结器函数附加到值

OCaml 的自动内存管理保证值最终会在不再使用时被释放，无论是通过 GC 扫描它还是程序终止。有时在 GC 释放值之前运行额外代码很有用，例如，检查文件描述符是否已关闭，或者记录日志消息。

Core 提供了一个 Heap_block 模块，该模块动态检查给定值是否适合终结。Core 将注册终结器的函数保存在 Core.Gc.Expert 模块中。终结器可以在任何线程中的任何时间运行，因此在多线程上下文中可能很难推断。我们在 使用 Async 进行并发编程 中讨论过的 Async 使用它自己的模块（其中包含一个函数 Gc.add_finalizer）来隐藏 Gc 模块，该模块是并发安全的。特别是，终结器在其自己的 Async 作业中调度，并且 Async 会小心地捕获异常并将它们引发到相应的监视器以进行错误处理。

让我们通过一个小型示例来探讨这一点，该示例终结不同类型的值，所有这些值都是堆分配的。

open Core
open Async

let attach_finalizer n v =
  match Heap_block.create v with
  | None -> printf "%20s: FAIL\n%!" n
  | Some hb ->
    let final _ = printf "%20s: OK\n%!" n in
    Gc.add_finalizer hb final

type t = { foo : bool }

let main () =
  attach_finalizer "allocated variant" (`Foo (Random.bool ()));
  attach_finalizer "allocated string" (Bytes.create 4);
  attach_finalizer "allocated record" { foo = Random.bool () };
  Gc.compact ();
  return ()

let () =
  Command.async
    ~summary:"Testing finalizers"
    (Command.Param.return main)
  |> Command_unix.run

构建和运行此操作应该显示以下输出

$ opam exec -- dune exec -- ./finalizer.exe
    allocated record: OK
    allocated string: OK
   allocated variant: OK

GC 按释放顺序调用终结函数。如果多个值在同一 GC 周期内变得不可达，则终结函数将按对应 add_finalizer 调用的反向顺序调用。每次 add_finalizer 调用都会添加到函数集中，这些函数在值变得不可达时运行。如果您愿意，可以有多个终结器都指向同一个堆块。

在垃圾收集确定堆块 b 不可达后，它会从终结器集中删除与 b 关联的所有函数，并依次将每个函数应用于 b。因此，附加到 b 的每个终结器函数最多运行一次。但是，程序终止不会在运行时退出之前导致所有终结器都运行。

终结器可以使用 OCaml 的所有功能，包括使值再次可达的赋值，从而防止它被垃圾收集。它也可以无限循环，这会导致其他终结器与它交织在一起。