CPython 中的垃圾回收机制

本文主要参考自 Python Developer’s Guide 中的这篇文章

CPython 是你可以从 Python.org 网站上下载到的原生 Python 解析器。在大多数系统中，当你输入 python 指令运行你的程序时，你通常是在使用默认的 CPython 实现。与大多数具有自动存储器管理机制的编程语言类似，Python 具有垃圾回收（Garbage Collection，GC）特性。了解 CPython 是如何实现垃圾回收机制对于深入了解 Python 编程语言是重要的。

del 语句

我们先从 Python 中的 del 语句开始讨论。与赋值语句类似，del 语句也是递归定义的。比如说，当我们要删除一个列表时，将会从左到右地递归删除其中的每一个目标。而我们在删除一个标识符（名称）的时候，则将从局部或全局命名空间中移除该名称的绑定。理解这一点非常重要，因为当存在下列代码时：

>>> a = list ()
>>> id(a)
139714769689088

>>> b = a
>>> id(b)
139714769689088

>>> del a
>>> id(b)
139714769689088

我们注意到，上述代码中 a 与 b 只是新创建的列表的引用。而使用 del 语句作用于标识符上时，仅删除了这种绑定关系，而非列表本身。理解了这一点，我们继续进行接下来的讨论。

CPython 的内存收集概览

CPython 中主要使用的垃圾回收算法是循环引用。其基本思路是 CPython 会统计有多少个不同的地方存在某一个对象的引用。上面提到的“地方”可以指另一个对象、一个全局（或静态）C 变量，或者一个在 C 函数中的局部变量。当一个对象的引用计数变为零时，对象即被释放。如果这个对象同时包含了对其他对象的引用，那么它们的引用计数就会被递减。如果这个递减使其他对象的引用数变为零，那么其他那些对象可能会被依次释放，以此类推。对象的引用计数域可以通过 sys.getrefcount 函数查看（注意到这个函数返回的值总是多 1，因为在调用函数时，函数本身也持对象的引用）：

>>> x = object()
>>> sys.getrefcount(x)
2
>>> y = x
>>> sys.getrefcount(x)
3
>>> del y
>>> sys.getrefcount(x)
2

引用计数机制的主要问题是无法处理包含循环引用的情况，如下例所示：

>>> container = []
>>> container.append(container)
>>> sys.getrefcount(container)
3
>>> del container

在上例中，container 包含了一个指向自己的引用，所以即便是我们移除了访问其本身的引用（变量“container”），其引用计数器也不可能减少至零，因为它仍然持有对它本身的内部引用。因此这种类型的对象无法被简单的循环引用机制所清理。为了使包含循环引用的对象变为不可直接访问的状态时即被清理，我们需要引入一些额外机制。这就是循环垃圾收集器，通常简称为垃圾收集器（GC），尽管引用计数也是垃圾收集的一种形式。

内存布局与对象结构

支持常规 Python 对象的 C 布局通常如下所示：

为实现垃圾收集器，对象的内存布局将在上述常规结构之前增加一些额外信息：

通过这种方式，该对象可以被视为一个普通的 Python 对象。当需要与 GC 相关的额外信息时，可以通过简单的类型转换从原始对象中访问先前的字段：((PyGC_Head *)(the_object)-1)。

这两个额外的字段实现了将所有由垃圾收集器跟踪的对象串联起来的双向链表。这是处于节省内存空间以及提高查找性能的目的。

在这里用到双向链表是因为其更有效地支持一些频繁进行的操作。总体来说，垃圾收集器跟踪的所有对象被分割成若干独立的集合，每个集合都有自己的双链列表。这些集合将所有对象分为若干“代”（generations），以反映在垃圾收集过程中这些对象存活的频率。收集过程中，被收集的每一代都被细分为两部分：可达（reachable）对象和不可达（unreachable）对象。双向链表支持将对象从一个分区移动到另一个分区、添加新的对象、删除一个对象（由垃圾回收器 GC 跟踪的对象其实最常在 GC 根本不运行的时候即被引用计数系统回收），以及合并分区，所有这些操作都只需要恒定代价的指针更新。这种数据结构还支持在对象被添加到分区和从分区中删除时对分区进行遍历操作，而这种操作在运行垃圾回收时是经常需要的。

