Списки изнутри: рост, сжатие и цена работы с началом

Два числа вместо одного

Список в CPython — это объект плюс отдельный массив указателей; сами элементы лежат где угодно. Массив при росте иногда удаётся расширить на месте, а иногда приходится перенести целиком, и заранее неизвестно, как выйдет. Чтобы платить за это не на каждом append, место берётся с запасом.

Длина вместе с запасом и есть второе число — ёмкость. Её не показывает ни len, ни какой-либо метод списка, зато её учитывает sys.getsizeof: размер списка — это заголовок плюс один указатель на каждое выделенное место, а не на элемент.

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

Одинаковые списки, разное место

Пять способов различаются одним: знал ли интерпретатор длину заранее. Литерал, [0] * 10 и list(range(10)) знают — место берётся ровно под десять элементов. Включение и генератор не знают, добавляют элементы по одному, и срабатывает тот же механизм запаса, что у append: шестнадцать мест вместо десяти, 184 байта вместо 136.

Запас берётся по формуле

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

Новая длина плюс её восьмая часть плюс шесть. Запас пропорционален длине, и поэтому число перевыделений на длинной череде append растёт логарифмически: на первых шестистах добавлениях их двадцать четыре.

Формула — деталь реализации CPython, в документации языка её нет. На 3.12.3, 3.13.7, 3.14.7 и свободнопоточных 3.13.7t, 3.14.7t она одна и та же.

Что происходит при удалении

Из списка в тысячу элементов удаляют девятьсот — двумя способами. Длина в итоге одинаковая, сто. А память — нет: на 3.13 и 3.14 L.pop(0) оставляет 184 места, а del L[0] — тысячу.

Причина в том, что удаление по индексу с 3.13 делает другая функция, и list_resize она не вызывает вовсе. То же и с конца списка: L.pop() ёмкость отдаёт, del L[-1] — нет.

Ни одна версия при этом не обещает, когда список сжимается. Если список сильно уменьшился и живёт дальше, надёжный способ один — пересобрать его: L.copy(), list(L) или L[:] приводят ёмкость к длине на всех проверенных сборках.

Почему начало дорого

Вставка в начало сдвигает весь уже накопленный хвост, и цена одной такой операции растёт вместе с длиной. Проверяется удвоением: при росте длины вдвое время insert(0) растёт вчетверо, а время append — вдвое. Цена одного append при этом не меняется вовсе: около двадцати наносекунд и на двух с половиной тысячах элементов, и на двадцати тысячах.

Стандартный ответ — collections.deque, и оба его конца действительно дёшевы. Платят за это индексом: на ста тысячах элементов d[50000] стоит 2418,3 наносекунды против 9,0 у списка. Список, из которого постоянно снимают первый элемент, — это deque, написанный неправильно; deque, в который лезут по индексу в середину, — список, написанный неправильно.

Что из этого делать

Строить список сразу нужной длины, если она известна. Не снимать с начала в цикле — брать deque. Пересобирать список, который сильно уменьшился и живёт дальше. И не полагаться ни на сжатие, ни на его отсутствие: это поведение уже менялось один раз без единой строки в «Что нового».

Кроме длины у списка есть второе число, и об этом вся статья.

Длину знают все: len(L) — сколько в списке элементов. Второе число — сколько мест под указатели уже выделено — не показывает ни одно публичное имя. Его обычно называют ёмкостью, и почти всё поведение списка объясняется именно им, а не длиной.

Не видя ёмкости, многого не объяснить: почему два списка из десяти одинаковых чисел занимают разное место; почему append в среднем дёшев, хотя массив при росте иногда приходится переносить целиком; почему список в тысячу элементов после девятисот удалений может по-прежнему занимать место под тысячу — и когда именно так бывает.

Статья движется снизу вверх: сначала два числа и связь между ними, затем удаление и лишь потом время. Время идёт последним не потому, что оно неважно, а потому, что без первых двух частей замеры времени выглядят набором несвязанных фактов.

Часть I. Длина и ёмкость

Зачем списку запас

Список в CPython устроен в три уровня, и их стоит сразу различать: сам объект PyListObject, отдельный непрерывный массив указателей и элементы — объекты, которые лежат где угодно в памяти. Отсюда понятно и что именно считает getsizeof (заголовок плюс массив, без объектов), и почему при удалении из начала сдвигаются указатели, а не элементы.

Иногда массив удаётся удлинить на месте: realloc расширяет выделенный блок, не перенося его, если за концом блока есть свободное место. Но рассчитывать на это нельзя.

Проверить это можно по адресу самого массива — значению поля ob_item до и после. Ёмкость меняется не на единицу, а скачками (о них ниже), и на каждом скачке прогон сравнивает два адреса: если адрес тот же, ничего не копировалось. На 3.13.7 с включённым GIL (на свободнопоточных сборках эта проверка не делается — ctypes читает поле по смещению, а раскладка объекта там другая), блок 6 прогона bench/lists/growth.py:

