10.3 CPython 内存分配器

CPython 的内存分配器位于系统的内存分配器之上，并拥有它自己的分配算法。该算法与系统内存分配器类似，不同之处在于它是为 CPython 定制的：

• 大部分需要分配的内存都是小块且大小固定的内存，因为 PyObject 占 16 字节，PyASCIIObject 占 42 字节，PyCompactUnicodeObject 占 72 字节，PyLongObject 占 32 字节；

• pymalloc 内存分配器最多只能分配 256 KB 大小的内存，更大的内存需要交给系统的内存分配器去处理；

• pymalloc 内存分配器使用 GIL 而不是系统的线程安全性检查。

为了更好的解释这种情况，我们来做个类比：你可以想象有一个 CPython 足球俱乐部的主场体育场。为了帮助管理人群，CPython 足球俱乐部实现了一个系统，这个系统将体育场分为 A 至 E 区，每个区都有 1 至 40 排的座位：

图10.3.1 CPython 内存体育场

在体育场前端，第 1 至 10 排是较宽敞的高级座位，每排有 80 个座位。在体育场后端，第 31 至 40 排是经济舱座位，每排有 150 个座位。

Python 内存分配算法也具有类似的特点：

• 就像体育场有座位一样，pymalloc 算法中也有 block；

• 就像座位可以是高级、普通和经济型，这些内存块也都是一系列固定大小的。你不能带上自己的躺椅；

• 就像同样大小的座位被排成一排一样，也需要将同样大小的内存块放入 pool 中。

核心存储单元会记录 block 存储的位置和在 pool 中可用的 block 数量，这与体育场分配座位类似。当体育场一排满员后，就将使用下一排。当一个 pool 的 block 达到最大时，就会使用下一个 pool。而 pool 被分组存储在 arena 中，就像体育场会将数排座位分配到几个片区一样。

这种策略有以下几种优点：

1. 这种算法在 CPython 的主要应用场景（小内存且生命周期较短的对象）下有更好的性能；

2. 这种算法使用了 GIL 而不是系统的线程锁检测；

3. 算法使用内存映射（mmap()）而不是堆上内存分配。

相关源文件

以下是与内存分配器相关的源文件：

文件	功能
Include/pymem.h	PyMem 分配器 API
Include/cpython/pymem.h	PyMem 内存分配器配置 API
Include/internal/pycore_mem.h	垃圾回收的数据结构及内部 API
Objects/obmalloc.c	域分配器的实现和pymalloc的实现

表10.3.1 内存分配器相关的源文件

重要术语

以下是本章中你将遇到的一些重要术语：

• 申请的内存大小需要和 block 大小匹配；

• 相同大小的 block 要放进同一个内存池（pool）中；

• pool 被分组存储在 arena 中。

Blocks，Pools 和 Arenas

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

即便是在现代高速内存架构中，连续内存的加载速度也比碎片化的内存更快。所以使用连续的内存块是有益的。

Arenas

Arena 需要在系统堆上进行内存分配，对于支持匿名内存映射的系统则会使用 mmap() 函数进行分配。内存映射有助于减少 arena 上的堆碎片。

下面是系统堆中四个 arenas 的可视化表示：

System Heap：系统堆

图10.3.2 Arenas的可视化表示

Arenas 对应数据结构 arenaobject:

字段	类型	用途
address	uintptr_r	arena 的内存地址
pool_address	block *	指向要分配的下一个 pool 的指针
nfreepools	uint	arena 中可用 pool 的数量（已被释放的 pool 加从未被分配过的 pool）
ntotalpools	uint	arena 中 pool 的总数，不论其是否可用
freepools	pool_header*	可用 pool 的单向链表
nextarena	arena_object*	下一个 arena（见注）
prevarena	arena_object*	前一个 arena（见注）

表10.3.2 arenaobject 数据结构

注

一系列的 Arenas 通过其数据结构中的双向链表指针（nextarena 和 prevarena）链接在一起。

如果当前的 arena 未被分配，就需要使用 nextarena 成员。nextarena 成员链接了所有独立、存储在全局变量 unused_arena_objects （一个单向链表）中的 arenas。

当这个 arena 与至少有一个可用 pool 的 arena 关联时，它的 nextarena 和 prevarena 都在双向链表 usable_arenas 中。这个链表根据 nfreepools 成员的值按升序排序。

Pools

在 arena 中，最多可以为大小是 512 字节的 block 创建 pool。对于 32 位系统，block 大小的步长是 8 字节，所以总共有 64 种不同大小的 block：

以字节为单位的请求	分配的 block 大小	类型尺寸索引
1-8	8	0
9-16	16	1
17-24	24	2
25-32	32	3
...	...	...
497-504	504	62
505-512	512	63

表10.3.3 32 位系统的 block 大小分类

对于 64 位系统，内存块大小的步长是 16 字节，所以有 32 种不同大小的 block：

以字节为单位的请求	分配的 block 大小	类型尺寸索引
1-8	16	0
9-16	32	1
17-24	48	2
25-32	64	3
...	...	...
497-504	496	30
505-512	512	31

表10.3.4 64 位系统的 block 大小分类

Pool 的大小都是 4096 字节（4 KB），所以一个 arena 中总是包含 64 个 pool。

图10.3.3 Arena与Pool的关系

Pool 将按需分配。当没有可用 pool 可以用于请求的类型尺寸索引时，就将调配一个新的 pool。Arena 中有一个 "高水位线" 的概念，用于查询已经调配的 pool 数量。

Pool 共有 3 种状态：

1. 满载（Full）：pool 中所有可用的 block 都已被分配；

2. 部分使用（Used）：pool 已被分配，其中部分 block 已被设置，但还有剩余的空间；

