Lists from the inside: growth, shrinking, and the price of the front

Two numbers instead of one

A list in CPython is an object plus a separate array of pointers; the elements themselves live anywhere. As the array grows it can sometimes be extended in place and sometimes has to be moved in its entirety, and which it will be is not knowable in advance. So that this is not paid for on every append, the array is allocated with room to spare.

That slack is the second number. Neither len nor any list method shows it, but sys.getsizeof counts it: a list's size is the header plus one pointer for each ALLOCATED slot, not for each element.

def capacity(seq):
    return (sys.getsizeof(seq) - sys.getsizeof([])) // struct.calcsize("P")

Identical lists, different memory

One thing separates the five ways: whether the interpreter knew the length up front. A literal, [0] * 10 and list(range(10)) do — room is taken for exactly ten elements. A comprehension and a generator do not, they add one at a time, and the same over-allocation as append applies: sixteen slots instead of ten, 184 bytes instead of 136.

The over-allocation follows a formula

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

The new length, plus an eighth of it, plus six. The over-allocation is proportional to the length, which is why the number of reallocations over a long run of appends grows logarithmically: twenty-four over the first six hundred.

The formula is an implementation detail of CPython and appears nowhere in the language documentation. On 3.12.3, 3.13.7 and 3.14.7 it is the same.

What deletion does

Nine hundred elements are removed from the front of a thousand-element list, in two ways. The length afterwards is the same — a hundred. The memory is not: on 3.13 and 3.14, L.pop(0) leaves 184 slots and del L[0] leaves a thousand.

The reason is that from 3.13 deletion by index is done by a different function, and that one never calls list_resize. The same holds at the other end: L.pop() gives capacity back, del L[-1] does not.

No version promises when a list shrinks. If a list has shrunk a lot and lives on, there is one reliable move — rebuild it: L.copy(), list(L) or L[:] bring the capacity down to the length on every build checked.

Why the front is expensive

An insertion at the front shifts the whole accumulated tail, so the cost of one such operation grows with the length. The check is doubling: double the length and insert(0) time grows fourfold while append time grows twofold. The cost of one append does not move at all — about twenty nanoseconds at two and a half thousand elements and at twenty thousand alike.

The standard answer is collections.deque, and both its ends really are cheap. The price is the index: on a hundred thousand elements d[50000] costs 2418.3 nanoseconds against 9.0 for a list. A list you keep taking the first element from is a deque written wrong; a deque you index into the middle of is a list written wrong.

What to do with this

Build a list at its final length when the length is known. Do not remove from the front in a loop — reach for deque. Rebuild a list that shrank a lot and lives on. And do not rely on shrinking, nor on its absence: this behaviour has already changed once without a line in "What's New".

A list has two lengths, and this article is about the second one.

Everybody knows the first: len(L), the number of elements. The second has no public name anywhere in Python — the number of pointer slots already allocated. The usual words are length and capacity, and nearly everything a list does is explained by the second number rather than the first.

As long as capacity stays invisible, none of this can be explained. Why two lists of the same ten numbers take different amounts of memory. Why append is cheap on average when growing the array sometimes means moving all of it. Why, after nine hundred removals from a thousand-element list, it may still be occupying room for a thousand — and exactly when that happens.

The article works upward: first the two numbers and how they relate, then what deletion does, and only then time. Time comes last not because it matters least but because without the first two parts it reads as a pile of unconnected facts.

Part I. Length and capacity

Why a list carries spare room

A list in CPython is three levels, and they are worth separating up front: the PyListObject itself, a separate contiguous array of pointers, and the objects themselves, which live anywhere in memory. Two things follow from that: what getsizeof counts (the header plus the array, not the objects), and why removing from the front shifts pointers rather than elements.

An array can sometimes be extended in place: realloc grows the allocation without moving it when there is free space past its end. What cannot be done is to count on that.

The way to check is the address of the array itself — the ob_item field before and after. Capacity changes not by one but in jumps (the jumps themselves are covered below), and at each of them the run compares two addresses: the same one means nothing was copied. On 3.13.7 with the GIL enabled (on the free-threaded builds this check is not made — ctypes reads the field by offset, and the object layout there is different) — bench/lists/growth.py, block 6:

Both outcomes occur — and that is all that follows. The proportion does not reproduce: on 3.12.3 and 3.14.7 the same run gives twelve against twelve, and it drifts between runs as well, because it depends on the state of the allocator and the history of the process. When there is no free space past the end, the allocation moves along with all of its contents, and which time that will be is not knowable in advance.

