Когда я в первый раз залез в dictobject.c (исходник словаря в CPython), я ожидал увидеть хеш-таблицу. Увидел три с половиной тысячи строк С-кода и комментарий Тима Петерса 2001 года, в котором он объясняет, почему CPython использует perturbation probing вместо линейного — и попутно опровергает пару теорем из учебника Кнута.

С тех пор код переписали дважды (compact dict в 3.6, потом inline values в 3.11), добавили key sharing, а теперь ещё и free-threading из 3.13 ломает некоторые инварианты, которые стояли двадцать лет.

Словарь — самая оптимизированная структура в CPython, и каждая мажорная версия добавляет ей новый слой работы.

Хеш-таблица, которой больше нет

До Python 3.6 dict был классической хеш-таблицей с открытой адресацией. Каждый слот хранил тройку (хеш ключа, указатель на ключ, указатель на значение) и занимал 24 байта на 64-битной системе. Таблица заполнялась не более чем на 2/3 (load factor), поэтому словарь из трёх элементов имел 8 слотов, из которых пять пустых. Пустые слоты занимали по 24 байта каждый — 120 байт на хранение ничего. Порядок итерации зависел от хешей, и если вы добавляли "name", "age", "city", при итерации получали что-то вроде "age", "city", "name".

В CPython 3.6 Рэймонд Хеттингер реализовал идею, которую Тим Петерс предложил в 2012 году в рассылке python-dev: разделить одну таблицу на две.

Первая — sparse index, массив целых чисел. На словарях до 128 элементов каждый индекс занимает 1 байт (вместо 24). Пустые слоты — -1. Вторая — dense entries, массив, в который элементы добавляются строго по порядку вставки. Каждая запись хранит хеш, ключ и значение.

sparse (8 байт):  [-1, 0, -1, -1, 1, -1, 2, -1]
                         ↓             ↓       ↓
dense (3 записи): [("name","Alice"), ("age",30), ("city","Msk")]

Sparse занимает 8 байт вместо 192. Итерация — проход по dense от начала до конца, без перебора пустых слотов. Экономия памяти 25-50% и сохранение порядка вставки бесплатно.

В Python 3.6 это было деталью реализации CPython. В 3.7 стало частью спецификации. Но порядок появился не потому что его хотели, а потому что compact layout оказался быстрее, и порядок стал побочным эффектом.

Perturbation probing

При коллизии CPython использует формулу из dictobject.c, которая не менялась с 2001 года:

j = ((5 * j) + 1 + perturb) % size;
perturb >>= 5;

Переменная perturb инициализируется полным значением хеша, потом на каждом шаге сдвигается вправо на 5 бит. Первые пробы используют старшие биты хеша (которые при остатке от деления теряются), по мере затухания perturb формула вырождается в (5*j+1) % size — полную перестановку {0..size-1} при степенях двойки. Линейное пробирование плохо тем, что коллизии кластеризуются, perturbation разбрасывает пробы по таблице.

Key sharing и inline values

Когда вы создаёте тысячу экземпляров одного класса, у каждого свой dict с одинаковыми ключами и разными значениями. До PEP 412 (Python 3.3) каждый экземпляр хранил полную копию ключей. На миллионе объектов с тремя атрибутами это мегабайты на хранение строк "name", "age", "city" миллион раз.

Key sharing решает все эти дела, экземплры одного класса разделяют один массив ключей. Каждый экземпляр хранит только массив значений. На тысяче экземпляров экономия десятки килобайт, на миллионе уже мегабайты.

class User:
    def __init__(self, name, age):
        self.name = name
        self.age = age

# shared keys: ["name", "age"]
# u1.values: ["Alice", 30]
# u2.values: ["Bob",   25]

Key sharing ломается, если экземпляры получают разные наборы атрибутов. Как только вы делаете u1.email = "..." (у u2 этого атрибута нет), CPython переключает u1.dict на unshared mode, и экземпляр получает собственную полную копию ключей.

В CPython 3.11 (PEP 659, specializing adaptive interpreter) пошли дальше. Если все экземпляры класса имеют одинаковый набор атрибутов (что обычно так), значения хранятся не в dict, а прямо в объекте, в фиксированных слотах. Байткод LOAD_ATTR специализируется в LOAD_ATTR_INSTANCE_VALUE, который читает атрибут по фиксированному смещению в объекте, без хеширования и без поиска по таблице. Это быстрее обычного dict lookup примерно в два раза.

Но это работает только пока форма объекта не меняется. Добавили атрибут — CPython де-оптимизирует: переключается с inline values обратно на обычный dict lookup, и LOAD_ATTR_INSTANCE_VALUE откатывается к LOAD_ATTR_ADAPTIVE.

