深入 Python —— Python 是如何管理内存的 （下）
在上篇中，我介绍了 Python 运行时内存池的组织，创建一个对象需要的内存是如何从内存池这个大蛋糕中切出来的，以及对象被回收交还给内存池的一系列行为。上篇中提到的引用计数机制是 Python 垃圾回收机制的主要部分，Python 还引入了另外一套机制来解决引用计数解决不了的一个严重问题。本文详细剖析这套机制的工作原理和实现。
引用计数和它的弊端
Python 首要的的垃圾回收是基于引用计数的，每个对象都有一个 ob_refcnt 属性记录这个对象的引用计数：
#define PyObject_HEAD \
_PyObject_HEAD_EXTRA \
Py_ssize_t ob_refcnt; \
struct _typeobject *ob_type;
...
typedef struct _object {
PyObject_HEAD
} PyObject;
当对象被创建出来给一个变量后，引用计数变成了 1，此后每被引用一次，引用计数的值增加。在 Python 代码中我们可以通过 sys.getrefcnt()方法获取一个对象的引用计数：
In [2]: a = 42
In [3]: sys.getrefcount(a)
Out[3]: 20
In [4]: b = 424242
In [5]: sys.getrefcount(b)
Out[5]: 2
In [6]: c = b
In [7]: sys.getrefcount(b)
Out[7]: 3
In [8]: d = [b]
In [9]: sys.getrefcount(b)
Out[9]: 4
这里问题就来了，a 不是刚创建出来的嘛，那引用计数不应该是 1 吗？这里就不得不提到 Python 对很多内置对象做的基于缓存的性能优化机制。对于整数对象的优化机制是，Python 会在虚拟机启动前创建 [-5, 256] 这个范围内的小整数对象，这些对象的生命周期和 Python 程序相同，不会被回收。这里获得的 42 的引用计数为 20 说明被 a 引用前 Python 内部已经有多处引用 42 这个小整数对象了。
那么 b 呢？424242 不在小整数范围呢，不应该是 1 吗？是的，应该是 1，但当 b 作为参数传入到 sys.getrefcount(param)，相当于进行了 param = b 的一次赋值，导致 b 的引用计数增加了 1，所以 b 的引用计数变成了 2。
当对象不再被引用，引用计数的值变成 0，就会触发内存回收机制：
#define Py_DECREF(op) \
do { \
if (_Py_DEC_REFTOTAL _Py_REF_DEBUG_COMMA \
--((PyObject*)(op))->ob_refcnt != 0) \
_Py_CHECK_REFCNT(op) \
else \
_Py_Dealloc((PyObject *)(op)); \
} while (0)
回收的内存交还给内存池，在特定时候（上文中的介绍）再有内存池交还给系统。这就是引用计数的工作机制。
引用计数有一个致命的弱点，它处理不了循环应用，一个最简单的例子：
>>> a = []
>>> b = []
>>> a.append(b)
>>> b.append(a)
a 引用了 b，b 中又引用了 a，现在如果程序中不再需要这俩个变量
>>> del a
>>> del b
通过 del 去除了 a，b 对自身的引用，但是这俩个对象之间还存在相互引用，所以它们的引用计数不为零，会一直留在内存中，这就造成了内存泄漏。
Python 的解决方案
不难理解，只有能包含其他对象的容器对象之间才可能发生循环引用，目前这类对象有：list，tuple，instance，dict，class，function……像整数或者字符串这种不可变对象是不能包含其它对象的。
Python 解决方案首先是要在这些可能发生循环引用的容器对象前增加额外的域将它们链接成一个双链表（更准确一点是循环双链表），下面是这个域的定义：
/* GC 信息存放在每个容器对象的前面 */
typedef union _gc_head {
struct {
union _gc_head *gc_next;
union _gc_head *gc_prev;
Py_ssize_t gc_refs;
} gc;
long double dummy; /* force worst-case alignment */
} PyGC_Head;
每个容器对象都带有这样一个头，Python 提供俩个宏用于容器对象指针和 PyGC_Head 之间进行切换：
#define _Py_AS_GC(o) ((PyGC_Head *)(o)-1)
#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))
图中蓝色部分是原始的 PyObject，绿色部分是 PyGC_Head。
下面是在这个容器对象组成的双链表上进行一次针对循环引用的垃圾回收的大致过程：
- 对于每个容器对象，将 gc_refs 设为 ob_refcnt
- 对于每个容器对象，找出这个对象引用的其他容器对象，将它们的 gc_refs 减去 1
- 现在所用容器对象如果 gc_refs >= 1， 说明这些对象存在容器对象外的其他引用（非循环引用），这个对象是不能回收的，需要将它移动到单独的集合上
- 对于不能回收的这部分对象，它们引用的对象也是不能清除的，这些对象也需要移到单独的集合，然后这些对象引用的对象也不能清除，这是一个递归的过程
- 现在所有不能被清除的对象移除后，剩下的这些对象可以认为只存在这些对象之间的相互引用（循环引用），我们可以清除这些对象了
这套方法在垃圾回收领域的专业称呼叫标记清除（Mark and Sweep），它并不是 Python 创造的。其中标记指的是找出哪些对象是还在用的，哪些是垃圾，清除就是清除垃圾。还在用的对象被称为可达的（reachable），可回收的对象就是不可达的（unreachable）。
在 Python 的实现中 gc_refs 也充当了标记的角色。
这个方案对于有析构方法（finalizers）的对象是存在一些问题的。定义了析构方法的的对象在 Python 中指的是对象定义了 __del__ 方法。在引用计数模式下，当对象应用计数变为零，在对象内存被释放前会先调用这个 __del__ 方法，这是没有问题的。但是在处理循环引用的 GC 模式下，析构方法就变得很难处理。考虑这样一种情况，如果俩个对象相互引用并且各自都有析构方法，那么在回收内存前我们要先调用哪一个呢？假设先调用了一个，第一个对象被释放，如果第二个对象的析构方法中还需要用到第一个对象怎么办？
这又是一个不得不考虑的 Edge Case，这种情况理论上可能发生，实际上极少发生，原则上不应该发生。很遗憾 Python 也没有解决方法，目前的做法是包含析构方法的对象也不会被释放。在 Python 看来，如果发生这种情况那完全是程序员的锅，最好是通过修改代码解决。
解决方案的优化
上述的方案解决了循环引用的问题，但是带来了额外的时空开销，而且随着创建的容器对象越来越多，这个开销会越来越大。为了尽可能降低这套方案对 Python 整体性能的影响，Python 在此基础了做一些优化，总的策略是：
- 通过减少需要扫描的对象让每次回收过程更快
- 降低回收的频率
优化1
引入了分代机制，其思想是将系统中的所有内存块根据其存货时间划分为不同的集合，每一个集合就称为一个“代”，垃圾收集的频率随着“代”的存活时间的增大而减小，也就是说，活的越长的对象，就越不可能是垃圾，就应该越少去收集。
Python 中总共分 3 代，我们后面称之为年轻代，中年代，老年代，
struct gc_generation {
PyGC_Head head;
/* 每一代是否进行垃圾回收的阈值 */
int threshold;
/* 与 threshold 对应，记录当前的数量 */
int count;
};
#define NUM_GENERATIONS 3 /* 总共 3 代 */
#define GEN_HEAD(n) (&generations[n].head) /* 获取指定代的头指针 */
每一代的触发垃圾回收的阈值（threshold）是不一样的，这些值在 generations 设置：
/* threshold 对于每一代的含义是不一样的
* 年轻代：默认为 700，表示每进行 700 次容器内存的分配执行一次年轻代的 GC
* 中年代：默认为 10，表示执行 10 次年轻代的 GC 才执行一次中年代 GC
* 老年代：默认为 10，表示执行 10 次中年代的 GC 才执行一次老年代 GC */
static struct gc_generation generations[NUM_GENERATIONS] = {
/* PyGC_Head, threshold, count */
{{{GEN_HEAD(0), GEN_HEAD(0), 0}}, 700, 0},
{{{GEN_HEAD(1), GEN_HEAD(1), 0}}, 10, 0},
{{{GEN_HEAD(2), GEN_HEAD(2), 0}}, 10, 0},
};
PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);
在 Python 的分代回收机制中，每一代并不是孤立回收的，而是把比当前代年轻的代都合并进来进行一次回收。比如进行一次老年代回收，会把年轻代和中年代维护的链表合并到老年代进行回收，所以对老年代的回收也叫完全回收（full collection），对年轻代和中年底啊的回收统称非完全回收（ non-full collection）。
优化 2
年轻代每 700 次分配触发一个，最多需要处理 700 个对象，中年代每 10 年轻代回收才触发一次，最多需要处理 7000 个对象，这俩代需要处理的对象都是有上限的，而老年代就不一样了，它是没上限的。考虑这样一种情况，应用程序中容器对象的数量达到 1,000,000 个，而且都不能回收（long live objects），随着程序的运行，这些对象最终都会进入老年代，这时候执行一次完全回收开销就会非常大。
Python 增加了逻辑限制完全回收的频率，方案是维护俩个全局变量：
/* 上一次完全回收中存活下来的对象数量 */
static Py_ssize_t long_lived_total = 0;
/* 在非完全回收中存活下来的对象数量，这些对象等待第一次完全回收 */
static Py_ssize_t long_lived_pending = 0;
只有当达到完全回收的阈值并且long_lived_pending /long_lived_total这个比值超过 25% 才执行完全回收。25% 这个比值是在代码中写死的。
优化3
当需要考虑一个对象的循环引用时，我们把它添加到 generation0 这个双链表中，这个过程叫做 track，从这个双链表移除对象叫 untrack。那是否每个容器对象都要 track 呢？显然不是。比如一个 tuple 存放的都是不可变对象，其实是不需要 track 的。把这些不需要考虑循环引用的对象排除掉可以提高 GC 的效率，但是排除这些容器本身也是需要资源的，所有要权衡好。
什么时候我们不去 track 容器对象呢？有俩个策略：
- 容器创建的时候
- 垃圾回收检查这个容器的时候
这俩个策略目前并没有应用到所有容器对象上，好像只在 tuple 和 dict 上用了，什么原因呢？估计是只在这俩个对象上有用户出现了 GC 相关的问题（issue 4074，issue 14775）。
除了空的 tuple，所有 tuple 在创建的时候被 track，当一次垃圾回收中发现 tuple 中对象没有被 track 的（没有容器对象），那么就 untrack 这个 tuple。如果 dict 的对象都是不可变对象也不需要 track，这个是在字典创建的时候就决定的。如果 dict 一开始被 track 了，在一次完全回收中发现里面的值对象都没有被 track，那么这个 dict 也会被 untrack。
>>> gc.is_tracked([])
True
>>> gc.is_tracked(())
False
>>> gc.is_tracked({})
False
>>> gc.is_tracked({'a': 1})
False
>>> gc.is_tracked({'a': {}})
True
track 和 untack 的实现
gc_ref 除了在垃圾回收是用来存放对象的引用计数，还被用来标记对象的状态。
/* 刚创建出来，还未被 track */
#define GC_UNTRACKED -2
/* 被 tackck */
#define GC_REACHABLE -3
/* 在垃圾回收过程中，还不确定是否是垃圾 */
#define GC_TENTATIVELY_UNREACHABLE -4
track 就是将对象加入个 generation0 循环双链表：
#define _PyObject_GC_TRACK(o) do { \
PyGC_Head *g = _Py_AS_GC(o); \
if (g->gc.gc_refs != _PyGC_REFS_UNTRACKED) \
Py_FatalError("GC object already tracked"); \
g->gc.gc_refs = _PyGC_REFS_REACHABLE; \
g->gc.gc_next = _PyGC_generation0; \
g->gc.gc_prev = _PyGC_generation0->gc.gc_prev; \
g->gc.gc_prev->gc.gc_next = g; \
_PyGC_generation0->gc.gc_prev = g; \
} while (0);
untrack 就是从双链表移除对象：
#define _PyObject_GC_UNTRACK(o) do { \
PyGC_Head *g = _Py_AS_GC(o); \
assert(g->gc.gc_refs != _PyGC_REFS_UNTRACKED); \
g->gc.gc_refs = _PyGC_REFS_UNTRACKED; \
g->gc.gc_prev->gc.gc_next = g->gc.gc_next; \
g->gc.gc_next->gc.gc_prev = g->gc.gc_prev; \
g->gc.gc_next = NULL; \
} while (0);
回收过程
- 首先是什么时候，在什么地方触发的垃圾回收？是在每次为容器对象分配内存时，容器对象的内存分配是在下面这个函数中进行，分配完后，会检测条件判断是否开始垃圾回收：
PyObject * _PyObject_GC_Malloc(size_t basicsize)
{
PyObject *op;
PyGC_Head *g;
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
return PyErr_NoMemory();
/* 容器对象需要在原来的大小基础上加上 PyGC_Head 的大小 */
g = (PyGC_Head *)PyObject_MALLOC(sizeof(PyGC_Head) + basicsize);
if (g == NULL)
return PyErr_NoMemory();
/* 刚创建的容器对象状态是 GC_UNTRACKED */
g->gc.gc_refs = GC_UNTRACKED;
generations[0].count++; /* number of allocated GC objects */
/* 分代垃圾回收触发的条件：
* 1. 最幼代的对象数量大于该代允许的最大数量
* 2. 开启了自动垃圾回收，默认是开启的，除非用户在程序中关闭了
* 3. 最幼代允许的最大数量不为零，默认是 700，除非用户修改了
* 4. 没有正在进行的回收，collecting 是个锁
*/
if (generations[0].count > generations[0].threshold &&
enabled &&
generations[0].threshold &&
!collecting &&
!PyErr_Occurred()) {
collecting = 1;
/* 开始分代回收 */
collect_generations();
collecting = 0;
}
op = FROM_GC(g);
return op;
}
- 触发垃圾回收后，下面的函数遍历每一代，判断是否触发这一代的垃圾回收。
static Py_ssize_t collect_generations(void)
{
int i;
Py_ssize_t n = 0;
/* 从老到幼遍历所有代 */
for (i = NUM_GENERATIONS-1; i >= 0; i--) {
/* 如果这代的回收阈值就开始回收内存，需要注意的是，这里不只是回收当前的这代，
* 也会把比当前代年轻的代的对象纳入当前代进行回收，这样年轻代中未被回收的对
* 象就升级了一代 */
if (generations[i].count > generations[i].threshold) {
/* 优化 2 的逻辑*/
if (i == NUM_GENERATIONS - 1 && long_lived_pending < long_lived_total / 4)
continue;
/* 开始这一代的垃圾回收 */
n = collect(i);
break;
}
}
return n;
}
- collect 是垃圾回收的核心函数，理解的这个函数，也就理解了整个垃圾回收机制流程。
static Py_ssize_t collect(int generation)
{
int i;
Py_ssize_t m = 0; /* # objects collected */
Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
PyGC_Head *gc;
double t1 = 0.0;
...
/* update collection and allocation counters */
if (generation+1 < NUM_GENERATIONS)
generations[generation+1].count += 1;
for (i = 0; i <= generation; i++)
generations[i].count = 0;
/* 上面提到的，如过回收的不是最幼代，会把比它年轻的代都合并过来 */
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
}
/* young 指向当前要回收的代
* old 指向比 young 老一代的代，如果 yound 已经是最老，那么和 yound 相等 */
young = GEN_HEAD(generation);
if (generation < NUM_GENERATIONS-1)
old = GEN_HEAD(generation+1);
else
old = young;
/* 垃圾回收流程的第一步：设置对象的 gc_refs 为 ob_refcnt */
update_refs(young);
/* 垃圾回收流程的第二步 1：将每个 reachable 的对象的 gc_refs 减 1 */
subtract_refs(young);
/* 初始化 unreachable 链表 */
gc_list_init(&unreachable);
/* 垃圾回收流程的第二步 2：将所有 unreachable 的对象移动到 unreachable 链表
* 注意：流程中是说将 reachable 的对象移动单独集合，这是老的实现方式，并没有错，只是后来发现
* unreachable 的对象往往对于 unreachable 的，移动 unreachable 更有效率 */
move_unreachable(young, &unreachable);
/* Move reachable objects to next generation. */
if (young != old) {
if (generation == NUM_GENERATIONS - 2) {
long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
/* We only untrack dicts in full collections, to avoid quadratic
dict build-up. See issue #14775. */
untrack_dicts(young);
long_lived_pending = 0;
long_lived_total = gc_list_size(young);
}
/* 初始化 finalizers 链表，用于存放带有析构方法的对象 */
gc_list_init(&finalizers);
/* unreachable 的对象本来是可以回收的，但是如果对象定义了析构方法，就要放弃回收
* 并将对象移到 finalizers 链表 */
move_finalizers(&unreachable, &finalizers);
/* finalizers 现在链接了所有 unreachable 但是带有析构方法的对象，被这些对象引用的
* 其它 unreachable 对象也不能回收，将它们也移动 finalizers 链表 */
move_finalizer_reachable(&finalizers);
/* 统计可回收对象的数量，打印 debug 信息 */
for (gc = unreachable.gc.gc_next; gc != &unreachable; gc = gc->gc.gc_next) {
m++;
if (debug & DEBUG_COLLECTABLE) {
debug_cycle("collectable", FROM_GC(gc));
}
}
/* 处理弱引用对象，这里暂不深入 */
m += handle_weakrefs(&unreachable, old);
/* unreachable 链表剩下的对象都是可回收的了，调用这些对象的 tp_clear 方法进行垃圾回收，
* 循环引用在这里被打破 */
delete_garbage(&unreachable, old);
/* Collect statistics on uncollectable objects found and print
* debugging information. */
for (gc = finalizers.gc.gc_next;
gc != &finalizers;
gc = gc->gc.gc_next) {
n++;
if (debug & DEBUG_UNCOLLECTABLE)
debug_cycle("uncollectable", FROM_GC(gc));
}
/* debug */
...
/* finalizers 里的 unreachable 对象往上移一代 */
(void)handle_finalizers(&finalizers, old);
/* freelist 是一些类型下面（如 tupe ）为了避免每次创建新对象都要申请内存而缓存的一些
* 空对象，当 GC 回收的是最老的代时，这些类型下的 freelist 里的对象会也被释放（不是全部
* 释放，tuple 下的逻辑是保留一个）*/
if (generation == NUM_GENERATIONS-1) {
clear_freelists();
}
...
return n+m;
}
这就是整个 GC 的工作流程，这里就不再深入里面调用的函数了。
GC 模块
整个 gc 模块（Modules/gcmudole.c）的接口对编程人员是开放的，就是标准库中的 gc 模块，可以通过这些接口在运行时动态地控制 GC 的行为和获取相关信息。
下面列几个：
- 控制是否开启 GC
开启（默认） gc.enable()
关闭 gc.disable()
- 设置每一代的上限值
gc.set_threshold(/threshold0/[,/threshold1/[,/threshold2/]])
- 获取每代中 count 的当前值，返回 (count0, count1, count2)
gc.get_count()
更多接口参考 https://docs.python.org/2/library/gc.html
总结
本文介绍了引用计数和它的解决不了的循环引用问题，Python 中解决这个问题的方案及对这个方案的各种优化。Python 语言本身就是个软件，而软件的设计是在不演化的。 GC 模块也不是一开始就设计成这样的，而是在解决问题的过程中不断进化成现在这样的，并且它还在进化。
参考
- Tracing garbage collection - Wikipedia
- Garbage Collection for Python
- Python-Dev Proposal: Run GC less often
- 《Python 源码剖析》
- Python 2.7.9 源码：Include/objimpl.h，Modules/gcmodule.c
- https://docs.python.org/2/library/gc.html
- issue 4074: Building a list of tuples has non-linear performance - Python tracker
- issue 14775: Dict untracking can result in quadratic dict build-up - Python tracker