2016 年 7 月 26 日
第 14 卷，第 3 期

空闲时间垃圾回收调度

利用空闲时间减少丢帧和内存消耗

Ulan Degenbaev，谷歌德国有限公司
Jochen Eisinger，谷歌德国有限公司
Manfred Ernst，谷歌公司
Ross McIlroy，谷歌英国有限公司
Hannes Payer，谷歌德国有限公司

谷歌的 Chrome 网络浏览器致力于提供流畅的用户体验。动画将以 60 FPS（帧每秒）的速度更新屏幕，这为 Chrome 提供了大约 16.6 毫秒的时间来执行更新。在这 16.6 毫秒内，所有输入事件都必须被处理，所有动画都必须被执行，最后帧必须被渲染。错过截止时间会导致丢帧。这些对用户是可见的，并且会降低用户体验。这种零星的动画瑕疵在这里被称为卡顿。³

JavaScript，网络的通用语言，通常用于动画网页。它是一种垃圾回收的编程语言，应用程序开发者不必担心内存管理。垃圾回收器会中断应用程序，遍历应用程序分配的内存，确定存活内存，释放死亡内存，并通过将对象更紧密地移动在一起来压缩内存。虽然其中一些垃圾回收阶段可以与应用程序并行或并发执行，但其他阶段则不能，因此它们可能会在不可预测的时间导致应用程序暂停。这种暂停可能会导致用户可见的卡顿或丢帧；因此，我们竭尽全力避免在 Chrome 中动画网页时出现这种暂停。

本文介绍了 Chrome 使用的 JavaScript 引擎 V8 中实现的一种方法，用于在 Chrome 空闲时调度垃圾回收暂停。¹ 这种方法可以减少真实世界网页上用户可见的卡顿，并减少丢帧。

V8 中的垃圾回收

垃圾回收器实现通常针对弱分代假设进行优化，⁶ 该假设指出应用程序中分配的大多数对象都很短命。如果该假设成立，则垃圾回收是高效的，并且暂停时间很短。如果该假设不成立，则暂停时间可能会延长。

V8 使用分代垃圾回收器，JavaScript 堆被分为一个用于新分配的小型年轻代和一个用于长寿命对象的大型老年代。由于大多数对象通常都很短命，因此这种分代策略使垃圾回收器能够在小型年轻代中执行定期的、短时间的垃圾回收，而无需跟踪大型老年代中的对象。

年轻代使用半空间分配策略，其中新对象最初分配在年轻代的活动半空间中。一旦半空间变满，清扫操作将遍历存活对象并将它们移动到另一个半空间。

这种半空间清扫是小垃圾回收。已经在年轻代中移动过的对象会被提升到老年代。在存活对象被移动之后，新的半空间变为活动状态，并且旧半空间中任何剩余的死亡对象都会被丢弃，而无需迭代它们。

因此，小垃圾回收的持续时间取决于年轻代中存活对象的大小。小垃圾回收通常很快，当年轻代中的大多数对象变得不可达时，耗时不超过一毫秒。但是，如果大多数对象都存活，则小垃圾回收的持续时间可能会显着延长。

当老年代中存活对象的大小超过启发式导出的已分配对象内存限制时，将执行整个堆的大垃圾回收。老年代使用标记-清除回收器进行压缩。标记工作取决于必须标记的存活对象的数量，对于具有许多存活对象的大型网页，整个堆的标记可能需要超过 100 毫秒。

为了避免这种长时间的暂停，V8 以许多小步骤增量地标记存活对象，仅在这些标记步骤中暂停主线程。当增量标记完成时，主线程会暂停以完成此大垃圾回收。首先，通过清除整个老年代内存来再次为应用程序提供可用内存，这由专用的清除器线程并发执行。之后，年轻代被疏散，因为我们通过年轻代进行标记并具有存活信息。然后执行内存压缩以减少老年代页面中的内存碎片。年轻代疏散和老年代压缩由并行压缩线程执行。之后，记住集合中移动对象的对象指针被并行更新。所有这些最终确定任务都发生在单个原子暂停中，这很容易花费几毫秒。

垃圾回收的两个致命罪过

此处概述的垃圾回收阶段可能在不可预测的时间发生，可能导致影响用户体验的应用程序暂停。因此，如果应用程序的性能受到影响，开发人员通常会创造性地尝试绕过这些中断。本节着眼于经常提出的两种有争议的方法并概述了它们的潜在问题。这些是垃圾回收的两个致命罪过。