Из таблицы следует только одно: встречаются оба исхода. Пропорция не воспроизводится: на 3.12.3 и 3.14.7 тот же прогон даёт двенадцать на двенадцать, да и от запуска к запуску она меняется, потому что зависит от состояния аллокатора и истории процесса. Если за концом блока свободного места нет, блок переезжает вместе со всем содержимым, и заранее неизвестно, на каком скачке это случится.

Так что вопрос не в том, возможно ли расширение, а в том, сколько раз за него приходится платить. Без запаса ёмкость менялась бы на каждом append; с запасом она меняется двадцать четыре раза за первые шестьсот — и копировать массив приходится не при каждом из этих скачков.

Выход — выделять место с запасом. Комментарий над функцией, которая за это отвечает, объясняет и зачем это нужно, и что это даёт:

«В среднем» здесь не смягчение: отдельный append, попавший на границу, может стоить дорого — если массиву некуда расти на месте, он копируется целиком. Но границы расставлены так, что на длинной череде добавлений эта стоимость распределяется и в пересчёте на один append остаётся постоянной.

Длина вместе с запасом — это и есть второе число, ёмкость. Её не показывает ни len, ни какой-либо другой метод списка. Зато она видна по размеру объекта — и вот почему.

Ёмкость можно узнать из getsizeof, и это не обходной путь

list.__sizeof__ в CPython считает размер по числу выделенных мест, а не по длине:

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);
}

Так ёмкость и вычисляется во всех замерах этой статьи:

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

Делитель — размер указателя, а не восьмёрка: на 64-битной сборке он равен восьми, но, если написать восьмёрку, в формулу окажется зашита разрядность.

Такому способу не нужен ctypes, а обычному способу прочитать то же поле — нужен: тот обращается к полям объекта по id(obj). В прогоне этот способ идёт рядом с чтением того же поля через ctypes, и прогон сравнивает их результаты, а не считает их совпадающими заранее: на сборках с GIL они сошлись, а на свободнопоточных ob_size по тому же смещению читается как ноль — раскладка объекта там другая. Поэтому во всех замерах ёмкость берётся из getsizeof.

Одинаковые списки, разное место

Пять способов построить список из десяти элементов. Длина у всех десять; размер — 136 байт у трёх и 184 у двух. Различаются они одним: знал ли интерпретатор длину заранее.

Литерал и [0] * 10 знают её из самой записи: сколько элементов перечислено и сколько раз повторено, известно ещё до того, как список начал заполняться. У range для этого есть __len__, и конструктор списка им пользуется. Место берётся ровно под десять элементов, запаса нет.

Списковое включение и list от генератора не знают: генератор о своей длине ничего не сообщает, и элементы добавляются по одному. Значит, работает тот же механизм запаса, что и у append, и на десяти элементах он даёт шестнадцать мест.

184 байта против 136 — сорок восемь байт на список, шесть пустых мест по восемь. Мелочь, но она умножается на число списков, и о ней стоит помнить там, где списков миллионы: если включение только перебирает range, замена на list(range(...)) убирает этот запас целиком и ничего не меняет в результате. Если же включение что-то вычисляет, такой замены нет, и тогда запас — цена вычисления, а не небрежность.

Формула роста

Запас берётся не «на глаз», а по формуле, и в исходнике она одна:

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

Читается она так: новая длина плюс её восьмая часть плюс шесть, с округлением вниз до кратного четырём. Иначе говоря, запас — не константа, а доля: чем длиннее список, тем больше места берётся впрок, и именно поэтому число перевыделений на длинной череде append растёт логарифмически, а не линейно.

Рядом с формулой в исходнике стоит вторая ветка — на случай, когда длина растёт сразу на много элементов, как при extend:

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

Смысл её такой: если скачок длины и так больше запаса, запас не берётся. При append длина растёт на единицу, и эта ветка не срабатывает никогда, поэтому дальше речь только о первой формуле.

Прогон bench/lists/growth.py проверяет её на каждом скачке ёмкости: на первых шестистах append их двадцать четыре, и совпали все двадцать четыре на пяти сборках: 3.12.3, 3.13.7, 3.14.7 и свободнопоточных 3.13.7t и 3.14.7t — во всех числах, до последнего. Первые четырнадцать скачков:

Ровно эта последовательность выписана и в комментарии рядом с формулой: The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... (Последовательность роста такая: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...)

Часть II. Что список отдаёт обратно

«Список никогда не отдаёт память»: неверно, причём дважды

