CPython(2) - 内存管理与垃圾回收

CPython的内存管理

首先我们设想下，CPython是由C语言实现的，为什么他不直接使用C语言中的malloc系列函数，而要自己折腾一个内存管理呢？

在C中，有三种内存分配方式：

• 静态内存分配（static memory allocation），编译期间即可计算所需分配内存大小，在可执行文件开始运行时分配。
• 自动内存分配（automatic memory allocation），当一个帧开始运行的时候，操作系统会在调用栈中为此作用域分配所需内存，当帧执行完成后，这部分内存会被释放。
• 动态内存分配（dynamic memory allocation），可以通过调用内存分配API在运行时动态地请求和分配内存。

考虑这个程序：

int main() {
    int n;
    printf("Enter the size of the array: ");
    scanf("%d", &n);
    // Dynamically allocate memory for the array
    int *array = (int *)malloc(n * sizeof(int));
    // Free the allocated memory
    free(array);
    return 0;
}

在上述程序运行时，系统并不清楚需要分配具体多大的内存，直到接收到用户输入后，通过C API动态分配内存。
由于Python是一门动态类型的语言，大多数内建类型大小都是可以动态调整的，比如List可以是任意长度，Dict键的数量可以动态变化，所以动态内存分配在Python中显得尤为重要。
而频繁的进行内存的分配与释放会严重影响程序的效率，并且可能造成大量的内存碎片。为了解决这些问题，Python自己设计了一套内存管理方案，包含了内存池、引用计数法、垃圾回收算法等内容。

CPython的内存分配域

• Raw Domain 原始内存分配域：用于从系统堆上分配内存，作用于大块或非对象的内存分配。
• Object Domain 对象内存分配域：用于所有Python对象的内存分配。
• Mem Domain PyMem 内存分配域：和PYMEM_DOMAIN_OBJ对象功能一致，用于支持旧版本API。

内存分配器

CPython使用两种内存分配器：

• malloc，操作系统层面的内存分配器，主要用于原始内存的分配。
• pymalloc，CPython层面的内存分配器，用于PyMem内存分配域和对象内存分配域。

由于Python中大部分需要分配的内存都是碎片化且是固定大小的，比如PyObject占16字节、PyLongObject占32字节。在这种情况下，内存碎片的产生概率是非常大的，所以CPython设计将需要分配的内存按大小进行统一管理。其中：

• 对象大于等于256KB，将会由系统内存分配管理。
• 对象小于256KB，将会由pymalloc进行分配。

内存块、内存池与堆区

堆区

堆区是最大的可分配内存单元。系统页的边界是固定长度的连续内存块，为了与系统页的大小对齐，CPython中创建的堆区大小固定为256KB。

与堆区对应的是arena_object

内存池

在堆区中，我们可以为最大为512字节的内存块创建内存池。每个内存池的大小为4096字节，也就是4K，一个堆区中总是存在64个内存池。

根据32位系统和64位系统的不同，内存块的步长也不同，对于32位系统，步长为8字节，总共有64种不同的内存块。

以字节为单位请求申请内存	分配内存块的大小	内存大小索引
1-8	8	0
9-16	16	1
…	…	…
505-512	512	63

以32位系统为例，只要请求的内存大小不超过 8 字节，Python 都在这个内存池为其分配一块 8 字节内存，就算只申请 1 字节内存也是如此。这种做法好处显而易见，内存起始地址均以计算机字为单位对齐。计算机以 字 ( word ) 为单位访问内存，因此内存以字对齐可提升内存读写速度。
CPython会根据内存请求的大小分配内存池，当没有可以用的内存池用于请求的内存大小索引时，就可以分配一个新的内存池。堆区中有一个概念叫高水位线，可以用于查询当前已经分配的内存池数量。内存池存在三种状态：

