Python 三种方式生成列表的内存分析

发表于 2023-03-01 分类于 Python 阅读次数：本文字数： 5.1k

通过 CPython 源码，分析 Python 三种方式生成列表的内存占用。

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

问题导入

使用不同方法生成相同结果的列表时，内存占用不同。

In [1]: import sys, dis

In [2]: sys.getsizeof([0] * 3)
Out[2]: 80

In [3]: sys.getsizeof([0 for _ in range(3)])
Out[3]: 88

In [4]: sys.getsizeof([0, 0, 0])
Out[4]: 120

初步分析

查看三者的字节码

In [5]: dis.dis("[0] * 3")
  1           0 LOAD_CONST               0 (0)
              2 BUILD_LIST               1
              4 LOAD_CONST               1 (3)
              6 BINARY_MULTIPLY
              8 RETURN_VALUE

In [6]: dis.dis("[0, 0, 0]")
  1           0 BUILD_LIST               0
              2 LOAD_CONST               0 ((0, 0, 0))
              4 LIST_EXTEND              1
              6 RETURN_VALUE

In [7]: dis.dis("[0 for _ in range(3)]")
  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x1047e05b0, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (range)
              8 LOAD_CONST               2 (3)
             10 CALL_FUNCTION            1
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x1047e05b0, file "<dis>", line 1>:
  1           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 8 (to 14)
              6 STORE_FAST               1 (_)
              8 LOAD_CONST               0 (0)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            4
        >>   14 RETURN_VALUE

分析可以知道，三者最主要的区别为

[0] * 3 使用了 BINARY_MULTIPLY 指令
[0, 0, 0] 使用了 LIST_EXTEND 指令
[0 for _ in range(3)] 使用了 LIST_APPEND 指令

列表乘法

BINARY_MULTIPLY 指令主要调用了 list_repeat 函数，该函数传入一个对象，和一个整数，返回一个新的列表，该列表的元素为原列表的元素重复 n 次。

list_repeat(PyListObject *a, Py_ssize_t n)
{
    ...
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) list_new_prealloc(size);
    ...
    return (PyObject *) np;
}

可以看到在代码第 7 行调用 list_new_prealloc(size) 进行了内存申请，申请的 size 为传入对象的占用大小乘以 n。

list_new_prealloc(Py_ssize_t size)
{
    ...
    op->ob_item = PyMem_New(PyObject *, size);
    ...
    op->allocated = size;
    return (PyObject *) op;
}

在 list_new_prealloc 定义中能看到，在代码第 4 行申请了 size 的内存

计算可知，Python 3.9 中，列表默认占用 56 个字节，在 64 位系统中，一个指针占用 8 个字节，因此列表占用内存为 56 + 8 * 3 = 80 个字节。

直接定义列表分析

LIST_EXTEND 指令主要调用了 list_extend 函数，该函数传入当前对象和一个可迭代对象，将可迭代对象的元素添加到当前对象中。

list_extend(PyListObject *self, PyObject *iterable)
{
    ...
    if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
                (PyObject *)self == iterable) {
        ...
        if (list_resize(self, m + n) < 0) {
            Py_DECREF(iterable);
            return NULL;
        }
    }
    ...
}

可以看到在代码第 7 行调用了 list_resize 函数，该函数主要是对列表进行扩容。

list_resize(PyListObject *self, Py_ssize_t newsize)
{
    ...
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize);
        return 0;
    }
    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    ...
}

看到在代码第 19 行计算了新内存的大小，计算公式为 (size + size // 4) + 6 后对 4 进行对齐。例如，需要的内存为 5，那么申请的内存大小为 (5 + 5 // 4) + 6 = 12 与 4 对齐 = 12 。在当前的例子中，需要的内存为 3，那么申请内存的大小为 3 + 3 // 4 + 6 = 9 与 4 对齐 = 8。根据上一节可以知道，直接定义列表占用的内存为 56 + 8 * 8 = 120

列表生成式分析

LIST_APPEND 指令主要调用了 list_append 函数，该函数传入当前对象和一个对象，将该对象添加到当前对象中。

list_append(PyListObject *self, PyObject *object)
/*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
{
    if (app1(self, object) == 0)
        Py_RETURN_NONE;
    return NULL;
}

app1(PyListObject *self, PyObject *v)
{
    ...
    if (list_resize(self, n+1) < 0)
        return -1;
    ...
}

list_append 函数调用了 app1 函数，该函数调用了 list_resize 函数，该函数主要是对列表进行扩容。每一次添加数据的时候，都会调用 list_resize 函数，同时，根据 list_resize 的定义，在上文代码第 4 到第 7 行中可知，如果内存足够，不需要扩容，那么列表生成式的执行逻辑就会变为：

list_resize(1) -> 开辟一个 4 个字节的内存
list_resize(2) -> 内存足够，不需要扩容
list_resize(3) -> 内存足够，不需要扩容

故列表生成式占用的内存为 56 + 8 * 4 = 88。

3.10 版本

有同学提到在 3.10 版本的效果不一样，这里也做一下分析。

In [2]: sys.getsizeof([0] * 3)
Out[2]: 80

In [3]: sys.getsizeof([0 for _ in range(3)])
Out[3]: 88

In [4]: sys.getsizeof([0, 0, 0])
Out[4]: 88

可以发现主要是 [0, 0, 0] 的内存发生了变化，这里单独分析下 3.10 中直接定义列表的内存占用

In [5]: dis.dis("[0, 0, 0]")
  1           0 BUILD_LIST               0
              2 LOAD_CONST               0 ((0, 0, 0))
              4 LIST_EXTEND              1
              6 RETURN_VALUE

看 Python 字节码依然调用的是 LIST_EXTEND 指令，但是在 3.10 版本中，LIST_EXTEND 指令的实现方法 list_extend 函数定义发生了改动，该函数的实现摘录如下：

list_extend(PyListObject *self, PyObject *iterable)
{
    ...
    if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
                (PyObject *)self == iterable) {
        ...
        if (self->ob_item == NULL) {
            if (list_preallocate_exact(self, n) < 0) {
                return NULL;
            }
            Py_SET_SIZE(self, n);
        }
        else if (list_resize(self, m + n) < 0) {
            Py_DECREF(iterable);
            return NULL;
        }
        ...
    }
}

可见，当列表对象初始为空的时候，会直接调用 list_preallocate_exact 函数，该函数的实现如下：

list_preallocate_exact(PyListObject *self, Py_ssize_t size)
{
    assert(self->ob_item == NULL);
    assert(size > 0);

    /* Since the Python memory allocator has granularity of 16 bytes on 64-bit
     * platforms (8 on 32-bit), there is no benefit of allocating space for
     * the odd number of items, and there is no drawback of rounding the
     * allocated size up to the nearest even number.
     */
    size = (size + 1) & ~(size_t)1;
    PyObject **items = PyMem_New(PyObject*, size);
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    self->allocated = size;
    return 0;
}

可以看到该函数中计算需要申请内存大小的方法为 size + 1 后与 2 对齐 ，本例子中 size=3，3 + 1 后与 2 对齐 = 4。故在 3.10 版本中 [0, 0, 0] 占用的内存为 56 + 8 * 4 = 88。

分析思路来自 gaogaotiantian