介绍 Riptide
WebKit 的退回波前并发垃圾回收器

2017 年 1 月 20 日

作者：Filip Pizlo

截至 r209827，64 位 ARM 和 x86 WebKit 移植版使用了一种名为 Riptide 的新垃圾回收器。Riptide 通过允许应用程序与回收器并发运行来减少最坏情况下的暂停时间。这对响应速度有很大影响，因为垃圾回收即使在快速硬件上也很容易花费 10 毫秒或更长时间。Riptide 将 WebKit 在 JetStream/splay-latency 测试上的性能提高了 5 倍，从而使 JetStream 的性能提升了 5%。Riptide 还改善了我们的 Octane 性能。我们希望 Riptide 将有助于减少各种应用程序中 GC 暂停的严重性。

本文首先简要介绍了并发 GC（垃圾回收）的背景。然后详细描述了 Riptide 算法，包括其所基于的成熟 WebKit GC 基础。增量和并发 GC 领域由来已久，WebKit 并非第一个使用它的系统，因此本文有一个部分介绍了 Riptide 如何融入相关工作。本文最后提供了性能数据。

引言

垃圾回收开销很大。在最坏的情况下，为了回收单个对象，回收器需要扫描整个堆，以确保没有其他对象引用它想要释放的对象。传统的回收器会定期扫描整个堆，这大致是 WebKit 的回收器自最初以来的工作方式。

这种方法的问题在于 GC 暂停时间可能长到导致渲染循环丢失帧，或者在某些情况下甚至长到表现为卡顿。这是一个计算机科学中已为人熟知的问题。Guy Steele 在 1975 年最初提出的解决 GC 卡顿暂停的方案是让一个 CPU 运行应用程序，另一个 CPU 运行回收器。这涉及到复杂的竞态条件，Steele 用一堆锁解决了这些问题。后来像 Baker 的算法是增量式的：它们假设只有一个 CPU，有时应用程序会调用回收器，但只进行有限的增量工作。从那时起，人们探索了各种各样的增量和并发技术。增量回收器避免了一些同步开销，但并发回收器具有更好的可扩展性。现代并发回收器如 DLG（Doligez、Leroy、Gonthier 的缩写，发表于 POPL ’93 和 ’94）具有非常低的同步开销，并且几乎完全避免暂停应用程序。将垃圾回收从主核心剥离，而不仅仅是缩短暂停时间，这是我们希望在 WebKit 中采取的方向，因为 WebKit 运行的几乎所有设备都有多个核心。

WebKit 新的 Riptide 并发 GC 的目标是通过将大部分回收器工作移出主线程来大幅减少 GC 暂停。由于 Riptide 将成为我们始终开启的默认 GC，我们还希望它在速度和内存方面与我们之前的回收器一样高效。

Riptide 算法

Riptide 回收器结合了

标记 (Marking)： 回收器在找到对象的引用时对其进行标记。未标记的对象将被删除。回收器的大部分时间都用于访问对象以查找对其他对象的引用。
约束 (Constraints)： 回收器允许运行时提供关于何时标记对象的额外约束，以支持自定义对象生命周期规则。
并行性 (Parallelism)： 标记在最多八个逻辑 CPU 上并行进行。（我们限制为八个是因为我们尚未针对更多 CPU 进行优化。）
分代 (Generations)： 如果内存充足，回收器会让对象的标记状态保持不变，从而允许下一次回收跳过访问这些对象。粘性标记位 (Sticky mark bits) 是一种无需复制即可实现分代回收的常见方法。在 WebKit 中，允许标记位保持不变的回收周期被称为伊甸园 (eden) 回收。
并发性 (Concurrency)： 回收器的大部分标记阶段与程序并发运行。由于这是回收过程中迄今为止最长的部分，因此剩余的暂停时间通常为 1 毫秒或更短。Riptide 的并发功能对伊甸园回收和完全回收都有效。
保守性 (Conservatism)： 回收器保守地扫描栈和寄存器，即检查每个字以查看它是否在某个对象的边界内，如果是则对其进行标记。这意味着我们系统中所有的 C++、汇编和即时 (JIT) 编译器生成的代码都可以将堆指针存储在局部变量中，而无需任何麻烦。
效率 (Efficiency)： 这是我们始终开启的垃圾回收器。它必须快速。

本节描述了回收器的工作原理。算法描述的第一部分着重于 Riptide 所基于的 WebKit 标记-清除算法。然后我们将深入探讨并发性以及 Riptide 如何在堆处于变化状态时遍历堆。

