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

У списка два числа длины. len(L) знают все; второе — allocated, число уже выделенных мест под указатели — из Python не видно ни одним публичным именем, и почти всё поведение списка объясняется именно им.

скрипт	что показывает
growth.py	ёмкость против длины; формула роста и её проверка на каждом скачке; почему одинаковые с виду способы построить список дают разный запас; переезжает ли массив при росте
shrink.py	список отдаёт ёмкость при pop, но с 3.13 не отдаёт при del; что освобождает её наверняка
ops.py	время: наполнение и опустошение с обоих концов, квадратичность insert(0), pop(0) против del L[0], цена индекса у deque

Запуск:

for v in 3.12 3.13 3.14 3.13t 3.14t; do echo "== $v"; python$v bench/lists/growth.py; done
for v in 3.12 3.13 3.14 3.13t 3.14t; do echo "== $v"; python$v bench/lists/shrink.py; done
python3.13 bench/lists/ops.py

Записи прогонов — в runs/. У growth.py и shrink.py записи на ПЯТИ сборках — 3.12.3, 3.13.7, 3.14.7 и свободнопоточных 3.13.7t, 3.14.7t: там меряются байты и ёмкость, то есть раскладка объекта, а её между версиями сравнивать можно и нужно — половина смысла именно в сравнении. Свободнопоточные сборки в списке не для полноты: в Objects/listobject.c у них свои пути выделения, и «проверено на 3.13» без указания сборки не значит ничего. У ops.py запись одна: там меряется время, а время между версиями не сравнивается вовсе (корневой bench/README.md), и второй файл провоцировал бы ровно такое сравнение.

Как читается ёмкость

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

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

Отсюда способ, которым ёмкость читается в обоих скриптах:

allocated = (sys.getsizeof(L) - sys.getsizeof([])) // struct.calcsize("P")

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

Способ не требует ctypes и потому работает в любой сборке. Блок 1 в growth.py печатает рядом и ctypes-чтение того же поля, и СРАВНИВАЕТ два числа, а не объявляет их совпавшими: на сборках с GIL они сходятся, а на свободнопоточных ob_size по тому же смещению читается нулём — раскладка объекта там другая. Это ровно та причина, по которой во всех замерах ёмкость берётся из getsizeof.

Сам способ — деталь реализации CPython, а не обещание языка: list.__sizeof__ считает по allocated потому, что так написано в Objects/listobject.c.

Что нашлось и чего в «Что нового» нет

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

Вывод shrink.py на 3.13.7, 3.14.7, 3.13.7t и 3.14.7t совпадает целиком; от них отличается только 3.12.3. То есть расхождение del и pop — не особенность сборки с GIL: свободнопоточные ведут себя так же. И всё же это поведение конкретных сборок, а не обещание языка: ни одна версия не говорит, когда список отдаёт ёмкость.

Причина видна в исходнике и не требует догадок. В 3.12 удаление по индексу уходит в общий путь присваивания срезу:

static int
list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
{
    ...
    if (v == NULL)
        return list_ass_slice(a, i, i+1, v);

а list_ass_slice после memmove хвоста вызывает 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 здесь не вызывается вовсе — длина уменьшается на месте. То же изменение объясняет и разницу во времени, которую печатает ops.py: внутри одного запуска 3.13.7 L.pop(0) дороже del L[0] в семь раз (×7,0 в записи прогона).

Чего этим замером утверждать нельзя. Что «del стал быстрее» — это сравнение времени между версиями, и оно в проекте запрещено (корневой bench/README.md). Утверждать можно ровно то, что измерено внутри одного запуска: на 3.13.7 две операции, делающие по смыслу одно и то же, стоят по-разному и оставляют объект в разном состоянии.

Формула роста не менялась

Блоки 2–5 growth.py — ёмкость, формула, запас по форме построения — совпадают целиком на всех пяти сборках. Формула

new_allocated = (n + (n >> 3) + 6) & ~3

совпала на всех 24 скачках ёмкости на первых шестистах append на каждой из пяти сборок.

Целиком файлы runs/growth*.txt при этом НЕ совпадают, и это нарочно. Блок 1 на свободнопоточных сборках честно сообщает, что ctypes-чтение ob_size там не сходится с len. Блок 6 считает переезды массива по адресу ob_item, и на свободнопоточных сборках он не делается вовсе; а на сборках с GIL его числа зависят от состояния аллокатора, так что от прогона к прогону меняются — там утверждается только то, что оба исхода встречаются.