几乎所有的高级编程语言都有自己的垃圾回收机制，开发者不需要关注内存的申请与释放，Python 也不例外。Python 官方团队的文章 https://devguide.python.org/internals/garbage-collector 详细介绍了 Python 中的垃圾回收算法，本文是这篇文章的译文。
摘要
CPython 中主要的垃圾回收算法是引用计数。引用计数顾名思义就是统计每个对象有多少个引用，每个引用可能来自另外一个对象，或者一个全局（或静态）C 变量，或者 C 语言函数中的局部变量。当一个变量的引用计数变成 0，那么这个对象就会被释放。如果被释放的对象包含对其他对象的引用，那么其他对象的引用计数就会相应地减 1。如果其他对象的引用计数在减 1 之后变成 0，这些对象也会级联地被释放掉。在 Python 代码中可以通过 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）container对象的引用计数也不会变成 0，因为 container 对象内部仍然有一个对自身的引用。因此如果仅仅通过简单的引用计数，container 对象永远不会被释放。鉴于此，当对象不可达的时候（译注：当代码中没有对实际对象的引用时），我们需要额外的机制来清除这些不可达对象间的循环引用。这个额外的机制就是循环垃圾收集器，通常简称为垃圾收集器（Garbage Collector，GC），虽然引用计数也是一种垃圾回收算法。
内存布局和对象结构
一般的 Python 对象在 C 语言中的结构体表示如下
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| ob_refcnt | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
为了支持垃圾回收，在一般 Python 对象的内存布局前面加了一些额外的信息
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
通过这种方式，object 可以被看做一般的 Python 对象，当需要垃圾回收相关的信息时可以通过简单的类型转换来访问前面的字段：((PyGC_Head *)(the_object)-1)。
在后面的章节 优化：通过复用字段来节省内存 会介绍这两个字段通常用来串联起被垃圾收集器管理的对象构成的双向链表（ 每个链表对应垃圾回收中的一个分代，更多细节在优化：分代回收 中有介绍），但是在不需要链表结构的时候这两个字段会被用作其他功能来减少内存的使用。
使用双向链表是因为其能高效地支持垃圾回收对链表的一些高频操作。所有被垃圾收集器管理的对象被划分成一些不相交的集合，每个集合都在各自的双向链表中。不同的集合表示不同的分代，对象所处的分代反映了其在垃圾回收中存活了多久。每次垃圾回收的时候，每个分代中的对象会进一步划分成可达对象和不可达对象。双向链表的一些操作比如移动对象、添加对象、完全删除一个对象（垃圾收集器管理的对象一般情况下会在两次垃圾回收之间通过引用计数系统回收）、合并链表等，都会在常量时间复杂度完成。并且双向链表支持在遍历的时候添加和删除对象，垃圾收集器在运行的时候这也是一个非常频繁的操作。
为了支持对象的垃圾回收，Python 的 C 接口提供了一些 API 来分配、释放、初始化、添加和移除被垃圾收集器维护的对象。这些 API 的详情参见 https://docs.python.org/3/c-api/gcsupport.html。
除了上面的对象结构之外，对于支持垃圾回收的对象的类型对象必须要在 tp_flags 字段中设置 Py_TPFLAGS_HAVE_GC 标记，并且实现 tp_traverse 句柄。另外这些类型对象还要实现 tp_clear 句柄，除非能够证明仅仅通过该类型的对象不会形成循环引用或者支持垃圾回收的对象是不可变类型。
循环引用的识别
CPython 中识别循环引用的算法在 gc 模块中实现。垃圾收集器只关注清除容器类型的对象（也就是那些能够包含对其他对象的引用的对象）。比如数组、字典、列表、自定义类实例和扩展模块中的类等等。虽然循环引用并不常见， 但是 CPython 解释器自身也会由于一些内部引用的存在形成循环引用。下面是一些典型场景
- 异常对象 exception 会包含栈跟踪对象 traceback，栈跟踪对象包含栈帧的列表，这些栈帧最终又会包含异常对象。
- 模块级别的函数会引用模块的字典 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
# 回收不可达的 Link 对象 (和它的字典 __dict__)。
>>> gc.collect()
2
当垃圾收集器开始工作的时候，会将所有要扫描的容器对象放在第一个链表中，这样做是为了将所有不可达对象移除。因为正常情况下大多数对象都是可达的，所以移除不可达对象会涉及更少的指针操作，因此更高效。
算法开始的时候会为所有支持垃圾回收的对象另外初始化一个引用计数字段（下图中的 gc_ref），初始值设置为对象实际的引用计数。因为算法在识别循环引用的计算中会修改引用计数，通过使用一个另外的字段 gc_ref 解释器就不会修改对象真正的引用计数。
垃圾收集器会遍历第一个列表中的所有容器对象，每遍历一个对象都会将其所引用的所有的其他对象的 gc_ref 字段减 1。为了找到容器对象所引用的其他对象需要调用容器类的 tp_traverse 方法（通过 C API 实现或者由超类继承）。在遍历完之后，只有那些被外部变量引用的对象的 gc_ref 的值才会大于 0。
需要注意的是即使 gc_ref == 0 也不能说明对象就是不可达的。因为被外部变量引用的对象（gc_ref > 0）仍然可能引用它们。比如在我们的例子中，link_2 对象在第一次遍历之后 gc_ref == 0，但是 link_1 对象仍然会引用 link_2，而 link_1 是从外部可达的。为了找到那些真正不可达的对象，垃圾收集器需要重新遍历容器对象，这次遍历的时候会将 gc_ref == 0 的对象标记为暂时不可达并且移动到暂时不可达的链表中。下图描述了垃圾收集器在处理了 link_3 和 link_4 对象但是还没处理 link_1 和 link_2 对象时的状态。
垃圾收集器接下来会处理 link_1 对象。由于 gc_ref == 1，垃圾收集器不会对其做特殊处理因为知道其可达（并且已经在可达对象链表中）。
当垃圾收集器遇到可达对象时（gc_ref > 0），会通过 tp_traverse 找到其所引用的其他对象，并且将这些对象移动到可达对象链表（它们最初所在的链表）的末尾，同时设置 gc_ref 字段为 1。link_2 和 link_3 对象就会被这样处理，因为它们都被 link_1 引用。在上图所示状态之后，垃圾收集器会检查被 link_1 引用的对象从而知道 link_3 是可达的，所以将其移回到原来的链表中并且设置 gc_ref 字段值为 1，那么垃圾收集器下次遇到 link_3 的时候就知道它是可达的。为了避免重复处理同一个对象，垃圾收集器在处理被可达对象引用的对象的时候会标记它们已经被访问过（通过清除 PREV_MASK_COLLECTING 标记）。
需要注意的是那些开始被标记为暂时性不可达后来又被移回到可达对象链表的对象，会再次被垃圾收集器访问到，因为按照算法逻辑现在被这些对象引用的其他对象也要被处理。第二次遍历实际上是对这些对象间引用关系构成的图的广度优先搜索。在第二遍遍历结束后，垃圾收集器就可以确定现在还留在暂时性不可达对象链表中的对象是真的不可达，因此可以被回收掉。
值得注意的是，整个算法中没有递归操作，也不需要相对于对象数量、指针数量或引用链长度的线性内存空间。除了临时的 C 变量占用 O(1) 的常量空间外，对象本身的字段都已经包含了算法需要的所有数据。
为什么选择移动不可达的对象
因为大多数对象都是可达对象，因此移动不可达对象看起来很合理。但是真正的原因并非想象的那么简单。
假设我们依次创建了 A、B 和 C 三个对象，那么它们在第一代（译注：这里的第一代指的是分代回收）中的顺序就是创建顺序。如果 B 引用 A，C 引用 B，并且 C 有外部引用，那么在垃圾回收算法的第一轮遍历之后 A、B 和 C 的 gc_ref 值分别为 0、0 和 1，因为只有 C 是外部可达对象。
在算法的第二轮遍历中，会先访问 A，因为 gc_ref 为 0 会被移动到暂时性不可达对象链表中，B 也一样。当访问到 C 的时候会将 B 移回到可达对象链表中，当再次访问 B 的时候 A 也会被移回到可达对象链表中。
本可以不用移动，A 和 B 却来回移动了两次，为什么要这么做呢？如果算法直接移动可达对象的话，那么只用将 A、B 和 C 分别移动一次即可。这么做的关键是在垃圾回收结束的时候这几个对象在链表中的顺序依次为 C、B 和 A，与它们最初的创建顺序相反。在后续的垃圾回收中，它们不再需要做任何移动。因为大多数对象之间都没有循环引用，这样做只会在第一次垃圾回收的时候开销比较大，在后续的垃圾回收中能节省很多移动的开销。
销毁不可达对象
一旦垃圾收集器确定了最终的不可达对象列表，就开始销毁这些对象，销毁的大体过程如下
-
处理并且清除弱引用（如果有的话）。如果要销毁的不可达对象有弱引用的回调，那么需要处理回调函数。这个处理过程需要特别小心，因为一个小小的错误就可能让状态不一致的对象被复活或者被回调函数所调用的 Python 函数引用。如果弱引用对象本身也是不可达的（弱引用和其引用的对象在不可达的循环引用中），那么这个弱引用对象需要马上被清理并且不用调用回调函数。如果不马上清理的话，那么在后来调用
tp_clear的时候会造成严重后果。当弱引用和其引用的对象都不可达的时候，那么两者都会被销毁，因此可以先销毁弱引用，这个时候其引用的对象还存在，所以可以忽略弱引用的回调。 -
如果对象有老版本的终结器（
tp_del）需要将其移到gc.garbage列表中。 -
调用不可达对象的终结器（
tp_finalize函数）并且标记这些对象已终结，避免对象被复活后或者在其他对象的终结器已经移除该对象的情况下重复调用tp_finalize。 - 处理被复活的对象。如果有些不可达对象在上一步被复活，垃圾收集器需要重新计算出最终的不可达对象。
-
对于每个最终的不可达对象，调用
tp_clear来打破循环引用使每个对象的引用计数都变成 0，从而触发基于引用计数的销毁逻辑。
优化：分代回收
为了避免每次垃圾回收的时候耗时太久，垃圾收集器使用了一个常用的优化：分代回收。分代回收有个前提假设，认为大多数对象的生命周期都很短，会在创建后很快就被回收。这个假设与现实中很多 Python 程序的情况一致，因为很多临时对象会被很快地创建和销毁。存活越久的对象越不容易因为不可达而被回收。
为了充分利用这一点，所有容器对象都会被分成三代中的某一代。每个新建的容器对象都处于第一代（generation 0）。上面描述的垃圾回收算法只在某一个具体的分代中进行，那些没有被回收的对象会进入下一代（generation 1），这一代中的对象相对于上一代执行垃圾回收的次数会更少。如果对象在新一代中仍然没有被回收就会移动到最后一代（generation 2），在最后一代中执行垃圾回收的次数是最少的。
垃圾收集器会记录在上次垃圾回收之后新增对象与销毁对象数量之差，也就是净新增对象数量。如果超过了 threshold_0 垃圾收集器就会执行。最初的时候垃圾回收只在 generation 0 中执行。如果 generation 1 在上次执行垃圾回收之后， generation 0 中执行垃圾回收的次数超过了 threshold_1 那么就会再次在 generation 1 中执行垃圾回收。对于 generation 2 的处理稍微复杂点，在第三代中的垃圾回收 中单独介绍。前面说的阈值 threshold_0 和 threshold_1 可以通过函数 gc.get_threshold 查看（译注：原文这里描述有误，我在 issue https://github.com/python/devguide/issues/1027 中提出并被作者采纳）：
>>> import gc
>>> gc.get_threshold()
(700, 10, 10)
每个分代中的对象可以通过函数 gc.get_objects(generation=NUM) 查看，另外可以通过调用函数 gc.collect(generation=NUM) 指定在哪个分代中执行垃圾回收。
>>> import gc
>>> class MyObj:
... pass
...
# 为了更容易观察年轻代中的对象需要将第一代和第二代中的对象都移动到第三代
>>> gc.collect()
0 # 译注：不同版本执行的时候的结果不一样
# 创建循环引用
>>> x = MyObj()
>>> x.self = x
# x 最初在第一代中
>>> gc.get_objects(generation=0)
[..., <__main__.MyObj object at 0x7fbcc12a3400>, ...]
# 在第一代中执行垃圾回收之后，x 就移动到了第二代
>>> 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%）的时候，才会在第三代中进行一次全量回收。因为尽管对于非全量的回收（比如创建很多被垃圾收集器管理的对象并且都放进一个列表中，那么垃圾回收的时间复杂度不是线性的，而是 O(N²)。（译注：这里的时间复杂度不是上面说的一次垃圾回收的时间与分代中对象数量的关系，而是指在创建很多对象到列表中这种程序模式下，所有垃圾回收的总耗时与创建的对象数量的关系，详情见 https://mail.python.org/pipermail/python-dev/2008-June/080579.html））。如果使用上面的比率，就会变成摊还之后的线性复杂度（这种做法可以总结为：尽管随着创建的对象越来越多全量垃圾回收会变得越来越慢，但是全量垃圾回收的次数也会变得越来越少）。
优化：通过复用字段来节省内存
为了节省内存，支持垃圾回收的对象中的用于链表的两个指针也会被用作其他用途。这种常见的优化叫做胖指针或标记指针：在指针中存储额外的数据，能够这样做也是利用了内存寻址的特性。大多数架构会将数据的内存同数据的大小对齐，通常是一个字或多个字对齐。对齐之后就会使得指针的最低几位不会被使用，而这些低位就可以用作标记或存储其他信息 —— 通常作为位域（每一位都是一个独立的标记）—— 只要程序在使用指针寻址前屏蔽掉这些位域即可。例如在 32 位架构上，一个字大小是 32 位 4 字节，所以字对齐的地址都是 4 的倍数，也就是以 00 结尾，因此最低 2 位可以用作他用；类似的在 64 位结构上，一个字大小是 64 位 8 字节，字对齐的地址以 000 结尾，最低 3 位可以用来保存其他数据。
CPython 的垃圾收集器的实现就使用了内存布局和对象结构 中描述的 PyGC_Head 结构体中的两个胖指针：
-
_gc_prev字段正常情况下用于指向双向链表中的前一个元素，低 2 位会用来保存PREV_MASK_COLLECTING和_PyGC_PREV_MASK_FINALIZED标记。在没有进行垃圾回收的时候只有表示对象是否被释放的标记_PyGC_PREV_MASK_FINALIZED会被使用。在垃圾回收期间，_gc_prev会被临时用来保存引用计数gc_ref，在此期间垃圾收集器维护的对象链表只能当做单链表使用，直到_gc_prev恢复原来的值。 -
_gc_next字段用于指向双向链表中的下一个元素，垃圾回收算法在检测循环引用时，它的最低位会用来保存表示对象是否暂时性不可达的标记NEXT_MASK_UNREACHABLE。垃圾回收算法中使用双向链表使得大多数操作都能在常量时间复杂度内完成，但是无法高效地判断一个对象是在可达链表中还是在暂时性不可达链表中。由于有标记NEXT_MASK_UNREACHABLE的存在，当需要判断对象在哪个链表中的时候只用检查该标记即可。
注意事项
因为胖指针或标记指针保存了其他数据，所以不能直接用来寻址，必须在清除这些其他数据之后才能得到真正的地址。尤其需要注意那些直接操作链表的函数，因为这些函数经常会假设链表中的指针状态一致。
优化：延迟管理容器对象
有些容器对象不会产生循环引用，所以垃圾收集器没必要管理它们。解除对这些对象的管理会提高垃圾收集器的性能。但是判断一个对象是否可以解除管理也是有成本的，因此必须要权衡一下成本和由此给垃圾收集器带来的收益。有两个可能的时机可以解除对容器对象的管理：
- 容器对象创建的时候
- 垃圾回收的时候
大的原则是原子类型不需要被垃圾收集器管理，非原子类型（容器、用户自定义对象等）需要。也有一些针对特定类型的优化避免垃圾收集器在垃圾回收时对一些简单对象做不必要的检查。下面是一些对内置类型延迟管理的例子：
- 只包含不可变对象（整数、字符串或者只包含不可变对象的元组）的元组不需要被管理。解释器会创建大量的元组，其中很多在垃圾回收之前就销毁了。因此没必要在创建时就对符合条件的元组解除管理。因此除了空元组之外的所有元组在创建时都会被垃圾收集器管理，直到垃圾回收的时候才会确定是否有存活的元组需要解除管理。如果一个元组中的所有元素都没有被垃圾收集器管理，那么元组本身也可以解除管理。每个分代中的垃圾回收都会对元组做是否需要解除管理的检查，因此一个元组可能在多次检查之后才会被解除管理。
- 只包含不可变对象的字典也不需要被垃圾收集器管理。字典是在创建时解除管理的。如果另一个被管理的对象加入到字典中（无论是作为键还是值），那么垃圾收集器都会重新管理字典。另外，在全量垃圾回收（所有分代中）时，垃圾收集器也会检查字典中的内容是否都没有被管理，如果满足条件也会对字典解除管理。
垃圾回收模块提供了 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
