29. 把内存串成一个同心圆

不是所有对象都有被 GC 照顾的殊荣，只有那些胸怀广大的 “容器” 才能被纳入 GC 的 “小圈圈”。我们已经直到所有在 GC 中的内存在创建之初，就被额外增加了一个包含 _gc_next 和 _gc_prev 的两个指针，这俩兄弟显而易见是在维护一个双向链表。

为了找到这个链表的位置，我们首先顺着 _PyObject_GC_TRACK 一层层抽丝剥茧，看看一个对象是如何被追加到某个链表中的，最终在这里找到了：

// include/internal/pycore_object.h：27
static inline void _PyObject_GC_TRACK_impl(const char *filename, int lineno,
                                           PyObject *op)
{
    // 获取对象头部的 GC_HEAD
    PyGC_Head *gc = _Py_AS_GC(op);

    // generation0 链表的前一个节点？
    PyGC_Head *last = (PyGC_Head*)(_PyRuntime.gc.generation0->_gc_prev);

    // 将 op 插入链表尾部
    _PyGCHead_SET_NEXT(last, gc);
    _PyGCHead_SET_PREV(gc, last);
    _PyGCHead_SET_NEXT(gc, _PyRuntime.gc.generation0);
    _PyRuntime.gc.generation0->_gc_prev = (uintptr_t)gc;
}

每当 Python 创建一个新的容器对象，其会立刻被插入 GC 的 generation0 链表尾部，从代码中的插入操作来看，这是一个当前运行时（PyRuntime）中的双向链表。generation0 的结构看起来这样：

（图中指针指向的位置实际上都应该是内存的起始位置，为了方便简化为图中表示）

gc.generation0 的类型也是 GC_HEAD, 它充当了链表的头部和哨兵（sentinal）节点，这是一种典型的链表操作方法。Python 中利用双向链表将所有 GC 对象链接成一个环。只要进入这个 GC “小圈子”，就会收到 GC 的特别关照了。

新创建的 GC 对象被链入了 gc.generation0，如果了解过常用 GC 算法就会想到，这里表示的是 “分代垃圾回收” 算法中的 0 代内存，那想必还有其他代内存了。这种直觉是正确的，可以在这里看到 Python 中内存分代的规划：

//Modules/gcmodule.c:128

void
_PyGC_Initialize(struct _gc_runtime_state *state)
{
    state->enabled = 1; /* automatic collection enabled? */

    // NUM_GENERATIONS 是 3
#define _GEN_HEAD(n) GEN_HEAD(state, n)
    struct gc_generation generations[NUM_GENERATIONS] = {
        /* PyGC_Head,                                    threshold,    count */
        // 0 代，1 代， 2 代
        {{(uintptr_t)_GEN_HEAD(0), (uintptr_t)_GEN_HEAD(0)},   700,        0},
        {{(uintptr_t)_GEN_HEAD(1), (uintptr_t)_GEN_HEAD(1)},   10,         0},
        {{(uintptr_t)_GEN_HEAD(2), (uintptr_t)_GEN_HEAD(2)},   10,         0},
    };

    // 初始化 Python 虚拟机的分代数组 generations[]
    for (int i = 0; i < NUM_GENERATIONS; i++) {
        state->generations[i] = generations[i];
    };

    // 其他代码
}

这里表示 Python 采用了 3 代内存回收策略，其中 0 代的触发阈值是 700，即 0 代对象超过 700 个就开始尝试回收，其他两代的阈值则是 10。使用分代垃圾回收策略的还有 C#、Java 等等，使用比较常见的垃圾回收策略，分代回收的主要目的是减少 GC 操作，提高虚拟机运行效率，其基本思想简而言之：

年轻代来去匆匆；
中老年安土重迁。

那些已经存在很久的对象更可能继续存在下去，刚创建的对象则很可能很快就被抛弃。

需要注意的是，Python 3.8 中 GC_HEAD 的两个指针在不同时刻可能被用来表示其他信息，明天继续了。

Think In Python

29. 把内存串成一个同心圆