高效标记-清除

Riptide 保留了 WebKit 成熟的垃圾回收代码的大部分基本架构。本节概述了我们的标记-清除回收器的工作原理：WebKit 使用一种简单分离存储 (simple segregated storage) 堆结构。DOM、Objective-C API、类型推断运行时和编译器都引入了自定义标记约束 (custom marking constraints)，GC 会执行这些约束直到达到不动点。标记以并行方式完成，以最大化吞吐量。分代回收很重要，因此 WebKit 使用粘性标记位 (sticky mark bits) 来实现它。回收器使用保守栈扫描 (conservative stack scanning) 以便于与 WebKit 的其余部分集成。

简单分离存储

WebKit 长期以来一直使用简单分离存储 (simple segregated storage) 堆结构来管理小型和中型对象（最大约 8KB）。

小型和中型对象从分离的空闲列表中分配。给定所需的对象大小，我们执行表查找以找到合适的空闲列表，然后从该列表中弹出第一个对象。查找表通常由编译器进行常量折叠。
内存被划分为 16KB 的块 (blocks)。每个块都包含单元 (cells)。块中的所有单元都具有相同的单元大小，称为该块的大小类 (size class)。在 WebKit 行话中，对象 (object) 是其 JavaScript 类型为“object”的单元 (cell)。例如，字符串是一个单元但不是一个对象。GC 文献通常会使用对象 (object) 来指代我们的代码称之为单元 (cell) 的内容。由于本文不关心 JavaScript 类型，我们将使用术语对象 (object) 来表示我们堆中的任何单元。
在任何时候，某个大小类的活动空闲列表只包含来自单个块的对象。当一个空闲列表中的对象用完时，我们会找到该大小类中的下一个块并对其进行扫描 (sweep) 以为其生成一个空闲列表。

扫描是增量的，因为我们只在分配之前才扫描一个块。在 WebKit 中，我们使用一种混合的碰撞指针/空闲列表分配器，我们称之为 bump’n’pop（在C++ 和编译器中都有）来进一步优化扫描。一个每块位（per-block bit）告诉扫描器该块是否完全为空。如果是，扫描器将在整个块上设置一个碰撞指针区域，而不是构建一个空闲列表。碰撞指针区域可以在 O(1) 时间内设置，而构建空闲列表是 O(n) 操作。Bump’n’pop 在大量分配内存的程序上实现了很大的加速，因为它避免了对完全空闲块的扫描。Bump’n’pop 的碰撞分配器总是按块的单元格大小进行碰撞，使其看起来像是从空闲列表中分配的对象。这保留了块在其大小类中的成员身份。

大型对象（大于约 8KB）使用 malloc 分配。

基于约束的标记

垃圾回收通常是一个图搜索问题，堆通常只是一个图：根是局部变量，它们的值是指向对象的有向边，这些对象具有字段，每个字段都创建指向其他对象的边。WebKit 的垃圾回收器还允许 DOM、编译器和类型推断系统安装约束回调。这些约束可以查询哪些对象被标记，并且允许它们标记对象。WebKit GC 算法执行这些约束直到达到不动点。GC 终止发生在所有已标记对象都被访问且所有约束都不再希望标记更多对象时。实际上，不动点的约束求解部分只占总时间的很小一部分。GC 的大部分时间都花在对已标记对象进行深度优先搜索上，我们称之为耗尽 (draining)。

并行耗尽

耗尽占用了回收器大部分时间。我们最古老的回收器优化之一是耗尽操作的并行化。回收器在每个 CPU 上都有一个耗尽线程。每个耗尽线程都有自己要访问的对象工作列表，通常它会运行一个只查看此工作列表的图搜索算法。使用本地工作列表意味着大部分时间可以避免工作列表同步。每个耗尽线程在以下条件下会与全局工作列表进行检查：

当它工作耗尽时。当一个线程工作耗尽时，它会尝试窃取全局工作列表的 1/N 部分，其中 N 是空闲耗尽线程的数量。这意味着需要获取全局工作列表的锁。
每访问 100 个对象，耗尽线程就会考虑将其工作列表的大约一半捐赠给全局工作列表。它只会在全局工作列表为空、可以无阻塞地获取全局工作列表锁以及本地工作列表至少有两个条目时执行此操作。

这种算法似乎能很好地扩展到大约八个核心，这对于 WebKit 通常运行的系统来说已经足够了。