Это утверждение встречается в двух формах, и обе не выдерживают проверки. Сразу оговорка: дальше речь идёт о ёмкости, то есть о размере массива указателей. Вернулась ли при этом память операционной системе, решает не список, а распределитель памяти: освободившийся кусок он обычно держит у себя. Сколько памяти процесс занимает по данным системы (RSS), по этим числам предсказать нельзя.

Первая форма: «ёмкость только растёт». Это не так. Условие, при котором массив оставляют как есть, записано в той же list_resize, и там, где оно не выполнено, начинается сжатие:

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

Пока новая длина не меньше половины ёмкости, массив остаётся прежним и меняется только длина. Как только длина опускается ниже половины, выполнение идёт дальше, и массив перевыделяется под меньший размер. Это видно и в прогоне: тысяча pop() с конца даёт двенадцать уменьшений ёмкости.

Вторая форма: «раз отдаёт, то отдаёт всегда». Тоже нет — и здесь начинается то, ради чего написана статья.

Две операции с одним смыслом и разными последствиями

Из списка в тысячу элементов удаляют девятьсот — с начала, двумя способами. Длина в итоге одинаковая: сто. А занятая память — нет.

На 3.12 обе операции оставляют ёмкость 184, то есть обе сжали массив. На 3.13 и 3.14 L.pop(0) оставляет те же 184, а del L[0] оставляет 1000: список из ста элементов продолжает занимать место под тысячу, 8056 байт против 1528.

То же происходит и с другого конца — а вот этого обычно не ждут. Каждая операция повторена девятьсот раз над списком из тысячи элементов, 3.13.7, bench/lists/shrink.py:

L.pop() ёмкость отдаёт. del L[-1] — нет. Две строки, которые на ревью выглядят одинаково безобидно.

Почему так: два разных пути в исходнике

Причину не пришлось выводить из чисел: она прочитана в исходнике. До 3.13 удаление по индексу само ничего не делало, а передавало работу общему пути присваивания срезу:

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 сдвигает хвост и вызывает list_resize — тот самый, с условием сжатия. Отсюда и уменьшение ёмкости.

В 3.13 у функции появился вариант, который работает под блокировкой и удаляет элемент сам:

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 здесь не вызывается вовсе: длина уменьшается на месте, массив остаётся прежним. Ни list_ass_slice, ни list_resize на этом пути больше не встречаются.

Изменение пришло вместе со свободнопоточной сборкой — отсюда и атомарные записи, и суффикс _lock_held в имени: функция рассчитывает, что вызывающий код уже заблокировал список. Поведение ёмкости при этом — побочный эффект, а не цель, и это видно по тому, что в «Что нового в Python 3.13» о нём нет ни строки: ни в разделе об изменениях языка, ни в разделе об оптимизациях.

Что освобождает ёмкость наверняка

Раз на поведение операции полагаться нельзя, полезно знать, что работает независимо от версии. bench/lists/shrink.py перебирает варианты над списком, у которого после девятисот del ёмкость осталась тысячей:

Первые три способа — по сути одно и то же действие: построить новый список, длина которого известна заранее. Место берётся ровно под сто элементов, а старый массив освобождается вместе со старым списком.

Последняя строка — не рецепт, а предупреждение: append с последующим pop ёмкость меняет, но приводит её не к длине, а к тому, что даст формула. Сто шестнадцать вместо ста — это снова запас.

Практическое правило одно: если список сильно уменьшился и должен жить дальше, его надо пересобрать. L = L.copy() — не суеверие: пересборка любым из трёх способов даёт одинаковый результат на всех проверенных сборках, а операции удаления — нет.

Часть III. Цена работы с началом

Квадратичность не на словах, а в замерах

«insert(0) квадратичен» — верно, но пока это только слова. Проверить это можно удвоением: если время растёт квадратично, то при вдвое большей длине получается вчетверо больше времени. Наполнение списка через insert(0), замер bench/lists/ops.py:

Та же таблица для append из того же прогона — здесь отношение около двух, а цена одной операции не меняется вовсе:

Правая колонка и есть вся разница. У append цена одной операции постоянна: около двадцати наносекунд и на двух с половиной тысячах элементов, и на двадцати тысячах. У insert(0) она растёт вместе с длиной, потому что каждая вставка сдвигает всё, что уже есть.

pop(0) против del L[0]: та же работа, разная цена

Изменение, описанное в части II, видно не только в байтах. Каждая операция ниже опустошает список из десяти тысяч элементов; всё снято в одном запуске 3.13.7, bench/lists/ops.py:

L.pop(0) дороже del L[0] в семь раз. Обе операции удаляют первый элемент и обе сдвигают хвост; различаются они всё тем же — путём в реализации: общий путь присваивания срезу против цикла на месте.

Обратите внимание на первые две строки той же таблицы: с конца списка те же две операции стоят 23,6 и 21,3 наносекунды, то есть разница — считаные проценты. В конце сдвигать нечего, и видны только накладные расходы вызова — у обеих операций они почти одинаковы. Семикратная разница возникает там, где на каждый вызов приходится сдвиг всего хвоста: эти два пути отличаются не проверками перед работой, а тем, что каждый из них делает с хвостом.

