Tuple: неизменяемый contiguous, hashable, иногда interned

Tuple на первый взгляд — «list, который нельзя менять». Но за этой поверхностной разницей лежат две архитектурные решения, которые делают tuple фундаментально другим контейнером:

1. ob_item встроен в struct как flex array — single allocation, не отдельный pointer-to-array.
2. Нет растущей capacity — размер фиксирован при создании.

Из этих двух фактов следует всё: tuple hashable (можно использовать как ключ в dict), у него меньше per-instance overhead, и для маленьких tuple’ов есть free-list cache (экономия allocator overhead).

PyTupleObject struct

Полная декомпозиция (см. Include/cpython/tupleobject.h):

typedef struct {
    PyObject_VAR_HEAD             // ob_refcnt + ob_type + ob_size
    PyObject *ob_item[1];         // C99 flexible array member
} PyTupleObject;

Самое важное здесь — ob_item[1] как flexible array member (C99-фича). Это означает: при создании tuple’а размером N CPython аллоцирует один блок памяти размером sizeof(PyTupleObject) + (N-1) * sizeof(PyObject*), и ob_item оказывается в той же выделенной области, что и header. Указатель &ob_item[0] — это адрес внутри той же malloc’нутой структуры.

Сравните с PyListObject:

Реальные размеры (cpython-3.12.7, baseline):

import sys
print(sys.getsizeof(()))         # 40 байт — header + null/sentinel
print(sys.getsizeof((None,)))    # 48 байт — header (40) + 1 указатель (8)
print(sys.getsizeof((1, 2, 3)))  # 64 байт — header (40) + 3 указателя (24)

Сравните с list: [] весит 56, [None] — 64, [1, 2, 3] — 64+ (зависит от capacity headroom). Tuple на каждый элемент тратит ровно 8 байт (без headroom); list — 8 байт + amortized capacity overhead.

Почему immutable означает hashable

Hashable объект должен иметь stable hash на всём времени жизни (см. Include/object.h и контракт hash(x) == hash(y) если x == y). Если объект мутирует, его hash может измениться → объект «потеряется» в dict/set, где он использовался как ключ:

# Гипотетический сценарий с hashable list (был бы баг):
key = [1, 2, 3]
d = {key: "value"}
key.append(4)        # mutation
# Теперь key.__hash__() даёт другое число.
# d[key] не находит entry — но и d[[1,2,3]] не найдёт (этот объект уже не в d).
# Запись потеряна навсегда: чтобы её удалить или найти, нужно знать prev hash.

Python предотвращает этот баг на уровне типа: list.__hash__ определён как None, что вызывает TypeError. Tuple, наоборот, гарантирует immutability → hash stable → safe to use as dict key.

t = (1, 2, 3)
hash(t)              # OK - все элементы immutable
d = {t: "value"}     # tuple как dict key

l = [1, 2, 3]
hash(l)              # TypeError: unhashable type: 'list'

t2 = (1, [2, 3])     # tuple содержит list
hash(t2)             # TypeError: unhashable type: 'list'
                     # (внутренний list не hashable -> tuple тоже не hashable)

Алгоритм tuple_hash (см. Objects/tupleobject.c) — XOR-shift комбинация hash’ей элементов:

// упрощённо: цикл по всем элементам, mix через XOR + multiply
Py_hash_t hash = INITIAL_VALUE;
for (i = 0; i < n; i++) {
    Py_hash_t lane = PyObject_Hash(item_i);
    hash = xor_shift_mix(hash, lane);
}

В Python 3.8+ алгоритм xxHash-inspired, в более ранних — Bernstein-style. Главное — каждый элемент должен быть hashable, иначе вся комбинация падает с TypeError.

Free-list cache для small tuples

Для частоиспользуемых маленьких tuples CPython держит free-list — pool недавно-освобождённых объектов, чтобы избегать malloc/free overhead на каждое создание. Cite: Objects/tupleobject.c — переменная numfree[PyTuple_MAXSAVESIZE] и константа PyTuple_MAXSAVESIZE = 20 (в 3.13 — есть нюансы по сборке freelists в interpreter state, но идея та же).

Как работает:

1. При создании tuple’а размера N (где N ≤ 20) CPython проверяет free_list[N].
2. Если pool непустой — берёт оттуда объект (сбрасывает refcount, заполняет ob_item) — без malloc’а.
3. Иначе — malloc’нет новый блок.
4. При уничтожении tuple’а размера N ≤ 20: вместо free() объект кладётся в free_list[N] (если pool не переполнен).

Зачем: маленькие tuples создаются постоянно: каждый вызов функции с *args создаёт tuple для аргументов; каждый for k, v in d.items() распаковывает в tuple; каждый multi-value return — tuple. Без free-list’а malloc/free в этих горячих путях стал бы заметным overhead.

# Каждая итерация создаёт и уничтожает tuple — free-list делает это дешёвым:
d = {'a': 1, 'b': 2, 'c': 3}
for k, v in d.items():           # items() возвращает iterator над tuple'ами
    print(k, v)

# *args тоже tuple:
def f(*args):                    # args — tuple, free-list reused для частых сигнатур
    return sum(args)
f(1, 2, 3)

Когда tuple, когда list

Часто встречается namedtuple (collections.namedtuple) — subclass tuple с именованными полями, plus type hints через typing.NamedTuple. Эти варианты сохраняют hashability и immutability, добавляя удобный API. Альтернатива в современном Python: dataclasses.dataclass(frozen=True) — больше boilerplate но богаче (validators, __post_init__).

Tuple interning — implementation detail

CPython интернирует литералы () (один глобальный singleton — пустой tuple) и иногда small literal tuples в bytecode constants:

a = ()
b = ()
print(a is b)        # True — empty tuple singleton

a = (1, 2, 3)
b = (1, 2, 3)
print(a is b)        # CPython 3.10+: часто True, ибо bytecode literal interning
                     #                 (но не гарантировано спецификацией)

a = tuple([1, 2, 3])
b = tuple([1, 2, 3])
print(a is b)        # обычно False — построены при runtime, не из constant'а

Никогда не пишите код, опирающийся на is для tuples (как и для int/str). == всегда работает корректно.

Cross-course context

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

1. tuple = contiguous immutable массив с ob_item как flex array — single allocation (vs list’s 2 allocations).
2. Immutable → hashable: stable hash → safe as dict key. Алгоритм tuple_hash — XOR-shift mix hash’ей элементов; если хоть один элемент не hashable, весь tuple не hashable.
3. Free-list cache для tuples размера ≤ 20: pool недавно-освобождённых объектов, экономит malloc/free overhead для частых маленьких tuples (*args, dict.items(), multi-return).
4. Sized memory: tuple ровно 40 + 8N байт (без capacity headroom); list ≥ 56 + 8 * allocated.
5. Когда tuple: dict key, fixed-shape record, multi-return, function args. Когда list: mutable sequence, accumulator, append-heavy workload.

В уроке M02-03 разберём dict — главную структуру Python: hash, open addressing, perturbation, load factor 2/3.