并行耗尽意味着必须同步标记。我们的标记算法使用无锁 CAS（原子比较并交换指令）循环来设置标记位。

粘性标记位

分代垃圾回收是一种经典的吞吐量优化，最早由 Lieberman 和 Hewitt 以及 Ungar 引入。它假设最近分配的对象不太可能存活。因此，将回收器集中在上次 GC 后分配的对象上，很可能会释放大量内存——几乎与回收整个堆一样多。分代回收器跟踪对象的代 (generation)：年轻代或老年代。分代回收器至少有两种模式：只回收年轻对象的伊甸园 (eden) 回收和回收所有对象的完全 (full) 回收。在伊甸园回收期间，只有当老对象被怀疑包含指向新对象的指针时才会被访问。

分代回收器需要克服两个障碍：如何跟踪对象的代，以及如何找出哪些老对象包含指向新对象的指针。

回收器需要知道对象的代，以便在标记期间确定哪些对象可以安全地忽略。在传统的分代回收器中，伊甸园回收会移动对象，然后使用对象的地址来确定其代。我们的回收器不移动对象。相反，它使用标记位来同时跟踪代。简单地说，在伊甸园回收开始时，我们不清除任何标记位。标记算法将已经忽略那些已设置标记位的对象。这被称为 粘性标记位 (sticky mark bit) 分代垃圾回收。

回收器在伊甸园回收期间会避免访问老对象。但它无法避免所有老对象：如果一个老对象包含指向新对象的指针，那么回收器就需要知道访问该老对象。我们使用写屏障 (write barrier) —— 一小段在每次写入对象后执行的插桩代码 —— 来告知 GC 对老对象的写入。为了廉价地知道哪些对象是老对象，对象头也包含对象状态的副本：要么是老对象，要么是新对象。对象在分配时是新的，在标记时被标记为老的。当写屏障检测到对一个老对象的写入时，我们通过将对象状态设置为已老但已记住 (old-but-remembered) 并将其放入标记栈来通知 GC。我们对写屏障标记的对象使用单独的标记栈，因此当我们访问对象时，我们知道是因为屏障还是因为正常标记（即第一次）而访问它。某些记账操作只需要在第一次访问对象时发生。完整的屏障很简单：

object->field = newValue;
if (object->cellState == Old)
    remember(object);

分代垃圾回收极大地提高了大量分配内存的程序的性能，这在 JavaScript 中很常见。许多新的 JavaScript 特性，如迭代器、箭头函数、展开语法和 for-of 循环会分配大量对象，并且这些对象几乎立即死亡。分代 GC 意味着我们的回收器不需要访问所有老对象，只为了删除短生命周期的垃圾。

保守根扫描

垃圾回收通过查看局部变量和一些全局状态来确定初始的标记对象集合。内省局部变量的值很棘手。WebKit 使用 C++ 局部变量作为指向垃圾回收器堆的指针，但类 C 语言没有提供精确内省任意栈帧特定变量值的功能。WebKit 通过在扫描根时保守地标记对象来解决这个问题。我们部分使用简单分离存储堆结构是因为它使得判断任意位模式是否可能是指向某个对象的指针变得容易。

我们认为这是一项重要的优化。如果没有保守根扫描，C++ 代码将不得不使用某个 API 来通知回收器它指向哪些对象。保守根扫描意味着无需执行任何此类工作。

标记-清除总结

Riptide 通过任意约束回调实现了复杂的对象可达性概念，并允许 C++ 代码直接操作对象。为了性能，它并行化标记并使用分代来减少平均标记工作量。

处理并发

Riptide 使垃圾回收的耗尽阶段并发进行。这得益于多种并发特性的结合：

Riptide 能够针对某些棘手操作（如栈扫描和 DOM 约束求解）进行世界暂停 (stop the world)。
Riptide 使用退回波前 (retreating wavefront) 写屏障来管理标记和对象变异之间的竞态条件。使用退回波前使我们能够避免分代和并发回收器优化之间的任何阻抗不匹配。
退回波前回收器可能会面临 GC 死循环的风险，因此 Riptide 使用时空调度器 (space-time scheduler) 来加以控制。
在对象被重塑时访问它特别困难，而 WebKit 会将对象重塑作为类型推断的一部分。我们使用无阻塞双重收集快照 (obstruction-free double collect snapshot) 来确保回收器永远不会因为访问-重塑竞态条件而标记到垃圾内存。
许多对象存在不在关键路径上的复杂竞态条件，因此我们在每个 JavaScript 对象中嵌入了一个快速、自适应且公平的锁，作为管理它们的一种便捷方式。它利用了两个原本未使用的位。

