What causes [*a] to overallocate?
Mar 5
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:
python
1 answer
Accepted answer · original discussion
Mar 5
[*a] is internally doing the C equivalent of:
- Make a new, empty
list - Call
newlist.extend(a) - Returns
list.
So if you expand your test to:
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))
you'll see the results for getsizeof([*a]) and l = []; l.extend(a); getsizeof(l) are the same.
This is usually the right thing to do; when extending you're usually expecting to add more later, and similarly for generalized unpacking, it's assumed that multiple things will be added one after the other. [*a] is not the normal case; Python assumes there are multiple items or iterables being added to the list ([*a, b, c, *d]), so overallocation saves work in the common case.
By contrast, a list constructed from a single, presized iterable (with list()) may not grow or shrink during use, and overallocating is premature until proven otherwise; Python recently fixed a bug that made the constructor overallocate even for inputs with known size.
As for list comprehensions, they're effectively equivalent to repeated appends, so you're seeing the final result of the normal overallocation growth pattern when adding an element at a time.
To be clear, none of this is a language guarantee. It's just how CPython implements it. The Python language spec is generally unconcerned with specific growth patterns in list (aside from guaranteeing amortized O(1) appends and pops from the end). As noted in the comments, the specific implementation changes again in 3.9; while it won't affect [*a], it could affect other cases where what used to be "build a temporary tuple of individual items and then extend with the tuple" now becomes multiple applications of LIST_APPEND, which can change when the overallocation occurs and what numbers go into the calculation.
3 question comments
Use comments to ask for clarification. Post a solution as an answer.
Mar 5
list(a) operates entirely in C; it can allocate the internal buffer node by node as it iterates over a. [x for x in a] just uses LIST_APPEND a lot, so it follows the normal "overallocate a little, reallocate when necessary" pattern of a normal list. [*a] uses BUILD_LIST_UNPACK, which... I don't know what that does, other than apparently over-allocate all the time :)Mar 5
sys.getsizeof is the right tool, it just shows that list(a) used to overallocate. Actually What’s New In Python 3.8 mentions it: "The list constructor does not overallocate [...]".