原文标题：Garbage collector design
原文作者：Pablo Galindo Salgado
原文链接：https://devguide.python.org/internals/garbage-collector/

摘要

引用计数（reference counting）是 CPython 中最主要的垃圾回收算法。它的主要思想是，CPython 会统计每个对象有多少不同的“地方”对该对象有引用。这个“地方”可能是其他对象，可能是全局（或静态）的 C 变量，也可能一些 C 方法中的本地变量。当一个对象的引用数降为 0 时，这个对象就会被回收。如果其中包含一些对其他对象的引用，那么这些“其他对象”的引用数也将减少，若恰好导致某些对象引用数也降为0，那么它们也会被依次回收。可以使用 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”），它的引用数也不会变成零，因为在它内部仍有一个引用。因此，仅靠简单的引用计数它将永远无法被清除。正因如此，当一些对象变得无法到达（unreachable）时，我们需要一些额外的机制来清除这些对象间的循环引用。这就是循环式垃圾回收器，通常也叫垃圾回收器（GC）。当然，引用计数也是垃圾回收的一种实现形式。

内存布局和对象结构

通常情况下，支持 Python 对象的 C 结构大致如此：

object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
              |                    ob_refcnt                  | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
              |                    *ob_type                   | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
              |                      ...                      |

为了支持 GC，对象的内存布局有了一些更改，它将在通用布局之前存储一些额外的信息：

              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
              |                    *_gc_next                  | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
              |                    *_gc_prev                  | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
              |                    ob_refcnt                  | \
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
              |                    *ob_type                   | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
              |                      ...                      |

在这种方式下，这个 C 结构既可以被当作一个普通 Python 对象，也可以在垃圾回收机制触发时，通过对该结构进行简单的类型转换，来访问其前一个内存域来获取垃圾回收相关的额外信息：
((PyGC_Head *)(the_object)-1)。

正如后文 优化：复用域以节省内存 部分中解释的那样，这两个附加的内存域通常用来维持一些双向链表，这些链表中存储的对象即是 GC 跟踪着的所有对象（这些链表就是 GC 的各个 代，更多关于详见本文 优化：代 部分）。当然，在 GC 做内存优化时，也不是总会需要完整的双向链表，这时没用到的部分就可以被重用来实现其他目的。

使用双向链表，是因为它能高效地支持那些 GC 使用最频繁的操作。通常情况下，被 GC 跟踪的对象们会被根据从垃圾回收机制中存活下来的频率收集为多个不相交的集合，收集成的每个集合都被存入独立的双向链表，一个集合被称为一“代”（generation）。在收集期间，每一个“代”又被进一步分为可到达（reachable）和不可到达（unreachable）。双向链表支持内部对象的移动、新增、彻底移除（被 GC 跟踪的对象在 GC 不运行时通常被引用计数回收）以及链表间的合并，所有的这些操作仅仅只需要更新一下几个指针就能完成。需要主义的是，双向链表还支持在其中增加或删除元素时对分区进行迭代，这也是 GC 在运行时经常需要做的。

GC 提供特定 API 以便对特定对象进行分配、解除分配、初始化、跟踪和解除跟踪。详见 Garbage Collector C API documentation 这篇文档。

除了上述的对象结构之外，用于支持 GC 对象的 type 对象必须在其 tp_flags 属性中包含 Py_TPFLAGS_HAVE_GC，并提供 tp_traverse 函数的实现。除非可以证明对象不能仅与自身类型的对象形成引用循环，或者除非类型是不可变的，否则还需要提供 tp_clear 函数的实现。

识别循环引用

CPython 中用来识别引用循环的算法在 gc 模块中有实现。垃圾回收器 仅专注于 清理容器对象（可以容纳一个或多个对象引用的对象）。它们可以是数组、字典、列表、自定义类的实例和拓展模块中的类等。可能有人会觉得循环并不常见，但事实是许多解释器用到的内部引用把循环建的到处都是。比较经典的例子有：

• Exception 包含 traceback 对象，而 traceback 包含了一个 Exception 自身也在其中的内容列表
• 模块级函数引用了该模块的字典用来解析全局变量，而这个字典又包含了该模块级函数的条目
• 实例有对它所属类的引用，所属类又有对其所在模块的引用。同时所在模块又有对它内部所有事物（也可能有其他import进来的模块）的引用，而这会追溯回最开始的那个实例
• 当表示类似图这样的数据结构时，它的内部节点能链接到自身是再正常不过的一件事

当对象变得不可到达时，要想正确的处理这些对象，首先需要做的就是识别出它们。在循环识别函数的内部有两个双向链表，其中一个包含了所有可以扫描到的对象，另一个包含所有“暂定为”不可到达的对象。