尽管我们为 WebKit 编写了 Riptide，但我们认为其底层原理对于任何希望编写并发、分代、并行、保守且非复制型回收器的人都可能有用。本节详细描述了 Riptide。

世界暂停与安全点

Riptide 并发地执行耗尽操作。最终目标是使回收器的其他阶段也并发运行。但只要某些阶段不能安全地并发运行，我们就需要在执行这些阶段之前能够使应用程序停止。回收器停止的位置需要精心选择，以避免重入问题：例如，在 GC 分配器的中间停止运行 GC 会产生微妙的问题。并发 GC 通过只在应用程序将触发 GC 的点停止应用程序来避免这些问题。我们称之为安全点 (safepoints)。当回收器使应用程序到达一个安全点时，我们称之为世界暂停 (stopping the world)。

Riptide 目前在大部分约束不动点期间暂停世界，并在耗尽期间恢复世界。耗尽完成后，世界再次暂停。一个典型的回收周期可能包含多个暂停-恢复循环。

退回波前

并发耗尽意味着当我们刚访问完某个对象时，应用程序可能会向其某个字段进行存储。我们可能将一个指向未标记对象的指针存储到一个已经访问过的对象中，在这种情况下，回收器可能永远找不到那个未标记对象。如果我们不对此采取措施，回收器肯定会因为与应用程序的竞态条件而过早地删除对象。并发垃圾回收器通过使用写屏障来避免这个问题。本节描述了 Riptide 的写屏障。

写屏障通过标记对象或使对象重新访问（GC 手册，第 15 章）来确保在任何竞态条件后回收器的状态仍然有效。标记对象有助于回收器向前推进；直观地看，这就像推进 (advancing) 回收器的波前 (wavefront)。重新访问对象会使波前退回 (retreats)。文献中充满了各种并发 GC 算法，例如 Metronome、C4 和 DLG，它们都使用某种推进波前写屏障。最简单的此类屏障是 Dijkstra 的，它在任何时候创建对对象的引用时都会标记对象。我在过去的工作中使用过这类屏障，因为它们使得回收器非常确定。将其中一个屏障添加到 WebKit 可能会产生一些性能开销，因为这意味着在每次对堆的写入中添加新代码。但退回波前屏障，最初由 Guy Steele 在 1975 年发明，其工作原理与我们现有的分代屏障完全相同。这使得 Riptide 可以通过重用 WebKit 现有屏障实现零屏障开销。

通过查看一些屏障代码，最容易理解其相似之处。我们旧的分代屏障看起来像这样：

object->field = newValue;
if (object->cellState == Old)
    remember(object);

Steele 的退回波前屏障看起来像这样：

object->field = newValue;
if (object->cellState == Black)
    revisit(object);

退回波前屏障与分代屏障的工作原理相同，因此可以两者共用一个屏障。唯一的区别是术语。黑色 (black) 状态表示回收器已经访问过该对象。如果对象的 cellState 告诉我们回收器已经访问过它，这个屏障就会指示回收器重新访问该对象。这种状态是经典三色抽象 (tri-color abstraction) 的一部分：白色 (white) 表示 GC 尚未标记该对象，灰色 (grey) 表示该对象已被标记且在标记栈上，黑色 (black) 表示该对象已被标记且已被访问（因此不再在标记栈上）。在 Riptide 中，与并发相关的三色状态（白、灰、黑）与与分代相关的粘性标记位状态（新、记住、老）完美重叠。Riptide 单元状态如下：

DefinitelyWhite（明确白色）：对象是新的且是白色的。
PossiblyGrey（可能灰色）：对象是灰色的，或已记住的，或新的且是白色的。
PossiblyBlack（可能黑色）：对象是黑色且是老的，或灰色的，或已记住的，或新的且是白色的。

一个朴素的分代/并发组合屏障可能看起来像这样：

object->field = newValue;
if (object->cellState == PossiblyBlack)
    slowPath(object);

事实证明这需要调整才能工作。PossiblyBlack 状态过于模糊，因此 slowPath 需要额外的逻辑来确定对象的真实状态。此外，执行顺序也很重要：CPU 必须在执行 object->field 存储之后再执行 object->cellState 加载。这很难，因为 CPU 不喜欢遵守存储-加载顺序。最后，我们需要保证屏障不会使波前退回太多。

