理解垃圾回收算法

来自Atomic Object公司的Ken Fox为了解释各种垃圾回收算法,开发了一个小工具,用于对各种垃圾回收算法进行可视化演示。这个工具通过动画的形式展示了垃圾回收算法的执行过程,让人非常直观地了解这些复杂算法背后的原理。这篇文章最早由Ken Fox于2014年9月3号发表在Atomic Spin博客上,以下译文已获得源网站的翻译授权。原文链接“Visualizing Garbage Collection Algorithms”。

自动垃圾回收机制对于大部分开发人员来说已经见惯不怪了,它只不过是语言运行时为了简化我们的工作而提供的一种特性。

如果我们不了解垃圾回收器的原理,在选择垃圾回收器时,就很难做出决定。一个垃圾回收器涉及数百个实现细节,如果不清楚它们的作用和陷阱,就很容易陷入迷茫之中。

我开发了一个好玩的小工具,用于可视化5种垃圾回收算法。这个工具把运行时的垃圾回收行为创建成动画,相关代码可以在github上找到。这些垃圾回收算法可以通过简单的动画来演示,连我自己都感到很惊讶。

在结束时进行清理—无垃圾回收(No GC)

在任务处理结束时一次性清理所有的资源,这是最简单的垃圾清理方式。如果任务可以被拆分成更小的单元,那么使用这种方式来清理垃圾会很有效。举个例子,Apache的Web服务器为每个请求创建了一个小型的内存池,请求被处理完之后,整个内存池会被清理掉。

下面的动画模拟了一个正在运行的程序,画布代表程序的整体内存。黑色表示未被使用的内存,闪烁的绿色表示内存读取,黄色表示内存写入。色块会随着时间衰退,我们不仅可以看到内存是如何被使用的,还能看到当前的活动情况。如果仔细看的话,我们会发现,程序会忽略掉一些内存区域。这些区域变成了垃圾,它们不会再被使用,程序也无法触及到这些区域。

理解垃圾回收算法

这个程序在内存中运行,不需要担心垃圾的清理问题。在下面的其他例子中,我也将使用这个程序作为示例。

引用计数回收器(Reference Counting Collector)

另一个简单的方案是使用计数器,计数器表示资源(内存中的对象)的使用次数,当计数器变成零的时候就可以将该资源销毁。在向已有的系统添加垃圾回收器时,开发人员通常会选择计数回收器,因为这种方式最容易与已有的资源管理器和代码集成在一起。Apple最初在Object-C里使用了标记清理回收器,不过这种回收器给他们带来了很多困扰,后来他们不得不使用计数回收器替代它。而且事实证明,自动计数回收器比之前的标记清理回收器更适合在Object-C中使用。

下面的动画模拟的是之前的那个程序,不过这次是根据内存对象的引用次数来清理垃圾。闪烁的红色表示正在进行引用计数。引用计数的最大好处在于它可以很快地检测出垃圾,从动画中你会发现,有些红色闪过之后的区域立即变成黑色。

理解垃圾回收算法

不过引用计数算法存在很多问题。最大的一个问题是,它无法解决循环引用问题。这种情况很常见,父对象和反向引用会形成引用环,造成内存泄露。除此之外,引用计数需要额外的开销。从动画中可以看到,在内存使用没有增长的情况下,红色区域也一直保持闪烁。虽然现代CPU的运算能力很强,但内存并不快,而计数器的运算需要频繁使用内存。因为计数器需要不断被更新,所以它们不是只读的,而且不能保证线程安全。

引用计数器算法是一种摊销算法(将开销分摊给了程序),不过它是偶然性的摊销,无法保证响应时间。例如,假设程序正在处理一个很大的树结构,最后一个使用这个树的程序会触发销毁操作,根据墨菲定律,其延迟会比期望的要高。不过,这篇文章所演示的其他算法也都不是完全的摊销算法,所以偶然性的摊销完全取决于所处理的数据(这些算法有些是并发的,有些是部分并发的,不过我开发的这个工具无法演示这些特性)。

