List как непрерывный массив PyObject*: amortized O(1) append

В большинстве языков «список» — это либо linked list (Lisp, Haskell), либо dynamic array (C++ std::vector, Java ArrayList, Go slice). Python list — это dynamic array из указателей, и его реализация в PyListObject (см. Include/cpython/listobject.h и Objects/listobject.c) объясняет всё: O(1) индексирование, amortized O(1) append, O(n) insert(0, x), и почему list — плохой контейнер для membership-проверок.

Этот урок — open-the-source-and-read. После него вы должны уметь нарисовать PyListObject от руки и за 30 секунд объяснить, почему amortized O(1) append работает.

PyListObject struct

Полная декомпозиция (упрощённо, см. Include/cpython/listobject.h):

typedef struct {
    PyObject_VAR_HEAD          // ob_refcnt + ob_type + ob_size
    PyObject **ob_item;        // C-массив указателей PyObject*
    Py_ssize_t allocated;      // capacity (≥ ob_size)
} PyListObject;

• PyObject_VAR_HEAD — расширенный header: refcount (8 байт) + type pointer (8 байт) + ob_size (8 байт; число фактически валидных элементов = текущая длина list).
• ob_item — указатель на отдельно-аллоцированный C-массив PyObject *. Это и есть содержимое списка — массив 8-байтовых указателей на heap-объекты.
• allocated — capacity (общее число slot’ов в ob_item-массиве). Инвариант: allocated ≥ ob_size.

Когда вы пишете lst.append(x):

1. Если ob_size < allocated — выполняется ob_item[ob_size] = x; Py_INCREF(x); ob_size++; — это O(1).
2. Если ob_size == allocated — нужно расширить массив через list_resize, что занимает O(n) (реаллокация и копирование указателей).

Из этой картинки сразу понятно:

• Indexing lst[i] — O(1): одно сложение ob_item + i * sizeof(PyObject*) и dereference.
• Memory overhead: per-element стоимость = 8 байт (указатель) + ~24-28 байт (сам PyObject). Для int-ов — заметно больше, чем packed C-массив (int64_t — 8 байт без header’а).
• Cache locality: сами указатели — contiguous, но указуемые объекты разбросаны по куче. Sequential обход for x in lst хорошо использует L1 для самого массива указателей, но каждый Py_INCREF/Py_DECREF или арифметика тянет указуемый объект из произвольной cache line.

Geometric reallocation: list_resize

Сердце amortized O(1) append — функция list_resize (см. Objects/listobject.c). Упрощённый код:

static int list_resize(PyListObject *self, Py_ssize_t newsize) {
    // ...
    Py_ssize_t new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    // эквивалентно: new_allocated = (newsize + newsize/8 + 6), округлено до multiple-of-4
    items = (PyObject **)PyMem_Realloc(self->ob_item, new_allocated * sizeof(PyObject *));
    // ...
}

Геометрический рост:

• Фактор ~1.125x: newsize + newsize/8 + 6 ≈ 1.125 · newsize + 6.
• Округление до multiple-of-4: уменьшает фрагментацию аллокатора.
• PyMem_Realloc копирует все 8-байтовые указатели в новый блок. Сами объекты, на которые указатели ссылаются, не копируются — указатель остаётся прежним.

Это означает: realloc — это memcpy 8 байт × N указателей, что fast (sequential) даже для больших list’ов. Затратность не пропорциональна реальному payload’у элементов.

Реальные значения capacity-роста на cpython-3.12.7 (из scripts/python-course/pyodide-baseline.json):

import sys
lst = []
for i in range(33):
    print(len(lst), sys.getsizeof(lst))
    lst.append(None)
# 0  56    <- header only, capacity=0
# 1  72    <- realloc на capacity=2 (72 = 56 + 2*8)
# 2  72    <- capacity=2 ещё хватает
# 3  88    <- realloc на capacity=4
# 4  88    <- capacity=4 ещё хватает
# 5  104   <- realloc на capacity=6
# 7  120   <- realloc на capacity=8
# 8  120
# 9  136   <- realloc на capacity=10
# ...
# 32 312   <- последняя ступенька (capacity=32)

(Точные числа: 56, 72, 72, 88, 88, 104, 104, 120, 120, 136, 136, 152, …, 312 — см. scripts/python-course/pyodide-baseline.json -> list_capacity_growth.sizes.)

