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借用检查器的方式上，这是一片未知的领域。它似乎很稳健，但我无法真正确信。

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

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

之前有一个复制收集器（它工作过）511be539228e7142，但我因为它的高内存使用而移除了它。

动机

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

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

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

我们的收集器只在特定的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还没有充分利用泛型关联类型。