对象状态消歧

GC 使用块头中的对象标记位和对象头中的 cellState 字节的组合来确定对象的状态。GC 在完全回收开始时清除标记位，并在标记和屏障期间设置 cellState。它在完全回收开始时不会将对象的 cellState 重置回 DefinitelyWhite，因为可以通过查看标记位来推断 cellState 应该已经被重置。重要的是，回收器永远不会扫描堆来清除标记状态，甚至标记位都是使用版本控制逻辑清除的。如果一个对象是 PossiblyBlack 或 PossiblyGrey 且其标记位逻辑上已清除，则这意味着该对象实际上是白色的。Riptide 的屏障 slowPath 几乎与我们旧的分代慢路径相同，但它有一个新检查：如果目标对象的标记位未设置，它将不执行任何操作，因为这意味着我们正在 GC 过程中，并且该对象实际上是白色的。此外，屏障将尝试将对象设置回 DefinitelyWhite，以便 slowPath 路径不必再次看到该对象（至少在它被标记和访问之前不会）。

屏障前存储顺序

GC 必须在开始访问对象之前将其标记为 PossiblyBlack，并且应用程序必须在加载 object->cellState 之前将数据存储到 field。这种顺序在任何现代体系结构上都无法保证：在某些情况下，x86 和 ARM 都会将存储操作下沉到加载操作之下。插入无条件存储-加载屏障，例如 x86 上的lock; orl $0, (%rsp) 或 ARM 上的 dmb ish，会极大地降低性能。因此，我们通过对屏障条件玩一个把戏来使屏障本身成为条件性的：

object->field = newValue;
if (object->cellState <= blackThreshold)
    slowPath(object);

其中 blackThreshold 是一个全局变量。PossiblyBlack 状态的值为 0，当回收器未运行时，blackThreshold 为 0。但是一旦回收器开始标记，在世界暂停时它会将 blackThreshold 设置为 100。然后屏障的 slowPath 会以这样的检查开始：

storeLoadFence();
if (object->cellState != PossiblyBlack)
    return;

这意味着在 Riptide 运行时，应用程序会受到轻微的性能影响。在典型程序中，这种开销在 GC 期间约为 5%，不在 GC 期间则为 0%。不进行 GC 时唯一的额外成本是必须从内存中加载 blackThreshold，但我们未能检测到由于此更改导致的性能下降。回收期间的 5% 性能损失值得修复，但从整体上看，应用程序过去在 GC 期间会承受 100% 的性能损失，因为 GC 会停止应用程序的运行。

完整的 Riptide 写屏障的生成方式，就像在任何对 target 的存储之后，以下 writeBarrier 函数被内联了一样：

ALWAYS_INLINE void writeBarrier(JSCell* target)
{
    if (LIKELY(target->cellState() > blackThreshold))
        return;
    storeLoadFence();
    if (target->cellState() != PossiblyBlack)
        return;
    writeBarrierSlow(target);
}

NEVER_INLINE void writeBarrierSlow(JSCell* target)
{
    if (!isMarked(target)) {
        // Try to label this object white so that we don't take the barrier
        // slow path again.
        if (target->compareExchangeCellState(PossiblyBlack, DefinitelyWhite)) {
            if (Heap::isMarked(target)) {
                // A race! The GC marked the object in the meantime, so
                // pessimistically label it black again.
                target->setCellState(PossiblyBlack);
            }
        }
        return;
    }

    target->setCellState(DefinitelyGrey);
    m_mutatorMarkStack->append(target);
}

JIT 编译器会将慢路径中在执行内存屏障后重新检查对象状态的部分内联，因为这有助于在 GC 期间保持较低的开销。此外，我们的即时编译器通过在存储 GC 不关心的值时移除屏障、在对新分配的对象（必须是白色的）移除屏障、将屏障聚类以分摊内存屏障的成本以及在对象重复存储时移除冗余屏障来进一步优化屏障。

重新访问

当屏障确实将对象附加到 m_mutatorMarkStack 时，该对象最终将被重新访问。重新访问可以与应用程序并发进行。这很重要，因为我们已经看到程序退回波前足够多，否则总的重新访问暂停时间会太长。

