各种编程语言的实现都采用了哪些垃圾回收算法?这些算法都有哪些优点和缺点?

关注者
1203
被浏览
46380

20 个回答

垃圾收集算法是个很大的话题。首先要明确的是,垃圾收集算法和语言不一定是绑定的。比如 Java,不同的 JVM 实现可能采用不同的算法。其次,垃圾收集算法数量庞大,一一列举是不可能的,篇幅所限这里只能给个非常概略的介绍。如果希望对垃圾收集相关算法有个全景式的了解,请参阅本人的译作,垃圾收集 (豆瓣)

==== 转入正文的分割线 ====

从各种垃圾收集算法最基本的运行方式来说,大概可以分成三个类型:

1. 引用计数(reference counting):

基本思路是为每个对象加一个计数器,记录指向这个对象的引用数量。每次有一个新的引用指向这个对象,计数器加一;反之每次有一个指向这个对象引用被置空或者指向其他对象,计数器减一。当计数器变为 0 的时候,自动删除这个对象。

引用计数的优点是 1)相对简单,不需要太多运行时(run-time)的支持,可以在原生不支持 GC 的语言里实现。2)对象会在成为垃圾的瞬间被释放,不会给正常程序的执行带来额外中断。它的死穴是循环引用,对象 A 包含一个引用指向对象 B ,同时对象 B 包含一个引用指向对象 A,计数器就抓瞎了。另外,引用计数对正常程序的执行性能有影响(每次引用赋值都要改计数器),特别是在多线程环境下(改计数器要加锁同步)。

现在仍然主要采用引用计数的例子有 Apple 的 ARC,C++ 新标准里的 std::shared_ptr。

2. 标记-清扫(mark-sweep)。

基本思路是先按需分配,等到没有空闲内存的时候从寄存器和程序栈上的引用出发,遍历以对象为节点、以引用为边构成的图,把所有可以访问到的对象打上标记,然后清扫一遍内存空间,把所有没标记的对象释放。

标记-清扫没有无法处理循环引用的问题,不触发 GC 时也不影响正常程序的执行性能。但它的问题是当内存耗尽触发 GC 时,需要中断正常程序一段时间来清扫内存,在内存大对象多的时候这个中断可能很长。

采用或者部分采用标记-清扫的例子非常多,不一一列举了。

3. 节点复制(copying)。

基本思路是把整个内存空间一分为二,不妨记为 A 和 B。所有对象的内存在 A 中分配,当 A 塞满的时候,同样从寄存器和程序栈上的引用出发,遍历以对象为节点、以引用为边构成的图,把所有可以访问到的对象复制到 B 去,然后对调 A 和 B 的角色。

相对于标记-清扫,节点复制的主要缺点是总有一半空间空闲着无法利用,另一个比较隐晦的缺点是它使用内存的方式与现有的内存换页、Cache 换入换出机制有潜在的冲突。但它有个很大的优点: 所有的对象在内存中永远都是紧密排列的,所以分配内存的任务变得极为简单,只要移动一个指针即可。对于内存分配频繁的环境来说,性能优势相当大。另外,由于不需要清扫整个内存空间,所以如果内存中存活对象很少而垃圾对象很多的话(有些语言有这个倾向),触发 GC 造成的中断会小于标记-清扫。

同样的,采用或者部分采用节点复制的例子也非常多,不一一列举了。

==== 基本算法介绍完毕的分割线 ====

以上三种基本算法各有优缺点,也各有许多改进的方案。目前工程实践上最为成功的方案应该要算分代(generational)垃圾收集。它的基本思路是这样的:程序中存在大量的临时对象,分配出来之后很快就会被释放,而同时如果一个对象分配出来之后相当长的一段时间内都没回收,那么极有可能它的生命周期很长,尝试收集它会是无用功。所以可以把内存有意识地按“对象年龄”分成若干块,不妨记为老中青(XD),所有的分配都在青代进行,青代塞满只对青代做 GC,然后把存活下来的对象移动到中代,直到中青代都塞满,再把存活下来下来的对象移动到老代 —— 这只是个思路上的例子,实践中分代式垃圾收集算法的方案五花八门,而且常常同时使用了不止一种基本算法(比如青代用节点复制,老代用标记清扫啥的)。
最近在看mruby的GC,传统的三色收集,有趣的地方是提供了一个分代模式,基本上完全重用三色收集的基础设施没加几行代码。