标记清除回收器(Mark Sweep Collector)

标记清除回收算法解决了一些在引用计数算法中存在的问题。它解决了循环引用问题,而且开销要小得多,因为它不需要维护计数器。

理解垃圾回收算法

不过,它无法立即检测到垃圾。从动画中可以看到,在一小段时间内没有出现红色闪烁,之后又突然出现了很多红色闪烁,说明它正在标记存活的对象。在完成标记之后,所有的垃圾被清除,释放出内存。我们还能从动画中看到,有些区域一下子全部转成黑色,而不是像引用计数算法那样慢慢地随时间扩散开来。

标记清除算法有更高的一致性要求,而且难以将其集成到已有的系统中。在标记阶段,回收器要求遍历所有的存活对象,包括封装在对象里的数据。如果某个对象不支持回收器的遍历访问,那么使用这种回收器就会存在风险。标记清除算法的另一个缺点是,在清除阶段,它会在整个内存范围内进行清除。如果系统的垃圾不多,那么问题不大,但是现代的函数式编程模型总是能产生大量的垃圾。

标记整理回收器(Mark Compact Collector)

你可能会注意到,在之前的动画里,对象不会发生移动。一旦对象分配到了内存,它就会待在原地不动,即使内存出现了很多碎片。后面的两个算法将会改变这种状况,它们使用不同的方式来实现回收。

理解垃圾回收算法

标记整理算法清理内存的方式不是通过清除,而是将对象移动到空余的内存空间。对象总是以不变的次序存留在内存里,先分配到内存的对象总处于较低的内存段,不过因为经过移动,对象间的内存间隙被消除。

也就是说,新创建的对象总是处于内存的高段。这种内存分配器被称为“bump”,类似于栈的分配,只是没有栈那样的大小限制。有些使用bump分配器的系统甚至不用调用栈来存储数据,它们直接在堆里分配调用帧,并把它们看成对象。

从理论上看,这种回收算法的另一个优势在于,程序具有了更好的内存访问模型,这种模型对现代硬件的内存缓存更加友好。不过,相比其他算法,我们很难直观地感受到这种优势,因为引用计数和标记清除算法里所使用的内存分配器虽然很复杂,但它们很健壮,很高效。

标记整理是一种复杂的算法,需要多次遍历所有分配到内存的对象。从动画里我们可以看到,在红色闪烁之后,在计算对象的目标地址时发生了很多读写操作,然后对象被移动到目标地址上,对象的引用也被指向新的地址。这种复杂性所带来的主要好处就是极低的内存开销。Oracle的Hotspot虚拟机使用了多种垃圾回收算法,其中老年代空间使用的是标记整理算法。

复制回收器(Copying Collector)

我要演示的最后一种算法是大部分高性能垃圾回收系统的基础。它有点类似标记整理算法,不过相比之下要简单很多。它把内存分为两个部分,然后在这两个内存空间之间移动对象。在实际应用当中,一般会有多个内存空间,每个空间分配给不同年代的对象。先是在其中一个内存空间创建新对象,如果它们存活下来,就把它们复制到另一个内存空间。最后,如果这些对象的寿命足够长,它们会被复制到老年代空间。如果一个垃圾回收器被贴上分代或者朝生夕灭的标签,那它极有可能是多空间的复制回收器。

除了简单性和灵活性,这种算法的最大优势在于,它只处理存活的对象。这种算法并不存在标记阶段,存活的对象直接被复制到新的地址上,对象引用也随之指向新的地址。

理解垃圾回收算法

从动画中我们可以看到,有些对象集合几乎是整块地被复制到另一个内存空间里,这是比较糟糕的情况,这也就是为什么我们需要对垃圾回收器进行调优。如果我们能够通过调整内存大小和控制内存分配,确保大部分对象在垃圾回收开始之前死亡,那么,我们就得到了函数式编程和高性能的一个完美组合。

相关推荐