与推进波前不同，退回波前意味着强制回收器重复已经完成的工作。如果没有一些设施来确保回收器进展，回收器可能会因为写屏障的重复重新访问请求而永远无法完成。Riptide 通过两种方式解决这个问题。首先，我们推迟所有重新访问请求。耗尽线程在没有其他工作可做之前不会处理任何重新访问请求。当一个对象被标记为需要重新访问时，它会在灰色 (grey) 状态下停留一段时间，并且只会在 GC 结束时被重新访问。这确保了如果一个老对象的字段经常被指向新对象的指针覆盖，那么 GC 通常只扫描这些字段的两个快照：一个快照是 GC 第一次访问对象时，另一个是在 GC 处理延迟的重新访问时。重新访问延迟减少了失控 GC 的可能性，但完全消除此类病态则留给我们的调度器。

时空调度器

退回波前 GC 周期的惨痛结局并不美好：就在回收器准备访问标记栈上最后一个对象时，某个已经访问过的对象被写入，然后又回到了标记栈上。这种情况可能会持续一段时间，在我们采取任何缓解措施之前，我们看到 Riptide 比同步回收多使用了 5 倍的内存。这种死循环发生是因为程序一直在大量分配内存，而回收器在完成标记之前无法释放任何内存。Riptide 通过一个控制应用程序速度的调度器来防止死循环。我们称之为时空 (space-time) 调度器，因为它将应用程序在一个时间片内运行的时间 (time) 量与应用程序在回收器预留空间 (headroom) 中通过分配所使用的空间 (space) 量联系起来。

时空调度器通过赋予回收器不公平的优势来确保退回波前屏障不会造成破坏：即使回收器可以并发运行，它也会周期性地短暂停留世界。它这样做只是为了让回收器在发生竞态条件时始终能超越应用程序。如果这是一个用于服务器的垃圾回收器，你可以想象为用户提供一堆旋钮来控制这些合成暂停的时间表。不同的应用程序将有不同的理想暂停长度。经常写入旧内存的应用程序会使回收器的波前大量退回，因此它们将需要更长的暂停时间来确保终止。函数式风格的程序倾向于只写入新分配的对象，因此它们可以使用更短的暂停。我们不希望网页用户或网页开发者必须配置我们的回收器，因此时空调度器会自适应地选择暂停时间表。

为了正确起见，调度器最终必须暂停世界足够长的时间以让回收器终止。时空调度器基于一个简单的思想：暂停的长度在回收期间会根据应用程序使用的内存量而增加。

时空调度器根据预留空间比 (headroom ratio) 来选择合成暂停的持续时间和间隔，预留空间比是衡量应用程序在并发回收期间额外分配的内存量的指标。并发回收由内存使用量超过触发阈值 (trigger threshold) 触发。由于回收器允许应用程序继续运行，应用程序将继续分配内存。回收器在回收期间为分配而留出的空间称为预留空间 (headroom)。Riptide 针对最大预留空间 (max headroom) 进行了调整，该空间比触发阈值大 50%：因此，如果应用程序需要分配 100MB 才能触发回收，则其最大预留空间为 50MB。如果我们耗尽所有预留空间，我们希望回收器同步完成：在那时，系统暂停并释放内存比继续运行并耗尽更多内存更好。预留空间比就是可用预留空间除以最大预留空间。时空调度器会将时间划分为固定的时间片，而预留空间比决定了在此期间应用程序恢复运行的时间量。

我们的回收器的默认调优是回收器时间片为 2 毫秒，其中前 C 毫秒分配给回收器，剩余的 M 毫秒分配给修改器（应用程序）。我们总是让回收器至少暂停 0.6 毫秒。令 H 为预留空间比：回收开始时为 1，如果耗尽所有预留空间则为 0。在最小暂停时间 0.6 毫秒和时间片 2 毫秒的情况下，我们定义 M 和 C 如下：

M = 1.4 H
C = 2 – M

例如，在常规回收开始时，我们将给回收器 0.6 毫秒，然后给应用程序 1.4 毫秒，但一旦应用程序开始分配，这个窗口就会发生变化。激进的应用程序，即大量分配内存且大量写入旧对象的应用程序，通常会以回收器接近 1 毫秒，随后应用程序 1 毫秒的分配结束回收。

多亏了时空调度器，对抗性程序最坏也只能导致 GC 不断重新访问某个对象。但它无法导致 GC 内存耗尽，因为如果对抗者用尽所有预留空间，那么 M 将变为 0，回收器就会暂停世界直到周期结束。

无阻塞双重收集快照

