垃圾回收机制，来源：https://patshaughnessy.net/2013/10/30/generational-gc-in-python-and-ruby https://patshaughnessy.net/2013/10/24/visualizing-garbage-collection-in-ruby-and-python

Python 和 Ruby 中的分代 GC 2013 年 10 月 30 日 - 评论和反应

Ruby 和 Python 垃圾收集器 以不同的方式处理老对象和年轻对象。 上周，我在 RuPy 上做了一个名为“在 Ruby 和 Python 中可视化垃圾收集”的演示，并写下了前半部分的笔记。我解释了标准 Ruby(也称为 Matz 的 Ruby Interpreter 或 MRI) 如何使用一种称为标记和扫描的垃圾收集 (GC) 算法，这与 1960 年为 Lisp 的原始版本开发的基本算法相同。我们还看到了 Python 如何使用一种非常不同的 GC 算法，也就是 53 年前发明的引用计数。

事实证明，除了引用计数，Python 还采用了第二种算法，称为分代垃圾收集。这意味着 Python 的垃圾收集器处理新创建的对象与处理旧的对象不同。从即将发布的 2.1 版本开始，MRI Ruby 还将首次使用分代 GC。(Ruby 的两种实现，JRuby 和 Rubinius，多年来一直在使用分代垃圾收集。我将在下周的 RubyConf 中讨论 JRuby 和 Rubinius 内部的垃圾收集工作。)

当然，“以不同的方式处理新对象与旧对象”这句话有点虚张声势。新对象和旧对象究竟是什么？Ruby 和 Python 在处理它们时究竟有何不同？今天，我将继续描述这两个垃圾收集器是如何工作的，并回答这些问题。但是在讨论分代 GC 之前，我们首先需要进一步了解 Python 引用计数算法的一个严重的理论问题。

更新：如果你会说俄语，HTR 上有 Vlad Brown 翻译的这篇文章。

Python 中的循环数据结构和引用计数 上次我们看到，Python 使用保存在每个对象中的整数值，称为引用计数，以跟踪有多少指针引用该对象。每当程序中的变量或其他对象开始引用一个对象时，Python 会增加这个计数器;当你的程序停止使用一个对象时，Python 会递减计数器。一旦引用计数变为零，Python 释放对象并回收其内存。

自 20 世纪 60 年代以来，计算机科学家已经意识到这种算法的一个理论问题：如果你的一个数据结构引用自己，如果它是一个循环数据结构，一些引用计数将永远不会变为零。为了更好地理解这个问题，让我们举个例子。下面的代码显示了我们上周使用的相同的 Node 类：

我们有一个构造函数 (在 Python 中称为init)，它在实例变量中保存单个属性。在类定义下面，我们创建两个节点 ABC 和 DEF，我使用左边的矩形表示它们。这两个节点内部的引用计数最初都是 1，因为一个指针 (分别是 n1 和 n2) 指向每个节点。

现在让我们在节点中定义另外两个属性，next 和 prev:

与 Ruby 不同，使用 Python 可以像这样动态地定义实例变量或对象属性。这似乎是 Ruby 中缺少的一些有趣的魔力。(免责声明：我不是 Python 开发人员，所以我可能在这里有一些命名错误。) 设 n1。接下来是 n2 和 n2。Prev 指向 n1。现在，我们的两个节点使用指针的循环模式形成了一个双链表。还要注意，ABC 和 DEF 的引用计数都增加到 2。有两个指针指向每个节点：像以前一样 n1 和 n2，现在还有 next 和 prev。

现在让我们假设我们的 Python 程序停止使用节点;我们把 n1 和 n2 都设为空。(在 Python 中，null 被称为 None。)

现在，Python 像往常一样，将每个节点内部的引用计数递减到 1。

Python 中的零世代 请注意，在上面的图中，我们已经结束了一个不寻常的情况：我们有一个“岛”或一组未使用的对象，它们相互引用，但没有外部引用。换句话说，我们的程序不再使用任何一个节点对象，因此我们期望 Python 的垃圾收集器足够聪明，可以释放两个对象，并回收它们的内存用于其他目的。但这不会发生，因为两个引用计数都是 1 而不是 0。Python 的引用计数算法无法处理相互引用的对象！

当然，这是一个虚构的例子，但是您自己的程序可能以您可能没有意识到的微妙方式包含这样的循环引用。事实上，随着 Python 程序运行时间的推移，它将构建一定数量的“浮动垃圾”，即 Python 收集器无法处理的未使用对象，因为引用计数永远不会达到零。

这就是 Python 的分代算法的用武之地！就像 Ruby 使用链表 (free list) 跟踪未使用的空闲对象一样，Python 使用不同的链表跟踪活动对象。Python 的内部 C 代码将其称为 Generation Zero，而不是将其称为“活动列表”。每次在程序中创建对象或其他值时，Python 都会将其添加到第 0 代链表中：

上面你可以看到，当我们创建 ABC 节点时，Python 将它添加到第 0 代。请注意，这不是您在程序中看到和访问的实际列表;这个链表完全是 Python 运行时内部的。

