Python列表在内存中的大小

Question

我刚刚试着测量了一下Python数据结构在内存中占用的大小。我写了下面这段代码：

import sys
lst1=[]
lst1.append(1)
lst2=[1]
print(sys.getsizeof(lst1), sys.getsizeof(lst2))

在不同的环境下，我得到了以下结果：

• 在64位的Windows 7上，使用Python3.1时，输出是 52 40（这意味着 lst1 占用52字节，而 lst2 占用40字节）
• 在32位的Ubuntu 11.4上，使用Python3.2时，输出是 48 32
• 在32位的Ubuntu 11.4上，使用Python2.7时，输出是 48 36

有没有人能告诉我，为什么这两个列表的大小不同，尽管它们都是包含一个数字1的列表呢？

在Python的文档中，我找到了关于 getsizeof 函数的说明：

...如果对象是由垃圾回收器管理的，会增加额外的垃圾回收开销。

这是不是我这个小例子中的情况呢？

Answer 1

这里有一个关于列表增长模式的简单演示。改变range()函数中的第三个参数会让输出结果和listobject.c中的注释看起来不一样，但当我们只是添加一个元素时，结果似乎是完全准确的。

allocated = 0
for newsize in range(0,100,1):
    if (allocated < newsize):
        new_allocated = (newsize >> 3) + (3 if newsize < 9 else 6)
        allocated = newsize + new_allocated;
    print newsize, allocated

Answer 2

你在查看列表是怎么分配内存的（我想你可能只是想看看它们有多大 - 如果是这样，可以用 sys.getsizeof() 来查看）。

当你往列表里添加东西时，会发生两种情况：

1. 额外的项目可以放进剩余的空间里。

2. 需要更多空间，所以会创建一个新的列表，把原来的内容复制过去，然后再添加新的东西。

第二种情况比较耗时（复制东西，甚至是指针，所花的时间和要复制的东西数量成正比，所以当列表变大时，这个时间也会增加），我们希望尽量少发生这种情况。因此，我们不是只增加一点空间，而是增加一大块。通常，增加的空间大小和当前使用的空间差不多，这样算下来，分配内存的平均成本就只和列表的大小成正比。

所以你看到的情况和这个行为有关。我不知道具体的细节，但如果 [] 或 [1]（或者两者）是特殊情况，只分配了足够的内存（为了节省这两种常见情况的内存），然后在追加时就会进行上面提到的“抓取新块”的操作，增加更多空间，我也不会感到惊讶。

不过我不知道具体的细节 - 这只是动态数组的一般工作方式。Python中列表的具体实现会经过精细调整，以便对典型的Python程序来说是最优的。所以我想说的是，你不能完全依赖列表的大小来判断它里面到底有多少东西 - 它可能会有额外的空间，而这些额外的空闲空间的数量很难判断或预测。

一个不错的替代方案是将列表做成 (值, 指针) 的对，每个指针指向下一个元组。这样你可以逐步增加列表的大小，尽管总的内存使用会更高。这就是链表（而Python使用的更像是向量或动态数组）。

Eli的精彩回答解释了 [] 和 [1] 是如何精确分配内存的，但向 [] 追加内容时会分配额外的一块。代码中的注释就是我上面说的（这叫做“过度分配”，增加的量和我们已有的空间成比例，这样平均（“摊销”）成本就和大小成正比）。

Answer 3

这里有一个更详细的互动示例，可以帮助我解释发生了什么（在Windows XP 32位上使用Python 2.6，但其实这并不重要）：

>>> import sys
>>> sys.getsizeof([])
36
>>> sys.getsizeof([1])
40
>>> lst = []
>>> lst.append(1)
>>> sys.getsizeof(lst)
52
>>> 

注意，空列表的大小比包含一个元素的列表[1]要小一些。不过，当你往空列表里添加元素时，它的大小会大幅增加。

这是因为在CPython的源代码中，Objects/listobject.c的实现细节。

空列表

当创建一个空列表[]时，并不会为元素分配空间——这可以在PyList_New中看到。在32位机器上，列表数据结构本身需要36个字节的空间。

包含一个元素的列表

当创建一个包含单个元素[1]的列表时，除了列表数据结构本身所需的内存外，还会为一个元素分配空间。同样，这可以在PyList_New中找到。给定size作为参数，它会计算：

nbytes = size * sizeof(PyObject *);

然后得到：

if (size <= 0)
    op->ob_item = NULL;
else {
    op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
    if (op->ob_item == NULL) {
        Py_DECREF(op);
        return PyErr_NoMemory();
    }
    memset(op->ob_item, 0, nbytes);
}
Py_SIZE(op) = size;
op->allocated = size;

所以我们看到，当size = 1时，会为一个指针分配空间。在我的32位机器上是4个字节。

向空列表添加元素

当在空列表上调用append时，会发生以下情况：

• PyList_Append调用app1
• app1询问列表的大小（得到的答案是0）
• app1然后调用list_resize，传入size+1（在我们的例子中是1）
• list_resize有一个有趣的分配策略，这在其源代码中的注释中有总结。

这里是：

/* 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().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

让我们做一些计算

让我们看看我在文章开头提到的数字是如何得出的。

所以，36个字节是32位机器上列表数据结构本身所需的大小。对于一个单独的元素，会额外分配4个字节的空间——总共40个字节。到这里为止都没问题。

当在空列表上调用app1时，它会以size=1调用list_resize。根据list_resize的过度分配算法，1之后下一个可用的最大大小是4，因此会为4个指针分配空间。4 * 4 = 16个字节，加上36个字节，总共52个字节。

确实，一切都说得通 :-)