加速Plush垃圾收集器

# 加速 Plush 垃圾回收器 来源：https://pointersgonewild.com/2026-08-17-speeding-up-the-plush-garbage-collector/ 一直关注本博客或在X上关注我的朋友们知道，我经常在各种副项目之间跳跃。前段时间，我做了个决定：允许自己跟随兴趣去探索新想法，因为我认为保持乐趣对副项目至关重要，绝不能使其沦为苦差。不过偶尔，我还是会想起之前搁置的某个项目，并琢磨如何让它更进一步。 去年我写过一系列关于Plush (https://github.com/maximecb/plush) 的文章，这是我创造的一个类似Lox的玩具语言 (https://pointersgonewild.com/2025-08-03-creating-a-toy-language-with-actor-based-parallelism/) 。创建它是为了探索不同的解释器和虚拟机设计思路。特别值得一提的是，它采用了基于Actor的并行模型，设计上保证了任何关键路径上都没有全局VM锁，也无需因任何情况暂停整个VM。后来我在Plush解释器中实现了一些基础优化 (https://pointersgonewild.com/2025-08-06-out-fibbing-cpython-with-the-plush-interpreter/) ，并为VM编写了一个复制式垃圾回收器 (GC) (https://pointersgonewild.com/2025-11-29-building-a-copying-gc-for-the-plush-programming-language/) 。GC本身并无特别之处，但其独特之处在于：每个Actor拥有完全独立的GC实例。每个Actor在运行回收周期时都无需任何同步操作。不过略显遗憾的是，这个GC的性能表现相当令人失望。 我对Plush GC有个个人目标：希望它能在20毫秒内回收一百万个活跃对象，如此速度足以在Plush中构建一个不会因GC暂停而产生明显卡顿的3D游戏引擎。我编写了一个名为`gc_many_objs.psh`的小型微基准测试，它会分配一个含百万节点的链表，然后在循环中触发GC。但性能结果远未达到目标。在我的MacBook Air M5上，该实现的回收耗时约117毫秒，比预期慢了好几倍。原因在于我实现复制式GC时采取了取巧的方式。 传统的Cheney复制收集器 (https://en.wikipedia.org/wiki/Cheney%27s_algorithm) 会将对象从一块内存空间（"源空间"）复制到另一块（"目标空间"），并利用每个对象头中的转发指针，同时将目标空间作为工作列表，在复制过程中传递性地遍历活跃对象图。 在Plush中，每个Actor拥有自己的私有分配器用于对象分配，以及一个消息分配器作为接收其他Actor消息的缓冲区。当对象作为消息发送时，发送方会将其复制到接收方的消息分配器中。这种设计旨在解耦发送方和接收方，意味着双方在交换消息时无需加锁同步。我希望复用同一种复制算法，既用于GC，也用于将消息复制到接收方的消息分配器中。为此，我不愿使用发送方堆中的转发指针（那会修改发送方的对象），而是采用了一个哈希表来记录对象与其副本的对应关系。当时我以为这对性能影响不大，毕竟指针哈希计算很快，但我错了。 **一个Actor的两个分配器，以及消息经历的两次复制过程。** (https://pointersgonewild.com/2026-08-17-speeding-up-the-plush-garbage-collector/actors.svg) 一个Actor的两个分配器，以及消息经历的两次复制过程。 我的同事兼朋友 Laurent Huberdeau 指出了一个我此前不知道的基本事实：默认的Rust `HashMap`使用的是安全哈希函数，专为抵御HashDoS攻击而设计。这不影响功能，但影响了性能。幸运的是，`rustc_hash` crate 中有一个等效的`FxHashMap`，由rust-lang项目维护，可直接替换使用。Laurent还发现了一处冗余的哈希表查找可以避免。这些简单的改动使复制式GC的运行速度提升了一倍以上，在我的M5笔记本上降至43毫秒。虽然快多了，但仍远未达到我最初的20毫秒目标。 性能分析显示，大部分开销仍来自哈希表。还有更糟的消息：转发指针哈希表本身占用的空间甚至超过了回收过程中复制的活跃数据。细想一下这很合理。我们复制的是链表，链表节点很小，每个节点只有一个next指针和一个value字段。哈希表条目本身是一对指针，更重要的是，哈希表需要一定量的额外容量（空槽位）才能良好运行，否则会遭遇哈希冲突导致性能骤降。此外，哈希函数的设计目标是不可预测，输出应呈现准随机分布。从缓存性能角度看，这其实糟糕透顶。它意味着在GC过程中，我们访问内存的位置会四处跳动，且不可预测，涉及的范围甚至超过了实际复制的数据量。这很不理想。 **同一次复制的两种实现方式：通过哈希表，以及使用转发地址。** (https://pointersgonewild.com/2026-08-17-speeding-up-the-plush-garbage-collector/forwarding.svg) 同一次复制的两种实现方式：通过哈希表，以及使用转发地址。 该GC还存在其他低效之处。在传统的Cheney GC中，目标空间被线性遍历并作为工作列表使用。我们利用目标空间本身来跟踪哪些对象已复制，然后遍历这些对象中的指针来复制其他活跃对象。如果没有这种机制，就需要维护一个单独的工作列表。这可以是一个简单的动态数组作为栈使用。虽非世界末日，但也会带来额外的分配、内存占用和访问等开销。而我实现中最糟糕的部分在于：对象被转发后，我会第二次遍历哈希表，逐一处理已转发的对象，将指向源空间对象的指针替换为指向目标空间副本的指针。然而如前所述，哈希表中指针的存储顺序是准随机的，因此现在我们访问源空间和目标空间的顺序也变得不可预测了。唉。 我想我潜意识里逐渐习惯了"哈希表是高效数据结构"这一假设。基础的计算机科学课程会告诉你，其平均时间复杂度为`O(1)`。它在众多场景下表现出色。但若目标是优化内存使用和缓存友好性以实现最大吞吐量，结果证明它们可能并不合适。我最初说不愿使用转发指针的原因是：我复用同一复制算法在发送消息时复制对象，且不想在过程中覆盖发送方堆中的对象（或对象头）。不过对于这个特定情况，有个简单的解决方案：我们可以维护一个已转发对象的列表，在复制完成后返回来撤销转发指针的写入操作。听起来低效，但实际上，发送给其他Actor的消息在大多数情况下可能并非巨大的对象图，而常规GC用法完全可以跳过此步骤。 此时我决定重写Plush GC，使其简单地遵循传统的Cheney复制算法，并增加一个开关选项，允许我们为消息发送这个特殊场景存储一个撤销列表，以移除转发指针并恢复对象头。这使得百万活跃对象的GC时间直接降至7毫秒，比最初的简单实现快了约16.7倍。这是惊人的性能提升，且远低于我20毫秒的目标。实际上，我有一个示例程序，它能渲染一个包含约2200个多边形的旋转城市景观。由于进行3D向量和矩阵运算并分配大量临时对象，该程序会定期触发GC。对于这个特定程序，GC时间低于1毫秒。 补充一些历史背景：Cheney于1970年发表了一篇论文 (https://dl.acm.org/doi/10.1145/362790.362798) ，阐述了现在被称为Cheney算法的方法。当时他正在Ferranti Atlas 2 (https://en.wikipedia.org/wiki/Atlas_(computer)) 计算机上工作。这是一台20世纪60年代早期的晶体管超级计算机，占据整整一个大房间，使用磁芯存储器，并且令人惊讶的是，它已经有了早期的缓存形式。不过无论缓存效率如何，内存在当时都是宝贵资源，使用转发指针比使用辅助数据结构在内存效率上要高得多。我希望这个结论不会显得太令人扫兴，因为我们似乎又回到了原点：原始的带转发指针的Cheney GC算法更为高效。这再次表明，我们应当尊重前人的智慧及其经典著作。尽管如此，我认为理解是什么使得某样东西高效或低效，以及缓存效率和可预测的内存访问模式能带来多大差异，仍然是有益的。同样重要的是要知道，Rust的`HashMap`是用一个安全陷阱换来了某种程度的性能陷阱。 **典型的Atlas 2安装，源自Ferranti Computer Systems宣传册。** (https://pointersgonewild.com/2026-08-17-speeding-up-the-plush-garbage-collector/atlas2_installation.jpg) 典型的Atlas 2安装，源自Ferranti Computer Systems宣传册。 除了让GC运行更快，我还做了另一项改进，它既消除了Plush的一个限制，又降低了内存使用。此前，我没有实现任何扩大Actor消息分配器的逻辑。这意味着消息大小被限制在硬编码的常量16MB以内。消息分配器像普通GC堆一样使用碰撞指针分配，调整其大小略显棘手：因为如果重新分配后备存储，会使指向队列中消息的指针失效。这意味着只有在队列为空且所有消息已被接收者消费时，才能重新分配后备存储。而这又需要发送者和接收者之间进行协调。如果某个Actor试图发送一条大消息，它需要通知接收者其消息分配器需要扩容，同时所有其他发送者都必须等待。不过有个更简单的解决方案。 有一个很酷的mmap (https://man7.org/linux/man-pages/man2/mmap.2.html) 技巧，我记得是从Alan Wu那里学来的。它已被用于YJIT、我自己的UVM项目以及许多其他运行时系统。你可以使用`mmap`通过`MAP_PRIVATE | MAP_ANONYMOUS`标志和`PROT_NONE`保护属性来预保留一大块连续的虚拟地址空间。这本质上是告诉操作系统不要在此块虚拟地址空间中映射任何其他内存或资源，但该内存没有物理RAM支持，因此不占用RSS（常驻内存集）。之后，你可以使用`mprotect`将这块空间中的页面设置为`PROT_READ | PROT_WRITE`以使其对程序可访问。这为你提供了可读写的零初始化内存，但操作系统直到你实际写入数据时才会将这些页面映射到物理RAM。 需要了解的是，虚拟地址空间非常庞大，目前在macOS和Linux上达到128TB（那是太字节，基于48位寻址），因此初始保留的大小可以非常慷慨。即使是512GB也仅占128TB可用空间的极小部分。这意味着你可以拥有一个等效于C++ `std::vector`或Rust `Vec`的结构，能够随意动态调整大小，但你总能在这个动态大小的向量内部取指针。调整向量大小增加其容量不会使旧指针失效。你甚至可以缩小该向量，将页面归还操作系统，而不改变任何地址。很酷吧？在Plush的上下文中，这意味着发送者可以轻松扩展接收者的消息分配器，而无需与接收者或其他发送者进行任何协调。如果消息分配器增长得过大，接收者稍后可以缩小它，将内存归还操作系统。 **扩展Vec与扩展具有稳定地址的保留区间的对比。** (https://pointersgonewild.com/2026-08-17-speeding-up-the-plush-garbage-collector/address-space.svg) 扩展Vec与扩展具有稳定地址的保留区间的对比。 经过重写的GC和`mmap`技巧，Plush现在拥有一个不仅快得多（推测足以应对需要大量分配的实时游戏），而且内存使用更少的GC。回收过程本身不再使用笨重的哈希表，基础RSS也显著降低。一个没有Actor的简单程序使用9.6MB峰值RSS，启动时间小于10毫秒。一个拥有2000个Actor的简单程序使用224MB峰值RSS，启动时间为0.23秒。表现不错。 关于下一步，我有几个关于如何提升Plush性能或使其更接近“真正”编程语言的想法。一个突出的问题是，Plush使用Rust的标签联合（tagged union）来表示其`Value`类型（也称为“胖值”表示）。这使得代码简洁易读，但考虑对齐后，每个值实际上占用了16字节。大多数动态语言使用标记方案。这会带来一些妥协，但可能大幅减少内存使用。Plush使用的是基于栈的解释器，而基于寄存器的解释器可能快得多。我也在想，让LLM为Plush编写一个简单的即时（JIT）编译器可行性如何。 顺便提一下，你可能想知道我为何为Plush选择复制式GC。也许标记-清除GC实际上会更快。我的动机是复制式GC可以实现非常快速的碰撞分配（对频繁分配的动态语言很棒），并且它们有一个美妙的特性：回收时间与被复制的活跃数据量成正比，而非堆总大小。理论上，相关数据在内存中聚集在一起也带来了缓存优势。可能这些假设是错误的，标记-清除可能更优。如果你好奇并想尝试，我已在Plush仓库 (https://github.com/maximecb/plush) 中添加了`benchmarks/gc_many_objs.psh`和`benchmarks/gc_alloc_speed.psh`。你常用的编程代理可能在30分钟内就能将Plush重构为使用标记-清除GC。如果有人愿意尝试这个实验，我将很想知道结果。只需确保使用`cargo run --release`运行基准测试，并执行`cargo test`确保测试仍然通过。 订阅我的邮件列表并关注本博客： 版权所有 © 2011–2026 Maxime Chevalier-Boisvert。保留所有权利。