Как устроен словарь в CPython: compact dict, key sharing и что с ним делает free-threading

В сфере искусственного интеллекта произошло заметное событие. badcasedaily1 38 минут назад Как устроен словарь в CPython: compact dict, key sharing и что с ним делает free-threading Средний 6 мин 863 Блог компании OTUS Python * Программирование * Обзор Когда я в первый раз залез в 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". 6 Рэймонд Хеттингер реализовал идею, которую Тим Петерс предложил в 2012 году в рассылке python-dev: разделить одну таблицу на две.

Отраслевые последствия

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

Каждая запись хранит хеш, ключ и значение. sparse (8 байт): ↓ ↓ ↓ dense (3 записи): Sparse занимает 8 байт вместо 192. Итерация — проход по dense от начала до конца, без перебора пустых слотов.

Экономия памяти 25-50% и сохранение порядка вставки бесплатно. 6 это было деталью реализации CPython. 7 стало частью спецификации.

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.