• 满载，所有可用内存块均已被分配，可以暂时不管。
• 部分使用，已经有部分内存被分配，但还存在空闲内存，会以双向链表的方式组织起来。
• 空闲，内存池被分配，但内存池中的内存块均未被使用，待使用或归还。

三种状态决定了CPython对其的管理方式。

[^A1]: 在创建堆（arena）时，CPython并不会一次性为所有大小类别的内存池都分配内存，而是根据实际需求逐步进行分配。例如，当需要一个 32 字节大小的对象时，Python会检查是否有合适的内存池，如果没有则创建一个用于存储 32 字节大小的内存块的内存池。另外，虽然每个内存池的总大小固定为4 KB，但因为每个池中内存块的大小不同，导致每个内存池内包含的内存块数量是不同的。

内存池表

在堆区中，内存池的存储单元名为内存池表，pool table记录了被部分使用的内存池的双向链表头节点。内存池表根据内存池的内存大小索引i进行分类。对于内存大小索引i，usedpools[i + 1]会指向所有被部分使用的内存池的双向链表头节点，链表中的内存池都拥有相同的类型大小。

• 当一个内存池饱和后，它就会被usedpools[]解除链接。
• 如果已经饱和的内存池中有一个内存块被释放了，那么内存池就将重新回到部分使用的状态。此时还会帮刚刚释放内存的内存池重新连接到usepools[]中链表的前面，这样在下次分配同样大小的内存时将复用刚刚释放的内存块。
• 当一个内存池变为全空时，这个内存池同样也会从usedpools[]中被移除，然后被链接到它所在的堆区的单向链表的freepools的前面。

内存块

内存块也是同样的，在一个内存池中有存在多个内存块，数量根据内存块的大小而有所不同，比如一个管理8字节的内存池中存在4096/8 = 512个内存块。而管理512字节内存块的内存池中仅有8个内存块。

• 在一个内存池中，可以分配和释放固定内存大小索引的内存块。
• 所有可用的内存块都会被链接到freeblock链表上。
• 当一个内存块被释放后，他会被插入到freeblock的头部。
• 当一个内存池被初始化时，只有最前面两个内存块会被链接到freeblock，因为接收到申请，才初始化内存池，并不存在创建内存池等分配的情况，并且下一个内存块的地址可以通过上一个内存块计算出来。
• 如果一个内存池处于被部分使用的状态，那么这个内存池里面至少有一个内存块用于内存分配。

CPython的垃圾内收

引用计数

引用计数真的是最简单及常见的垃圾回收方法之一了。CPython通过维护内部对象的引用次数，将没有被引用的对象回收以释放内存。每一个PyObject实例对象都有一个ob_refcnt属性来记录引用数量，且CPython通过Py_INCREF和Py_DECREF来控制引用计数属性的增减。在Include/object.h中：

static inline void _Py_INCREF(PyObject *op)
{
#ifdef Py_REF_DEBUG
    _Py_RefTotal++;
#endif
    op->ob_refcnt++;
}

#define Py_INCREF(op) _Py_INCREF(_PyObject_CAST(op))

static inline void _Py_DECREF(
#ifdef Py_REF_DEBUG
    const char *filename, int lineno,
#endif
    PyObject *op)
{
#ifdef Py_REF_DEBUG
    _Py_RefTotal--;
#endif
    if (--op->ob_refcnt != 0) {
#ifdef Py_REF_DEBUG
        if (op->ob_refcnt < 0) {
            _Py_NegativeRefcount(filename, lineno, op);
        }
#endif
    }
    else {
        _Py_Dealloc(op);
    }
}

Py_INCREF的定义是简单的，只需控制引用计数属性的自增，Py_DECREF还需要处理当引用计数为0后的触发析构函数的操作。
一般来说Python的开发者几乎无法控制引用计数的操作，因为他都发生在CPython字节码中。但是引用计数最大的问题是会产生循环引用，比如在Python代码中:

a = []
a.append(a)
del a

