CPython 使用的主要垃圾回收算法是引用计数。基本思想是 CPython 统计有多少不同的地方引用了一个对象。这样的地方可以是另一个对象，或者一个全局（或静态）C 变量，或者某个 C 函数中的局部变量。当一个对象的引用计数变为零时，该对象将被释放。如果它包含对其他对象的引用，则这些对象的引用计数将递减。这些其他对象也可能被释放，如果这种递减使它们的引用计数变为零，依此类推。可以使用 >>> 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”），引用计数也不会降至 0，因为它仍然有自己的内部引用。因此，仅通过简单的引用计数永远无法清理它。出于此原因，需要一些额外的机制来清理对象之间的这些引用循环，一旦它们变得不可达。这是循环垃圾收集器，通常称为垃圾收集器 (GC)，即使引用计数也是一种形式的垃圾收集。
从 3.13 版本开始，CPython 包含两个 GC 实现
默认构建实现依赖于 全局解释器锁 以实现线程安全性。
自由线程构建实现为了实现线程安全性，在执行收集时暂停其他正在执行的线程。
这两个实现都使用相同的基本算法，但在不同的数据结构上操作。 GC 实现之间的差异 部分总结了这两个 GC 实现之间的差异。
垃圾收集器需要 Python 对象中的附加字段来支持垃圾收集。这些额外字段在默认构建和自由线程构建中是不同的。
通常，支持常规 Python 对象的 C 结构如下所示
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| ob_refcnt | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
为了支持垃圾收集器，对象的内存布局已更改，以便在正常布局之前容纳额外信息
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
通过这种方式，对象可以被视为一个正常的 Python 对象，当需要与 GC 关联的额外信息时，可以通过从原始对象简单类型转换来访问前面的字段：((PyGC_Head *)(the_object)-1)。
如 优化：重用字段以节省内存 部分稍后所解释的，这两个额外字段通常用于保存垃圾收集器跟踪的所有对象的双向链表（这些列表是 GC 代，更多内容请参见 优化：代 部分），但当不需要完整的双向链表结构作为内存优化时，它们也会被重用以实现其他目的。
使用双向链表，因为它们有效地支持最频繁需要的操作。通常，GC 跟踪的所有对象的集合被划分为不相交的集合，每个集合都在自己的双向链表中。在集合之间，对象被划分为“代”，反映了它们在收集尝试中幸存下来的频率。在收集期间，正在收集的代进一步划分为例如可达和不可达对象的集合。双向链表支持将对象从一个分区移动到另一个分区，添加新对象，完全删除对象（GC 跟踪的对象在 GC 根本不运行时最常被引用计数系统回收！），以及合并分区，所有这些都只需要少量恒定的指针更新。小心的话，它们还支持在向分区添加和从中删除对象时对其进行迭代，这在 GC 运行时经常需要。
在自由线程构建中，Python 对象包含一个 1 字节字段 ob_gc_bits，用于跟踪与垃圾收集相关的状态。该字段存在于所有对象中，包括不支持循环垃圾收集的对象。该字段用于识别收集器跟踪的对象，确保每个对象仅调用一次析构函数，并在垃圾收集期间区分可达对象和不可达对象。
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| ob_tid | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |
| pad | ob_mutex | ob_gc_bits | ob_ref_local | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| ob_ref_shared | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
请注意，并非所有字段都是可扩展的。 pad 为两个字节，ob_mutex 和 ob_gc_bits 各为一个字节，ob_ref_local 为四个字节。其他字段 ob_tid、ob_ref_shared 和 ob_type 都是指针大小（即在 64 位平台上为 8 个字节）。
垃圾收集器还会在收集期间暂时重新利用 ob_tid（线程 ID）和 ob_ref_local（本地引用计数）字段用于其他目的。
提供特定的 API 来分配、释放、初始化、跟踪和取消跟踪具有 GC 支持的对象。这些 API 可以 垃圾收集器 C API 文档 中找到。
除了此对象结构外，支持垃圾回收的对象的类型对象必须在其 tp_flags 槽中包含 Py_TPFLAGS_HAVE_GC 并提供 tp_traverse 处理程序的实现。除非可以证明对象不能仅使用其类型的对象形成引用循环，或者除非该类型不可变，否则还必须提供 tp_clear 实现。
CPython 用于检测那些引用循环的算法在 gc 模块中实现。垃圾回收器仅专注于清理容器对象（即可以包含对一个或多个对象的引用的对象）。这些对象可以是数组、字典、列表、自定义类实例、扩展模块中的类等。人们可能会认为循环并不常见，但事实是解释器所需的许多内部引用到处都会创建循环。一些值得注意的示例
异常包含跟踪对象，其中包含包含异常本身的帧列表。
模块级函数引用模块的字典（需要它来解析全局变量），而该字典又包含模块级函数的条目。
实例引用它们的类，而类本身引用其模块，并且模块包含对其中所有内容（以及可能的其他模块）的引用，这可能会导致返回到原始实例。
在表示诸如图形之类的数据结构时，它们通常具有指向自身的内部链接。
为了在这些对象变得不可达后正确处置它们，需要首先识别它们。为了了解算法的工作原理，让我们以一个循环链表为例，该链表有一个由变量 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 对象引用。为了获得真正不可达的对象集，垃圾回收器使用 tp_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 毕竟是可访问的，因此它被移回原始列表，并且它的 gc_ref 字段设置为 1，以便如果 GC 再次访问它，它将知道它是可访问的。为了避免访问一个对象两次，GC 会标记所有已经访问过一次的对象（通过取消设置 PREV_MASK_COLLECTING 标志），以便如果已经处理过一个对象，而该对象被其他对象引用，则 GC 不会处理它两次。
请注意，一个被标记为“暂时不可访问”并且后来被移回可访问列表的对象将再次被垃圾收集器访问，因为现在该对象拥有的所有引用也需要被处理。此过程实际上是对对象图的广度优先搜索。一旦扫描所有对象，GC 就知道暂时不可访问列表中的所有容器对象实际上是不可访问的，因此可以进行垃圾回收。
实际上，重要的是要注意，所有这些都不需要递归，并且也不需要以任何其他方式需要与对象数量、指针数量或指针链长度成正比的额外内存。除了内部 C 需求的 O(1) 存储之外，对象本身包含 GC 算法所需的所有存储。
在大多数对象通常可访问的前提下，移动不可访问的对象听起来很合乎逻辑，直到你思考一下：它之所以值得，实际上并不明显。
假设我们按顺序创建对象 A、B、C。它们按相同的顺序出现在年轻代中。如果 B 指向 A，C 指向 B，并且 C 可从外部访问，那么在算法的第一步运行后调整后的引用计数将分别为 0、0 和 1，因为从外部可访问的唯一对象是 C。
当算法的下一步找到 A 时，A 被移动到不可访问列表中。当第一次遇到 B 时，B 也是如此。然后遍历 C，B 被移动回可访问列表。最终遍历 B，然后 A 被移回可访问列表。
因此，可访问对象 B 和 A 并没有完全不动，而是各移动了两次。为什么这是一个胜利？一个直接的算法来移动可访问的对象只会移动 A、B 和 C 各一次。关键在于，这种移动将对象按顺序排列为 C、B、A - 它与原始顺序相反。在所有后续扫描中，它们都不会移动。由于大多数对象不在循环中，因此这可以在无限数量的后续收集中节省无限数量的移动。唯一可能成本更高的时间是第一次扫描链时。
一旦 GC 知道不可访问对象列表，一个非常精细的过程就会开始，目的是完全销毁这些对象。大致上，该过程按顺序执行以下步骤
处理并清除弱引用（如果有）。指向不可达对象的弱引用被设置为 None。如果弱引用具有关联的回调，则会将回调排队，以便在清除弱引用后调用。我们仅调用可达弱引用的回调。如果弱引用和指向的对象都不可达，则我们不会执行回调。这部分是出于历史原因：回调可能会复活一个不可达的对象，而对弱引用的支持早于对对象复活的支持。忽略弱引用的回调是可以的，因为对象和弱引用都会消失，所以可以说弱引用首先消失了。
如果对象具有旧式析构函数（tp_del 槽），则将其移动到 gc.garbage 列表中。
调用析构函数（tp_finalize 槽），并将对象标记为已完成，以避免在对象复活或其他析构函数首先删除对象时再次调用析构函数。
处理复活的对象。如果某些对象已复活，则 GC 会再次运行循环检测算法，找到仍然不可达的对象的新子集，并继续处理这些对象。
调用每个对象的 tp_clear 槽，以便断开所有内部链接，引用计数降至 0，从而触发所有不可达对象的销毁。
为了限制每次垃圾回收所花费的时间，默认构建的 GC 实现使用了一种流行的优化：代。此概念背后的主要思想是假设大多数对象的生命周期非常短，因此可以在创建后立即收集它们。事实证明，这与许多 Python 程序的实际情况非常接近，因为许多临时对象会被创建并很快销毁。
为了利用这一事实，所有容器对象都被隔离到三个空间/代中。每个新对象都从第一代（第 0 代）开始。仅对特定代的对象执行前面的算法，如果一个对象在其代的收集中存活下来，它将被移到下一代（第 1 代），在那里它将被调查以进行收集的频率较低。如果同一对象在此新代（第 1 代）中存活了另一轮 GC，它将被移到最后一代（第 2 代），在那里它将被调查的频率最低。
自由线程构建的 GC 实现不使用多代。每个收集都在整个堆上操作。
为了决定何时运行，收集器会跟踪自上次收集以来对象分配和释放的数量。当分配数量减去释放数量超过 threshold_0 时，收集开始。最初只检查第 0 代。如果自检查第 1 代以来，第 0 代已被检查的次数超过 threshold_1 次，则也会检查第 1 代。对于第 2 代，事情会稍微复杂一些；有关更多信息，请参见 收集最旧的代。可以使用 gc.get_threshold() 函数检查这些阈值
>>> import gc
>>> gc.get_threshold()
(700, 10, 10)
可以使用 gc.get_objects(generation=NUM) 函数检查这些代的内容，并且可以通过调用 gc.collect(generation=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>, ...]
除了各种可配置阈值之外，GC 仅在比率 long_lived_pending / long_lived_total 高于给定值（硬编码为 25%）时才触发最旧代的完全收集。原因是，“非完全”收集（即年轻代和中年代的收集）将始终检查大约相同数量的对象（由上述阈值确定），而完全收集的成本与长期存在的对象总数成正比，这实际上是无界的。事实上，有人指出，每创建 <常数> 个对象就进行一次完全收集，会导致在由创建和存储大量长期存在对象的工作负载中出现严重的性能下降（例如，构建一个包含 GC 跟踪对象的列表将显示二次性能，而不是预期的线性性能）。相反，使用上述比率会在对象总数中产生摊销的线性性能（其效果可以概括为：“随着对象数量的增加，每次完全垃圾回收的成本越来越高，但我们进行的次数越来越少”）。
为了节省内存，每个支持 GC 的对象中的两个链表指针被重新用于多个目的。这是一个常见的优化，称为“胖指针”或“标记指针”：携带附加数据、将数据“折叠”到指针中的指针，这意味着将数据存储在表示地址的数据中，利用内存寻址的某些属性。这是可能的，因为大多数架构将某些类型的数据对齐到数据的尺寸，通常是字或其倍数。这种差异导致指针的最低有效位没有使用，这些位可用于标记或保留其他信息——最常见的是作为位字段（每个位是一个单独的标记）——只要使用指针的代码在访问内存之前屏蔽掉这些位即可。例如，在 32 位架构（对于地址和字大小）上，一个字是 32 位 = 4 字节，因此字对齐的地址始终是 4 的倍数，因此以 00 结尾，留下最后 2 位可用；而在 64 位架构上，一个字是 64 位 = 8 字节，因此字对齐的地址以 000 结尾，留下最后 3 位可用。
CPython GC 使用两个胖指针，它们对应于 内存布局和对象结构 部分中讨论的 PyGC_Head 的额外字段
警告
由于存在额外信息，“标记”或“胖”指针不能直接解除引用，并且在获取真实内存地址之前必须剥离额外信息。直接操作链表的函数需要特别小心，因为这些函数通常假设列表中的指针处于一致状态。
_gc_prev 字段通常用作“前一个”指针来维护双向链表，但其最低两位用于保留标志 PREV_MASK_COLLECTING 和 _PyGC_PREV_MASK_FINALIZED。在收集之间，唯一可能存在的标志是 _PyGC_PREV_MASK_FINALIZED，它表示对象是否已被终结。在收集期间， _gc_prev 除了两个标志之外，还临时用于存储引用计数 (gc_ref) 的副本，并且 GC 链表在 _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
本节总结了默认构建中的 GC 实现和自由线程构建中的实现之间的差异。
默认构建实现广泛使用 PyGC_Head 数据结构，而自由线程构建实现不使用该数据结构。
默认构建实现使用 PyGC_Head 将所有跟踪对象存储在双向链表中。自由线程构建实现则依赖于嵌入式 mimalloc 内存分配器来扫描堆以查找跟踪对象。
默认构建实现使用 PyGC_Head 作为不可达对象列表。自由线程构建实现重新利用 ob_tid 字段来存储不可达对象链表。
默认构建实现将标志存储在 PyGC_Head 的 _gc_prev 字段中。自由线程构建实现将这些标志存储在 ob_gc_bits 中。
默认构建实现依赖于 全局解释器锁 来实现线程安全性。自由线程构建实现有两个“停止世界”暂停，其中所有其他正在执行的线程都会暂时暂停，以便 GC 可以安全地访问引用计数和对象属性。
默认构建实现是代收集器。自由线程构建是非代收集器；每次收集都会扫描整个堆。
在默认构建中跟踪对象代非常简单且成本低廉。自由线程构建依赖于 mimalloc 来查找跟踪对象；在不扫描整个堆的情况下识别“年轻”对象会更困难。
文档历史记录
Pablo Galindo Salgado - 原作者