What causes [*a] to overallocate?

Question

Apparently list(a) doesn't overallocate, [x for x in a] overallocates at some points, and [*a] overallocates all the time?

Here are sizes n from 0 to 12 and the resulting sizes in bytes for the three methods:

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

Computed like this, reproducable at repl.it, using 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]))

So: How does this work? How does [*a] overallocate? Actually, what mechanism does it use to create the result list from the given input? Does it use an iterator over a and use something like list.append? Where is the source code?

(Colab with data and code that produced the images.)

Zooming in to smaller n:

Zooming out to larger n:

Answer 1

[*a] 在内部做 C 等价物：

1. 做一个新的，空的 list
2. 称呼 newlist.extend(a)
3. 返回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))

在线试试吧！

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

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

相比之下，list由单个预先设置的可迭代对象（with list()）构造的 a在使用过程中可能不会增长或缩小，并且在证明否则之前过度分配为时过早；Python 最近修复了一个错误，即使对于已知大小的输入，该错误也会使构造函数过度分配。

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

需要明确的是，这些都不是语言保证。这正是 CPython 实现它的方式。Python 语言规范通常不关心特定的增长模式list（除了保证最终摊销O(1) appends 和pops ）。如评论中所述，具体实现在3.9中再次发生变化；虽然它不会影响[*a]，但它可能会影响其他情况，其中过去是“构建tuple单个项目的临时对象，然后extend使用tuple” 现在变成了 的多个应用程序LIST_APPEND，当发生过度分配以及哪些数字进入计算时，这些应用程序可能会发生变化。

Answer 2

的全貌是什么情况，建立在其他的答案和评论（尤其是ShadowRanger的答案，这也解释了为什么它这样做）。

反汇编显示BUILD_LIST_UNPACK使用：

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

这是在 中ceval.c处理的，它构建一个空列表并扩展它（使用a）：

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

_PyList_Extend 用途 list_extend：

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

其中调用list_resize大小的总和：

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

并且过度分配如下：

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) {

Answer 3

这些将是 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).