为了更好的理解这个算法，我们以一个循环链表为例，它有一个有变量 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 启动时，会将它所有想扫描的容器对象放入第一个链表，目的是移动所有无法到达对象。由于大部分对象都是可到达的，所以移动不可到达对象显然更加高效，因为这样能更新更少的指针以达到相同的目的。

每当算法启动时，每个支持垃圾回收的对象都会初始化一个额外的引用计数域，用来存放它被引用的数量（图中的 gc_ref 字段）。这是因为算法需要通过修改引用计数来进行计算，又保证了解释器不用调整对象实际的引用计数。

然后，GC 会遍历第一个列表中的所有容器，并将容器引用的任何其他对象的 gc_ref 字段数值减一。可以利用容器类中的 tp_traverse 槽（由 C API 实现或者由超类继承）来获取每个容器引用的对象。在扫描完所有对象之后，只有那些引用来自“要扫描的对象”列表之外的对象，其 gc_ref 字段值才会 > 0

需要注意的是，即便某对象的 gc_ref == 0，也不一定意味着它是不可到达的。这是因为可能会有外部的另一个可访问的对象（gc_ref > 0）对它仍有引用。比如，在我们例子中的 link_2 对象在扫描结束后 gc_ref == 0，但是它仍然在被 link_1 引用，而 link_1 是一个外部可到达的对象。为了获得一个由真正无法到达对象组成的集合，垃圾回收器会使用 tp_traverse 槽再次扫描容器对象，但这次会使用不同的 traverse 方法，将 gc_ref == 0 的对象标记为“暂时不可到达”，然后再将它们移动到暂时不可到达列表中。下图描绘了这样一个状态，GC 已经处理了 link_3 和 link_4 对象，但还没有处理 link_1 和 link_2 对象。

然后，GC 会接着扫描 link_1 对象，由于 gc_ref == 1 代表它一定可到达（并且它已经在即将成为可访问列表的列表中了），所以 GC 不会做任何事。

当 GC 遇到一个可到达对象（gc_ref > 0）时，它将使用 tp_traverse 槽遍历该对象的引用，获取该对象所有可到达的对象，再将它们移动到可到达对象列表的末尾（本例中也就是它们初始的位置），最后将它们的 gc_ref 字段值设置为 1。这就是下图中 link_2 和 link_3 的情况，因为它们可以通过 link_1 到达。从上一张图的状态到检查完 link_1 引用的对象之后，GC 知道了 link_3 是可到达的，因此 link_3 被移动回了初始的列表，并且它的 gc_ref 值也被设置为了 1，以便当 GC 再次访问它时能知道它是可到达的。为了避免访问一个对象两遍的问题，GC 会将所有它已经访问过一次的对象做出标记（通过取消 PREV_MARK_COLLECTING 标志），这样，如果一个已经被处理过的对象也被其他对象引用，GC 就不会对它进行二次处理。

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

从实际意义上讲，需要注意的是，这些都是不需要递归的，也不会以任何其他方式需要额外线性增长的内存，不管是对象数量、指针数量或指针链长度都不会影响。除了满足 C 需求的 O(1) 存储空间外，对象本身包含了 GC 算法所需的所有存储空间。

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

在假定大多数对象都是可以到达的情况下，移动不可到达对象听起来还是挺符合逻辑的。但仔细想想看，这么做值得的原因好像也并不太明显。

假设我们按顺序创建了 A、B、C 三个对象，那它们在新生代（young generation）中也会以同样的顺序出现。如果 C 指向 B，B 指向 A，然后 C 是外部可到达对象，那么经过算法第一步调整后，A、B、C 的引用计数会变为 0、0、1，因为唯一一个外部可到达的对象是 C。

然后算法的下一步扫描到 A，A 被移动到暂时不可达列表，同样的事也会发生在 B 身上。接着，当算法扫描到 C 时，B 又被移回了可到达列表。最后，B 又再次被扫描，A 也被移回到了可到达列表。

所以，虽然看起来结果和最初时完全没有差别，但事实上可到达对象 B 和 A 分别被移动了两次。那为什么这还能算是一次胜利呢？移动可到达对象最直接的算法是将 A、B、C 各移动一次。关键在于，反复横跳的方式把对象的顺序变为 C、B、A - 正好和原始顺序相反。而且在以后的扫描中，它们都不会被移动。由于大部分对象都不是循环的，这可以在无限数量的后续集合中节省无限数量的移动。唯一可能会增加成本的，是第一次的扫描链。

销毁不可到达对象

