如何实现垃圾收集器？
任何人都可以指出我如何实施垃圾收集的好来源？ 我正在做一个类似lisp的解释性语言。 它目前使用引用计数，但当然不能释放循环依赖对象。
我一直在阅读标记和扫描，三色标记，移动和非移动，渐进和停止的世界，但是…我不知道什么是最好的方式来保持整齐的物体分成几组，尽可能减less对象内存开销，或者如何增量执行。
我已经阅读了一些引用计数的语言使用循环参考检测，我可以使用。 我知道我可以像Boehm一样免费使用collections家，但我想学习如何自己做。
我将不胜感激任何在线教材，或者帮助那些没有像我这样的主题经验的人。
任何人都可以指出我如何实施垃圾收集的好来源？
那里有很多关于垃圾收集的高级资料。 垃圾收集手册是伟大的。 但是我发现有一些宝贵的基本介绍信息，所以我写了一些关于它的文章。 原型化标记扫描垃圾收集器描述了用F＃编写的最小标记扫描GC。 非常并发的垃圾收集器描述了一个更高级的并发收集器。 HLVM是我写的一个虚拟机，它包含一个处理线程的“世界停止”收集器。
实现垃圾收集器的最简单的方法是：
-
确保你能整理全球的根源。 这些是包含对堆的引用的本地和全局variables。 对于局部variables，在它们的作用域期间将它们推到一个影子堆栈上。
-
确保可以遍历堆，例如，堆中的每个值都是一个实现了一个
Visit方法的对象，该方法返回该对象的所有引用。 -
保留所有分配的值的集合。
-
通过调用
malloc分配，并将指针插入到所有已分配值的集合中。 -
当所有分配的值的总大小超过配额时，启动标记，然后扫描阶段。 这个recursion遍历堆累积所有可达值的集合。
-
分配的值减去可达值的设置差值是不可达值的集合。 迭代他们
free调用，并从分配的值集中删除它们。 -
将配额设置为所有分配值的总大小的两倍。
看看下面的页面。 它有很多链接。 http://lua-users.org/wiki/GarbageCollection
正如delnan所build议的那样，我从一个非常天真的停止世界的三色标记和扫描algorithm开始。 我设法通过使链表节点保持对象在集合中，但它确实为每个对象（虚拟指针，两个指向节点的指针，一个枚举来保存颜色）添加了大量的数据。 它完美的工作，没有记忆valgrind丢失:)从这里我可能会尝试添加一个免费的回收列表，或某种东西，检测什么时候方便停止世界，或增量的方法，或一个特殊的分配器避免碎片，或别的东西。 如果你能指出我在哪里寻找信息或build议（我不知道你是否可以评论一个回答的问题）如何做这些事情或做什么，我会非常感激。 我将在此期间检查Lua的GC。
我已经在大约400 SLOC中用C语言实现了Cheney式的复制垃圾回收器 。 我做了一个静态types的语言，而令我吃惊的是，更难的部分是实际上传达的信息，哪些是指针，哪些不是。 在dynamictypes语言中，这可能更容易，因为您必须已经使用某种forms的标记scheme。
还有一个关于垃圾收集的标准书的新版本：Jones，Hosking，Moss的“Garbage Collection Handbook：自动内存pipe理的艺术” 。 （亚马逊英国网站说2011年8月19日。）
我还没有看到的一件事就是使用内存句柄。 如果每个对象引用是指向包含所讨论的对象的真实地址的结构的指针，则可以避免在内存上加倍（如Cheney风格的复制algorithm所需要的）。 对内存对象使用句柄会使某些例程变慢一点（在任何时候都可能会发生移动的对象时，必须重新读取对象的内存地址），而对于只能在可预测的时间发生垃圾收集的单线程系统，没有太多问题，也不需要特殊的编译器支持（multithreadingGC系统可能需要编译器生成的元数据，无论它们是使用句柄还是直接指针）。
如果使用句柄，并使用一个链接列表作为活动句柄（可以使用同一个存储器来容纳需要重新分配的死句柄的链表），则可以在为每个句柄标记主logging之后，继续处理句柄列表，按分配顺序，并将该句柄引用的块复制到堆的开头。 由于句柄将按顺序复制，因此不需要使用第二个堆区。 而且，可以通过跟踪一些堆顶指针来支持世代。 当简化记忆时，只需简单地简化自上次GC以来添加的项目。 如果这样不能释放出足够的空间，那么从上一级GC开始就会增加一些物品。 如果这样不能释放出足够的空间，就要压缩一切。 标志阶段可能要作用于所有世代的对象，但昂贵的紧凑阶段不会。
实际上，如果使用基于句柄的方法，如果要标记所有世代的东西，则可以在每个GC上计算每一代中可以释放的空间量。 如果Gen2中的一半物体已经死亡，则可能需要进行Gen2收集，以减lessGen1收集的频率。
阅读内存pipe理：C / C ++中的algorithm和实现 。 这是一个很好的开始。
我正在为我的后记解释器做类似的工作。 更多信息通过我的问题。 我同意德尔南的评论，一个简单的标记扫描algorithm是一个很好的开始。 您将需要为所有容器设置标记，复选标记，清除标记和迭代器的函数。 一个简单的优化就是在分配一个新对象时清除标记，在扫描期间清除标记。 否则在开始设置之前，您需要整个通行证清除标记。
