Python和Ruby 的分代垃圾回收机制

上周我根据上半年在 RuPy 中演讲的内容写了一篇笔记，主题为“Ruby 与 Python 的可视化垃圾回收”（译者注：本文写于 2013 年 10月）。我解释了标准 Ruby（又称为 MRI）是如何使用一套名为标记和清扫的垃圾回收算法，这套算法的核心与 1960 年 Lisp 的原始版本所使用的相似。同时，我们也了解到 Python 是怎样使用另外一套在53年前被发明，称为 引用计数的垃圾回收算法。然而，除了引用计数，Python 还使用了另一种叫做分代垃圾回收的算法。这意味着 Python 的垃圾回收器对新创建的对象和旧的对象的处理会有所不同。随着 2.1 发布版本的到来，MRI Ruby 也将优先使用分代垃圾回收算法。（另外两个 Ruby 的实现版本，JRuby 和 Rubinius 已经使用了分代垃圾回收很长时间了。我将在下周的 RubyConf 谈一下 JRuby 和 Rubinius 的垃圾回收机制）

当然，“对新创建的对象和旧的对象的处理会有所不同”有点让人难以理解。究竟什么是新对象，什么是旧对象？实际上 Ruby 和 Python 是怎么分别处理它们的呢？今天我将继续讲述这两种垃圾回收器的工作原理和回答这些问题。在我们讲述分代垃圾回收前，我们需要学习一些关于 Python 引用计数算计的理论问题。

Python 的循环引用数据结构和引用计数

我们目前已经知道 Python 使用一个整数为每个对象记录其被引用的数目，并保存在对象里面，这被称为 引用计数。在你的程序里，当一个变量或其它对象引用一个对象时，Python 会增加这个计数；当你的程序停止使用这个对象时，Python 就会减小这个计数。当引用数量变为零时，Python 会析构这个对象并回收它占用的内存。

自1960年代起，计算机科学家们就意识到这个算法存在一些理论上的问题：当一个数据结构是一个循环引用的结构，即自己引用了自己，它们的引用计数是永远不会变为零的。为了更好地了解这个问题，我们来看个例子。下面的代码使用了一个 Node 类：

我们有个构造器（这在 Python 里称为init方法）把一个值保存到一个实例属性里。然后我们创建了两个 Node，“ABC” 和 “DEF”，我在左边用矩形表示它们。在矩形里的数字 1 是它们的引用计数，因为它们分别被变量 n1、n2 引用了。

现在我们为它们俩增加一个额外的属性，next 和 prev：

不像 Ruby，Python 可以让你自由地定义实例变量或对象属性。这些有趣的魔法是 Ruby 所缺少的。（声明：本人并非使用 Python 的开发者，所以我使用的术语和命名可能存在错误）我们设置 n1.next 引用 n2，n2.prev 指向回 n1。现在我们的两个 Node 通过使用循环指针变成了一个双向链表。需要注意的是，这时它们的引用计数被加到 2。因为有两个地方引用到它们：之前有 n1 和 n2，现在多了 next 和 prev。

现在我们假设我们的 Python 程序停止使用这些 Node；我们把 n1 和 n2 都设为 null。（在 Python 的 null 是用 None 来表示）

现在 Python 像往常一样，把它们的引用计数降到了 1。

Python 的零世代

注意上面的最后的图例，里面有个不寻常的情况：我们有很多不再使用但相互引用的对象，它们是已经没有任何外部引用的。换句话说，我们的程序已经不需要再使用上面的 Node 对象了，因此我们希望 Python 的垃圾回收器可以智能地把它们析构并回收它们占用的内存。但这并不会发生，因为它俩的引用计数是 1 而不是 0。Python 的引用计数机制无法处理这些互相引用的对象。

当然，像这样的情况并不常见，但万一你的程序出现循环引用的情况在一些很微妙的位置里，你是很难发现到的。在你的 Python 程序执行的过程中，它会产生不少的“漂浮垃圾”，那些不再使用但引用计数无法变为 0 而导致 Python 的回收器无法处理的对象。

这就是 Python 分代算法出现的原因！类似 Ruby 使用一个链表去持续地跟踪空闲对象的方法，Python 使用了不同的链表去跟踪处于活动状态的对象。Python 在它的 C 源码中称它为 零世代，而不是称为活动列表。每当你在程序中创建一个对象或者其它的值，Python 会把它添加到零世代链表中：

上面你可以看到我们创建的 ABC，Python 把它添加到零世代里。注意，这并不是一个你可以在程序里看到或者接触到的真实的列表；这个链表存在于 Python 的执行环境内部。

同样地，当我们创建 DEF 时，Python 也把它添加到相同的链表：

现在零世代里包含两个 Node 对象。（其实它会包含每个我们使用 Python 代码创建的值，和 Python 内部使用的值）