一旦 GC 获取到一个确定不可访问对象的列表，它就会启动一个非常脆弱的进程，其目标是完全销毁列表中的对象。这个过程大致来说是按照以下顺序进行：

1. 处理和清理弱引用（如果有的话）。如果不可达对象集合中的一个元素即将被销毁，但它有些带回调的弱引用，那么这些回调需要被执行。这个过程会非常脆弱，因为任何错误都可能会导致那些处于相悖状态的对象被回调中调用的某些 Python 方法复活或重新可到达。另外，同属于不可到达集合中的弱引用（对象和它的弱引用在同一个不可达的循环中）则需要立即清除，而不需要执行回调。否则它将会在稍后 tp_clear 槽被调用时被触发，造成严重的后果。忽略弱引用的回调没啥大问题，因为对象和弱引用都将会消失，所以说让弱引用先走一步也是合理的。
2. 如果对象有过时的终结器（tp_del 槽），则需要将它们移到 gc.garbage 列表中。
3. 调用终结器（tp_finalize 槽），并将对象标记为已终结，以免因为对象复活或其他终结器先删除该对象时被调用两次。
4. 处理复活的对象。如果某些对象已经复活，GC 将通过再次运行检测算法找到仍然无法访问的新对象子集，并继续处理它们。
5. 调用每个对象的 tp_clear 槽，这样所有内部链接都将被摧毁，引用数降为0，最后触发所有不可达对象的销毁。

优化：代

为了限制每次垃圾回收所花费的时间，GC 使用了一种流行的优化：代。这个概念背后的主要思想是，假设大多数对象的生命周期很短，因此可以在创建后不久就被回收。事实证明，这与很多 Python 程序的现实非常接近，因为许多临时对象的创建和销毁都非常快。对象越老，它就越不可能变得不可访问。利用这一事实，所有的容器对象会被划分为三个空间/代。每个新创建的对象都属于新生代（generation 0）。之前提到的算法将只对特定一代的对象执行，假设 A 对象处在初生代，如果它在这次回收扫描中幸存下来，那么它将被移动到下一代中生代（generation 1），在中生代它被调查的频率将被降低。如果处于中生代的 A 对象在另一轮的 GC 中又幸存了下来，那么它将被移动到最后一代老生代（generation 2），在那里它的被调查频率将被降到最低。

为了决定垃圾回收运行的时间，收集器会跟踪自上一次收集以来对象分配和回收的数量。当分配的数量减去回收的数量超过 threshold_0 时，将启动回收。最初只检查初生代（generation 0）。如果自检查中生代（generation 1）以来，检查初生代的次数超过了 threshold_1 次，则也检查中生代。对于老生代（generation 2），情况有些复杂；详见下文 回收老生代。刚刚提到的那些阈值可以使用 gc.get_threshold() 函数进行检查：

>>> import gc
>>> gc.get_threshold()
(700, 10, 10)

这些代的内容可以使用 gc.get_objects(generation=NUM) 方法来检查，同时可以通过调用 gc.collect(genereation=NUM) 在特定的代中触发收集。

>>> import gc
>>> class MyObj:
...     pass
...

# Move everything to the last generation so it's easier to inspect
# the younger generations.

>>> gc.collect()
0

# Create a reference cycle.

>>> x = MyObj()
>>> x.self = x

# Initially the object is in the youngest generation.

>>> gc.get_objects(generation=0)
[..., <__main__.MyObj object at 0x7fbcc12a3400>, ...]

# After a collection of the youngest generation the object
# moves to the next generation.

>>> gc.collect(generation=0)
0
>>> gc.get_objects(generation=0)
[]
>>> gc.get_objects(generation=1)
[..., <__main__.MyObj object at 0x7fbcc12a3400>, ...]

回收老生代

除了各种可配置的阈值之外，只有当 long_lived_pending / long_lived_total 的比值高于给定值（固定值为25%）时，GC 才会触发老生代（generation 2）的完整回收流程。原因是，虽然“非完整回收”（即新生代和中生代的收集）需要检查的对象数量大致相同（由上述阈值决定），但完整回收的成本与长寿命对象的总数成正比，而长寿命对象几乎是无限的。确实，有人指出，每次创建 <常量> 对象时都需要进行完整收集，这会导致工作负载的性能急剧下降，因为这些工作负载包括创建和存储大量的长寿命对象（例如，构建一个大的 GC 跟踪列表将显示平方级性能，而不是预期的线性性能）。相反，使用上述比值会在对象总数中产生平摊的线性性能（其效果可以总结为：“随着对象数量的增长，每次完整的垃圾回收的成本越来越高，但我们做的垃圾收集却越来越少”）。

