6

我一直在尝试编程语言设计，并且已经到了需要实现垃圾收集系统的地步。现在首先想到的是引用计数，但这不会处理引用循环。我在搜索算法时遇到的大多数页面都是关于在现有语言（例如 Java）中调整垃圾收集器的参考资料。当我确实找到描述特定算法的任何内容时，我没有获得足够的实施细节。例如，大多数描述包括“当您的程序内存不足时...”，这在具有大量交换空间的 4 GB 系统上不太可能很快发生。所以我正在寻找一些具有良好实现细节的教程，例如如何调整何时启动垃圾收集器（即，

为了提供更多关于我正在尝试做的事情的详细信息，我开始编写一个类似于 Postscript 的基于堆栈的解释器，我的下一次尝试可能是基于其中一种 Lisp 方言的 S 表达式语言. 我在直接 C 中实施。我的目标既是自学，又是把各个阶段记录为“如何设计和编写解释器”教程。

至于我到目前为止所做的事情，我已经编写了一个简单的解释器，它实现了一种 C 风格的命令式语言，它被堆栈机器风格的 VM 解析和处理（参见 lang2e.sourceforge.net）。但是这种语言在进入任何函数时不会分配新的内存，也没有任何指针数据类型，所以当时真的不需要任何类型的高级内存管理。对于我的下一个项目，我正在考虑从非指针类型对象（整数、字符串等）的引用计数开始，然后在单独的内存池中跟踪任何指针类型对象（可以生成循环引用） . 然后，每当池比上一个垃圾回收周期结束时增长超过 X 个分配单元时，再次启动收集器。

我的要求是它不能太低效，而且易于实施和清楚地记录（请记住，我想将其发展成论文或书籍供其他人遵循）。我目前在前面得到的算法是三色标记，但看起来世代收集器会更好一些，但更难记录和理解。所以我正在寻找一些清晰的参考材料（最好是在线提供），其中包含足够的实现细节来帮助我入门。

4

2 回答 2

5

There's a great book about garbage collection. It's called Garbage Collection: Algorithms for Automatic Dynamic Memory Management, and it's excellent. I've read it, so I'm not recommending this just because you can find it with Google. Look at it here.

For simple prototyping, use mark-and-sweep or any simple non-generational, non-incremental compacting collector. Incremental collectors are good only if you need to provide for "real-time" response from your system. As long as your system is allowed to lag arbitrarily much at any particular point in time, you don't need an incremental one. Generational collectors reduce average garbage collection overhead with the expense of assuming something about the life cycles of objects.

我已经实现了所有（分代/非分代，增量/非增量）并且调试垃圾收集器非常困难。因为你想专注于你的语言设计，而不是调试一个更复杂的垃圾收集器，你可以坚持一个简单的。我很可能会去标记和扫描。

使用垃圾收集时，不需要引用计数。把它扔掉。

于 2012-05-18T06:01:42.127 回答
1

何时启动分配器可能是完全开放的——您可以在内存分配失败时进行 GC，或者您可以在每次删除引用时进行 GC，或者在中间的任何地方进行 GC。

等到你别无选择可能意味着你永远不会 GC，如果运行的代码被很好地包含的话。或者，它可能会在您的环境中引入巨大的暂停，并完全破坏您的响应时间或动画或声音播放。

对每一个运行完整的 GCfree()可以在更多操作中分摊成本，尽管整个系统可能会因此运行得更慢。你可能更容易预测，但总体上更慢。

如果你想通过人为地限制内存来测试这个东西，你可以简单地在非常严格的资源限制下运行。运行ulimit -v 1024，由该 shell 生成的每个进程将只有 1 兆字节的内存可供使用。

于 2012-05-18T01:39:51.777 回答