Zero Sound

Garbage Collection Algorithm

七月 2, 2007 at 8:47 下午 | In Technology, gc |

Quick Taxonomy:

• Reference Counting
• Tracing Collector - traverse live objects
  • Mark-and-Sweep Collectors
  • Copying Collectors
  • Hybrids

Other collector characteristics:

• Conservative Tracing
• Generational Tracing
• Real or Incremental

上面这个大纲基本上概括了目前的主流垃圾收集算法。一般来说，工业产品级的实现，通常是在标记-清扫算法和复制算法的基础上，引入分代式或渐进式（也叫增量式）策略。对像我这样单枪匹马实现语言的人来说，暂时可以把分代式和渐进式仍在一边，先把标记-清扫算法和复制算法弄清楚再说。至于古老的，最通俗易懂容易实现的引用计数，我想已经成为边缘算法了。据说Python用的还是RC，反正Python这么慢，也不差这一点了……

说到垃圾收集，最重要的莫过于性能问题。垃圾收集和人肉回收哪个比较快？标记-清扫算法和复制算法哪个比较好？就算是标记-清扫算法，在这个名下也有许多变种，哪个最好？在下结论之前，不妨先问一问：好的标准是什么？衡量垃圾收集算法的指标在哪里？垃圾收集界老大之一，Hans-J.Bohem做过一个lecture，题为Memory Allocation Myths and Half-Truths，前半部分集中谈内存分配算法，后半部分讲垃圾收集，很值得一读，作为进一步研究前扫除知识垃圾之用，充分凸显了内存管理这一问题的复杂性，让我们养成一种小心谨慎的态度。Bohem的演讲可以概括成一句话：具体问题具体分析，实事求是（这是我党的重要思想，可以应用于世上一切已解决与未解决的问题……）

下面简单的列举一下gc算法需要考虑的几个方面：

• 时间，包括垃圾收集本身的时间，以及内存分配的时间
• 空间，主要是内存的使用量
• 局部性，碎片问题以及缓存性能

上面三点，每一点展开都洋洋洒洒，并且三者相互影响，错综复杂。特别是最后一点,很容易被人忽视但实际上非常重要——也非常难搞。把这些内容全部弄清楚不是像我这样的门外汉力所能及；就算是专家，面对这样复杂的问题也不敢妄言自己都明白了，并且本身这里面还有许多未解决的问题。我的目标，就是学习一下基本的Mark-Sweep Algorithm和Copying Algorithm，并实现一个Garbage Collector来用在我自己的语言上。

阅读(946 次)