此时由于a引用了自己，所以即使在del操作后，a的引用计数也会为1。为了解决此类问题，Python还引入了垃圾回收。

垃圾回收

由于Python中充斥着大量的容器类型，如列表、元组、字典、集合等，在开发者的操作下很容易造成循环引用且生成大量不可达对象而垃圾回收算法的主要目的就是找到这些不可达对象且将他们回收。对于长期运行的程序来说，这是非常重要的一个操作。垃圾回收器只会查找在类型定义中设置了Py_TPFLAGS_HAVE_GC标志的类型。以下是在Python3.9.12中被标记为需要垃圾回收的类型：

• 类、方法、函数对象
• cell对象
• 字节数组、单字节、Unicode字符串
• 字典
• 属性中的描述符对象
• 枚举对象
• 异常
• 帧对象
• 列表、元组、命名元组和集合
• 内存对象
• 模块和命名空间
• 类型和弱引用对象
• 迭代器和生成器
• pickle缓存区

诸如浮点数类型、整型、布尔类型、NoneType都不会被标记。当然如果自己编写Python的C语言拓展模块，也可以按需增加标记，从而使得CPython的垃圾回收机制能够追踪。

其中垃圾回收机制还创造了一种取消追踪的机制，由于元组是不可变对象，所以他一旦被创建，就不会改变，但是元组中可以包含可变类型。所以当垃圾回收器运行的时候，每一个元组都会检查自己是否只包含不可变（或者不需要追踪）对象，如果只包含不可变对象的话，元组就会申请取消对自己的追踪，从而减少垃圾回收器的开销。

当我们创建空字典时，他虽然是可变对象，但是在未往其中添加数据时，垃圾回收器并不会追踪他们，可以通过gc模块中的gc.is_tracked(obj)来查看一个对象是否被追踪。

import gc
a = dict()
gc.is_tracked(a)
>>>False

[!NOTE]

https://github.com/python/cpython/issues/48324

https://github.com/python/cpython/issues/48938

2008年，为了解决创造a list of tuples中大量空元组使得gc性能下降明显而做的优化。

此处有一个较为疑惑的点是，为什么在Python3.1中，减少了对新建的空字典的GC追踪而不取消对新建的空列表的追踪呢？当然字典这个结构在Python层面是非常重要的，对性能的影响也是巨大，但这不意味改变对新建空List的追踪不会带来性能上的提升，挖个坑补全下这个的历史原因及相关的实验。

分代回收

Python 程序启动后，内部可能会创建大量对象。如果每次执行标记清除法时，都需要遍历所有对象，多半会影响程序性能。为此，Python 引入分代回收机制——将对象分为若干“代”( generation )，每次只处理某个代中的对象，因此 GC 卡顿时间更短。

考察对象的生命周期，可以发现一个显著特征：一个对象存活的时间越长，它下一刻被释放的概率就越低。我们应该也有这样的亲身体会：经常在程序中创建一些临时对象，用完即刻释放；而定义为全局变量的对象则极少释放。

因此，根据对象存活时间，对它们进行划分就是一个不错的选择。对象存活时间越长，它们被释放的概率越低，可以适当降低回收频率；相反，对象存活时间越短，它们被释放的概率越高，可以适当提高回收频率。

对象存活的时间	释放的概率	GC检查的频率
长	低	低
短	高	高

Python 内部根据对象存活时间，将对象分为 3 代。

每个代都由一个 gc_generation 结构体来维护，定义于 Include/internal/pycore_gc.h 头文件：

struct gc_generation {
    PyGC_Head head;
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
                  generations */
};

• head ，可收集对象链表头部，代中的对象通过该链表维护；
• threshold ，仅当 count 超过本阀值时，Python 垃圾回收操作才会扫描本代对象；
• count ，计数器，不同代统计项目不一样；

每个 gc_generation 结构体链表头节点都指向自己，换句话说每个可收集对象链表一开始都是空的；计数器字段 count 都被初始化为 0 ；而阀值字段 threshold 则有各自的策略。

