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启发，想要为垃圾回收创建一个安全抽象，但我希望它具有零运行时开销和可以复制的指针。

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

我对一些JIT实现很熟悉，我知道它们倾向于使用安全点来显式控制垃圾回收可以发生的地方。这通常是一个不安全操作。栈上的所有活动引用都必须在栈上给出或使用后。

我们的收集器只在特定的安全点具有运行时开销，即当阴影栈正在更新时。

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

现有技术

自从原始的rust gc以来，其他人尝试过制作零开销收集器。我开始这个项目时并不知情。

1. shifgrethor

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

2. cell-gc

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

3. gc-arena

• 看起来是一个类似的想法，但稍后实现。
• 通过使用类似future的API来解决生命周期的尴尬。
• 与我们的收集器一样，用户必须显式请求安全点
• 然而，他们不是尝试重新绑定生命周期，而是尝试使用future来构建状态机

缺点

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

实现缺陷

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

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