So the point is not that growing in place is impossible — it is how many times you pay for it. Without spare room the capacity would change on every append; with it, it changes twenty-four times over the first six hundred, and not every one of those costs a copy.

The way out is to allocate with room to spare. The comment above the function that does this states both the reason and the result:

"Amortized" is not a hedge here: an individual append that lands on a boundary is expensive — it copies the whole array. The boundaries are just spaced so that over a long run of additions the cost flattens into a constant.

That spare room is the second number. Neither len nor any list method shows it. The size of the object does, and here is why.

Capacity is read from getsizeof, and that is not a workaround

CPython's list.__sizeof__ counts by allocated slots, not by length:

list___sizeof___impl(PyListObject *self)
{
    size_t res = _PyObject_SIZE(Py_TYPE(self));
    Py_ssize_t allocated = FT_ATOMIC_LOAD_SSIZE_RELAXED(self->allocated);
    res += (size_t)allocated * sizeof(void*);
    return PyLong_FromSize_t(res);
}

That gives the way capacity is read in every measurement in this article:

def capacity(seq):
    return (sys.getsizeof(seq) - sys.getsizeof([])) // struct.calcsize("P")

The divisor is the pointer size rather than an eight: on a 64-bit build it is eight, but writing eight bakes the word size into the formula.

It needs no ctypes — and the usual way of reading the same field does: it addresses object fields through id(obj). In the run this way stands next to a ctypes read of the same field, and the run COMPARES the two rather than declaring them equal: on builds with the GIL they agreed, while on the free-threaded ones ob_size at the same offset reads as zero — the object layout there is different. That is why every measurement takes capacity from getsizeof.

Identical lists, different memory

Five ways to build a ten-element list. The length is ten in all of them; the size is 136 bytes for three and 184 for two. One thing separates them: whether the interpreter knew the length up front.

A literal and [0] * 10 know it from the way they are written: both the number of elements listed and the number of repetitions are settled before the list starts filling. range has __len__ for the same purpose, and the list constructor uses it. Room is taken for exactly ten elements, with none to spare.

A list comprehension and list() of a generator do not: a generator says nothing about its length, and elements arrive one at a time. So the same over-allocation as for append applies, and at ten elements it gives sixteen slots.

Forty-eight bytes per list is nothing. But it is nothing multiplied by the number of lists, and it is worth knowing where lists run into the millions: where a comprehension only walks a range, replacing it with list(range(...)) removes that nothing entirely and changes nothing about the result. Where the comprehension computes something, there is no such replacement — and then the spare is the price of computing, not of carelessness.

The growth formula

The spare is not approximate. There is one formula, and it is in the source:

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

Read it as: the new length, plus an eighth of it, plus six, rounded down to a multiple of four. The over-allocation is a FRACTION rather than a constant: the longer the list, the more is taken in reserve — which is exactly why the number of reallocations over a long run of appends grows logarithmically rather than linearly.

Next to the formula sits a second branch, for the case where the length jumps by a lot at once, as in extend:

if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
    new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

Its point is that nothing is over-allocated when the jump is already larger than the over-allocation would be. With append the length grows by one, so this branch never fires — which is why the rest of the article only concerns the first formula.

bench/lists/growth.py checks it at every capacity jump: over the first six hundred appends there are twenty-four of them, and all twenty-four matched on five builds: 3.12.3, 3.13.7, 3.14.7 and the free-threaded 3.13.7t and 3.14.7t — every number, down to the last one. The first eight jumps, as the run prints them:

The same sequence is written out in the comment beside the formula: "The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...". After six hundred appends the length is 600 and the capacity 672 — seventy-two slots of spare.

Part II. What a list gives back

"A list never releases memory" is wrong, and wrong twice

The claim travels in two shapes, and neither survives a check. One caveat up front: what follows is about CAPACITY, the size of the pointer array. Whether the memory went back to the operating system is a question not for the list but for the memory allocator, which usually keeps the freed block. How much memory the process holds according to the system (its RSS) cannot be predicted from these numbers.

First shape: "capacity only grows". It does not only grow. The condition under which the array is LEFT as it is sits in the same list_resize, and shrinking begins where that condition fails:

if (allocated >= newsize && newsize >= (allocated >> 1)) {
    assert(self->ob_item != NULL || newsize == 0);
    Py_SET_SIZE(self, newsize);
    return 0;
}

