c - 我如何为用 C 实现的解释语言提供垃圾收集？

Question

如果我要在 C 中实现垃圾收集解释型语言，我如何在不编写自己的垃圾收集器的情况下提供精确(即不保守)的垃圾收集？有图书馆吗？如果有，是哪些？我知道我必须在我这边为垃圾收集器跟踪的任何对象维护某些不变量。

Answer 1

如果你想要一个精确 GC(不是一个保守的 GC，比如 Boehm's GC，它在实践中表现得很好)你应该跟踪本地指针(指向 GC 数据)变量，否则当您确定没有这样的局部变量时，仅使用几乎为空的调用堆栈调用 GC(顺便说一句，GCC 编译器有这样一个 mark&sweep garbage collector - 带有由一些专门的 gengtype 生成的标记例程C++ 代码生成器；GGC 仅在之间 次调用)。当然，您还应该跟踪全局(包括静态或线程本地)指针(指向 GC 数据)变量。

或者，有一些字节码虚拟机(如 OCaml 或 NekoVM)，然后本地 GC-ed 变量是字节码 VM 的堆栈和/或寄存器中的变量，并且您在特定的时间触发 GC并仔细选择您的 VM 解释器的要点。 (参见 Ocaml GC 的 this explanation)。

您应该阅读更多关于 Garbage Collection 的内容技术，参见 GC handbook .

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

您可能想使用一些宏技巧(就像我的 Qish 所做的那样)来帮助保留您的局部变量。查看Living in harmony with the garbage collector Ocaml 文档的一部分作为示例(或查看 Qish 内部)。

请注意，分代复制 GC 在手动编写的 C 代码中处理起来并不友好(因为您需要显式保留本地指针，并且因为您需要写屏障来记住旧值何时被修改为具有指向新一代)。如果你想这样做，你的 C 代码应该在 A-normal form 中。 (你不能编码 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 内部的垃圾收集器(恕我直言，它不是很好；这是很多年前的肮脏 hack 设计)。

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

附言。我还推荐 Queinnec 的书:Lisp In Small Pieces ;它有一些关于 GC 及其与编程语言的联系的有趣 Material ，当您实现解释器时，这是一本非常适合阅读的好书。斯科特关于 Programming Languages Pragmatics 的书也值得一读。