slots: когда dict не нужен

slots — радикальная версия той же идеи: вообще не создавать dict. Атрибуты хранятся как С-структура фиксированного размера, доступ по смещению, никакого хеширования. Экземпляр со slots занимает вдвое-втрое меньше памяти. 

class User:
    __slots__ = ('name', 'age')
    def __init__(self, name, age):
        self.name = name
        self.age = age

Цена: нельзя добавлять произвольные атрибуты, u.email = "..." вызовет AttributeError. И наследование: если подкласс не объявит свой slots, у его экземпляров появится dict, и экономия исчезнет.

Ресайзинг и удаление

Когда dense entries заполняется на 2/3, CPython перестраивает таблицу: создаёт новую sparse table большего размера (всегда степень двойки), перехешивает все элементы. Размер в степенях двойки позволяет вычислять индекс через битовую маску hash & (size-1) вместо дорогого деления с остатком. Начальный размер — 8 слотов, пустой словарь {} в CPython 3.11+ не аллоцирует таблицу вообще, она создаётся при первой вставке.

При удалении элемента слот в sparse table помечается как DKIX_DUMMY (-2) — «надгробие». Оно говорит алгоритму поиска «здесь что-то было, ищи дальше» и не даёт сломать цепочку пробирования. Tombstones накапливаются между ресайзами и замедляют поиск. Иногда пересоздание через comprehension d = {k: v for k, v in d.items() if cond} быстрее серии del, потому что строит чистую таблицу.

Free-threading и dict: что ломается без GIL

CPython 3.13 добавил экспериментальный режим free-threading (PEP 703), где GIL отключён. Для dict это серьёзный вызов, потому что GIL традиционно защищал словари от гонок: пока один поток модифицирует dict, никакой другой поток не может выполнять Python-код.

Без GIL два потока могут одновременно вставлять в один словарь или один читает, а другой пишет. Ресайзинг особенно опасен: один поток начинает перестраивать таблицу, другой в это время ищет элемент по старой таблице, которая уже частично перезаписана.

CPython 3.13t решает это через per-object locks (мелкозернистые блокировки на каждом объекте) и lock-free чтение для операций, которые не модифицируют словарь. Для чтения (LOAD_ATTR, getitem) используются атомарные операции и memory barriers, которые позволяют читать без захвата лока в большинстве случаев. Для записи берётся лок на конкретном dict-объекте.

Для словарей это означает: если ваш код однопоточный, free-threading добавляет overhead на атомарные операции при каждом чтении атрибута. Если многопоточный — впервые в истории CPython несколько потоков могут параллельно читать из одного dict без блокировки.

Что из этого нужно запомнить

  • dict упорядочен с 3.7 не потому что так задумывали, а потому что compact layout оказался быстрее, и порядок вставки стал бесплатным побочным эффектом

  • slots экономит память потому что dict стоит пару сотен байт на каждый экземпляр, а slots хранит атрибуты по фиксированному смещению без хеш-таблицы

  • Динамическое добавление атрибутов замедляет код потому что ломает inline values и заставляет specializing interpreter откатывать LOAD_ATTR обратно к медленной версии с поиском по таблице

  • Частые del замедляют поиск потому что tombstones накапливаются между ресайзами и удлиняют цепочки пробирования

  • Free-threading замедляет однопоточный код потому что каждое чтение из dict теперь проходит через атомарные операции и memory barriers, даже если второго потока нет

Если у вас миллион объектов в памяти, используйте slots. Если горячий цикл читает атрибуты, не добавляйте их динамически — дайте specializing interpreter работать по быстрому пути. Если переходите на free-threaded CPython, будьте готовы к тому, что однопоточная производительность просядет, а выигрыш будет только при реальной параллельности.

В CPython многие вещи, которые снаружи выглядят как обычный доступ к ключу или атрибуту, внутри упираются в layout объектов, работу интерпретатора и компромиссы между памятью и скоростью. Разобраться в таких деталях проще на живом разборе Python-проектов: можно увидеть, как решения на уровне кода, окружения и фреймворков влияют на поведение приложения, задать вопросы экспертам и заодно понять, как устроен формат обучения на практике. Участие бесплатное:

  • 7 мая в 20:00 — «Настройка удобного рабочего окружения для Python проекта» Разбор типовой архитектуры Python-приложения и инфраструктурных компонентов, которые нужны для нормальной разработки и поддержки проекта. Записаться

  • 20 мая в 20:00 — «SSE в FastAPI: отправка данных в реальном времени» Практический вебинар про Server-Sent Events в FastAPI: как создавать SSE-эндпоинты и отправлять клиенту актуальные данные в режиме реального времени. Записаться

Полный список бесплатных уроков мая смотрите в дайджесте.