Python 调用 _PyObject_GC_Alloc 为需要跟踪的对象分配内存时，该函数将初生代 count 计数器加一，随后对象将接入初生代对象链表；当 Python 调用 PyObject_GC_Del 释放垃圾对象内存时，该函数将初生代 count 计数器减一；*_PyObject_GC_Alloc* 自增 count 后如果超过阀值( 700 )，将调用 collect_generations 执行一次垃圾回收( GC )。

collect_generations 函数从老生代开始，逐个遍历每个生代，找出需要执行回收操作( count>threshold )的最老生代。随后调用 collect_with_callback 函数开始回收该生代，而该函数最终调用 collect 函数。

collect 函数处理某个生代时，先将比它年轻的生代计数器 count 重置为 0 ；然后将它们的对象链表移除，与自己的拼接在一起后执行 GC 算法；最后，将下一个生代计数器加一。

• 系统每新增 701 个需要 GC 的对象，Python 就执行一次 GC 操作；
• 每次 GC 操作需要处理的生代可能是不同的，由 count 和 threshold 共同决定；
• 某个生代需要执行 GC ( count>threshold )，在它前面的所有年轻生代也同时执行 GC ；
• 对多个代执行 GC ，Python 将它们的对象链表拼接在一起，一次性处理；
• GC 执行完毕后，count 清零，而后一个生代 count 加一；

初生代触发 GC 操作，Python 执行 collect_generations 函数。它找出了达到阀值的最老生代是中生代，因此调用 collection_with_callback(1) ，1 是中生代在数组中的下标。

collection_with_callback(1) 最终执调用 collect(1) ，它先将后一个生代计数器加一；然后将本生代以及前面所有年轻生代计数器重置为零；最后调用 gc_list_merge 把可回收对象链表合并在一起。

• 每新增 701 个需要 GC 的对象，触发一次新生代 GC ；
• 每执行 11 次新生代 GC ，触发一次中生代 GC ；
• 每执行 11 次中生代 GC ，触发一次老生代 GC (老生代 GC 还受其他策略影响，频率更低)；
• 执行某个生代 GC 前，年轻生代对象链表也移入该代，一起 GC ；
• 一个对象创建后，随着时间推移将被逐步移入老生代，回收频率逐渐降低；

标记清除法

Python 采用标记清除法识别垃圾对象。该算法的输入是可收集对象链表，链表给出所有需要检测的对象；算法的输出是两个链表，其中一个包含 可达 ( reachable )对象，另一个包含 不可达 ( unreachable )对象。

标记清除算法在 collect 函数中实现，它位于 Modules/gcmodule.c ，步骤并不复杂。为避免深陷源码细节，我们先抽出身来进行一次直观考察。假设待检测可收集对象链表中的对象引用关系如下：

其中，数字表示引用计数，箭头表示引用关系，虚线表示链表外对象(来自其他年代)，

首先，我们需要找出根对象。这里根对象是指被本链表以外的对象引用或被 Python 虚拟机直接引用的对象，与上一小节讨论的略有不同。由于根对象存在来自外部的引用，不能安全释放，应该标记为 可达 ( reachable )。

根对象集合不难确定：我们只需遍历每个对象引用的对象，将它们的引用计数减一，最后计数不为零的就是根对象。

请注意，虚线表示外部对象，它既不会被遍历到，引用计数也不会被减一。然后从根节点对象出发，将所有不可达的节点标记为不可达节点，如最左边图中的三个对象均为不可达对象。这样一来，他们就是只存在循环引用的垃圾对象，可以被安全释放。

对于collect 函数的算法处理逻辑，它先将对象引用计数拷贝到 gc_refs 字段：

update_refs(young);

这是因为直接操作 ob_refcnt 字段的话，对象的引用计数就被破坏了，而且无法复原。操作 gc_refs 副本字段，就不存在这个问题。

