list — не «настоящий» массив

В прошлом уроке мы сказали: массив — это непрерывный блок ячеек одного размера. С array.array('i', ...) это так и есть — все элементы лежат подряд, по 4 байта на штуку. А вот Python list устроен иначе. И когда люди говорят «list это массив», это полуправда. Точнее так:

Python list — это массив указателей на объекты. Сами объекты живут где-то в куче, разбросанные по разным адресам. В массиве лежат только 8-байтовые ссылки на них.

Это объясняет всё странное в list: почему [1, "abc", {"x":1}] валидно, почему list на миллион int съедает ~28 MB вместо ожидаемых ~4 MB, почему list медленнее numpy на численных операциях.

PyListObject в CPython 3.13

В исходниках CPython (Include/cpython/listobject.h) структура такая:

typedef struct {
    PyObject_VAR_HEAD          // ob_refcnt, ob_type, ob_size
    PyObject **ob_item;        // указатель на массив указателей
    Py_ssize_t allocated;      // ёмкость выделенного буфера
} PyListObject;

Разберём поля:

• ob_refcnt — счётчик ссылок. CPython считает их вручную, чтобы освобождать память.
• ob_type — указатель на PyTypeObject (это «класс»). Для list — &PyList_Type.
• ob_size — текущая длина списка (то, что возвращает len(xs)).
• ob_item — указатель на буфер. Сам буфер — это блок памяти, в котором лежат указатели на PyObject. То есть ob_item это PyObject ** — указатель на массив указателей.
• allocated — сколько ячеек в буфере выделено. Может быть больше, чем ob_size: это запас на будущие append (overallocation, разберём ниже).

xs[i] в Python — это:

1. Прочитать ob_item[i] — указатель (8 байт) из буфера.
2. По этому указателю взять объект.
3. Вернуть PyObject *.

Когда вы пишете xs[i] + 1, добавляется ещё разыменование, чтение полей PyLongObject, вызов tp_add. Каждое такое чтение стоит дороже, чем чтение из чисто-числового массива (array.array или numpy), где сразу хранится int32.

Размер list на миллион int

Посмотрим, что list реально съедает:

import sys

xs = list(range(1_000_000))
print(f"len:           {len(xs):>15,}")
print(f"sys.getsizeof: {sys.getsizeof(xs):>15,} bytes")
print(f"per element:   {sys.getsizeof(xs) / len(xs):>15.2f} bytes")

На CPython 3.13 64-bit получится примерно:

len:                 1,000,000
sys.getsizeof:       8,448,728 bytes
per element:               8.45 bytes

«Всего 8 байт на элемент» — но это только размер самого буфера указателей. Сами объекты int не учтены. Маленькие int (-5..256) кэшируются Python, но 1 миллион уникальных int — нет:

total = sys.getsizeof(xs) + sum(sys.getsizeof(x) for x in xs)
print(f"with objects:  {total:>15,} bytes")

Получим ~36 MB. Это против 4 MB у array.array('i', range(1_000_000)) и 4 MB у numpy.arange(1_000_000, dtype='int32'). В 9 раз больше памяти, и это только пример с маленькими целыми.

Почему такой overhead

Каждый PyLongObject хранит:

• ob_refcnt — 8 байт.
• ob_type — 8 байт (указатель на PyLong_Type).
• ob_size — 4 байта (фактически 8 с выравниванием), знак и количество цифр.
• ob_digit[1] — 4 байта (одна 30-битная цифра).

Итого ~28 байт на крошечное число, которое в C занимает 4. Это плата за «всё — объект»: все int dynamically-typed, везде refcounting, везде дискриптор типа.

allocated и overallocation

Поле allocated — ключ к амортизированному O(1) для append. Когда вы создаёте list через [] или литерал, allocated может быть больше, чем len. Это запас. Когда append достигает границы (ob_size == allocated), CPython делает realloc с экспоненциальным ростом — и снова появляется запас.

Посмотреть можно через приватный API (sys.getsizeof показывает фактически выделенный буфер плюс header):

import sys

xs = []
prev = -1
for i in range(20):
    xs.append(i)
    size = sys.getsizeof(xs)
    if size != prev:
        # ёмкость в элементах: (sys.getsizeof(xs) - 56) / 8
        capacity = (size - 56) // 8
        print(f"len={len(xs):>3}  size={size:>4} bytes  capacity={capacity}")
        prev = size

Вывод (CPython 3.13):

len=  1  size=  88 bytes  capacity=4
len=  5  size= 120 bytes  capacity=8
len=  9  size= 184 bytes  capacity=16
len= 17  size= 248 bytes  capacity=24

Видно: capacity растёт ступенями (4, 8, 16, 24, …). Между ступенями append — это просто запись в ob_item[ob_size] и инкремент ob_size. Никакой работы с памятью. О точной формуле роста — следующий урок.

Что значит «slot указателя пустой»

Поскольку буфер хранит указатели, «удалить элемент» можно двумя способами:

• Записать NULL в slot — но тогда xs[i] будет ломаться.
• Сдвинуть все элементы за i влево на 1 — это del xs[i] и xs.pop(i).

list.pop() без аргумента работает быстро: убирает последний элемент, просто декрементит ob_size. list.pop(0) или del xs[0] сдвигают все остальные N-1 указателей на одну позицию — это O(n). Поэтому очередь на list строить плохо (используйте collections.deque, см. модуль 7).

Попробуй сам

Запустите этот код и посмотрите, насколько Python list «дороже», чем numpy:

import sys
import array
import numpy as np

N = 1_000_000

lst = list(range(N))
arr = array.array('i', range(N))
ndarr = np.arange(N, dtype='int32')

# size of header/buffer
print("list   buffer:       ", f"{sys.getsizeof(lst):>12,}")
print("array  buffer:       ", f"{sys.getsizeof(arr):>12,}")
print("ndarr  buffer:       ", f"{ndarr.nbytes:>12,}")

# size including objects (для list это критично)
lst_total = sys.getsizeof(lst) + sum(sys.getsizeof(x) for x in lst)
print("list   total (objects too):", f"{lst_total:>12,}")

Скорее всего увидите: list в ~9 раз тяжелее на одинаковых данных. Когда вас просят «обработать 100M строк», это разница между «влезает в RAM» и «своп».