ZeroGc

[WIP] 为 Rust 提供零开销的跟踪垃圾收集。

特性

1. 由于 Gc<T> 是 Copy 并强制转换为引用，因此易于使用。
2. 由于 Gc<T> 是 Copy，因此在修改指针时绝对没有开销。
3. 实现无关的 API
4. 不安全代码可以自由操作垃圾收集指针，而不需要了解这些区别。
5. 使用 Rust 的生命周期系统来确保在显式安全点时所有根都是已知的，而不产生任何运行时开销。
6. 只有在显式 safepoint 调用时才能进行收集，这些调用之间没有开销。
7. API 支持移动对象（允许复制/代际 GC）

它不要求编译器支持跟踪 GC 根（如 Java/Go），而是使用影子堆栈来跟踪 GC 根。收集只能在显式安全点发生。

它使用 Rust 的生命周期系统来确保在收集后不会访问已释放的垃圾。分配的对象与垃圾收集器的生命周期相关联。安全点（潜在的收集）被借用检查器视为突变。在没有 zerogc（使用 Vec 或 typed-arena）的情况下，这会使所有先前分配的指针无效。然而，任何给安全点的 '根' 都会重新绑定到新的生命周期（通过黑暗魔法）。

此 API 旨在实现无关性，仅定义了 Trace 特性和安全点的接口。

目前唯一的实现是 zerogc-simple，它是一个基本的标记-清除收集器。它相对快速且轻量，因此是一个良好的默认选项。它使用快速区域分配来处理小对象（可选，默认开启）并回退到系统分配器来处理其他所有对象。

尽管标记/清除收集器很简单，但它的速度相当快，并且能够与Go/Java等生产级别的收集器竞争。

该库大部分没有文档，因为我认为它在未来会有很大的变化。请参见二叉树示例，以获取一个基本样本。

状态

这非常实验性。它在使用Rust借用检查器的方面是未知的领域。它似乎很可靠，但我没有真正知道如何确定。

简单的标记/清除收集器通过了基本测试，但它仍然依赖于大量内部的不安全代码。

我最终计划在语言虚拟机中使用它，因此它需要非常灵活！我希望通过相同的API支持简单和复杂的收集器。

之前有一个复制收集器（它工作过）511be539228e7142，但由于内存使用量高，我将其删除。

动机

我最初受到rust gc的启发，想要创建一个垃圾回收的安全抽象，但我希望它具有零运行时开销和指向Copy的指针。

rust-gc解决的主要问题是找到垃圾回收的“根”。它的收集器使用运行时跟踪来维护每个GC对象的引用。

我对一些JIT实现很熟悉，我知道它们倾向于使用safepoints来显式控制垃圾回收可以发生的地方。这通常是一个不安全操作。栈上的所有活动引用都必须在栈上给出或在栈后使用。最终我意识到，我可以使用借用检查器来限制safepoints周围根的使用。我部分受到indexing使用生命周期来强制执行索引有效性的启发。

我们的收集器只在特定的safepoints处具有运行时开销，即当影子栈被更新时。

这不仅比跟踪每个单独指针的运行时跟踪或保守收集更快，而且更加灵活。它为任何组合的代、增量复制垃圾收集铺平了道路。

现有技术

自从最初的rust gc以来，其他人已经尝试过创建零开销收集器。我开始这个项目时并不知道这一点。

1. shifgrethor

• 这非常令人印象深刻。它似乎是唯一另一个使Gc: Copy并强制转换为引用的收集器。
• 然而，这些收集器必须支持根的固定（我们不支持）
• 请参阅博客系列了解更多信息

2. cell-gc

• 不幸的是，它有一个相当笨拙的Rust代码接口，所以它不合适。
• 他们实现了一个基本的List VM作为概念验证。

3. gc-arena

• 似乎是一个类似的想法，稍后实现。
• 通过使用类似未来的API来处理生命周期的尴尬。
• 与我们的收集器一样，safepoints是由用户显式请求的
• 然而，他们不是尝试重新绑定生命周期，而是尝试使用未来构建状态机

缺点

1. 垃圾收集器只能在显式的safepoint!响应下运行，而不是内存压力
   • 这是一个基本的设计限制。
   • 人们可以将其视为一个特性，因为垃圾回收可以限制在特定的时间和地点。
   • 用户必须对插入safepoint持开放态度。
     • 通常，使用GC的高级语言会自动插入对safepoint的调用。
     • 它们的safepoint通常比我们的开销更低，因此需要权衡成本和收益。
2. 为类型实现GcSafe会阻止它有显式的Drop实现。
   • 这是为了确保析构函数不会做坏事，因为我们不想处理终结器。
   • 当然，不安全的代码不受此限制，因为假设它会表现得很好（如果你知道你很安全，可以退出）。

实现缺陷

这些都不是基本的设计缺陷。它们都可以修复（应该修复）。

1. 目前，无法从使用safepoint的方法返回垃圾回收类型。
   • 这不是设计的根本限制。我计划修复API以支持这一点。
   • 不幸的是，这对许多用例来说几乎是致命的，但可以使用'unchecked_safepoint'来规避。
2. 目前，无法在垃圾回收代码中使用短生命周期。
   • 这是因为Gc<'gc, T>目前要求T: 'gc
   • 放松这个限制是可能的，但可能会使使用变得更困难...
3. 对可能别名化的GC内存向量借用有限制
   • 由于可能共享的gc内存，很难强制执行Rust的可变性规则（参见问题#30）
4. 实现（目前）不是代际的
5. 由于API尚未充分利用泛型关联类型，从泛型上下文中使用很尴尬。