罪过一：关闭垃圾回收器。 开发人员经常要求提供 API，以便在时间关键的应用程序阶段关闭垃圾回收器，在这些阶段，垃圾回收暂停可能会导致丢帧。但是，使用此类 API 会使应用程序逻辑复杂化，并使其更难以维护。忘记在程序中的单个分支上打开垃圾回收器可能会导致内存不足错误。此外，这也使垃圾回收器实现复杂化，因为它必须支持永不失败的分配模式，并且必须调整其启发式方法以考虑这些非垃圾回收的时间段。

罪过二：显式垃圾回收调用。 JavaScript 没有 Java 风格的 System.gc() API，但一些开发人员希望拥有它。他们的动机是在非时间关键阶段主动调用垃圾回收，以避免在稍后时间关键时调用。但是，应用程序不知道这种垃圾回收将花费多长时间，因此可能会自行引入卡顿。此外，如果开发人员在任意时间点调用垃圾回收器，垃圾回收启发式方法可能会感到困惑。

鉴于开发人员使用这些方法触发意外副作用的可能性，他们不应干扰垃圾回收。相反，运行时系统应努力避免需要此类技巧，方法是在主线应用程序执行期间提供高性能的应用程序吞吐量和低延迟的暂停，同时在空闲期间调度长时间运行的工作，使其不影响应用程序性能。

空闲任务调度

为了在 Chrome 空闲时调度长时间运行的垃圾回收任务，V8 使用 Chrome 的任务调度器。此调度器根据从 Chrome 的各种其他组件收到的信号以及旨在估计用户意图的各种启发式方法动态地重新确定任务的优先级。例如，如果用户触摸屏幕，调度器将在 100 毫秒内优先处理屏幕渲染和输入任务，以确保在用户与网页交互时用户界面保持响应。

调度器对任务队列占用情况的综合了解，以及它从 Chrome 的其他组件收到的信号，使其能够估计 Chrome 何时空闲以及可能保持空闲多长时间。此知识用于调度低优先级任务，以下称为空闲任务，这些任务仅在没有更重要的事情要做时运行。

为了确保这些空闲任务不会导致卡顿，它们仅在当前帧被绘制到屏幕和预期开始绘制下一帧的时间之间的时间段内有资格运行。例如，在活动动画或滚动期间（参见图 1），调度器使用来自 Chrome 合成器子系统的信号来估计当前帧的工作何时完成，以及基于预期的帧间间隔（例如，如果以 60 FPS 渲染，则帧间间隔为 16.6 毫秒），下一帧的估计开始时间是多少。如果未对屏幕进行活动更新，则调度器将启动更长的空闲时间段，该时间段将持续到下一个挂起的延迟任务的时间，上限为 50 毫秒，以确保 Chrome 对意外的用户输入保持响应。

为了确保空闲任务不会超出空闲时间段，调度器在空闲任务开始时将截止时间传递给空闲任务，指定当前空闲时间段的结束时间。空闲任务应在此截止时间之前完成，方法是调整它们执行的工作量以适应此截止时间，或者，如果它们无法在截止时间之前完成任何有用的工作，则重新发布自己以在未来的空闲时间段内执行。只要空闲任务在截止时间之前完成，它们就不会导致网页渲染中的卡顿。

V8 中的空闲时间垃圾回收调度

Chrome 的任务调度器允许 V8 通过将垃圾回收工作调度为空闲任务来减少卡顿和内存使用量。但是，为此，垃圾回收器需要估计何时触发空闲时间垃圾回收任务以及这些任务预计需要多长时间。这使垃圾回收器能够充分利用可用的空闲时间，而不会超过空闲任务的截止时间。本节介绍小垃圾回收和大垃圾回收的空闲时间调度的实现细节。

小垃圾回收空闲时间调度

小垃圾回收不能分成更小的工作块，必须完全执行或完全不执行。在空闲时间执行小垃圾回收可以减少卡顿；但是，过于积极地调度小垃圾回收可能会导致提升对象，否则这些对象可能会在随后的非空闲小垃圾回收中死亡。这可能会增加老年代的大小和未来大垃圾回收的延迟。因此，在空闲时间调度小垃圾回收的启发式方法应在尽早启动垃圾回收（以使年轻代大小足够小，以便在常规空闲时间期间可以回收）和延迟足够长的时间（以避免虚假提升对象）之间取得平衡。

每当 Chrome 的任务调度器在空闲时间调度小垃圾回收任务时，V8 都会估计执行小垃圾回收的时间是否适合空闲任务的截止时间。时间估计是使用平均垃圾回收速度和年轻代的当前大小计算的。它还会估计年轻代的增长率，并且仅当估计在下一个空闲时间段年轻代的大小预计将超过可以在平均空闲时间段内回收的大小才执行空闲时间小垃圾回收。

