Python 列表结构及内存分析

发表于 分类于 阅读次数： 本文字数： 6.8k
通过 CPython 源码，分析 Python 列表的底层结构和内存占用。

注意：以下内容均在 Python 3.9.13 上进行实验，其他版本可能有所不同。

问题导入

上篇文章 Python 三种方式生成列表的内存分析 讲到，python 中 list 初始占用空间为 56 个字节，但是这 56 个字节都是些什么内容呢，本文将进行分析

1
2
3
4
5
6
In [1]: a = []

In [2]: import sys

In [3]: sys.getsizeof(a)
Out[3]: 56

PyListObject 源码分析

cpython 中，列表的定义都是存储在 /Objects/listobject.c 中的，其中定义了一个 PyListObject 结构体，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;
  • allocated - 当前已为该 list 分配的内存大小，不表示 list 的长度，类型为 Py_ssize_t，即为 c 语言中 long 类型的别名，在 64 位系统上为 8 个字节
  • ob_item - 指向 list 中每个元素的指针向量。list[0] 即为 ob_item[0]，类型为 PyObject **，即为指向 PyObject 指针的指针，每个类型为指针的元素占用 8 个字节，所以 ob_item 占用的内存大小为 8 个字节，所指向对象占用的内存为 allocated * 8 个字节
  • PyObject_VAR_HEAD - 该指令为一个宏定义，实际内容为 PyVarObject ob_base;，PyVarObject 为一个结构体，定义如下：
1
2
3
4
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
  • ob_size - 该变量表示 list 的使用长度，类型为 Py_ssize_t，占用 8 个字节
  • PyObject - 该结构体为 python 中所有对象的基类，定义如下：
1
2
3
4
5
typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
} PyObject;
  • ob_refcnt - 该变量表示对象的引用计数，类型为 Py_ssize_t，占用 8 个字节
  • ob_type - 该变量表示对象的类型，类型为 PyTypeObject *，即为指向 PyTypeObject 的指针，所以 ob_type 占用的内存大小为 8 个字节
  • _PyObject_HEAD_EXTRA - 该指令为一个宏定义，实际内容为空，用于扩展 PyObject 结构体

综上，PyListObject 结构体如下所示

1
2
3
4
5
6
7
typedef struct {
    PyTypeObject *ob_type;  # 8
    Py_ssize_t ob_size;     # 8
    Py_ssize_t ob_refcnt;   # 8
    PyObject **ob_item;     # 8
    Py_ssize_t allocated;   # 8
} PyListObject;

由上可知，PyListObject 结构体默认占用 40 个字节，但为什么是 56 个字节呢？

PyList_New 源码分析

通过名称可知，该函数用于创建一个新的 list 对象，既然分析定义无法找出为什么，那么就分析创建的过程吧。

PyList_New 的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
PyObject *
PyList_New(Py_ssize_t size)
{
    PyListObject *op;

    // size 为负数时，抛出异常
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    // 创建 op 对象
    if (numfree) {
        // 内存优化，使用已经申请的内存块
        numfree--;
        op = free_list[numfree];
        _Py_NewReference((PyObject *)op);
    } else {
        // 此处实际创建出了 op 变量，即 PyListObject 结构体
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL)
            return NULL;
    }
    // 为 op 分配存储空间内容
    if (size <= 0)
        op->ob_item = NULL;
    else {
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    Py_SET_SIZE(op, size);
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

分析可知，主要逻辑为使用 PyObject_GC_New 函数创建一个 PyListObject 对象，该函数的实际逻辑最后定位到 _PyObject_GC_Alloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static PyObject *
_PyObject_GC_Alloc(int use_calloc, size_t basicsize)
{
    PyThreadState *tstate = _PyThreadState_GET();
    GCState *gcstate = &tstate->interp->gc;
    if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head)) {
        return _PyErr_NoMemory(tstate);
    }
    // 计算得到 size 的值
    size_t size = sizeof(PyGC_Head) + basicsize;

    PyGC_Head *g;
    if (use_calloc) {
        g = (PyGC_Head *)PyObject_Calloc(1, size);
    }
    else {
        g = (PyGC_Head *)PyObject_Malloc(size);
    }
    if (g == NULL) {
        return _PyErr_NoMemory(tstate);
    }
    assert(((uintptr_t)g & 3) == 0);  // g must be aligned 4bytes boundary

    g->_gc_next = 0;
    g->_gc_prev = 0;
    gcstate->generations[0].count++; /* number of allocated GC objects */
    if (gcstate->generations[0].count > gcstate->generations[0].threshold &&
        gcstate->enabled &&
        gcstate->generations[0].threshold &&
        !gcstate->collecting &&
        !_PyErr_Occurred(tstate))
    {
        gcstate->collecting = 1;
        collect_generations(tstate);
        gcstate->collecting = 0;
    }
    PyObject *op = FROM_GC(g);
    return op;
}

