如何实现垃圾收集器？

谁能给我指出一个关于如何实现垃圾收集的好资料？

那里有很多关于垃圾收集的高级材料。 Garbage Collection Handbook 很棒。但是我发现基本的介绍性信息很少，所以我写了一些关于它的文章。 Prototyping a mark-sweep garbage collector 描述了用 F# 编写的最小标记清除 GC。 Very Concurrent Garbage Collector 描述了更高级的并发收集器。 HLVM 是我编写的一个虚拟机，它包含一个处理线程的停止世界收集器。

实现垃圾收集器的最简单方法是：

确保您可以整理全局根。这些是包含对堆的引用的局部和全局变量。对于局部变量，在其作用域期间将它们推送到影子堆栈。确保您可以遍历堆，例如，堆中的每个值都是一个对象，该对象实现了一个访问方法，该方法返回该对象的所有引用。保留所有分配值的集合。通过调用 malloc 并将指针插入到所有已分配值的集合中进行分配。当所有分配值的总大小超过配额时，开始标记然后扫描阶段。这递归地遍历堆累积所有可达值的集合。分配值减去可达值的集合差就是不可达值的集合。遍历它们调用 free 并将它们从分配的值集中删除。将配额设置为所有已分配值总大小的两倍。

查看以下页面。它有很多链接。 http://lua-users.org/wiki/GarbageCollection

正如 delnan 所建议的，我从一个非常天真的停止世界的三色标记和扫描算法开始。我设法通过使它们成为链表节点来将对象保留在集合中，但它确实为每个对象添加了大量数据（虚拟指针、两个指向节点的指针、一个用于保存颜色的枚举）。它工作得很好，在 valgrind 上不会丢失内存 :) 从这里我可能会尝试添加一个空闲列表以进行回收，或者某种检测何时可以方便地停止世界的东西，或者一种增量方法，或者一个特殊的分配器来避免碎片化或其他。如果您能指出我在哪里可以找到有关如何做这些事情或做什么的信息或建议（我不知道您是否可以对已回答的问题发表评论），我将非常感激。与此同时，我将检查 Lua 的 GC。

我已经在大约 400 SLOC 中用 C 语言实现了一个 Cheney-style copying garbage collector。我是为静态类型语言做的，令我惊讶的是，更难的部分实际上是传达信息哪些是指针，哪些不是。在动态类型语言中，这可能更容易，因为您必须已经使用某种形式的标记方案。

还有一本关于垃圾收集的标准书的新版本即将问世："The Garbage Collection Handbook: The Art of Automatic Memory Management" by Jones, Hosking, Moss。 （亚马逊英国网站称 2011 年 8 月 19 日。）

我还没有看到提到的一件事是内存句柄的使用。如果每个对象引用都是指向包含所讨论对象的真实地址的结构的指针，则可以避免在内存上加倍的需要（正如切尼式复制算法所需要的那样）。对内存对象使用句柄会使某些例程变慢一些（任何时候都必须重新读取一个对象的内存地址，任何时候可能发生的事情会移动它）但是对于垃圾收集只会在可预测的时间发生的单线程系统，这问题不大，也不需要特殊的编译器支持（多线程 GC 系统可能需要编译器生成的元数据，无论它们使用句柄还是直接指针）。

如果使用句柄，并为活动句柄使用一个链表（相同的存储可用于保存需要重新分配的死句柄的链表），则可以在为每个句柄标记主记录后，继续遍历句柄列表，按分配顺序，并将该句柄引用的块复制到堆的开头。因为句柄将按顺序复制，所以不需要使用第二个堆区域。此外，可以通过跟踪一些堆顶指针来支持生成。压缩内存时，首先压缩自上次 GC 后添加的项目。如果这不能释放足够的空间，请压缩自上一次 1 级 GC 以来添加的项目。如果这不能释放足够的空间，请压缩所有内容。标记阶段可能必须作用于所有代的对象，但昂贵的紧缩阶段则不会。

实际上，使用基于句柄的方法，如果要标记所有代的东西，如果需要，可以在每个 GC 上计算传递每一代可以释放的空间量。如果 Gen2 中有一半的对象已经死亡，那么进行 Gen2 收集以减少 Gen1 收集的频率可能是值得的。

Lisp 中的垃圾回收实现

构建 LISP | http://www.lwh.jp/lisp/

阿卡迪亚 | https://github.com/kimtg/arcadia

阅读Memory Management: Algorithms and Implementations in C/C++。这是一个很好的起点。

我正在为我的 postscript 解释器做类似的工作。 more info via my question. 我同意 Delnan 的评论，即简单的标记扫描算法是一个很好的起点。您需要为所有容器设置标记、复选标记、清除标记和迭代器的函数。一个简单的优化是在分配新对象时清除标记，并在扫描期间清除标记；否则，在开始设置标记之前，您需要一个完整的通行证来清除标记。