大垃圾回收空闲时间调度

大垃圾回收由三个部分组成：启动增量标记、多个增量标记步骤和最终确定。当堆的大小达到某个限制时，增量标记开始，该限制由堆增长策略配置。此限制在上次大垃圾回收结束时设置，基于堆增长因子 f 和老年代中存活对象的总大小：限制 = f ⋅ 大小。

一旦启动增量大垃圾回收，V8 就会向 Chrome 的任务调度器发布一个空闲任务，该任务将执行增量标记步骤。这些步骤可以按应标记的字节数线性缩放。基于平均测量的标记速度，空闲任务尝试在给定的空闲时间内完成尽可能多的标记工作。空闲任务会不断重新发布自己，直到所有存活对象都被标记。然后，V8 发布一个空闲任务以最终确定大垃圾回收。由于最终确定是原子操作，因此仅当估计它适合任务的分配空闲时间时才执行；否则，V8 会重新发布该任务，以便在具有更长截止时间的未来空闲时间运行。

内存缩减器

当网页显示稳定的分配速率时，基于分配限制调度大垃圾回收效果良好。但是，如果网页在达到分配限制之前变得不活动并停止分配，则在页面不活动的整个期间内将不会进行大垃圾回收。有趣的是，这是一种可以在实际应用中观察到的执行模式。许多网页在页面加载期间表现出较高的分配率，因为它们初始化其内部数据结构。加载后不久（几秒钟或几分钟），网页通常会变得不活动，导致分配率降低和 JavaScript 代码执行减少。因此，网页将在不活动状态下保留比其实际需要的更多的内存。

一个名为内存缩减器的控制器尝试检测网页何时变得不活动，并主动调度大垃圾回收，即使未达到分配限制也是如此。图 2 显示了大垃圾回收调度的示例。

第一次垃圾回收发生在时间 t₁，因为达到了分配限制。V8 根据堆大小设置下一个分配限制。随后的垃圾回收在时间 t₂ 和 t₃ 由内存缩减器在达到限制之前触发。虚线显示了没有内存缩减器的情况下堆大小会是多少。

由于这可能会增加延迟，因此 Google 开发了启发式方法，该方法不仅依赖于 Chrome 的任务调度器提供的空闲时间，还依赖于网页现在是否处于不活动状态。内存缩减器使用 JavaScript 调用和分配率作为网页是否处于活动状态的信号。当速率降至预定义阈值以下时，网页被认为是不活动的，并且在空闲时间执行大垃圾回收。

丝般顺滑的性能

我们这项工作的目的是通过减少垃圾回收引起的卡顿来提高基于动画的应用程序的用户体验质量。基于动画的应用程序的用户体验质量不仅取决于平均帧率，还取决于其规律性。过去已经提出了各种指标来量化卡顿现象，例如，测量帧率变化的频率、计算帧持续时间的方差或仅使用最大的帧持续时间。尽管这些指标提供了有用的信息，但它们都未能衡量某些类型的不规则性。基于帧持续时间分布的指标，例如方差或最大帧持续时间，无法考虑帧的时间顺序。例如，它们无法区分两个丢帧彼此靠近的情况和它们彼此远离的情况。前一种情况可以说更糟。

我们提出了一种新的指标来克服这些限制。它基于帧持续时间序列的差异。差异传统上用于衡量蒙特卡洛积分的样本质量。它量化了数字序列与均匀分布序列的偏差程度。直观地说，它衡量了最坏情况的卡顿持续时间。如果仅丢弃一帧，则差异指标等于绘制帧之间的间隙大小。如果连续丢弃多个帧（中间有一些好帧），则差异将报告整个不良性能区域的持续时间，并根据好帧进行调整。

差异是量化动画内容最坏情况性能的绝佳指标。给定帧绘制的时间戳，可以使用 Kadane 算法的变体在 O(N) 时间内计算差异，以解决最大子数组问题。