除了这个对象的结构以外，对于支持垃圾回收的对象的类型对象必须在其 tp_flags 槽中包含 Py_TPFLAGS_HAVE_GC，并提供 tp_traverse 处理程序的实现。除非能证明对象不能只与它的类型的对象形成引用循环，或者除非类型是不可变的，否则还必须提供 tp_clear 的实现。

识别循环引用

CPython 用于识别循环引用的算法被实现于 gc 模块下。垃圾收集器仅关注于清理容器类对象（一种能够包含一个或多个对象的引用的类型）。这种对象可以是数组、字典、列表、自定义类的实例以及拓展模块中的类等。人们可能会认为循环并不常见，但事实是，解释器需要的许多内部引用到处都会产生循环。一些显著的例子是：

• 异常包含回溯对象，回溯对象包含一个包含异常本身的帧列表
• 模块级函数引用了模块的 dict（解析全局变量时需要用到），而该字典又包含了模块级函数的条目
• 实例有对其类的引用，而类本身也会引用它的模块，而模块包含了对里面所有东西的引用（也许还有其他模块），这可以导致回溯到原来的实例
• 当表示类似于图等数据结构时，其中很可能包含至其自身的链接

一旦这些对象成为不可达的对象，要想正确处置它们，首先需要对它们进行识别。在识别循环的函数内部，会维护两个双向链表：一个列表包含所有要扫描的对象，另一个列表将包含所有“暂时”不可达的对象。

为了理解算法的工作原理，我们以一个循环链表为例，该链表中有一个连接是由变量 A 引用的，还有一个自引用对象是完全无法到达的：

>>> import gc

>>> class Link:
...    def __init__(self, next_link=None):
...        self.next_link = next_link

>>> link_3 = Link()
>>> link_2 = Link(link_3)
>>> link_1 = Link(link_2)
>>> link_3.next_link = link_1
>>> A = link_1
>>> del link_1, link_2, link_3

>>> link_4 = Link()
>>> link_4.next_link = link_4
>>> del link_4

# Collect the unreachable Link object (and its .__dict__ dict).
>>> gc.collect()
2

当垃圾回收过程开始时，它在第一个链表上持有它要扫描的所有容器对象。其目的是移动所有不可达的对象。由于大多数对象最终都是可以到达的，所以移动不可达对象的效率更高，因为这涉及到较少的指针更新。

每个支持被垃圾收集的对象在算法开始时，都会有一个额外的引用计数字段，初始化为该对象的引用计数（图中的 gc_ref 字段）。这是因为算法需要修改引用计数来进行计算，这样解释器就不会修改真实的引用计数字段。

然后垃圾回收算法会遍历第一个链表中的所有容器，并将该容器引用的任何其他对象的 gc_ref 字段减 1。这样做的目的是利用容器类中的 tp_traverse 槽（使用 C API 实现或由超级类继承）来了解每个容器引用了哪些对象。在扫描完所有对象后，只有那些来自“要扫描的对象”列表之外的引用的对象才会有 gc_refs > 0。

需要注意，gc_refs == 0 并不意味着这个对象是不可达的。这是因为，这些对象还可以从另一个外部可达的对象（gc_refs > 0）中被引用。例如上图中，link_2 的 gc_refs == 0，但仍然被外部可达的 link_1 对象引用。为了获得真正无法到达的对象集合，垃圾收集器使用 tp_traverse 槽重新扫描容器对象；这次使用不同的遍历函数，将 gc_refs == 0 的对象标记为“暂时无法到达”，然后将它们移到暂时无法到达的列表中。下图描述了 GC 处理器处理 link_3 和 link_4 但还没有处理 link_1 和 link_2 时的状态：

然后垃圾收集程序继续处理 link_1 对象。由于该对象的 gc_refs == 1，因此垃圾收集程序不需要做任何事情，因为它知道 link_1 一定是可达的（并且已经在可达的列表中）。