循环引用检测

Python 会循环遍历零世代链表，每个被遍历到的对象都会递减它的引用计数。通过这种方式，Python 解除了从一个对象到另一个对象的内部引用，使得 Python 能及早地释放对象。

为了更简单地理解，我们来举个例子：

你可以在从上面看到 ABC 和 DEF 的引用计数都是 1。还有其它三个对象也在零世代链表里。蓝色箭头表示有其它的对象在引用着它们，这些对象处于另外一个地方 —— 来自零世代以外的地方。（我们等下将会看到 Python 也使用了称为 一世代 和 二世代 的链表。）因为有来自其他的引用，这些被引用的对象有着更高的引用计数。

下面你能看到在 Python 垃圾回收器处理零世代后发生的事情。

通过识别内部引用，Python 能够减少零世代里所有对象的引用计数。在上图的第一行，你能看到 ABC 和 DEF 现在的引用计数已经为 0。这意味着回收器将析构它们并回收内存。那些仍然存活的对象将转移至一个新的链表：一世代。

某种程度上来说，Python 的垃圾回收算法类似 Ruby 所使用标记和清扫算法。它定期跟踪对象与其它对象的引用，决定这些对象是否可以保留，存活的对象是我们的程序仍在使用的——就像 Ruby 的标记处理。

Python 垃圾回收器的阈值

Python 是什么时候进行这个标记操作的呢？在你的 Python 程序执行的过程中，解释器会一直跟踪有多少个新对象被创建，多少个对象因为引用计数为 0 而被它释放。理论上，这两个值应该始终一致：每个由你的程序创建的都应该从根本上被释放。

当然，现实并不是这样子。由于循环引用和程序中部分长期使用的对象的存在，构建和被释放的数字差距将被慢慢拉开。当这个差值达到一个阈值，Python 的回收器就会被触发并使用减法处理零世代链表里的对象，释放那些“漂浮的垃圾”和转移剩余的对象到一世代。

随着时间的推移，你的 Python 程序中被长时间使用的对象会被从零世代转移至一世代。Python 当构建和被释放的差值达到一个更高的阈值时，使用同样的方式处理一世代里的对象。Python 把剩下的对象转移到二世代链表。

某种程度上，Python 程序中长时间被使用的对象将从零世代转移到一世代再到二世代。使用不用的阈值来决定 Python 处理这些对象的间隔。Python 会频繁的处理零世代里的对象，一世代会相对没那么频繁，二世代则更久才执行一次。

弱世代假设

这种行为是分代垃圾回收算法的难点：相对新对象，回收器会更频繁处理旧对象。一个新的或年轻的对象是程序中刚创建的，而旧的或成熟的对象是已经存活了一段时间的。Python 会升级对象，当它从零世代转移至一世代，或者从一世代转移至二世代。

为什么要这样做？这个算法的关键思路源于弱世代假设。这个假设实际由这个思路组成：大部分的新对象要在年轻时死掉，而旧对象可能将存活一段更长的时间。

假设我使用 Python 或者 Ruby 创建了一个对象：

根据假设，我的代码可能只在短时间内使用 ABC。对象可能只是为了作为一个函数的参数值，而当函数返回时就会成为垃圾。大部分的对象都是这样很快地变成垃圾。偶尔地，我的程序创建少量且重要的对象并长时间使用 —— 例如 Web 应用中 session 变量或配置项里的值。

Python 的回收器花更多的时间，更频繁的处理新对象是有很大的好处：它使得短寿命的新对象能够更快更迅速地变成垃圾。极少情况下，当构建阈值上升到一定程度，使得 Python 的回收器去处理旧对象。

回到 Ruby 的空闲对象链表

随着 Ruby 发布版本 2.1 的到来，现在 Ruby 也在第一时间使用分代垃圾回收算法进行垃圾回收！（记住，像 JRuby 和 Rubinius 这些其它的 Ruby 实现，已经使用这种方式好多年了。）为了了解它是如何运作的，让我们回顾一下我上一篇文章中空闲对像链表的示例图：

通过这个示例图，我们看到有三个分别被 n1、n2 和 n3 引用的活跃对象。这些剩下的白色方块代表垃圾对象。（当然，空闲对象链表使用了更复杂的模式来包含成千上万的互相引用的对象。这个简单的示例图是为了帮助我们更好理解 Ruby 垃圾回收算法的基础原理，而不被具体的实现所干扰。）

Ruby 会把垃圾对象放置到空闲对象链表，当它需要构建新对象时就可以循环利用这些垃圾对象了。

Ruby 2.1 的分代垃圾收回