在线 WebGL (Web Graphics Library) 基准测试 OortOnline (http://oortonline.gl/#run) 展示了空闲时间垃圾回收调度的卡顿改进。图 3 显示了这些改进：帧时间差异、帧时间、由于垃圾回收而错过的帧数以及与 oortonline.gl 基准测试上的基线相比的总垃圾回收时间。

帧时间差异平均从 212 毫秒减少到 138 毫秒。平均帧时间从 17.92 毫秒提高到 17.6 毫秒。我们观察到 85% 的垃圾回收工作是在空闲时间调度的，这显着减少了在时间关键阶段执行的垃圾回收工作量。空闲时间垃圾回收调度将总垃圾回收时间增加了 13% 至 780 毫秒。这是因为主动调度垃圾回收并利用空闲任务更快地进行增量标记导致了更多的垃圾回收。

空闲时间垃圾回收还改进了常规网页浏览。在滚动 Facebook 和 Twitter 等流行的网页时，我们观察到大约 70% 的总垃圾回收工作是在空闲时间执行的。

当网页变得不活动时，内存缩减器会启动。图 4 显示了在 Google 网页搜索页面上使用和不使用内存缩减器的 Chrome 的示例运行。在最初的几秒钟内，两个版本都使用相同的内存量，因为网页加载并且分配率很高。过一会儿，网页变得不活动，因为页面已加载且没有用户交互。一旦内存缩减器检测到页面不活动，它就会启动大垃圾回收。此时，基线和内存缩减器的图表开始发散。在网页变得不活动后，使用内存缩减器的 Chrome 的内存使用量降至基线的 34%。

有关如何运行此处介绍的实验以重现这些结果的详细说明，请参见 2016 年 PLDI（编程语言设计和实现）工件评估文档。²

其他空闲时间垃圾回收系统

上一篇文章中提供了利用空闲时间的垃圾回收器的全面概述。⁴ 作者将不同的方法分为三类：基于松弛的系统，其中垃圾回收器在系统中没有其他任务处于活动状态时运行；定期系统，其中垃圾回收器在预定义的时间间隔内运行给定的持续时间；以及利用这两种想法的混合系统。作者发现，平均而言，混合系统提供最佳性能，但某些应用程序更喜欢基于松弛或定期的系统。

我们的空闲时间垃圾回收调度方法有所不同。它的主要贡献在于，它分析应用程序和垃圾回收组件，以预测垃圾回收操作将花费多长时间，以及由于应用程序分配吞吐量，何时将发生下一次小垃圾回收或大垃圾回收。该信息允许在空闲时间有效地调度垃圾回收操作，以减少卡顿，同时提供高吞吐量。

并发、并行、增量垃圾回收

避免在执行应用程序时出现垃圾回收暂停的另一种正交方法是通过使垃圾回收操作并发、并行或增量来实现的。使标记阶段或压缩阶段并发或增量通常需要读取或写入屏障，以确保堆状态一致。由于昂贵的屏障开销和虚拟机代码的复杂性，应用程序吞吐量可能会降低。

空闲时间垃圾回收调度可以与并发、并行和增量垃圾回收实现相结合。例如，V8 实现了增量标记和并发清除，这些也可以在空闲时间执行以确保快速进度。最重要的是，诸如年轻代疏散或老年代压缩之类的昂贵的内存压缩阶段可以在空闲时间有效地隐藏，而不会引入昂贵的读取或写入屏障开销。

对于尽力而为的系统，其中不必满足硬实时截止时间，空闲时间垃圾回收调度可能是一种提供高吞吐量和低卡顿的简单方法。

超越垃圾回收和结论

空闲时间垃圾回收调度侧重于用户的期望，即以每秒 60 帧的速度渲染的系统看起来非常流畅。因此，我们对空闲时间的定义与屏幕渲染信号紧密耦合。当应用空闲时间的适当定义时，其他应用程序也可以从空闲时间垃圾回收调度中受益。例如，基于 node.js 的服务器（构建在 V8 之上）可以在等待网络连接时将空闲时间段转发到 V8 垃圾回收器。

空闲时间的利用不仅限于垃圾回收。它已以 requestIdleCallback API 的形式公开给 Web 平台，⁵ 使网页能够在空闲时间调度自己的回调以运行。作为未来的工作，JavaScript 引擎的其他管理任务可以在空闲时间执行（例如，使用优化即时编译器编译代码，否则将在 JavaScript 执行期间执行）。

参考文献

1. Degenbaev, U., Eisinger, J., Ernst, M., McIlroy, R., Payer, H. 2016. 空闲时间垃圾回收调度。在 SIGPLAN 编程语言设计与实现会议论文集中。

2. Degenbaev, U., Eisinger, J., Ernst, M., McIlroy, R., Payer, H. 2016. PLDI'16 工件：空闲时间垃圾回收调度；PLDI'16，2016 年 6 月 13-17 日，美国加利福尼亚州圣巴巴拉。978-1-4503-4261-2/16/06，第 570-583 页。 https://goo.gl/AxvigS。

3. 谷歌公司。RAIL 性能模型； http://developers.google.com/web/tools/chrome-devtools/profile/evaluate-performance/rail。

4. Kalibera, T., Pizlo, F., Hosking, A. L., Vitek, J. 2011. 在单处理器上调度实时垃圾回收。 计算机系统事务 29(3): 8:1-8:29。

5. McIlroy. R. 2016. 后台任务的协同调度。W3C 编辑草案； https://w3c.github.io/requestidlecallback/。

6. Ungar, D. 1984. 分代清扫：一种非破坏性的高性能存储回收算法。在第一届 SIGSOFT/SIGPLAN 实用软件开发环境研讨会论文集 (SDE 1) 中。

Ulan Degenbaev 是 Google 的一名软件工程师，致力于 V8 JavaScript 引擎的垃圾回收器。他获得了萨尔兰大学的计算机科学硕士学位和博士学位，在那里他从事形式化规范和软件验证工作。

Jochen Eisinger 是 Google 的一名软件工程师，致力于 V8 JavaScript 引擎和 Chrome 安全性。在此之前，他曾在 Chrome 的其他各个部分工作过。在加入 Google 之前，他是加拿大不列颠哥伦比亚大学温哥华分校的博士后研究员。他获得了德国弗莱堡大学的 Diplom 学位和计算机科学博士学位。

Manfred Ernst 是 Google 的一名软件工程师，他在那里从事虚拟现实工作。在此之前，他将 GPU 光栅化引擎集成到 Chrome 网络浏览器中。在加入 Google 之前，Ernst 曾是英特尔实验室的研究科学家，在那里他领导了 Embree 光线追踪内核的开发。他还是 Bytes+Lights 的联合创始人兼首席执行官，这是一家为汽车行业开发可视化工具的初创公司。他获得了埃尔兰根-纽伦堡大学的 Diplom 学位和计算机科学博士学位。

Ross McIlroy 是 Google 的一名软件工程师，也是 V8 解释器工作的技术主管。他之前曾在 Chrome 的调度子系统和移动优化工作方面工作过。在加入 Google 之前，McIlroy 曾从事各种操作系统和虚拟机研究项目，包括 Singularity、Helios、Barrelfish 和 HeraJVM。他获得了格拉斯哥大学的计算科学博士学位，在那里他从事异构多核虚拟机的研究。

Hannes Payer 是 Google 的一名软件工程师，V8 JavaScript 垃圾回收工作的技术主管，也是一位虚拟机爱好者。在 V8 之前，Hannes 曾在 Google 的 Dart 虚拟机和各种 Java 虚拟机上工作过。他获得了萨尔茨堡大学的博士学位，在那里他从事并发对象的多核可扩展性研究，并且是 Scal 项目的首席研究员。

queue.acm.org 上的相关内容

实时垃圾回收
- David F. Bacon

与 David Anderson 的对话

网络虚拟化：打破性能壁垒
- Scott Rixner

最初发表于 Queue vol. 14, no. 3—
在数字图书馆中评论本文

更多相关文章

David Collier-Brown - 你不了解应用程序性能
您不需要在每次遇到性能或容量规划问题时都进行全面的基准测试。一个简单的测量将提供您系统的瓶颈点：这个示例程序在每 CPU 每秒八个请求后会显着变慢。这通常足以告诉您最重要的事情：您是否会失败。

Peter Ward, Paul Wankadia, Kavita Guliani - 在 Google 重新发明后端子集化
后端子集化对于降低成本非常有用，甚至对于在系统限制内运行可能是必要的。十多年来，Google 使用确定性子集化作为其默认的后端子集化算法，但是尽管此算法平衡了每个后端任务的连接数，但确定性子集化具有高水平的连接流失。我们在 Google 的目标是设计一种具有减少连接流失的算法，该算法可以替代确定性子集化作为默认的后端子集化算法。

Noor Mubeen - 工作负载频率缩放定律 - 推导和验证
本文介绍了与每个 DVFS 子系统级别的工作负载利用率缩放相关的方程。建立了频率、利用率和比例因子（其本身随频率变化）之间的关系。这些方程的验证结果证明是棘手的，因为工作负载固有的利用率似乎也在治理样本的粒度上以未指定的方式变化。因此，应用了一种称为直方图脊迹的新颖方法。当将 DVFS 视为构建块时，量化缩放影响至关重要。典型应用包括 DVFS 调控器和/或其他影响系统利用率、功耗和性能的层。

Theo Schlossnagle - DevOps 世界中的监控
监控看起来可能非常势不可挡。最重要的是要记住，完美永远不应该是更好的敌人。DevOps 使组织内部能够进行高度迭代的改进。如果您没有监控，请获取一些；获取任何东西。有些东西总比没有好，如果您已经接受了 DevOps，那么您就已经同意随着时间的推移使其变得更好。