并发垃圾回收意味着寻找令人兴奋的新方法来规避昂贵的同步。在专注于良好类型语言的传统并发标记-清除 GC 中，最糟糕的竞态条件是写屏障所覆盖的那一种。但由于这是 JavaScript，我们能获得更多乐趣。

JavaScript 对象可以在任何时候添加属性。WebKit JavaScript 对象模型有三个特性使其高效：

每个对象都有一个结构 ID (structure ID)：每个对象的前 32 位是其结构 ID。通过表格查找，这会给出一个指向对象结构 (structure) 的指针：一种描述对象应该如何的元对象。对象的布局由其结构决定。有些对象具有不可变结构，因此对于这些对象，我们知道只要它们的结构 ID 保持不变，它们的布局也将保持不变。
结构可能会告诉我们该对象具有内联存储 (inline storage)。这是对象本身内部的一块空间，专门用于 JavaScript 属性。
结构可能会告诉我们对象的蝴蝶 (butterfly)。每个对象都有一个指针的空间，该指针可用于指向额外的属性的溢出存储，我们称之为蝴蝶。蝴蝶是一个双向对象，可以在指针的左侧存储命名属性，在右侧存储索引属性。

垃圾回收器必须使用与其对应的确切结构来访问蝴蝶。如果对象具有可变结构，则回收器必须使用与该蝴蝶对应的结构中的数据来访问蝴蝶。如果回收器尝试使用错误的信息解码蝴蝶，它将会崩溃。

为此，我们使用了非常简单的无阻塞 (obstruction-free) 版本的 Afek 等人的双重收集快照 (double collect snapshot)。为了处理不可变结构的情况，我们只需确保应用程序使用此协议来设置结构和蝴蝶：

清除结构 ID — 这会在结构 ID 中设置一个位，以向 GC 指示结构和蝴蝶正在改变。
设置蝴蝶。
设置新的（去污染的）结构 ID — 去污染意味着清除清除位。

同时，回收器执行以下操作来读取结构和蝴蝶：

读取结构 ID。
读取蝴蝶。
再次读取结构 ID，并与 (1) 比较。

如果回收器读取到已清除的结构 ID，或者 (1) 和 (3) 中的结构 ID 不同，那么我们就知道将存在蝴蝶-结构不匹配。但如果这些条件都不成立，那么我们保证回收器将拥有一个一致的结构和蝴蝶。证明请参阅此处。

更困难的是结构可变的情况。在这种情况下，我们确保设置结构中字段的协议是在结构被清除之后但在安装新结构之前设置它们。回收器也会在之前/之后读取这些字段。这使得回收器无需使用任何锁就能看到结构、蝴蝶以及结构内部一个位的 K/V 一致快照。重要的是应用程序中的存储和回收器中的加载是有序的。在 x86 上我们免费获得这一点，而在 ARM 上我们在应用程序中使用存储-存储屏障（dmb ishst），在回收器中使用加载-加载屏障（dmb ish）。

这种算法被称为无阻塞的，因为它无论遇到何种竞态条件都能在 O(1) 时间内完成，但如果确实遇到竞态条件，它会告诉你重试。无阻塞算法需要某种竞争管理器 (contention manager) 来确保它们最终能够完成。竞争管理器必须能证明性地最大化无阻塞算法最终在没有任何竞态条件的情况下运行的可能性。例如，一个合理的竞争管理器是：指数退避，其中实际的退避量是 0 到 X 之间的一个随机数，X 在每次尝试时呈指数增长。事实证明，Riptide 的退回波前重新访问调度器本身就是一个天然的竞争管理器。当回收器因为检测到竞态条件而放弃访问某个对象时，它会像屏障执行一样调度对该对象的重新访问。因此，GC 无论如何都会再次访问任何遇到此类竞态条件的对象。GC 会在稍后访问该对象，并且由于操作系统调度，访问时机将有些伪随机。如果一个对象确实不断被重新访问，最终时空调度器会增加回收器的合成暂停时间，直到在世界暂停的情况下发生重新访问。由于在任何结构/蝴蝶原子协议中都没有可能的安全点，停止世界确保了算法不会被阻塞。

嵌入式 WTF 锁

