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

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

Список в 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. ПЕРЕЕЗЖАЕТ ЛИ МАССИВ ПРИ РОСТЕ
---------------------------------
  Ходовое объяснение запаса: «массив нельзя удлинить на месте».
  Проверяется это адресом самого массива: ob_item до скачка ёмкости
  и после. Если адрес тот же — realloc расширил выделение на месте,
  ничего не копируя.
     600 append: скачков  24, массив остался на месте  13, переехал  11
   20000 append: скачков  53, массив остался на месте  41, переехал  12

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

Поэтому дело не в том, что расширение невозможно, а в том, СКОЛЬКО РАЗ за него приходится платить. Без запаса ёмкость менялась бы на каждом 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 длина растёт на единицу, и эта ветка не срабатывает никогда — поэтому дальше речь только о первой формуле.

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

2. ЧТО ДЕЛАЕТ append: ЁМКОСТЬ РАСТЁТ СКАЧКАМИ
---------------------------------------------
  скачок происходит на длине, ёмкость становится равной:
    длина:      1     5     9    17    25    33    41    53    65    77    93   109   129   149
    ёмкость:    4     8    16    24    32    40    52    64    76    92   108   128   148   172
  всего скачков на первых 600 append: 24
  после 600 append: длина 600, ёмкость 672, запас 72

Ровно эта последовательность выписана и в комментарии рядом с формулой: 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, и это половина, которой не ждёшь:

3. ТО ЖЕ САМОЕ ИЗ СЕРЕДИНЫ И С КОНЦА
------------------------------------
  операция, повторённая 900 раз над списком из 1000:
  операция             длина  ёмкость
  L.pop(0)               100      184
  del L[0]               100     1000
  L.pop(len(L)//2)       100      184
  del L[len(L)//2]       100     1000
  L.pop()                100      184
  del L[-1]              100     1000

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» о нём нет ни строки: ни в разделе про изменения языка, ни в разделе про оптимизации.

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

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

4. ЧТО ОСВОБОЖДАЕТ ЁМКОСТЬ НАВЕРНЯКА
------------------------------------
  после 900 × del L[0]:        длина 100, ёмкость 1000
  L.copy() от него:            длина 100, ёмкость 100
  list(L) от него:             длина 100, ёмкость 100
  L[:] от него:                длина 100, ёмкость 100
  append + pop над ним:        длина 100, ёмкость 116

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

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

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

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

Квадратичность, предъявленная, а не названная

«insert(0) квадратичен» — верно, но само по себе это слова. Проверяется оно удвоением: если время растёт как квадрат, удвоение длины даёт вчетверо больше времени.

3. КВАДРАТИЧНОСТЬ, ПРЕДЪЯВЛЕННАЯ, А НЕ НАЗВАННАЯ
------------------------------------------------
  наполнение через insert(0): длина удваивается — время вчетверо
  длина    всего, мкс   нс на операцию   отношение к предыдущей строке
    2500          583            233.4            —
    5000         2129            425.8        ×3.65
   10000         9066            906.6        ×4.26
   20000        36773           1838.7        ×4.06

  Для сравнения — та же таблица для append, где отношение около двух:
  длина    всего, мкс   нс на операцию   отношение к предыдущей строке
    2500           49             19.7            —
    5000          101             20.3        ×2.06
   10000          201             20.1        ×1.98
   20000          441             22.0        ×2.19

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

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

Изменение из части II видно не только в байтах. Внутри одного запуска 3.13.7:

2. ОПУСТОШИТЬ СПИСОК: С КОНЦА, С НАЧАЛА, ДВУМЯ СПОСОБАМИ
--------------------------------------------------------
  операция, повторённая 10000 раз       всего, мкс   нс на операцию
  L.pop()                                 236             23.6
  del L[-1]                               213             21.3
  L.pop(0)                             120766          12076.6
  del L[0]                              17342           1734.2
  d.pop()                                 272             27.2
  d.popleft()                             269             26.9

  L.pop(0) / del L[0] = ×7.0 — одна и та же работа по смыслу,
  разные пути в реализации. Что при этом происходит с ёмкостью — в shrink.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) в середине). Вот во что это обходится на списке в сто тысяч элементов:

4. ЧЕМ ЗА ЭТО ПЛАТИТ deque: ЦЕНА ИНДЕКСА
----------------------------------------
  Обе стороны у deque дёшевы — но индекс перестал быть постоянным.
  выражение, повторённое 1000 раз в витке     нс на операцию
  L[0]                                              7.5
  L[50000]                                          9.0
  L[99999]                                          9.1
  d[0]                                             11.6
  d[50000]                                       2418.3
  d[99999]                                         18.1

У списка три числа почти совпали — индекс не зависит от позиции. У 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 дословно.