While the new length is at least half the capacity, the array stays and only the length changes. Once the length drops below half, control falls through and the array is reallocated smaller. The run shows exactly that: a thousand pop() calls from the end produce twelve capacity reductions.

Second shape: "if it releases, it always releases". Also no — and this is where the article's real subject begins.

Two operations with one meaning and different traces

Nine hundred elements are removed from the front of a thousand-element list, in two ways. The length afterwards is the same: one hundred. The memory is not.

On 3.12 both operations leave a capacity of 184 — both shrank the array. On 3.13 and 3.14, L.pop(0) leaves the same 184 while del L[0] leaves 1000: a hundred-element list still occupies room for a thousand, 8056 bytes against 1528.

The same holds from the other end, and this half is the one nobody expects. Each operation below was repeated nine hundred times over a thousand-element list, measured on 3.13.7 with bench/lists/shrink.py:

L.pop() gives capacity back. del L[-1] does not. Two lines that look equally harmless in review.

Why: two different paths in the source

The cause was not inferred from the numbers but read. Before 3.13, deletion by index did nothing itself and handed the work to the general slice-assignment path:

static int
list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
{
    if (!valid_index(i, Py_SIZE(a))) {
        PyErr_SetString(PyExc_IndexError,
                        "list assignment index out of range");
        return -1;
    }
    if (v == NULL)
        return list_ass_slice(a, i, i+1, v);

list_ass_slice shifts the tail and calls list_resize — the one with the shrink condition. That is where the capacity reduction came from.

In 3.13 the function gained a variant that runs under a lock, and it performs the deletion itself:

static int
list_ass_item_lock_held(PyListObject *a, Py_ssize_t i, PyObject *v)
{
    ...
    PyObject *tmp = a->ob_item[i];
    if (v == NULL) {
        Py_ssize_t size = Py_SIZE(a);
        for (Py_ssize_t idx = i; idx < size - 1; idx++) {
            FT_ATOMIC_STORE_PTR_RELAXED(a->ob_item[idx], a->ob_item[idx + 1]);
        }
        Py_SET_SIZE(a, size - 1);
    }

list_resize is not called at all here: the length drops in place and the array stays as it was. Neither list_ass_slice nor list_resize appears on this path any more.

The change arrived with the free-threaded build — that is where the atomic stores come from, and the _lock_held suffix in the name: the function expects the list to be locked already by whoever called it. The capacity behaviour is a side effect rather than the goal, and that shows in the fact that "What's New In Python 3.13" does not mention it at all: not under language changes, not under optimizations.

What frees capacity for certain

Since the behaviour of an operation cannot be relied on, it helps to know what works regardless of version. bench/lists/shrink.py tries the options on a list whose capacity stayed at a thousand after nine hundred del calls:

The first three are the same action: build a new list whose length is known up front. Room is taken for exactly a hundred elements, and the old array is released along with the old list.

The last row is not a recipe but a warning: append followed by pop does change the capacity, yet it brings it not to the length but to whatever the formula gives. One hundred and sixteen instead of a hundred — that is spare again.

There is one practical rule: a list that has shrunk a lot and must live on should be REBUILT. L = L.copy() is not superstition: rebuilding by any of the three answers the same way on all the builds checked, while the deletion operations do not.

Part III. The price of the front

Quadratic behaviour, shown rather than named

"insert(0) is quadratic" is true, but on its own it is just words. The check is doubling: if time grows as the square, doubling the length gives four times the time.

Filling a list through insert(0), measured with bench/lists/ops.py:

And the same table for append, from the same run, where the ratio is about two and the cost of a single operation does not move at all:

The right-hand column is the whole difference. With append the cost of one operation is constant: about twenty nanoseconds at two and a half thousand elements and at twenty thousand alike. With insert(0) it grows with the length, because every insertion shifts everything already there.

pop(0) against del L[0]: same work, different price

The change from Part II shows up in more than bytes.

Each operation below empties a ten-thousand-element list, inside a single run of 3.13.7 with bench/lists/ops.py:

L.pop(0) costs seven times what del L[0] costs. Both remove the first element and both shift the tail; what separates them is the same path in the implementation — the general slice-assignment route against an in-place loop.

Look at the first two rows of the same table: from the END of the list those two paths cost 23.6 and 21.3 nanoseconds, a difference of a few per cent. At the end there is nothing to shift, so what shows is the per-call overhead alone — and that is nearly the same on both paths. The sevenfold gap appears where every call shifts the whole tail: what separates these two paths is not the checks before the work but what each of them does with the tail.

What this number cannot be used to claim is that the whole sevenfold difference falls on list_resize. The paths diverge in more than one place: pop also RETURNS the removed element, handing out a reference and looking after its lifetime, while del returns nothing. How much each of those costs is not something the measurement breaks down: it shows the total price of two different paths, and list_resize on one of them is a cause named from the source, not a measured summand.

The second thing this number cannot be used to claim is that "del got faster". That would compare time across versions, which this project forbids: the builds have different compilers and different flags, and nothing here separates "the language got faster" from "the build got faster". What can be claimed is exactly what was measured inside one run: on 3.13.7 two operations with the same meaning cost different amounts and leave the object in different states.

What deque charges for this

The standard answer to "I need both ends" is collections.deque, and the promise there is official:

The measurement agrees: for a deque, appendleft costs 29.4 nanoseconds against 29.3 for d.append, and popleft costs 26.9 against 27.2 for d.pop. Against nine hundred nanoseconds for insert(0) that is a different class of thing.

But the same documentation carries the other half: "Indexed access is O(1) at both ends but slows to O(n) in the middle". Here is what that costs on a hundred thousand elements, each expression repeated a thousand times per round — bench/lists/ops.py:

For the list the three numbers nearly coincide — the index does not depend on position. For the deque the middle costs hundreds of times what the ends cost: this is not a list with two cheap ends but a chain of BLOCKS — not a linked list of single elements and not an array, but a chain of chunks of several elements each, whose middle has to be walked to.

So the practical criterion is not about "which is faster" but about WHAT YOU DO with the container. Need access by arbitrary index — a list, and then the front is expensive. Need both ends and sequential traversal — a deque, and then the index is expensive. A list you keep taking the first element from is a deque written wrong.

Part IV. Practice

import struct
import sys


def capacity(seq):
  return (sys.getsizeof(seq) - sys.getsizeof([])) // struct.calcsize("P")


a = list(range(1000))
b = list(range(1000))

for _ in range(900):
  a.pop(0)

for _ in range(900):
  del b[0]

print(len(a), capacity(a))
print(len(b), capacity(b))

100 184
100 1000

100 184
100 184

100 1000
100 1000

100 100
100 100

Part V. What to do with this

Four rules that follow from the measurements

Build a list at its final length when the length is known. list(range(n)), a literal and [0] * n take room for exactly the elements; a comprehension and a generator take it with slack. On one list that is forty-eight bytes, on a million it is forty-eight megabytes.

Do not work with the front of a list in a loop. The cost of one such operation grows with the length: at ten thousand elements an insertion at the front costs nine hundred nanoseconds against twenty for append, and a removal from the front costs 1734.2 nanoseconds through del L[0] and 12,076.6 through L.pop(0). If both ends are needed, use collections.deque; if an index into the middle is needed as well, what is needed is a different algorithm rather than a different container.

Rebuild a list that shrank a lot and lives on. L.copy() brings the capacity down to the length on all five builds checked, while del brings it down on none of the four builds from 3.13 onwards; on 3.12.3 it still did. And separately: a list gives back CAPACITY, not memory to the operating system — the memory allocator usually keeps the freed block, so the memory the process holds (its RSS) may not change after a rebuild.

Do not rely on shrinking, nor on its absence. No version promises when a list gives capacity back. What is measured here is the behaviour of five specific builds, and it has already changed once without a line in "What's New".

Version history

How this was measured

The numbers in this article come from these scripts. Each opens from here, together with the record of its run.

Bytes and capacity — comparable across versions, recorded on all five builds, including two free-threaded ones:

• bench/lists/growth.py
• bench/lists/shrink.py

Time — one record, one build:

• bench/lists/ops.py

The basis for the exercises in "Practice":

• bench/lists/practice.py

Python 3.12.3 (GCC 13.3.0), 3.13.7 (Clang 20.1.4), 3.14.7 (Clang 22.1.3) and the free-threaded 3.13.7t, 3.14.7t; Intel Xeon 2.80 GHz, 2 vCPU, 64-bit. Capacity and bytes are comparable across versions — that is object layout. Time is not: the builds have different compilers and different flags, and these measurements cannot separate "the language got faster" from "the build got faster". Time was taken on 3.13.7 with the GIL enabled only.

Fragments of Objects/listobject.c are quoted verbatim at tags v3.12.3 and v3.13.7.