记一次列表预分配空间的锅

Python猫

修改于 2019-07-12 18:03:43

6190

修改于 2019-07-12 18:03:43

文章被收录于专栏：Python无止境Python无止境

花下猫语：Python 中的列表是可变对象，但是在每次扩容的时候，并不是要加入多少新元素，就申请多少新的内存空间，而是采用了超额分配的机制，在所需空间之外，还会多分配一些空间。

我之前的文章《Python对象的空间边界：独善其身与开放包容》介绍过这个特性，今天再分享一篇文章，对此问题做了更详细的专题介绍。

作者：weapon

原文：https://zhuanlan.zhihu.com/p/47006584

起步

两个存储元素内容相同的列表占用内存空间可能会不一样。

甚至 a == b 都是成立的。是什么导致了占用的空间不一致的呢？

列表对象的存储方式

Python 中 list 的实现方式和 C++ 的 vector 类似，它并不是存多少东西就申请多少内存，它会申请一块较大的内存，避免每次新增元素都要进行内存申请和元素拷贝。当空间不足以容纳新元素时会进行扩容。

上图中 [0] 时是确定的元素个数，就只申请容纳一个元素空间，而 append 追加的方式会导致 list 对象扩容。

解答

为了解释最开始图片里的问题，还要先知道乘法 * 和 *= 是两个不同的操作符。这点上可以通过字节码来得到：

import dis
def fun():
    a = [0]
    a = a * 10
    b = [0]
    b *= 10

dis.dis(fun)

相关的字节码为：

6 LOAD_FAST                0 (a)
 8 LOAD_CONST               2 (10)
10 BINARY_MULTIPLY          # * 操作符
12 STORE_FAST               0 (a)
...
20 LOAD_FAST                1 (b)
22 LOAD_CONST               2 (10)
24 INPLACE_MULTIPLY         # *= 操作符
26 STORE_FAST               1 (b)

我们初学时总是会将 a *= n 理解为 a = a * n （当然这里理解是没错的），深入后就会发现他们的不同了。用 Python 中的魔术方法来说就是一个会调用 __mul__ 一个会调用 __imul__ 。

而 list 对象是 C 实现的，自然是调用 C 函数了，乘法操作会调用 list_repeat()；*= 会调用list_inplace_repeat()。

[listobject.c  v3.6.5]
static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
    ...
    size = Py_SIZE(a) * n;
    if (size == 0)
        return PyList_New(0);
    np = (PyListObject *) PyList_New(size);  // 创建容纳size个空间的列表
    ...
}

从这可以看出 list_repeat 需要多少空间就申请多少空间，从这里也可以看出乘法操作是返回一个新的列表对象。

再来看看 list_inplace_repeat ：

[listobject.c  v3.6.5]
static PyObject *
list_inplace_repeat(PyListObject *self, Py_ssize_t n)
{
    ...
    size = PyList_GET_SIZE(self);
    ...
    if (list_resize(self, size*n) < 0)
        return NULL;
    ...
}

代码中试图通过 list_resize 来进行扩容，并告诉它这个列表需要容纳 size * n 个元素，那么 resize 函数里面会申请比所需的空间还要大点的内存吗？显然是的：

[listobject.c  v3.6.5]
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    ...
    new_allocated = newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
    ...
}

resize 后的空间总是比所需要的大的。按照这里的扩容规则，如果一个空列表通过 append 不断往里面添加元素，那么空间占用会是 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

所以这个 *= 会引起列表 resize，而比 * 的方式占用空间大；解释完毕。