Amortized O(1) append: формальное доказательство

Как уже показано в уроке M01-05 (operators-and-bigO), aggregate-method для n append’ов:

• Дешёвые operations (capacity hit): n штук, каждая O(1). Суммарно O(n).
• Дорогие operations (realloc + memcpy): происходят при capacity = 4, 8, 16, 24, 32, …, каждая копирует k указателей. Геометрический ряд: 4 + 8 + 16 + 24 + 32 + ... ≤ n / (1 - 1/1.125) = 9n для фактора 1.125. Суммарно O(n).
• Total work: O(n) + O(n) = O(n).
• Average per append = O(n) / n = O(1) amortized.

Формальное доказательство — accounting method (CLRS глава 17): каждому дешёвому append’у приписываем «cost = 9 ops» (1 на сам append + 8 на «оплату» будущего realloc’а). Дорогому realloc’у — «cost = 0» (он уже оплачен предыдущими дешёвыми). Сумма приписанных costs ≥ реальной работы → upper bound = 9n / n = O(1).

Big-O для list operations (revisit)

Ключевое: только операции, которые касаются хвоста, дешёвые. Любая операция с серединой/началом — O(n), потому что dynamic array требует shift.

Когда list — wrong choice

1. Membership-тест в горячем цикле. x in lst — O(n). Если lst — 10⁶ элементов и вы делаете 10³ запросов — это 10⁹ операций. Перепакуйте в set (preprocess O(n), потом каждый запрос O(1)) — итого O(n + m).

# anti-pattern: O(n*m)
allowed = ['alice', 'bob', ..., '1M items']
for user in incoming:
    if user.name in allowed:  # O(n) per check
        admit(user)

# Правильно: preprocess, потом O(1) per check
allowed_set = set(allowed)  # O(n) one-time
for user in incoming:
    if user.name in allowed_set:  # O(1) per check
        admit(user)

2. Front-prepend. list.insert(0, x) — O(n). Используйте collections.deque (block-allocated, O(1) на обоих концах). См. Modules/_collectionsmodule.c — deque реализован как block-linked list с capacity 64-element блоков.

3. Numeric data большого объёма. Каждый Python int — heap-allocated PyLong (~28 байт на штуку, см. урок M01-02). Список из 10⁶ int’ов — 8MB указателей + 28MB самих PyLong’ов = 36MB. То же самое в array.array('q', ...) или numpy.int64 — 8MB total (packed primitives, no PyObject overhead).

4. Hashable container (key в dict / element в set). List не hashable (mutable). Если нужен — используйте tuple или frozenset.

Cross-course context

Cross-course → Storage Formats: 02/01 row-groups — Parquet column chunk внутри row group хранится contiguously (в одном диск-блоке), что эквивалентно ob_item[] массиву PyListObject — sequential scan дёшев из-за prefetching. Различие: Parquet column — packed primitives без header’ов (8 байт на INT64); Python list — массив указателей плюс отдельные PyObject’ы (~32 байт overhead на элемент).

Cross-course → Spark: 02/01 catalyst-overview — Spark DataFrame immutable: каждое преобразование (filter, select) создаёт новый logical plan node, исходный DataFrame не меняется. Та же идея, что Python tuple (immutable: создание нового tuple вместо mutation) — но на уровне query plan, а не runtime структуры. Catalyst optimizer rewrites дерево plans, как inline transformations над immutable AST.

Ключевые выводы

1. list = contiguous массив PyObject* + capacity. Header (~56 байт) + ob_item-массив указателей (8 байт × allocated).
2. list_resize использует geometric factor ~1.125x — newsize + newsize/8 + 6, округлено до multiple-of-4. Это amortized O(1) append (формальное доказательство — accounting method).
3. O(1) для indexing/append/pop, O(n) для insert(0)/pop(0)/membership. List плохо подходит для membership-проверок в горячем цикле — используйте set.
4. Memory overhead на элемент — указатель (8 байт) + сам PyObject (~28+ байт). Для numerics — array.array или NumPy.
5. Geometric factor 1.125 — компромисс CPython между memory waste и частотой realloc. Java ArrayList использует 1.5; Go slice — 2.0 (до 1024) затем 1.25; C++ std::vector — обычно 2.0.

В уроке M02-02 разберём tuple — близкий родственник list, но immutable и hashable, с другой memory layout.