当垃圾收集程序遇到一个可达的对象时（gc_refs > 0），它就会使用 tp_traverse 槽遍历它的引用，找到所有可从它那里到达的对象，将它们移到可达对象链表的末尾（一开始的那个链表），并将它们的 gc_refs 字段设置增加 1，下面的 link_2 和 link_3 就是这样，因为它们是可从 link_1 到达的。从上图中的状态和检查了 link_1 所引用的对象后，GC 程序知道 link_3 也是可以到达的，所以把它移回原来的列表中，并把它的 gc_refs 字段设置为 1，这样如果 GC 再次访问它，就已经知道它是可达的了。为了避免对一个对象进行两次访问，GC 会对所有已经访问过一次的对象进行标记（通过取消设置 PREV_MASK_COLLECTING 标志），所以如果一个已经被处理过的对象被其他对象引用，GC 就不会对其进行两次处理。

需要注意，一旦一个对象被标记为“暂时不可达”，后来又被移回可达列表，它将被垃圾收集器再次访问，因为现在该对象的所有引用也需要被处理。这个过程实际上是在对象图上进行广度优先搜索。一旦所有的对象都被扫描完，垃圾收集程序就会知道，在暂时不可达列表中的所有容器对象都是真正不可达的，因此可以进行垃圾收集。

有趣的是，上述的全部操作都不涉及到递归（递归需要用到数据结构“栈”以及额外的空间用于存储其递归状态）。也不以任何其他方式需要与对象数量、指针数量或指针链长度成比例的额外内存。除了 C 语言内部需要的常数项（O(1)）存储外，要遍历的对象本身就包含了垃圾收集算法所需要的所有存储空间。这也保证了在内存不足的情况下继续运行垃圾收集程序的可行性。

为什么移动不可达对象要更好

在大多数对象通常都可达的情况下，移动不可达的对象到另一个链表看似很合逻辑。你要明白：移动这些对象付出的成本并不高。

假设我们按顺序创建对象 A、B、C。它们以同样的顺序出现在最年轻一代（generations）中。如果 B 指向 A，C 指向 B，而 C 是可以从外部到达的，那么算法第一步运行后调整后的 refcounts 将分别为 0，0，1，因为唯一可以从外部到达的对象是 C。

CPython 对于垃圾回收的一种优化机制是将对象依据生存时间划分为不同代，请见《CPython 中的垃圾回收：代（generation）的概念》一文。

当执行算法的下一步骤时，我们找到 A，A 会被移动到不可达列表中。当第一次遇到 B 时，B 也一样。然后 C 被遍历，B 被移回可达列表。最终遍历到 B，再将 A 移回可达列表。

所以比起来什么都不移动，可达对象 B 与 A 在这种情况下被分别移动了两次。那为什么说这种方法更好呢？一种简单的移动可达对象的算法将移动 A、B、C 各一次。但关键是这算法扫描对象的顺序是 C、B、A——与原来的顺序相反。在随后的所有次扫描中，这些对象都不会再被移动。由于大多数对象都不构成引用循环，这样可以在以后的垃圾收集中节省多次移动次数。唯一一次成本比较高的情况是在第一次扫描链表的时候。

销毁非可达对象

一旦垃圾收集程序得到了不可达的对象列表，一个用于销毁这些对象的非常精细的过程就开始了。该过程大致按以下步骤进行：

1. 收集并处理弱引用（如果有）。如果一个处于不可达列表的对象即将要被销毁，并且其中包含弱引用与回调函数，这些回调函数需要被首先尊重。这个过程是非常微妙的，因为任何错误都可能导致将处于不一致状态的对象被一些从回调函数中调用的 Python 函数恢复或改变。此外，同样属于不可达列表中的弱引用（对象及其弱引用处于不可达的循环引用中）需要立即清理，而不忽略回调函数。否则稍后会在调用 tp_clear 槽时被触发，就会造成混乱。忽略弱引用的回调函数是可行的，因为对象和弱引用最终都要被销毁，所以说，让弱引用先消失是可行的。
2. 如果一个对象有遗留版本的终结器（finalizers，也就是 tp_del 槽），就把它们移到 gc.garbage 列表中。
3. 调用终结器（finalizers，也就是 tp_finalize 槽），并将对象标记为已经终结的对象，以避免在对象恢复或其他终结器先删除对象时被调用两次。
4. 处理恢复（复活）的对象。如果一些对象已经复活，垃圾处理程序通过再次运行循环检测算法，找到新的、仍然无法到达的对象子集，并继续处理它们。
5. 调用每一个对象的 tp_clear 槽，使所有的内链被破坏，引用计数降为 0，触发所有不可达的对象的销毁进程。