python - 内存中列表的大小

Question

我刚刚试验了内存中 python 数据结构的大小。我写了以下片段:

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

我在以下配置上测试了代码:

• Windows 7 64bit，Python3.1:输出为:52 40 所以 lst1 有 52 字节，lst2 有 40 字节。
• Ubuntu 11.4 32bit with Python3.2:输出为 48 32
• Ubuntu 11.4 32bit Python2.7:48 36

谁能向我解释为什么这两种尺寸不同，尽管它们都是包含 1 的列表？

在 getsizeof 函数的 python 文档中，我发现了以下内容:...如果对象由垃圾收集器管理，则会增加额外的垃圾收集器开销。 我的小宝贝可能就是这种情况例子？

Answer 1

这是一个更完整的交互式 session ，它将帮助我解释发生了什么(Windows XP 32 位上的 Python 2.6，但这并不重要):

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

请注意，空列表比包含 [1] 的列表要小一些。但是，当添加一个元素时，它会变得更大。

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

空列表

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

一个元素的列表

当创建具有单个元素 [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 的情况下，为一个指针分配了空间。 4 个字节(在我的 32 位机器上)。

追加到空列表

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

• PyList_Append 调用 app1
• app1 询问列表的大小(并得到 0 作为答案)
• app1 然后用 size+1 调用 list_resize(在我们的例子中是 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;
}

让我们做一些数学运算

让我们看看我在文章开头的 session 中引用的数字是如何达到的。

所以 36 字节是列表数据结构本身在 32 位上所需的大小。对于单个元素，为一个指针分配了空间，因此这是 4 个额外字节 - 总共 40 个字节。到目前为止还可以。

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

确实，一切都有意义:-)