一个简单的垃圾回收算法，适合用于简单解释器的实验？

Question

我一直在尝试编程语言设计，并且现在需要实现一个垃圾回收系统。首先想到的是引用计数，但这无法处理引用循环。大多数搜索算法的页面都是关于调整现有语言中垃圾收集器的参考资料，例如Java。当我找到描述特定算法的内容时，通常没有足够的实现细节。例如，大多数描述包括“当程序内存不足时……”，这在具有充足交换空间的4 GB系统上不太可能发生。因此，我正在寻找一些教程，其中包含良好的实现细节，例如如何调整何时启动垃圾收集器（即在X个内存分配之后进行收集，或每Y分钟进行一次等）。

为了更详细地说明我正在尝试做什么，我开始编写类似于Postscript的基于堆栈的解释器，并且我的下一个尝试可能是基于Lisp方言之一的S表达式语言。我使用纯C进行实现。我的目标是自我学习，并记录各个阶段成为“如何设计和编写解释器”的教程。

至于我迄今为止所做的事情，我编写了一个简单的解释器，它实现了类似于C的命令式语言，该语言通过堆栈机器样式的虚拟机进行解析和处理（请参见lang2e.sourceforge.net）。但是，该语言在进入任何函数时不会分配新内存，并且没有任何指针数据类型，因此当时没有需要进行任何类型的高级内存管理。对于我的下一个项目，我考虑为非指针类型对象（整数、字符串等）使用引用计数，然后在单独的内存池中跟踪任何指针类型对象（可能会生成循环引用）。然后，每当池增长超过上一个垃圾回收周期结束时的X个分配单位时，再次启动收集器。

我的要求是它不要太低效，但易于实现并清晰地记录（请记住，我想将其开发成为供他人遵循的论文或书籍）。我目前正在使用三色标记算法，但似乎分代收集器会更好一些，但难以理解和记录。因此，我正在寻找一些清晰的参考资料（最好在线可用），其中包含足够的实现细节，以便让我入门。

- Derek Pressnall

---

我应该补充一下，我看过几个垃圾收集器的描述，比如标记和清除的变体，但我遇到的大多数页面都不比维基百科文章好多少。例如，正如我在问题中提到的那样，它们说当内存不足时就启动垃圾收集器。在现代系统上，在大多数轻量级脚本运行期间，这不太可能发生，即使发生了，使用完所有系统内存再启动收集器也不是一个好主意。我正在寻找的就是这样的细节。 - Derek Pressnall

http://doc.cat-v.org/inferno/concurrent_gc/ - 这里提供了足够实现它的详细信息。 - SK-logic

如果你正在运行一个轻量级脚本，那么最好不要运行GC，因为它只会浪费时间。当进程退出时，内存将被释放。 - Marcin

Answer 1

有一本关于垃圾回收的好书叫做《Garbage Collection: Algorithms for Automatic Dynamic Memory Management》，非常优秀。我已经阅读过，所以我推荐这本书并不仅仅是因为你可以在Google上找到它。在这里查看。

对于简单的原型制作，使用标记-清除或任何简单的非分代、非增量压缩收集器即可。增量收集器只有在需要从系统提供实时响应时才有效。只要您的系统在任何特定时间点上允许任意滞后，就不需要增量收集器。分代收集器通过假设对象的生命周期来减少平均垃圾回收开销。

我已经实现了所有（分代/非分代、增量/非增量）的垃圾收集器，调试起来非常困难。因为您想专注于语言设计，而可能不太想专注于调试更复杂的垃圾收集器，所以您可以坚持使用简单的垃圾收集器。我可能会选择标记-清除。

当您使用垃圾收集时，您不需要引用计数。将其丢弃。

- Antti Huima

---

关于放弃引用计数，会有许多高度瞬态的对象，大多数是暂时在堆栈上的 - 例如“2 * 3 + 5”（或以RPN顺序，“2 3 * 5 +”将在堆栈上留下“6”，直到添加运算符消耗它）。仅使用标记和扫描，似乎垃圾回收会经常启动。但这仍然比引用计数的开销更有效吗？还是我应该为这些临时对象查找另一个优化？谢谢。 - Derek Pressnall

如果您可以尽可能少地进行垃圾回收，那么垃圾回收比引用计数更快。事实上，如果您有足够的额外堆空间，垃圾回收甚至比显式内存管理（例如new/delete或malloc/free）更快。引用计数还会消耗额外的内存，因为您需要存储引用计数字段本身。请注意，通常情况下，您根本不会分配整数，而是会将它们就地表示为指向GC'd对象的指针的位置。 - Antti Huima

@DerekPressnall，如果你期望的是函数式语言典型的GC负载，那么最好采用停止-复制（它将清除所有短暂的临时内容）和标记-清除来处理堆中的其余部分。 - SK-logic

@antti.huima，我是在提到他的评论（“将会有很多高度短暂的对象，主要是那些暂时存在于堆栈上的对象”）- 这基本上是与函数式编程语言相同类型的负载，因此可能可以采用相同的方法。 - SK-logic

@SK-logic 当然可以，但仅适用于大数字。在32位架构上，您可以轻松地存储30位数字，只需保留两个最高位（例如）以区分堆指针和数字，并用于GC标记。 - Antti Huima

Answer 2

何时启动分配器可能是非常开放的 - 您可以在内存分配失败时进行垃圾回收，或者每次引用被删除时进行垃圾回收，或者在中间任何位置进行垃圾回收。

如果等到没有选择余地，可能意味着您永远不会进行垃圾回收，如果运行代码相当好，那么它可能会在您的环境中引入巨大的暂停，并完全破坏您的响应时间、动画或声音播放。

在每个free()上运行完整的GC可以将成本分摊到更多操作中，尽管整个系统可能会因此运行得更慢。您可以更可预测，但总体速度较慢。

如果您想通过人为限制内存来测试该功能，则可以简单地使用非常严格的资源限制运行。运行ulimit -v 1024，由该shell生成的每个进程只能使用一兆字节的内存。

- sarnold