如何实现垃圾收集器？ [英] How to implement a garbage collector?

问题描述

任何人都可以指出我是如何实施垃圾收集的一个很好的来源？我正在制作一种类似lisp的解释性语言。

我一直在阅读标记和扫描，三色标记，移动和非移动，增量并停止这个世界，但是......我不知道什么是最好的方式来保持对象整齐地分成集合，同时保持每个对象的内存开销最小化，或者如何增量执行。

我已经阅读了一些使用循环引用检测的引用计数语言，我可以使用它。我知道我可以免费使用像Boehm这样的收藏家，但是我想学习如何自己做。

我会很感激任何带有某种教程的在线材料或帮助没有像我这样的主题经验的人。

解决方案

正如delnan所建议的，我从一个非常天真的停止世界三色标记和扫描算法。我设法通过使对象成为链表节点来保留对象，但它确实为每个对象（虚拟指针，两个指向节点的指针，一个枚举来保存颜色）添加了很多数据。它的工作原理完美，valgrind没有丢失任何内存:)从这里我可以尝试添加一个免费的回收列表，或者某种方式来检测什么时候方便停止世界，或者增量方法，或者一个特殊的分配器避免碎片或其他东西。如果你能指出我在哪里寻找信息或建议（我不知道你是否可以评论一个回答的问题）如何做这些事情或做什么，我会非常感激。我将在此期间检查Lua的GC。

Could anyone point me to a good source on how to implement garbage collection? I am making a lisp-like interpreted language. It currently uses reference counting, but of course that fails at freeing circularly dependent objects.

I've been reading of mark and sweep, tricolor marking, moving and nonmoving, incremental and stop-the-world, but... I don't know what the best way to keep the objects neatly separated into sets while keeping per-object memory overhead at a minimum, or how to do things incrementally.

I've read some languages with reference counting use circular reference detection, which I could use. I am aware I could use freely available collectors like Boehm, but I would like to learn how to do it myself.

I would appreciate any online material with some sort of tutorial or help for people with no experience on the topic like myself.

解决方案

As suggested by delnan, I started with a very naïve stop-the-world tri-color mark and sweep algorithm. I managed to keep the objects in the sets by making them linked-list nodes, but it does add a lot of data to each object (the virtual pointer, two pointers to nodes, one enum to hold the color). It works perfectly, no memory lost on valgrind :) From here I might try to add a free list for recycling, or some sort of thing that detects when it is convenient to stop the world, or an incremental approach, or a special allocator to avoid fragmentation, or something else. If you can point me where to find info or advice (I don't know whether you can comment on an answered question) on how to do these things or what to do, I'd be very thankful. I'll be checking Lua's GC in the meantime.

这篇关于如何实现垃圾收集器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！