类似地，当我们创建 DEF 节点时，Python 将它添加到相同的链表中：

现在第 0 代包含两个节点对象。(它还将包含 Python 代码创建的所有其他值，以及 Python 本身使用的许多内部值。)

循环引用检测 随后，Python 循环遍历零代列表中的对象，并检查列表中的每个对象引用的其他对象，并在此过程中递减引用计数。通过这种方式，Python 解释了从一个对象到另一个对象的内部引用，这些引用阻止了 Python 更早地释放对象。

为了更容易理解，让我们举个例子：

上面可以看到 ABC 和 DEF 节点包含 1 的引用计数。另外三个对象也在零代链表中。蓝色箭头表示一些对象是由位于其他地方的其他对象引用的——来自第 0 代以外的引用。(稍后我们将看到，Python 还使用另外两个列表，分别称为 Generation One 和 Generation two。) 这些对象具有更高的引用计数，因为其他指针都引用了它们。

下面你可以看到 Python 的垃圾收集器处理第 0 代之后发生了什么。

通过识别内部引用，Python 能够减少许多第 0 代对象的引用计数。在上面的第一行中，您可以看到 ABC 和 DEF 现在的引用计数为零。这意味着收集器将释放它们并回收它们的内存。剩余的活动对象然后被移动到一个新的链表：第一代。

在某种程度上，Python 的 GC 算法类似于 Ruby 使用的标记和清除算法。它周期性地跟踪从一个对象到另一个对象的引用，以确定哪些对象仍然是活动的，我们的程序仍然在使用的活动对象——就像 Ruby 的标记过程一样。

Python 中的垃圾收集阈值 Python 什么时候执行标记过程？当你的 Python 程序运行时，解释器会跟踪它分配了多少新对象，以及因为零引用计数而释放了多少对象。理论上，这两个值应该保持不变：程序创建的每个新对象最终都应该被释放。

当然，事实并非如此。由于循环引用，并且由于您的程序使用某些对象的时间比其他对象长，分配计数和发布计数之间的差异会慢慢增大。一旦这个增量值达到某个阈值，Python 的收集器就会被触发，并使用上面的减法算法处理第 0 代列表，释放“浮动垃圾”并将幸存的对象移动到第 1 代。

随着时间的推移，Python 程序长期使用的对象将从第 0 代列表迁移到第 1 代列表。在分配 - 释放计数增量值达到更高的阈值之后，Python 以类似的方式处理第一代列表上的对象。Python 将剩余的活动对象移到第二代列表中。

通过这种方式，你的 Python 程序长期使用的对象，你的代码保持活动引用的对象，从第 0 代移动到第 1 代和第 2 代。使用不同的阈值，Python 以不同的时间间隔处理这些对象。Python 在第 0 代处理对象的频率最高，第 1 代处理的频率较低，第 2 代处理的频率更低。

弱代际假说 这种行为是分代垃圾收集算法的关键：收集器处理新对象的频率高于旧对象。一个新的或年轻的对象是您的程序刚刚创建的对象，而一个旧的或成熟的对象是一个已经活跃了一段时间的对象。当 Python 将一个对象从第 0 代移动到第 1 代，或从第 1 代移动到第 2 代时，它会提升一个对象。

为什么要这么做？这种算法背后的基本思想被称为弱代假设。该假说实际上包含两个观点：大多数新天体很早就消亡了，而较老的天体可能会长期保持活跃状态。

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

根据假设，我的代码可能只在很短的时间内使用新的 ABC 节点。对象可能只是一个方法内部使用的中间值，一旦方法返回，它就会变成垃圾。大多数新对象很快就会变成垃圾。然而，我的程序偶尔会创建一些在较长时间内仍然重要的对象——例如会话变量或 web 应用程序中的配置值。

通过更频繁地处理第 0 代中的新对象，Python 的垃圾收集器将大部分时间花在它将受益最大的地方：它处理将快速且频繁地成为垃圾的新对象。只有在分配阈值增加时，Python 的收集器才会处理较旧的对象。

回到 Ruby 中的 Free List 即将发布的 Ruby 版本 2.1 现在首次使用了分代垃圾回收算法!(请记住，Ruby 的其他实现，如 JRuby 和 Rubinius，多年来一直在使用这种思想。) 让我们回到我上一篇文章中的自由列表图来理解它是如何工作的。

回想一下，当空闲列表用完时，Ruby 会标记程序仍在使用的对象：

在这个图中，我们看到有三个活动对象，因为指针 n1、n2 和 n3 仍然指向它们。剩下的对象，即白色方块，都是垃圾。(当然，空闲列表实际上包含数千个以复杂模式相互引用的对象。我的简单图表帮助我传达 Ruby GC 算法背后的基本思想，而不会陷入细节中。)

还记得 Ruby 将垃圾对象移回空闲列表中，因为现在它们可以被你的程序在分配新对象时回收和重用：