接着，collect 函数调用 subtract_refs 遍历链表中每个对象，将它们引用的对象引用计数( gc_refs )减一。注意到，subtract_refs 函数调用 tp_traverse 函数，来遍历被一个对象引用的对象：

subtract_refs(young);

static int
visit_decref(PyObject *op, void *data)
{
    assert(op != NULL);
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        assert(_PyGCHead_REFS(gc) != 0); /* else refcount was too small */
        if (_PyGCHead_REFS(gc) > 0)
            // 将对象引用计数减一(gc_refs)
            _PyGCHead_DECREF(gc);
    }
    return 0;
}

static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = containers->gc.gc_next;
    // 遍历链表每一个对象
    for (; gc != containers; gc=gc->gc.gc_next) {
        // 遍历当前对象所引用的对象，调用visit_decref将它们的引用计数减一
        traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
        (void) traverse(FROM_GC(gc),
                       (visitproc)visit_decref,
                       NULL);
    }
}

经过这个步骤之后，根对象就被找出来了，它们的引用计数( gc_refs )不为零。

最后，collect 函数初始化一个链表 unreachable 来保存不可达对象，调用 move_unreachable 标记可达对象，并将不可达对象移入 unreachable 链表：

gc_list_init(&unreachable);
move_unreachable(young, &unreachable);

move_unreachable 遍历给定对象链表，如果一个对象的引用计数不为 0 ，就将它标记为可达( GC_REACHABLE )；否则将它标记为临时不可达，移入不可达链表。

// 遍历链表每个对象
while (gc != young) {
    PyGC_Head *next;

    // 如果引用计数不为0，说明它可达
    if (_PyGCHead_REFS(gc)) {
        PyObject *op = FROM_GC(gc);
        traverseproc traverse = Py_TYPE(op)->tp_traverse;
        assert(_PyGCHead_REFS(gc) > 0);
        // 将它标记为可达
        _PyGCHead_SET_REFS(gc, GC_REACHABLE);
        // 遍历被它引用的对象，调用visit_reachable将被引用对象标记为可达
        (void) traverse(op,
                        (visitproc)visit_reachable,
                        (void *)young);
        next = gc->gc.gc_next;
        if (PyTuple_CheckExact(op)) {
            _PyTuple_MaybeUntrack(op);
        }
    }
    else {
        next = gc->gc.gc_next;
        // 暂时移入不可达链表
        gc_list_move(gc, unreachable);
        _PyGCHead_SET_REFS(gc, GC_TENTATIVELY_UNREACHABLE);
    }
    gc = next;
}

如果一个对象可达，Python 还通过 tp_traverse 逐个遍历它引用的对象，并调用 visit_reachable 函数进行标记：

static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        const Py_ssize_t gc_refs = _PyGCHead_REFS(gc);

        if (gc_refs == 0) {
            // 引用计数为零，将计数设置为1，表明它是可达的
            _PyGCHead_SET_REFS(gc, 1);
        }
        else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
            // 如果对象被临时标记为不可达，将引用计数设置为1表明它是可达的
            // 并移回原链表继续处理
            gc_list_move(gc, reachable);
            _PyGCHead_SET_REFS(gc, 1);
        }
         else {
            assert(gc_refs > 0
                   || gc_refs == GC_REACHABLE
                   || gc_refs == GC_UNTRACKED);
         }
    }
    return 0;
}

如果被引用的对象引用计数为 0 ，将它的引用计数设为 1 ，之后它将被 move_unreachable 遍历到并设为可达；如果被引用的对象被临时移入 unreachable 链表，同样将它的引用计数设为 1 ，并从 unreachable 链表移回原链表尾部，之后它将被 move_unreachable 遍历到并设为可达。

当 move_unreachable 函数执行完毕，unreachable 链表中的对象就是不可达对象，可被安全回收。

Ref:

1. CPython设计与实现
2. Python源码深度剖析
3. CPython3.9源码