Python列表在内存中的大小

Question

我刚刚尝试了一下Python数据结构在内存中的大小。我写了以下代码片段：

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

我在以下配置中得到了以下输出：

• Windows 7 64位，Python3.1：52 40（因此lst1有52个字节，lst2有40个字节）
• 带有Python3.2的Ubuntu 11.4 32位：输出为48 32
• Ubuntu 11.4 32位Python2.7：48 36

有人能解释一下为什么这两个大小不同吗？尽管两者都是包含1的列表。

在Python的getsizeof函数文档中，我发现了以下内容：

...如果对象由垃圾收集器管理，则会添加额外的垃圾收集器开销。

在我的小例子中是否可能是这种情况？

- halex

---

列表不是逐个分配的，而是以“块”为单位进行分配（随着列表增长，块的大小也会增加）。这样做是为了使附加数据的摊销成本低廉。因此，我猜想在这两种情况下分配器的工作方式是不同的。但是，你为什么如此关心列表的分配方式呢？如果需要了解某些东西的大小，请使用sys.getsizeof()函数。 - andrew cooke

@andrew cooke：请把它作为答案，这基本上就是全部内容。 - user395760

@andrew-cooke 我只是对低级实现感到好奇，并不会在真实世界的问题中使用它。 - halex

@halex：你可以阅读实现，Python是开源的。 - Jochen Ritzel

@Jochen：我很好奇，所以我做了那个。请看下面的答案。 - Eli Bendersky

@riaz-rizvi，我不知道你为什么删除了你的答案，但它非常好和清晰。 - not2qubit

Answer 1

这是一个更详细的互动会话，将帮助我解释正在发生的事情（Python 2.6在Windows XP 32位上，但实际上并不重要）。

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

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

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

空列表

当创建空列表[]时，不会分配元素的空间 - 这可以在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时，会分配一个指针的空间。在我的32位系统上是4个字节。

向空列表添加元素

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

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

让我们做些数学题

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

所以，在32位系统上，列表数据结构本身需要36字节的大小。对于单个元素，会为一个指针分配空间，因此额外需要4个字节，总共40字节。到目前为止没问题。

当对空列表调用app1时，它将使用size=1调用list_resize。根据list_resize的过度分配算法，1之后最接近的可用大小是4，因此将分配4个指针的空间。4 * 4 = 16字节，36 + 16 = 52。

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

- Eli Bendersky

---

这是我遇到的所有编程语言/库中List.append()的标准分配策略。我想我本来就会猜到这是原因，即使没有读过你的答案（但现在我已经读过了，所以我无法确定）。不管怎样，非常详细的答案。 - ripper234

@ripper234：是的，分配策略很常见，但我想知道增长模式本身。教科书上关于摊销线性运行时间的例子通常提到2的幂次方。这似乎是一种不寻常的模式，仍然满足线性行为的公式 - 我觉得这非常有趣。 - Eli Bendersky

有趣的是，“增长模式是：”一条有关代码策略的注释实际上并没有描述该策略。它从基础超额分配开始，如果新的大小在9的哪一侧则为3或6，然后每8个增加1个超额分配。（我怀疑该注释早于当前版本的超额分配策略）。 - teepark

@teepark：您能详细说明一下吗？根据我的粗略计算，我认为代码符合注释。但请记住，一旦超额分配到8个位置，下一个“newsize”请求将是9。 - Eli Bendersky

那么，我在加载文件时应该使用 numpy column_stack 或类似的方式来附加列表，而不是 .append() 吗？这样会更有性能优势吗？ - wordsforthewise

Answer 2

你正在看列表如何分配空间（我想也许你只是想知道事物有多大 - 在这种情况下，使用sys.getsizeof()）。

当向列表添加内容时，可能会发生以下两种情况：

1. 额外的项目适合剩余空间。 2. 需要额外的空间，因此创建一个新列表，并将内容复制过去，然后再添加额外的内容。

由于第二种情况很昂贵（即使是复制指针，也需要与要复制的项目数量成正比的时间，因此随着列表变大，时间也会增长），我们希望尽量减少这种情况的发生。因此，我们不仅仅添加一点点空间，而是添加一整块空间。通常，所添加的空间大小与已使用的空间相似 - 这样数学计算出来，内存分配的平均成本在多次使用中只与列表大小成正比。

所以你看到的是与这种行为有关的。我不知道具体细节，但如果[]或[1]（或两者）是特殊情况，只分配足够的内存（为了在这些常见情况下节省内存），然后添加操作会执行上述描述的“获取新块”的操作来增加更多内存。

但我不知道具体细节 - 这只是动态数组一般工作方式。Python中列表的确切实现将被精心调整，以使其对典型的Python程序最优化。所以我真正想说的是，你不能完全相信列表的大小来告诉你它包含了多少 - 它可能包含额外的空间，并且额外的空闲空间的数量很难判断或预测。

一个巧妙的替代方法是将列表制作成(value, pointer)对，其中每个指针指向下一个元组。通过这种方式，你可以逐步扩展列表，尽管总内存使用量更高。这就是链表（Python使用的更像是向量或动态数组）。 艾利的出色回答解释了[]和[1]都被精确分配，但是向[]添加元素会额外分配一块内存。代码中的注释就是我上面所说的（这被称为“过度分配”，数量与我们拥有的大小成比例，以使平均（“摊销”）成本与大小成比例）。

- andrew cooke

Answer 3

这是列表增长模式的快速演示。更改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

- Dean Stamler

Answer 4

公式根据系统架构而变化 (size-36)/4 适用于32位机器，(size-64)/8 适用于64位机器

36,64 - 基于机器的空列表大小 4,8 - 基于机器的单个元素大小

- user12732063