可以看到，最终 size 的计算方法为 size_t size = sizeof(PyGC_Head) + basicsize;

其中 basicsize 为 PyListObject 结构体的大小，即 40 个字节，PyGC_Head 的定义如下

1
2
3
4
5
6
7
8
9
typedef struct {
    // Pointer to next object in the list.
    // 0 means the object is not tracked
    uintptr_t _gc_next;

    // Pointer to previous object in the list.
    // Lowest two bits are used for flags documented later.
    uintptr_t _gc_prev;
} PyGC_Head;

PyGC_Head 存储了两个 uintptr_t 的指针变量。即为 16 个字节，故 PyListObject 创建出来后的结构如下所示

1
2
3
4
5
6
7
8
9
typedef struct {
    PyTypeObject *ob_type;  # 8
    Py_ssize_t ob_size;     # 8
    Py_ssize_t ob_refcnt;   # 8
    PyObject **ob_item;     # 8
    Py_ssize_t allocated;   # 8
    uintptr_t _gc_next;     # 8
    uintptr_t _gc_prev;     # 8
} PyListObject;

故最终 list 默认占用的空间为 56 个字节；但是，按照上述分析，列表的空间占用应该始终只有 56 个字节。因为 ob_item 为指针的指针，故无论列表中有多少个元素，ob_item 的大小始终为 8 个字节，故列表的大小始终为 56 个字节。但当进行列表扩容的时候。列表的大小会发生变化，这是为什么呢？

1
2
3
4
5
6
7
8
9
10
11
In [1]: import sys

In [2]: a = []

In [3]: sys.getsizeof(a)
Out[3]: 56

In [4]: a.append(1)

In [5]: sys.getsizeof(a)
Out[5]: 88

sys.getsizeof 源码分析

sys.get_sizeof 调用的 c 函数为 sys_getsizeof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static PyObject *
sys_getsizeof(PyObject *self, PyObject *args, PyObject *kwds)
{
    static char *kwlist[] = {"object", "default", 0};
    size_t size;
    PyObject *o, *dflt = NULL;
    PyThreadState *tstate = _PyThreadState_GET();

    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O:getsizeof",
                                     kwlist, &o, &dflt)) {
        return NULL;
    }

    size = _PySys_GetSizeOf(o);

    if (size == (size_t)-1 && _PyErr_Occurred(tstate)) {
        /* Has a default value been given */
        if (dflt != NULL && _PyErr_ExceptionMatches(tstate, PyExc_TypeError)) {
            _PyErr_Clear(tstate);
            Py_INCREF(dflt);
            return dflt;
        }
        else
            return NULL;
    }

    return PyLong_FromSize_t(size);
}

核心逻辑即为 size = _PySys_GetSizeOf(o);， _PySys_GetSizeOf 函数的实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
size_t
_PySys_GetSizeOf(PyObject *o)
{
    PyObject *res = NULL;
    PyObject *method;
    Py_ssize_t size;
    PyThreadState *tstate = _PyThreadState_GET();

    /* Make sure the type is initialized. float gets initialized late */
    if (PyType_Ready(Py_TYPE(o)) < 0) {
        return (size_t)-1;
    }

    method = _PyObject_LookupSpecial(o, &PyId___sizeof__);
    if (method == NULL) {
        if (!_PyErr_Occurred(tstate)) {
            _PyErr_Format(tstate, PyExc_TypeError,
                          "Type %.100s doesn't define __sizeof__",
                          Py_TYPE(o)->tp_name);
        }
    }
    else {
        res = _PyObject_CallNoArg(method);
        Py_DECREF(method);
    }

    if (res == NULL)
        return (size_t)-1;

    size = PyLong_AsSsize_t(res);
    Py_DECREF(res);
    if (size == -1 && _PyErr_Occurred(tstate))
        return (size_t)-1;

    if (size < 0) {
        _PyErr_SetString(tstate, PyExc_ValueError,
                          "__sizeof__() should return >= 0");
        return (size_t)-1;
    }

    /* add gc_head size */
    if (_PyObject_IS_GC(o))
        return ((size_t)size) + sizeof(PyGC_Head);
    return (size_t)size;
}

该函数存在一个逻辑 method = _PyObject_LookupSpecial(o, &PyId___sizeof__); 为寻找对象是否实现了 __sizeof__ 这个魔术方法，查看 PyListObject 对 __sizeof__ 的实现

1
2
3
4
5
6
7
8
9
static PyObject *
list___sizeof___impl(PyListObject *self)
/*[clinic end generated code: output=3417541f95f9a53e input=b8030a5d5ce8a187]*/
{
    Py_ssize_t res;

    res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
    return PyLong_FromSsize_t(res);
}

可见，获取列表的大小，实际上是获取了 PyListObject 结构体的大小，加上 allocated * sizeof(void*)，即为 allocated * 8，故列表的大小为 56 + allocated * 8。