(貌似从lua山寨来的?

三色收集来自dijistra的三色图遍历算法,将GC的mark与sweep均摊到多次渐进片段中,虽然简单,但其可贵之处在于能够确保正确性。然而将一个GC周期拉得较长,内存消耗会多一些。

分代收集是历史经验选择出来的优生品,可以视为最经考验的GC算法。"老的对象活得更长,新的对象死的快" 是基本思想,将老的对象移动到记忆集里,每一轮minor GC只mark-sweep新对象,一轮minor GC之后存活得对象就被当成老对象,慢慢得老对象会遗留得越来越多,超过某一阙值之后会触发依次major GC,这时摘掉所有老对象的免死金牌,搞一轮大清理。相对三色GC和传统GC的好处是GC周期缩短,内存消耗少一点。优化的实现会复杂一些?(也可以反过来说优化的空间更大)

mruby三色GC中分代模式的实现就是,黑色对象=老对象,mark阶段不标记它。到触发老对象的数量的阙值时,把所有黑对象再变回白色跑一轮完整GC。

三色GC与分代GC都需要维护一个write barrier(跟乱序执行那个内存栅栏完全是无关的两码事),当黑色对象(或者老对象)有添加新对象的引用时,GC必须对此有所处理。对于扩展的开发者而言,这是一个需要小心注意的地方。

lua和mruby都需要维护对象的引用关系,属于严格式GC。cruby与之相对,采用了保守式GC,传统的mark-sweep。好处是不需要write barrier,C结构体里直接引用ruby对象,提高了C扩展开发者的生活质量,不然现在绝对不会有这么多好用的gem。缺点搞过rails的同学都懂的,而且给gc的设计者挂了个大脚镣,以后优化起来得想更多办法吧。

原则上保守式GC可以为C/C++提供垃圾收集的支持。按指针的宽度遍历栈,调用 is_point_to_heap() 猜这条指针是否指向堆(就一个简单的判断看看这个值是不是在堆的地址的范围之内),如果有个数值恰好跟堆里的指针的值一样,那么只能将哪个位置的对象mark掉了。如果碰巧这个对象是一大堆对象的根,那么恭喜,内存会很吃亏了。

boehm对于这种情况有所研究,出了一个算法可以减少这种误判(书上看的,详细不知道了)。它就只暴露了malloc()和free()两个接口,C程序员可以很轻松利用它到现有项目中。为了捕获write barrier同时不引入额外的接口,印象中它严重地依赖写保护和页面错误。

cruby和mruby的堆是个偷懒的实现,维护两个堆,一个对象堆,一个系统堆。ruby的所有对象的大小都相同,使得对象堆看起来有点像slab。以字符串对象为例,它会保存字符串的长度,和一个指向系统堆的字符串内容的指针,系统堆中的字符串的内容的生命周期与对象堆中的字符串对象保持一致。

ree与cruby2.0的gc对于写时复制友好下了很大功夫,可以说这个特性这跟ruby的应用场景息息相关。在web服务器中,fork一个进程的实例之后,如果跑一轮GC,就会写遍所有对象,堆里所有的写保护的页面都会失效,不得不触发写时复制,吃掉 (进程数*堆大小) 的物理内存。nari和matz的方案是移除对象中的标记位,统一挪到堆的头部搞成一个bitmap。这样在mark阶段,所有的写都会集中到这个bitmap上,原则上只会触发少数几次写时复制,可以省不少内存。
为什么?