跳到主要内容

V8中的并发标记

· 阅读需 13 分钟
Ulan Degenbaev, Michael Lippautz 和 Hannes Payer — 主线程解放者

这篇文章描述了一种叫做_并发标记_的垃圾回收技术。这项优化使 JavaScript 应用程序在垃圾回收器扫描堆以发现并标记活动对象时可以继续执行。我们的基准测试表明，并发标记将主线程上标记所需的时间减少了60%-70%。并发标记是 Orinoco 项目 的最后一块拼图 — 这是一个逐步用新的大多数并发和并行垃圾回收器替换旧垃圾回收器的项目。并发标记在 Chrome 64 和 Node.js v10 中默认启用。

背景​

标记是 V8 的 Mark-Compact 垃圾回收器的一个阶段。在这个阶段，回收器会发现并标记所有活动对象。标记从已知活动对象（例如全局对象和当前活动函数，也称为根）的集合开始。回收器将根标记为活动对象，并跟随其中的指针以发现更多活动对象。回收器继续标记新发现的对象并跟随指针，直到没有更多对象需要标记。标记结束后，堆中所有未标记的对象均无法由应用程序访问，可以安全回收。

我们可以将标记视为图遍历（graph traversal）。堆中的对象是图中的节点。从一个对象到另一个对象的指针是图中的边。给定图中的一个节点，我们可以使用对象的 隐藏类 找到该节点的所有出边。

图1. 对象图

V8 使用每个对象的两个标记位和一个标记工作列表来实现标记。两个标记位编码三种颜色：白色 (00)、灰色 (10) 和黑色 (11)。起初，所有对象都是白色的，这意味着回收器尚未发现它们。回收器发现一个白色对象后会将其变成灰色，并推送到标记工作列表中。当回收器从标记工作列表中弹出一个灰色对象并访问其所有字段时，该灰色对象会变成黑色。这种方案称为三色标记。标记结束时，不再有灰色对象。所有剩余的白色对象都是无法访问的，可以安全回收。

图2. 标记从根开始

图3. 回收器通过处理指针将灰色对象变成黑色

图4. 标记完成后的最终状态

请注意，上述标记算法仅在应用程序暂停时才有效。如果在标记进行时允许应用程序运行，那么应用程序可能会更改图，并最终欺骗回收器释放活动对象。

减少标记暂停​

一次性执行的标记对大型堆的处理时间可能需要数百毫秒。

如此长时间的暂停可能会导致应用程序响应不良，并带来较差的用户体验。在 2011 年，V8 从全停止标记切换到增量标记。在增量标记过程中，垃圾回收器将标记工作拆分为较小的块，并允许应用程序在块之间运行：

垃圾回收器选择每块要执行的增量标记工作量，以匹配应用程序的分配速率。在常见情况下，这极大地改善了应用程序的响应性。但对于内存压力下的大型堆，由于回收器尝试跟上分配量，仍然可能出现较长的暂停。

增量标记并非免费。应用程序必须通知垃圾回收器所有更改对象图的操作。V8 使用 Dijkstra 风格的写入障碍来实现通知。在 JavaScript 中每次以 object.field = value 形式的写入操作后，V8 插入写入障碍代码：

