是什么导致 [*a] 过度分配？

Question

显然 list(a) 没有过度分配，[x for x in a] 在某些点过度分配，而 [*a] 一直 过度分配?

以下是从 0 到 12 的大小 n 以及三种方法的结果大小（以字节为单位）：

0 56 56 56
1 64 88 88
2 72 88 96
3 80 88 104
4 88 88 112
5 96 120 120
6 104 120 128
7 112 120 136
8 120 120 152
9 128 184 184
10 136 184 192
11 144 184 200
12 152 184 208

这样计算，reproducable at repl.it，使用 Python 3.8:

from sys import getsizeof

for n in range(13):
    a = [None] * n
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]))

所以：这是如何工作的？ [*a] 如何过度分配？实际上，它使用什么机制从给定的输入创建结果列表？它是否在 a 上使用迭代器并使用类似 list.append 的东西？源代码在哪里？

（生成图像的Colab with data and code。）

放大到更小的n：

缩小到更大的 n:

Answer 1

[*a] is internally doing the C equivalent of:

新建一个空的list
致电newlist.extend(a)
Returns list.

因此，如果您将测试扩展到：

from sys import getsizeof

for n in range(13):
    a = [None] * n
    l = []
    l.extend(a)
    print(n, getsizeof(list(a)),
             getsizeof([x for x in a]),
             getsizeof([*a]),
             getsizeof(l))

Try it online!

您会看到 getsizeof([*a]) 和 l = []; l.extend(a); getsizeof(l) 的结果相同。

这通常是正确的做法；当 extending 时，您通常希望稍后添加更多内容，并且对于广义解包也类似，假设多个内容将一个接一个地添加。 [*a] 不是正常情况； Python 假设有多个项目或可迭代对象被添加到 list ([*a, b, c, *d])，因此在常见情况下过度分配可以节省工作。

相比之下，一个list由一个单一的、预定义的可迭代对象（list()）构造的在使用过程中可能不会增长或收缩，并且过度分配是不成熟的，除非证明不是这样； Python recently fixed a bug that made the constructor overallocate even for inputs with known size.

至于 list 推导式，它们实际上等同于重复 appends，因此您看到的是一次添加元素时正常过度分配增长模式的最终结果。

需要说明的是，none 这是语言保证。这就是 CPython 实现它的方式。 Python 语言规范通常不关心 list 中的特定增长模式（除了保证从末尾开始分摊 O(1) appends 和 pops ）。如评论中所述，具体实现在 3.9 中再次发生变化；虽然它不会影响 [*a]，但它可能会影响其他情况，即以前的 "build a temporary tuple of individual items and then extend with the tuple" 现在变成了 LIST_APPEND 的多个应用程序，这可能会在发生过度分配和进入的数字时发生变化计算。

Answer 2

这些将是 CPython 解释器的实现细节，因此在其他解释器中可能不一致。

就是说，您可以在这里看到理解力和 list(a) 行为的来源：

https://github.com/python/cpython/blob/master/Objects/listobject.c#L36

专为理解：

 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
...

new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

在这些行的正下方，有 list_preallocate_exact，它在调用 list(a) 时使用。

Answer 3

发生了什么的全貌，建立在其他答案和评论的基础上（尤其是，这也解释了为什么就这样完成了）。

反汇编显示BUILD_LIST_UNPACK被使用：

>>> import dis
>>> dis.dis('[*a]')
  1           0 LOAD_NAME                0 (a)
              2 BUILD_LIST_UNPACK        1
              4 RETURN_VALUE

已处理 in ceval.c，它构建一个空列表并扩展它（使用 a）：

        case TARGET(BUILD_LIST_UNPACK): {
            ...
            PyObject *sum = PyList_New(0);
              ...
                none_val = _PyList_Extend((PyListObject *)sum, PEEK(i));

_PyList_Extend uses list_extend:

_PyList_Extend(PyListObject *self, PyObject *iterable)
{
    return list_extend(self, iterable);
}

哪个calls list_resize with the sum of the sizes:

list_extend(PyListObject *self, PyObject *iterable)
    ...
        n = PySequence_Fast_GET_SIZE(iterable);
        ...
        m = Py_SIZE(self);
        ...
        if (list_resize(self, m + n) < 0) {

而overallocates如下：

list_resize(PyListObject *self, Py_ssize_t newsize)
{
  ...
    new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

让我们检查一下。使用上面的公式计算预期的点数，并通过将其乘以 8 来计算预期的字节大小（因为我在这里使用 64 位 Python）并添加一个空列表的字节大小（即列表对象的常量开销):

from sys import getsizeof
for n in range(13):
    a = [None] * n
    expected_spots = n + (n >> 3) + (3 if n < 9 else 6)
    expected_bytesize = getsizeof([]) + expected_spots * 8
    real_bytesize = getsizeof([*a])
    print(n,
          expected_bytesize,
          real_bytesize,
          real_bytesize == expected_bytesize)

输出：

0 80 56 False
1 88 88 True
2 96 96 True
3 104 104 True
4 112 112 True
5 120 120 True
6 128 128 True
7 136 136 True
8 152 152 True
9 184 184 True
10 192 192 True
11 200 200 True
12 208 208 True

除了 n = 0 之外的其他匹配项，list_extend 实际上 shortcuts，所以实际上也匹配：

        if (n == 0) {
            ...
            Py_RETURN_NONE;
        }
        ...
        if (list_resize(self, m + n) < 0) {

是什么导致 [*a] 过度分配？

What causes [*a] to overallocate?

python

python-3.x

list

cpython

python-internals