3. 空闲（Empty）：pool 已被分配，但没有 block 被设置。

在 arena 中，高水位线位于最后一个被分配的 pool：

图10.3.4 高水位线示意图

Pool 包含数据结构 poolp，是结构体 pool_header 的静态内存分配。pool_header 类型有以下属性：

字段	类型	用途
ref	uint	当前这个 pool 中分配的 block 数量
freeblock	block *	指向这个 pool 空闲列表头的指针
nextpool	pool_header*	指向下一个此类型尺寸的 pool 的指针
prevpool	pool_header*	指向前一个此类型尺寸的 pool 的指针
arenaindex	uint	可用 pool 的单向链表
szidx	uint	此 pool 的类型尺寸索引
nextoffset	uint	未使用的 block 字节数
maxnextoffset	uint	在 pool 满载之前，nextoffset 的最大数量

表10.3.5 pool_header结构体属性

特定大小的 pool 会使用双向链表在前后链接同一大小的 pool。当内存分配的发生时，通过这个双向链表就很容易从相同大小的 pool 之间跳转。当内存分配发生时，通过此双向链表可以很容易地在 arena 内相同大小的 pool 之间跳转。

Pool Tables

在 arena 中 pool 的存储单元名为 pool table，pool table 是记录了已被部分使用的 pool 的双向循环链表头节点。

内存池表按 pool 的类型尺寸索引 i 进行分类。基于索引 i，usedpools[i + i] 指向所有已被部分使用且具有相同大小索引的 pool 双向链表头节点，

Pool table 有如下基本特性：

• 当一个 pool 饱和后，它将不再链接在 usedpools[] 中；

• 如果已饱和的 pool 中有一个 block 被释放了，pool 将重新回到部分使用的状态。此时会把刚刚释放过内存的 pool 链接到 usepools[] 的前面，这样下一次分配同样大小的内存时将复用刚刚释放内存的 block；

• 当一个 pool 变为空闲状态时，这个 pool 将从链表 usedpools[] 中脱离，同时链接到它所在的 arena 中的单向链表 freepools 前面。

Blocks

在 pool 内，内存被分配到一个个 block 中。Block 有以下特征：

• 在一个 pool 中，可以分配和释放固定大小尺寸索引的 block；

• 在一个 pool 中，所有可用的 block 都链接在单向链表 freeblock 上；

• 当一个 block 被释放后，它会被重新插入到 freeblock 链表的最前面；

• 当 pool 初始化时，只有前两块内存被链接到 freeblock 链表上；

• 只要 pool 处于部分使用的状态，就至少有一个 block 可以用于内存分配。

这里是已被分配了部分内存的 pool 示意图，它由已使用、已被释放和未被分配过的 block 组合而成：

图10.3.5 已被部分使用的 Pool 示意图

内存块分配 API

当使用 pymalloc 的内存域请求一块内存时，将会调用 pymalloc_alloc() 函数。这个函数是插入断点，然后逐步调试代码去检验你对于 block、pool 和 arena 相关知识的好地方。

// Object/obmalloc.c line 1590
static inline void*
pymalloc_alloc(void *ctx, size_t nbytes)
{
...

首先内存请求 nbytes 既不能为 0，也不能超过 SMALL_REQUEST_THRESHOLD (512 字节)，现以 nbytes = 30 为例进行说明：

if (UNLIKELY(nbytes == 0)) {
    return NULL;
}
if (UNLIKELY(nbytes > SMALL_REQUEST_THRESHOLD)) {
    return NULL;
}

在 64 位系统上，可以求解出 30 字节 对应的 block 类型尺寸索引是 1，这对应第二行类型尺寸索引（17-32 字节）。

此目标的 pool 是 usedpools[1 + 1] (即 usedpools[2]) ：

uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
poolp pool = usedpools[size + size];
block *bp;

接下来，首先需要校验该类型尺寸索引的 pool 是否可用（包括部分使用）。如果 freeblock 链表在该 pool 的末尾，则说明 pool 中仍有未分配过内存的 block。

此时可以调用 pymalloc_pool_extend() 去扩展 freeblock 链表：

    if (LIKELY(pool != pool->nextpool)) {
        /*
         * There is a used pool for this size class.
         * Pick up the head block of its free list.
         */
        ++pool->ref.count;
        bp = pool->freeblock;
        assert(bp != NULL);

        if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL)) {
            // Reached the end of the free list, try to extend it.
            pymalloc_pool_extend(pool, size);
        }
    }

如果没有可用的 pool，就会创建一个新的 pool 并将其中第一个 block 返回。allocate_from_new_pool() 函数将创建一个新的 pool 并自动将它插入到 usedpools 中。

    else {
        /* There isn't a pool of the right size class immediately
        * available: use a free pool.
        */
        bp = allocate_from_new_pool(size);
    }
    return (void *)bp;
}

最终，函数会返回一个新的 block 地址。

使用 Python Debug API

sys 模块包含了一个内部方法 _debugmallocstats()，用于获取在特定类型尺寸索引的 pool 中已使用的 block 数量。同时，它还将打印已分配和已回收的 arena 数量以及已用 block 的数量等数据。

你可以使用这个函数去查看运行时内存的使用情况：

$ ./python -c "import sys; sys._debugmallocstats()"

Small block threshold = 512, in 32 size classes.

class 	size 	num pools 	blocks in use 	avail blocks
----- 	---- 	--------- 	------------- 	------------
0 		16 		1 			181 			72
1 		32 		6 			675 			81
2 		48 		18 			1441 			71
...
2 free 18-sized PyTupleObjects * 168 bytes each = 336
3 free 19-sized PyTupleObjects * 176 bytes each = 528

上述输出展现了内存类型尺寸索引表、内存分配情况和其他的一些统计信息。