无阻塞对象快照很棒，但从 WebKit 开发人员的理智角度来看，它并不适合在所有地方使用。因为我们已经向 WebKit 添加了一段时间的并发性，所以我们通过在 WTF (Web 模板框架) 中拥有一个自定义锁定基础设施，从而使这变得更容易。WTF 锁的目标之一是将锁压缩到两位中，以便我们有一天可以将锁塞入每个 JavaScript 对象的头部。并发垃圾回收器中的许多极端情况竞态条件发生在获取锁没有问题的路径上，特别是如果该锁具有像 WTF 锁那样优秀的内联快速路径。因此，WebKit 中的所有 JavaScript 对象现在都在对象头中原本是 indexingType 字节的两位中嵌入了一个快速、自适应且公平的 WTF 锁。这个内部锁 (internal lock) 用于保护各种杂项数据结构的变异。回收器在访问这些对象时会持有内部锁。

加锁应该始终谨慎使用，因为它可能导致性能下降。在 Riptide 中，我们只使用加锁来保护不常见操作。此外，我们使用优化的锁实现来进一步降低同步成本。

算法总结

Riptide 是对 WebKit 回收器的一次改进，并保留了旧算法的许多优点。过去六个月里，改变 WebKit 回收器的修改陆续提交，始于移除 WebKit 之前使用复制的痛苦工作。Riptide 将 Guy Steele 经典的退回波前写屏障与成熟的粘性标记-清除回收器以及大量并发技巧相结合，实现了高 GC 吞吐量和低 GC 延迟的有效组合。

评估

当我们确信 Riptide 没有任何主要的性能、内存使用或稳定性方面的回归，并且在某些 GC 暂停测试中表现出改进时，我们启用了它。现在启用它使我们能够将其暴露给大量测试，以便我们继续调优和验证这个回收器。本节总结了我们目前对 Riptide 性能的了解。

启用并发回收的同步功能在 2016 年 7 月开始的六个月内分多个版本提交。本节重点介绍启用 Riptide 后我们获得的性能提升。启用 Riptide 意味着耗尽操作将恢复应用程序的运行，并允许应用程序和回收器并行运行。应用程序仍会经历暂停：包括来自时空调度器的合成暂停，以及 DOM 约束评估等操作的强制暂停。本次评估的目标是让大家一窥 Riptide 对观察到的暂停能带来什么影响。

最能体现我们垃圾回收器卡顿现象的测试是 Octane SplayLatency 测试。这个测试也包含在 JetStream 中。WebKit 以前在这两个版本的测试中表现都不是最好的，所以我们想要一个能带来巨大改进的 GC。这个测试的 Octane 版本报告均方根的倒数，这奖励了均匀的性能。JetStream 报告最差 0.5% 样本平均值的倒数，这奖励了快速的最坏情况性能。我们在 JetStream 版本的此测试上调整了 Riptide，但我们展示了两个版本的结果。

性能数据是在一台配备 2.8 GHz Intel Core i7 处理器和 16GB RAM 的 15 英寸 MacBook Pro 上收集的。这台机器有四个物理核心，并由于超线程技术而拥有八个逻辑 CPU。在运行基准测试之前，我们特意将机器静音，方法是关闭几乎所有应用程序，断开网络连接，禁用 Spotlight，以及禁用 ReportCrash。我们的 GC 擅长利用超线程 CPU，因此它在这台机器上运行八个耗尽线程。

上图显示 Riptide 将 JetStream/splay-latency 分数提高了五倍。

上图显示 Riptide 将 Octane/SplayLatency 分数提高了 2.5 倍。

上图显示了 Splay 基准测试 10,000 次迭代过程中发生的情况：如果没有 Riptide，偶尔会有一次迭代因垃圾回收而暂停超过 10 毫秒。启用 Riptide 后，这些卡顿现象降至 3 毫秒以下。

如果你想了解你的浏览器 GC 性能如何，你可以交互式地运行此基准测试。该版本将绘制 2,000 次迭代中每次迭代的时间（以毫秒为单位）。

我们在更多样化的工作负载上验证 Riptide 的同时，继续对其进行调优。我们的目标是继续减少暂停时间。这意味着使回收器更多地并发运行并改进时空调度器。持续调优的进展通过bug 165909 跟踪。

结论

本文描述了 WebKit 中新的 Riptide 垃圾回收器。Riptide 大部分工作都在主线程之外完成，从而显著减少了最坏情况下的暂停时间。根据 JetStream/splay-latency 测试的报告，启用 Riptide 可使延迟提高五倍。Riptide 现在已在 WebKit 主干中默认启用，您可以在Safari 技术预览版 21 中试用它。请试用它并提交错误报告！