// 在 `object.field = value` 操作后调用。
write_barrier(object, field_offset, value) {
  if (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

写屏障强制保持一个不变性，即黑色对象不能指向白色对象。这也被称为强三色不可变性，确保应用程序无法将活动对象隐藏于垃圾回收器之外，因此标记结束时所有白色对象对应用程序不可达，可以安全释放。

增量标记很好地与空闲时间垃圾回收调度集成，如之前的博客文章中所述。Chrome 的 Blink任务调度器可以在主线程的空闲时间调度小型的增量标记步骤，而不会引起卡顿。如果有空闲时间，这种优化效果非常好。

由于写屏障的开销，增量标记可能会降低应用程序的吞吐量。通过利用额外的工作线程，可以同时提高吞吐量和暂停时间。工作线程上的标记有两种方式：并行标记和并发标记。

并行标记发生在主线程和工作线程上。整个并行标记阶段，应用程序是暂停的。这是停止世界标记的多线程版本。

并发标记主要发生在工作线程上。并发标记进行时，应用程序可以继续运行。

以下两部分将描述我们如何在 V8 中增加对并行标记和并发标记的支持。

并行标记​

在并行标记期间，我们可以假设应用程序不是并发运行的。这大大简化了实现，因为我们可以假设对象图是静态的且不会发生变化。为了并行标记对象图，我们需要使垃圾收集器的数据结构线程安全，并找到一种方法在线程之间高效地共享标记工作。下图显示了并行标记中涉及的数据结构。箭头表示数据流的方向。为了简单起见，图中省略了堆碎片整理所需的数据结构。

图5. 用于并行标记的数据结构

注意，线程只从对象图中读取数据，永远不会更改对象图。对象的标记位和标记工作列表必须支持读写访问。

标记工作列表和工作窃取​

标记工作列表的实现对于性能至关重要，它平衡了快速的线程本地性能与当线程耗尽工作时分发工作给其他线程的能力。

在权衡空间中最极端的两种情况是：(a) 使用一个完全并发的数据结构以实现最佳共享，因为所有对象都有可能被共享；(b) 使用一个完全线程本地的数据结构，在没有对象共享的情况下优化线程本地吞吐量。图6展示了 V8 如何通过使用基于段的标记工作列表在线程本地插入和移除之间取得平衡。一旦一个段变满，它将被发布到一个共享的全局池中，以便被窃取使用。这样，V8 允许标记线程尽可能在本地操作而无需同步，同时可以处理当一个线程到达对象的一个新子图，而另一个线程因耗尽其本地段而饿死的情况。

图6. 标记工作列表

并发标记​

并发标记允许 JavaScript 在主线程上运行，同时工作线程正在遍历堆上的对象。这为许多潜在的数据竞争打开了大门。例如，JavaScript 可能在工作线程读取字段的同时写入对象字段。数据竞争可能会让垃圾收集器错误地释放一个活动对象或将原始值与指针混淆。

主线程上任何更改对象图的操作都是潜在的数据竞争来源。由于 V8 是一个具有许多对象布局优化的高性能引擎，潜在数据竞争来源的列表相当长。这是一份高级的归纳列表：

  • 对象分配。
  • 写入对象字段。
  • 对象布局更改。
  • 从快照反序列化。
  • 函数去优化过程中的物化。
  • 年轻代垃圾回收中的疏散。
  • 代码修补。

主线程需要在这些操作上与工作线程进行同步。同步的成本和复杂性取决于操作。大多数操作允许通过原子内存访问进行轻量级同步，但一些操作需要对象的独占访问。在以下小节中，我们将重点讨论一些有趣的情况。

写屏障​

由写入对象字段引起的数据竞争通过将写操作变为松散的原子写并调整写屏障解决：

// atomic_relaxed_write(&object.field, value); 之后调用
write_barrier(object, field_offset, value) {
  如果 (color(value) == white && atomic_color_transition(value, white, grey)) {
    marking_worklist.push(value);
  }
}

与之前使用的写屏障进行比较：

// 在执行 `object.field = value` 后调用。
write_barrier(object, field_offset, value) {
  如果 (color(object) == black && color(value) == white) {
    set_color(value, grey);
    marking_worklist.push(value);
  }
}

有两处改动：

  1. 去掉了对于源对象颜色 (color(object) == black) 的检测。
  2. value 的颜色从白色到灰色的转换是原子操作。

没有源对象颜色检测时，写屏障变得更加保守，即可能将对象标记为存活，即使这些对象实际上不可达。我们移除了检测，以避免写操作和写屏障之间需要昂贵的内存栅栏：

atomic_relaxed_write(&object.field, value);
memory_fence();
write_barrier(object, field_offset, value);

没有内存栅栏时，对象颜色加载操作可能在写操作之前进行重排序。如果我们不防止重排序，那么写屏障可能观察到灰色对象颜色并退出，而工作线程标记对象时没有看到新的值。Dijkstra 等人提出的原始写屏障也没有检查对象颜色。他们这样做是为了简单起见，但我们需要这样做以确保正确性。

Bailout 工作队列​

某些操作（例如代码修补）需要对对象的独占访问。在早期，我们决定避免使用每个对象锁，因为它们可能导致优先级反转问题，主线程不得不等待已解除调度但持有对象锁的工作线程。我们并没有锁定对象，而是允许工作线程在访问对象时退出访问。工作线程通过将对象放入 Bailout 工作队列来实现该操作，该队列仅由主线程处理：

图 7：Bailout 工作队列

工作线程在对优化代码对象、隐藏类和弱集合进行访问时退出，因为这些对象的访问需要锁定或昂贵的同步协议。

回顾来看，Bailout 工作队列在增量开发中效果显著。我们从工作线程退出所有对象类型的访问开始实现，并逐渐添加并发访问功能。

对象布局变化​

对象的字段可以存储三种类型的值：标记指针、标记小整数（也称为 Smi），或非标记值，如未装箱的浮点数。指针标记 是一种公认的技术，可高效表示未装箱的整数。在 V8 中，标记值的最低有效位指示它是指针还是整数。这基于指针是字对齐的事实。关于字段是标记还是非标记的信息存储在对象的隐藏类中。

V8 中的一些操作通过将对象过渡到另一个隐藏类来改变对象字段从标记到非标记（或相反）。这种对象布局变化对于并发标记是不安全的。如果在工作线程使用旧隐藏类并发访问对象时发生变化，则可能出现两种类型的错误。首先，工作线程可能错过一个指针，认为它是一个非标记值。写屏障能够防止这类错误。其次，工作线程可能将一个非标记值视为指针并解引用，导致无效内存访问，通常伴随程序崩溃。为了处理这种情况，我们使用一个快照协议，对对象的标记位进行同步。协议涉及两个参与者：主线程将对象字段从标记改为非标记以及工作线程访问该对象。在改变字段之前，主线程确保对象被标记为黑色，并将其放入 Bailout 工作队列以供稍后访问：

atomic_color_transition(object, white, grey);
如果 (atomic_color_transition(object, grey, black)) {
  // 在主线程清理 Bailout 工作队列时，该对象将被重新访问。
  bailout_worklist.push(object);
}
unsafe_object_layout_change(object);

如下代码片段所示，工作线程首先加载对象的隐藏类，并使用原子松弛加载操作快照对象隐藏类指定的所有指针字段。然后，它尝试使用原子比较并交换操作将对象标记为黑色。如果标记成功，这意味着快照必须与隐藏类一致，因为主线程在更改其布局之前将对象标记为黑色。

snapshot = [];
hidden_class = atomic_relaxed_load(&object.hidden_class);
对于(hidden_class的pointer_field_offsets中的字段偏移量) {
  pointer = atomic_relaxed_load(object + 字段偏移量);
  快照.add(字段偏移量, pointer);
}
如果(atomic_color_transition(object, grey, black)) {
  访问指针(快照);
}

请注意，发生不安全布局更改的白色对象必须在主线程上标记。不安全布局更改相对罕见，因此这对实际应用程序性能的影响不大。

整体整合​

我们将并行标记集成到现有的增量标记基础设施中。主线程通过扫描根并填充标记工作列表来启动标记。在此之后，它将并行标记任务发布到工作线程上。工作线程通过协作排空标记工作列表帮助主线程更快地完成标记进程。主线程偶尔会通过处理备用工作列表和标记工作列表来参与标记。当标记工作列表变为空时，主线程会完成垃圾收集。在最终清理期间，主线程重新扫描根对象，并可能会发现更多白色对象。这些对象通过工作线程的帮助并行标记。

结果​

我们的真实世界基准测试框架显示，在移动和桌面设备上，每次垃圾收集循环主线程标记时间分别减少了大约65%和70%。

主线程标记所耗时间（越低越好）

并行标记还减少了 Node.js 中的垃圾收集抖动。这一点尤为重要，因为 Node.js 从未实现闲时垃圾收集调度，因此无法在非关键阶段隐藏标记时间。并行标记已在 Node.js v10 中发布。