tuple в CPython – мутабельный! И другие шокирующие детали из C-шной реализации

Привет! Меня зовут Никита Соболев, я core-разработчик языка программирования CPython, а так же автор серии видео про его устройство.

Я продолжаю свой цикл статей на хабре про детали реализации питона. Сегодня я хочу рассказать, как tuple устроен внутри.

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

Ну и конечно – мое полное видео на полтора часа, где будет множество дополнительной информации о деталях работы VM.

Если вам такое интересно или целиком незнакомо – добро пожаловать!

Для начала – вот вам видео; в нем я постарался рассказать вообще все, что я знаю про tuple в CPython. От аннотаций (tuple[int, ...], tuple[()], *tuple[int, int]) и TypeVarTuple до сишных деталей: _PyFreeList_ C-API и оптимизаций AST, VM и компилятора.

Видео действительно получилось очень насыщенным, так что рекоммендую к просмотру.

Устройство tuple

Начнем со структуры данных PyTupleObject, которая представляет собой внутреннее устройство tuple в CPython. Структура довольно простая:

typedef struct {
    PyObject_VAR_HEAD
    /* ob_item contains space for 'ob_size' elements.
       Items must normally not be NULL, except during construction when
       the tuple is not yet visible outside the function that builds it. */
    PyObject *ob_item[1];
} PyTupleObject;

По сути тут у нас просто массив объектов, которые хранит tuple в ob_item. Но где же сам размер кортежа? А вот он хранится в PyObject_VAR_HEAD. В CPython есть два типа C-шных структур: с постоянным размером (как int с python3.11+) и с переменным (variable) размером. PyObject_HEAD и PyObject_VAR_HEAD соответсвенно. Сравним их!

#define PyObject_HEAD PyObject ob_base;
#define PyObject_VAR_HEAD PyVarObject ob_base;

Где PyObject ob_base будет сразу хранить тип объекта, а PyVarObject ob_base будет делать так:

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

Рядом еще будет лежать и длина объекта. Следовательно, получить длину мы всегда можем за O(1), вот как выглядит __len__ кортежа:

static Py_ssize_t
tuple_length(PyObject *self)
{
    PyTupleObject *a = _PyTuple_CAST(self);
    return Py_SIZE(a);
}

Где Py_SIZE – просто получает значение из ob_size

static inline Py_ssize_t Py_SIZE(PyObject *ob) {
    return _PyVarObject_CAST(ob)->ob_size;
}

Аллокация и деалокация

Все мы знаем, что tuple – объект иммутабельный