Ruby 2.1 中的分代 GC 从 Ruby 2.1 开始，GC 代码采取了额外的步骤：它将剩余的活动对象提升到成熟的生成。(MRI C 源代码实际上使用了“老”和“不成熟”这个词。) 下图展示了 Ruby 2.1 的两个对象生成的概念视图：

左边是空闲列表的不同视图。我们看到垃圾对象是白色的，其余活跃的活动对象是灰色的。灰色的物体只是做了标记。

一旦标记和清除过程完成，Ruby 2.1 将认为剩余的标记对象是成熟的：

Ruby 2.1 的垃圾收集器不像 Python 那样使用三代，而是只使用两代。左边是年轻代中的新对象，右边是成熟代中的旧对象。一旦 Ruby 2.1 标记了一个对象一次，它就认为该对象是成熟的。Ruby 打赌对象已经保持了足够长的活动时间，不会很快变成垃圾。

重要提示:Ruby 2.1 实际上并不在内存中复制对象。这些代并不由物理内存的不同区域组成。(其他语言和其他 Ruby 实现使用的一些 GC 算法，即所谓的复制垃圾收集器，在提升对象时确实会复制对象。) 相反，Ruby 2.1 在内部使用的代码在标记和清除过程中不包括以前标记过的对象。一旦一个对象被标记了一次，它就不会被包括在下一次标记和扫描过程中。

现在假设 Ruby 程序继续运行，创建更多新的年轻对象。这些在年轻一代中再次出现，在左边：

就像 Python 一样，Ruby 的收集器将精力集中在年轻一代上。它只包括自标记和扫描算法中发生的最后一个 GC 进程以来创建的新的年轻对象。这是因为许多新对象可能已经是垃圾 (左边的白色方框)。Ruby 没有重新标记右边的成熟对象。因为它们已经在一个 GC 过程中存活了下来，所以它们很可能保持活动状态，在较长时间内不会变成垃圾。通过只标记年轻对象，Ruby 的 GC 代码运行得更快。它只是完全跳过成熟对象，减少了程序等待垃圾收集完成的时间。

Ruby 偶尔会运行“完整收集”，重新标记和重新扫描成熟对象。Ruby 通过监视成熟对象的数量来决定何时运行完整的集合。当成熟对象的数量比上次完整收集增加了一倍时，Ruby 会清除标记，并认为所有对象都是年轻的。

写屏障 该算法面临的一个重要挑战值得进一步解释。假设您的代码创建了一个新的、年轻的对象，并将其作为现有的、成熟的对象的子对象添加。例如，如果您向一个已经存在很长时间的数组添加了一个新值，就会发生这种情况。

在左边我们看到新的，年轻的物体和成熟的物体在右边。在左侧，标记过程已经识别出 5 个新对象仍然是活动的 (灰色)，而两个新对象是垃圾 (白色)。但是中心那个新的年轻物体呢？这是用白色标着问号的那个。这个新对象是垃圾还是活动的？

当然，它是活动的，因为右边有一个成熟对象对它的引用。但是请记住，Ruby 2.1 在标记和扫描中不包括成熟对象 (直到发生完整的收集)。这意味着新对象将被错误地认为是垃圾并被释放，导致程序丢失数据！

Ruby 2.1 通过监视成熟对象来克服这一挑战，以查看您的程序是否将它们的引用添加到新的年轻对象。Ruby 2.1 使用一种称为写屏障的旧 GC 技术来监视对成熟对象的更改——无论何时从一个对象向另一个对象添加引用 (无论何时写入或修改对象)，都会触发写屏障。barrier 检查源对象是否成熟，如果是，则将成熟对象添加到一个特殊列表中。后来的 Ruby 2.1 在下一次标记和清除过程中包含了这些修改过的成熟对象，以防止活动的年轻对象被错误地视为垃圾。

Ruby 2.1 写障碍的实际实现相当复杂，主要是因为现有的 C 扩展不包含它们。Koichi Sasada 和 Ruby 核心团队也使用了许多聪明的解决方案来克服这一挑战。要了解更多技术细节，请观看 Koichi 在 2013 年 eurouko 上的精彩演示。

站在巨人的肩膀上 乍一看，Ruby 和 Python 实现垃圾收集的方式似乎非常不同。Ruby 使用 John McCarthy 最初的标记和扫描算法，而 Python 使用引用计数。但是当我们更仔细地观察时，我们会发现 Python 使用标记和清除思想来处理循环引用，并且 Ruby 和 Python 都以类似的方式使用分代垃圾收集。Python 使用三个独立的代，而 Ruby 2.1 使用两个代。

这种相似之处不足为奇。这两种语言都使用了几十年前的计算机科学研究——在 Ruby 或 Python 发明之前。我发现，当你深入研究不同的编程语言时，你经常会发现它们都使用相同的基本思想和算法。现代编程语言在很大程度上归功于约翰·麦卡锡 (John McCarthy) 和他的同时代人在 20 世纪 60 年代和 70 年代所做的开创性计算机科学研究。