从 Ruby 2.1 开始，垃圾回收增加了一个步骤：它会升级剩下的活跃对象到成熟世代。（MRI C 源码中的表述实际是 旧 而不是 成熟。）这个示例图展示了 Ruby 2.1 对象世代的概念视图：

左边是空闲对象链表的另一个表现方式。我们看到垃圾对象是白色的，而剩下存活的、活跃的对象则是灰色的。这些灰色的对象就是被标记了的。

当标记和扫描处理完成，Ruby 2.1 将认为被标记的对象是成熟的：

跟 Python 的使用三个世代不同，Ruby 2.1 的垃圾回收器只使用两个。这些世代并不由不同区域的物理内存组成。（一些其他编程语言的垃圾回收算法和其它 Ruby 实现，使用一种被称为复制式垃圾回收器，在对象升级时会对对象进行复制。）相反，Ruby 2.1 内部代码并不会保存之前在标记和扫描中被标记的对象。对象一旦被标记，将不再参与下次的标记与扫描处理。

现在假设你的 Ruby 程序一直在执行，创建更多的新对象。这些对象也会在年轻世代中出现：

跟 Python 相似， Ruby 的回收器专注于年轻世代的处理。它在标记与扫描算法中只关注那些在最近一次垃圾回收处理后被创建的年轻新对象。这是因为很多新对象有很大的可能已经变成垃圾（如图中左边的白色盒子）。Ruby 不会重复标记图中右边的成熟对象。因为它们已经免除了一次垃圾回收的处理，意味着它们有可能会保持活跃并存活很长的一段时间。因为只标记年轻的对象，使得 Ruby 的垃圾回收代码能执行的更快。它跳过了对成熟对象的处理，减少了程序等待垃圾收回完成的时间。

Ruby 会偶尔执行“完全回收”，连同成熟对象一起进行标记与扫描。Ruby 通过监控成熟对象的数量来决定什么时候执行完全回收。当成熟对象的数量达到上次完全收回后剩余数量的两倍时，Ruby 会清除所有的标记让所有成熟的对象重新处于年轻状态。

写屏障

这个算法的实现有一个重要的难题，很值得我们进行进一步的解释。假设你的代码创建了一个新的年轻的对象并同时使它被一个已存在的成熟对象引用。举个例子，当你往一个存在了很长时间的数组中添加新值时就会出现这种情况。

我们看到新的年轻的对象在图的左边，而成熟的对象在右边。左边有5个新对象已经被用灰色标记为仍然活跃的对象，还有两个用白色标记垃圾对象。但中间的那个新对象是什么回事呢？它是白色的同时中间有个问号。这个新对象究竟是垃圾还是存活的？

当然，它是存活的，因为它被右边的一个成熟对象所引用。但我们记得 Ruby 2.1 的标记和扫描处理是不包含成熟对象的（除了完全回收）。这意味着这个新对象会被错误的认为是垃圾并被回收，从而导致你的程序出现数据丢失！

Ruby 2.1 解决了这个问题，通过监控成熟对象来得知它们是否引用了一个新的年轻的对象。Ruby 2.1 使用了一种成为 写屏障 的旧的垃圾回收技术来监控成熟对象的变化 —— 当你把一个对象引用另外一个对象时（无论是新建或者修改引用），写屏障就会被触发。这个屏障会检查源对象是否成熟的，如果是则把它添加到一个特殊的列表。然后，Ruby 2.1 会把这些刚被修改的成熟对象投入到下一次标记和扫描处理中，防止新的活跃的对象被错误的删除。

Ruby 2.1 对写屏障实现实际是相当复杂的，主要是因为没现成的 C 扩展。Koichi Sasada 和 Ruby 的核心团队使用了一系列聪明的解决方案来解决了这个难题。想学习更多的这些技术细节，可以看 EuRuKo 2013 Koichi 那令人着迷的演讲

站在巨人的肩膀上

第一眼看上去，Ruby 和 Python 的垃圾回收实现十分不同。Ruby 使用了 John McCarthy 原始的标记与扫描算法，而 Python 使用的是引用计数。但当我们再靠近一点，我们能够看到 Python 也利用了一些标记与扫描的原理来处理循环引用问题，而且 Ruby 和 Python 都通过相似的方式来使用分代垃圾回收。Python 使用了三个独立的世代，而 Ruby 2.1 使用了两个。

不需要为这些相似感到惊讶。两个语言都是使用了几十年前的计算机科学研究成果 —— 远远早于 Ruby 或 Python 被发明的时间。我发现令人着迷的是，当你深入了解不同的编程语言，你常常会发现它们都使用了相似的基本思路和算法。现代编程语言很大程度上归功于 John McCarthy 和他的同时代人在20世纪60年代和70年代所做的开创性的计算机科学研究。

英文原文：http://patshaughnessy.net/2013/10/30/generational-gc-in-python-and-ruby

译者：天