如何为用 C 实现的解释型语言提供垃圾回收？

Question

如果我要在 C 中实现垃圾收集解释语言，我怎样才能在不编写自己的垃圾收集器的情况下提供精确的（即非保守的）垃圾收集？有可用的库吗？如果有，是哪些？我知道我必须为垃圾收集器跟踪的任何对象维护某些不变量。

Answer 1

如果您想要一个精确的GC（不是保守的 GC，如Boehm 的 GC，它在实践中表现得很好），您应该跟踪本地指针（指向 GC 数据）变量，或者仅在以下情况下使用几乎为空的调用堆栈来调用 GC：你确定不存在这样的局部变量（顺便说一句，GCC编译器有这样一个标记和清除垃圾收集器- 带有由一些专门的 C++ 代码生成器生成的标记例程；GGC 仅在传递之间gengtype调用）。当然，您还应该跟踪全局（包括静态或线程本地）指针（指向 GC 数据）变量。

或者，拥有一些字节码虚拟机（如OCaml或NekoVM），然后本地 GC 变量是字节码 VM 的堆栈和/或寄存器中的变量，并且您可以在 VM 的特定且精心选择的点触发 GC口译员。（看这个解释）。

您应该阅读有关垃圾收集技术的更多信息，请参阅GC 手册。

如果您的 GC 是分代复制，则需要实现写屏障（以处理指向新区域的旧数据的突变）。你可以使用我的旧Qish GC（我不再维护它了），或者Ravenbrook的MPS，或者编写你自己的分代复制GC（这在理论上并不难，但是调试GC在实践中是一场噩梦，所以它是很多工作）。

您可能想使用一些宏技巧（就像我的 Qish 所做的那样）来帮助保留局部变量。请参阅Ocaml 文档的与垃圾收集器和谐相处部分作为示例（或查看 Qish 内部）。

请注意，分代复制 GC 在手动编写的 C 代码中处理起来并不友好（因为您需要显式保留本地指针，并且因为您需要一个写屏障来记住何时修改旧值以拥有指向新一代的指针） 。如果你想这样做，你的 C 代码应该是A 范式（你不能编码x=f(g(y),z);，但你需要编码temp=g(y); x=f(temp,z);并添加temp为局部变量，假设 , x,y是z局部 GC 变量，并且 和f返回g一个 GC -ed 指针）。实际上，生成 C 代码要容易得多。请参阅我的MELT域特定语言（用于扩展和自定义GCC）作为示例。

如果您的语言是真正的多线程（多个变异线程并行分配），那么编写 GC 就会变得相当棘手。这可能需要几个月的工作（并且调试可能是一场噩梦）。

实际上，我今天推荐使用 Boehm 的 GC（注意它是多线程友好的）。一个简单的标记和清除手工编码的 GC 可能不会比 Boehm 的 GC 更快。而且你将无法（而且我不推荐）使用 GGC，GCC 内部的垃圾收集器（恕我直言，它不是很好；这是很多年前的肮脏黑客设计）。

顺便说一句，您可能会考虑使用MELT自定义-eg - GCC 编译器（通过添加一些特定于应用程序的 或）来帮助您的 GC。通过一些工作，您可以生成一些标记例程等。但是，这种方法可能会非常痛苦（我真的不知道）。请注意，MELT（免费软件，GPLv3+）包含一个复制分代 GC，其老一代是 GGC 堆，因此您至少可以查看以下代码__attribute__#pragmamelt-runtime.cc

附言。我还推荐 Queinnec 的书：Lisp In Small Pieces；它有一些关于 GC 及其与编程语言的联系的有趣材料，当您实现解释器时，这是一本值得阅读的好书。Scott 的《编程语言语用学》一书也值得一读。