工作包（Work Packets）：垃圾回收软件工程、优化与创新的新抽象概念

《Proceedings of the ACM on Programming Languages》：Work Packets: A New Abstraction for GC Software Engineering, Optimization, and Innovation

本文提出了一种基于工作包的垃圾收集器设计方法，通过将GC任务抽象为包含工作项、处理内核和调度约束的工作包，实现了效率与敏捷性的平衡。实验表明，该设计在LXR收集器中显著优于传统相位式GC和OpenJDK 24的G1收集器，同时支持多种GC算法的高效实现。

　　

摘要

垃圾收集（GC）的实现必须同时满足效率性和可维护性的要求，而这两者往往被视为相互矛盾的。此外，对效率性的追求通常会牺牲灵活性，从而阻碍快速开发和创新，并对长期性能目标产生不良影响。以往的GC实现难以做到以下几点：i) 最大化效率、并行性和硬件利用率；ii) 正确且优雅地实现优化和调度约束。这种困境在当前的GC实现中依然存在，这些实现往往采用单体架构，并依赖粗粒度的同步机制。

本文提出了一种新的GC实现设计，该设计同时强调灵活性和效率性。该设计将所有GC任务简化并统一为工作包，工作包包括：i) 需要处理的任务项；ii) 处理这些任务项的内核；以及iii) 调度约束。我们的基本观点是：执行过程主要由少数执行频率极高的内核主导，而GC实现本质上是一种高级算法，用于协调大量的性能关键任务项。工作包由具有相似性质的任务项组成，例如扫描线程栈或跟踪包含数百万对象的内存堆中的某个对象。与工作包相关联的内核负责指定如何处理其中的任务项（例如如何扫描栈或如何跟踪对象）。调度约束用于表达任务之间的依赖关系，例如所有修改对象的操作必须在进行对象复制之前完成。完全并行的操作（如扫描根对象或执行传递闭包）几乎不需要同步。GC算法的实现仅需声明所需的工作包、相关内核及其依赖关系即可。该执行模型能够透明地处理不同的GC算法和工作包类型。我们扩展了“工作窃取”（work-stealing）技术的应用范围，使其适用于任何类型的GC任务，并引入了一种新型的双层工作窃取算法，以在更细粒度的层面进一步提升并行性。

我们通过八个使用MMTk GC框架中23种常见工作包类型的收集器来展示这种设计的软件工程优势。我们使用LXR收集器证明了工作包抽象机制能够支持创新并实现高性能：i) 相比基于阶段划分的方法，工作包能够带来更好的性能提升；ii) 带有工作包的LXR在性能上优于经过高度优化的最新版（OpenJDK 24）G1垃圾收集器。由此可见，工作包不仅简化了GC实现，还使其更易于优化和验证。