优化：复用域以节省内存

为了节省内存，支持 GC 的每个对象中的两个链表指针会被重用于多个目的。这也是一种常见的优化，被称为“胖指针”或“标记指针”：携带额外数据的指针。“折叠”到指针中，意味着内联存储在表示地址的数据中，利用内存寻址的某些属性。（译者注：这段没看懂。。）大多数体系结构会将数据的类型与数据的大小对齐（通常是一个字或多个字），这种差异使得指针的一些最低有效位未被使用，这些位就可以用来标记或保存其他信息 - 最常见的是作为位字段（每个位都是一个单独的标记）- 只要使用指针的代码在访问内存之前屏蔽掉这些位。例如，在32位体系结构上（地址和字长），一个字是32位 = 4字节，因此字对齐的地址总是4的倍数，也就是说二进制串都会以00结束，最后两位就可以别做他用了；而在64位体系结构中，一个字是64位 = 8字节，所以对齐的地址总是8的倍数，二进制串都会以000结束，就会有三位可以使用。

CPython GC 使用两个胖指针，它们对应于上文 内存布局和对象结构 一节中讨论的 PyGC_Head 的额外字段域：

警告 由于存在额外的信息， “标记”或“胖”指针不能直接解引用，在获取真正的内存地址之前，必须剥离额外信息。对于直接操作链表的函数，需要特别小心，因为这些函数通常假定链表中的指针初一一致状态。

• _gc_prev 字段通常作为“前一个”指针来维护双链表，但其最低的两位用于保存标记 PREV_MASK_COLLECTING 和 _PyGC_PREV_MASK_FINALIZE。在每次回收间隙，唯一可以出现的标志是 _PyGC_PREV_MASK_FINALIZE，他表示对象是否已经被终结。在回收期间，除了这两个标志之外，_gc_prev 还临时用于存储引用计数（gc_ref）的副本，届时 GC 链表会变成单链表，直到 _gc_prev 被恢复。
• _gc_next 字段被用作“下一个”指针来维护双链表，但在收集期间，它的最低位用于保存标记 NEXT_MASK_UNREACHABLE，该标记表示在周期检测算法期间对象是否暂时不可达。这是仅用双链表实现分区（译者注：分为可到达和暂时不可达列表，详见上文识别循环引用）的一个缺点：虽然大多数操作的耗时都是恒定的，但是没有有效的方法来确定对象当前在哪个分区中。所以，当需要时，会使用特别的技巧（如 NEXT_MASK_UNREACHABLE）。

优化：延迟追踪容器

某些类型的容器无法产生引用循环，因此不需要由垃圾回收器跟踪。取消对这些对象的跟踪可以减少垃圾回收的成本，但是确定哪些对象可以不跟踪并不是那么容易，这就需要权衡二者利弊。解除对容器对象追踪的时刻，有两种可能的策略：

1. 在容器对象被创建时
2. 在容器对象被垃圾回收检查时

一般来说，不跟踪原子类型的实例，而跟踪非原子类型的实例（容器、用户定义对象等）。当然，可以提供一些特定类型的优化，来压缩简单实例在垃圾回收时占用的空间。以下是受益于延迟追踪的原生类型示例：

• 只包含不可变对象（整数、字符串等，以及递归包含不可变对象的元组）的元组不需要追踪。解释器创建了大量的元组，其中许多元组直到垃圾回收时才会存在。因此，符合这样条件元组，不值得在对象创建时取消追踪。也就是说，除了空元组之外，所有的元组在创建时都会被追踪，后面在垃圾回收期间，再来确定是否可以不追踪幸存的元组（译者注：额，感觉有点车轱辘话）。如果元组的所有内容都没有被追踪，那么该元组可以不被追踪。在每个垃圾回收周期中，检查元组都会被检查是否被追踪。取消元组的追踪可能需要一个周期以上。
• 只包含不可变对象的字典也不需要被追踪。字典在创建时，不会被追踪。如果有被追踪项被插入到字典中，不管其作为键亦或是值，都会将该字典设置为需要追踪。在完整的垃圾回收期间（所有代），收集器将取消跟踪所有内容都未被追踪的字典。

垃圾回收器模块提供了 Python 函数 is_tracked(obj)，他返回对象当前的跟踪状态。当然，后续的垃圾回收可能会改变这个状态。

>>> gc.is_tracked(0)
False
>>> gc.is_tracked("a")
False
>>> gc.is_tracked([])
True
>>> gc.is_tracked({})
False
>>> gc.is_tracked({"a": 1})
False
>>> gc.is_tracked({"a": []})
True