如何为C中实现的解释语言提供垃圾收集?

如果我要在C中实现垃圾收集的解释语言,如何在不编写自己的垃圾收集器的情况下提供精确(即不保守)的垃圾收集? 有可用的库吗? 如果是这样,哪些? 我知道我必须在垃圾收集器跟踪的任何对象上维护某些不变量。

如果你想要一个精确的 GC(不是一个保守的GC ,比如Boehm的GC ,它在实践中表现很好),你应该跟踪本地指针(到GC-ed数据)变量,否则只在几乎空的调用堆栈中调用GC。你确定没有这样的局部变量(顺便说一句, GCC编译器有这样一个标记和清除垃圾收集器 – 由一些专门的gengtype C ++代码生成器生成的标记例程; GGC仅传递之间调用)。 当然,您还应该跟踪全局(包括静态或线程本地)指针(到GC-ed数据)变量。

或者,有一些字节码虚拟机(如OCaml或NekoVM ),然后本地GC-ed变量是字节码VM的堆栈和/或寄存器中的变量,并且您可以在VM的特定和精心选择的点触发GC翻译。 (参见Ocaml GC的这个解释 )。

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

如果GC正在复制世代,则需要实现写入障碍(以处理指向新区域的旧数据的突变)。 您可以使用我的旧Qish GC(我不再保留太多),或Ravenbrook的MPS ,或编写您自己的世代复制GC(理论上这并不难,但调试GC在实践中是一场噩梦,所以它是很多工作)。

您可能想要使用一些宏技巧(比如我的Qish)来帮助保留您的局部变量。 请参阅 Ocaml文档的垃圾收集器部分协调一致生活作为示例(或查看Qish内部)。

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

如果您的语言是真正的multithreading(几个并行分配的mutator线程),那么编写GC变得非常棘手。 它可能需要几个月的工作(并且可能是调试的噩梦)。

实际上,我今天建议使用Boehm的GC(注意它是multithreading友好的)。 一个天真的标记和扫描手动编码的GC可能不会比Boehm的GC更快。 并且你将无法(我不建议)使用GGC,GCC内部的垃圾收集器(IMNSHO,它不是很好;多年前它是一个肮脏的黑客设计)。

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

PS。 我还推荐Queinnec的书: Lisp In Small Pieces ; 它有一些关于GC及其与编程语言的连接的有趣材料,当你实现一个解释器时,它是一本很好的书。 斯科特关于编程语言语用学的书也值得一读。

对于C程序,有两个选项:Boehm GC替换malloc (它是一个保守的 GC,所以可能不是你正在寻找的但是它或者……),或者自己编写

但是写自己的并不是那么难。 做标记扫描算法。 用于标记的根集将是您的符号表。 并且你需要另一个表或链表来跟踪所有可以free分配的内存。 当您浏览分配列表时, free任何没有标记的内容。

实际编码当然会更复杂,因为你必须遍历这两种数据结构,但算法本身非常简单。 你能行的。


几年前,我发现自己处于相同的搜索状态,这些结果(和AFAIK仍然是)。 写自己的作品是非常有益的,也是值得的。

在实践中,当Basile的答案触及时,会出现许多其他问题。

如果从调用堆栈的深处调用垃圾收集器(通过可能需要更多内存的分配例程),则必须注意其句柄仍保存在调用堆栈中C函数的局部变量中的任何分配,而不是保存到它们的符号表或数据库位置。 在我的postscript解释器中,我通过使用所有分配器推送到的临时堆栈来解决这个问题。 在所有子程序返回后,主循环清除此堆栈,并在标记期间将其视为根集的一部分。 在我的APL解释器中,我每次都在主循环周围调用GC。 对于小语言的小程序,速度问题不如更可怕的内存泄漏 ,至少在影响我的圈子中。

在实现这种语言时,您的解释器需要跟踪其运行的程序中的所有对象,包括其类型的知识以及数据的哪个部分是对其他数据的引用。 然后,您可以轻松地遍历所有数据并实现您喜欢的任何类型的垃圾收集器。 没有虚假的黑客像试图确定C实现的“堆”/“堆栈”/等。 找到或猜测可能需要什么指针,因为您正在处理您知道其结构的数据。