Утверждать по этому числу, что вся семикратная разница приходится на list_resize, нельзя. Пути расходятся не в одном месте: pop ещё и возвращает снятый элемент, то есть отдаёт наружу ссылку и следит за её временем жизни, а del ничего не возвращает. Сколько стоит каждое из этих различий, замер не показывает: он даёт суммарную цену двух разных путей, а list_resize на одном из них — причина различия, указанная по исходнику, а не измеренное слагаемое.

Нельзя по нему утверждать и того, что «del стал быстрее». Это было бы сравнением времени между версиями, а оно здесь ничего не значит: у сборок разные компиляторы и разные флаги, и разделить «стал быстрее язык» и «стала быстрее сборка» нечем. Утверждать можно ровно то, что измерено внутри одного запуска: на 3.13.7 две операции с одинаковым смыслом стоят по-разному и оставляют объект в разном состоянии.

Чем за это платит deque

Стандартный ответ на задачу «работать с обоими концами» — collections.deque, и его поведение обещано официально:

Замер это подтверждает: у deque appendleft стоит 29,4 наносекунды против 29,3 у d.append, а popleft — 26,9 против 27,2 у d.pop. По сравнению с девятьюстами наносекундами на insert(0) это другой класс.

Но в той же документации есть и вторая половина: Indexed access is O(1) at both ends but slows to O(n) in the middle (Доступ по индексу — O(1) на обоих концах, но замедляется до O(n) в середине). Вот во что это обходится на ста тысячах элементов; каждое выражение повторено по тысяче раз за круг замера, bench/lists/ops.py:

У списка все три числа почти одинаковы — время доступа по индексу не зависит от позиции. У deque середина дороже краёв в сотни раз: это не список с двумя дешёвыми концами, а цепочка блоков — не связный список из отдельных элементов и не массив, а связанные куски по нескольку элементов, и до середины приходится идти по цепочке.

Отсюда практический критерий, и он не про «что быстрее», а про то, что вы делаете с контейнером. Нужен доступ по произвольному индексу — список, и тогда работа с началом обойдётся дорого. Нужны оба конца и обход подряд — deque, и тогда дорого обойдётся индекс. Список, из которого постоянно снимают первый элемент, — это deque, написанный неправильно.

Часть IV. Практика

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

Часть V. Что с этим делать

Четыре правила, которые следуют из замеров

Строить список сразу нужной длины, если она известна. list(range(n)), литерал, [0] * n берут место ровно под элементы; включение и генератор — с запасом. На одном списке это сорок восемь байт, на миллионе — сорок восемь мегабайт.

Не работать с началом списка в цикле. Цена одной такой операции растёт вместе с длиной: на десяти тысячах элементов вставка в начало стоит девятьсот наносекунд против двадцати у append, а снятие с начала — 1734,2 наносекунды через del L[0] и 12 076,6 через L.pop(0). Если нужны оба конца — collections.deque; если нужен ещё и доступ по индексу к середине — значит, нужен другой алгоритм, а не другой контейнер.

Пересобирать список, который сильно уменьшился и живёт дальше. L.copy() приводит ёмкость к длине на всех пяти проверенных сборках, а del не приводит её ни на одной из четырёх сборок 3.13 и новее; на 3.12.3 он её ещё уменьшал. И отдельно: список отдаёт ёмкость, а не память операционной системе — освободившийся кусок распределитель памяти обычно держит у себя, так что занятая процессом память (RSS) после пересборки может не измениться.

Не полагаться ни на сжатие, ни на его отсутствие. Ни одна версия не обещает, когда список отдаёт ёмкость. То, что здесь измерено, — поведение пяти конкретных сборок, и оно уже менялось один раз без единой строки в «Что нового».

История версий

Чем измерено

Числа в статье получены следующими скриптами. Каждый можно открыть прямо отсюда вместе с записью прогона.

Байты и ёмкость сравнимы между версиями; записи есть для всех пяти сборок, включая две свободнопоточные:

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

Время — одна запись, одна сборка:

• bench/lists/ops.py

Основа для задач раздела «Практика»:

• 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) и свободнопоточные 3.13.7t, 3.14.7t; Intel Xeon 2,80 ГГц, 2 vCPU, 64 бита. Ёмкость и байты между версиями сравнимы — это раскладка объекта. Время — нет: у сборок разные компиляторы и разные флаги, и разделить «стал быстрее язык» и «стала быстрее сборка» этими замерами нельзя. Время снято только на 3.13.7 со включённым GIL.

Фрагменты Objects/listobject.c приводятся по тегам v3.12.3 и v3.13.7 дословно.