几乎所有的高级编程语言都有自己的垃圾回收机制，开发者不需要关注内存的申请与释放，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):