Compact dict (PEP 468) и порядок вставки

В уроке M02-03 мы разобрали dict как hash table с perturbation probe. Но мы оставили одну деталь open: каков именно layout? До Python 3.6 это был наивный sparse table (один массив (hash, key, value) triples). С Python 3.6 — compact layout (PEP 468, идея Naoki Inada, реализация Inada + Hettinger): два массива (dk_indices + dk_entries), который экономит ~30-65% памяти и бесплатно preserves insertion order. Раймонд Хеттингер представил этот дизайн в talk «Modern Dictionaries» (PyCon 2017), и это до сих пор самая elegant memory-оптимизация в современной Python-кодовой базе.

После этого урока вы должны уметь нарисовать compact dict layout от руки, объяснить почему insertion order сохраняется бесплатно, и оценить memory savings.

Old layout (до Python 3.6) — naïve sparse table

До 3.6 dict использовал один большой sparse массив записей размера ~3·N (load factor ≤ 1/3). Каждая запись содержала (hash, key, value) triple = 3 указателя × 8 байт = 24 байта на slot, занят он или пуст.

slot 0: empty (24 bytes wasted)
slot 1: (hash_a, 'apple',  ptr_1)
slot 2: empty
slot 3: empty
slot 4: (hash_b, 'banana', ptr_2)
slot 5: empty
slot 6: (hash_c, 'cherry', ptr_3)
slot 7: empty

Для dict из 3 записей при load factor 1/3 нужно ~9 slot’ов (округлено до степени двойки = 16). Это 16 × 24 = 384 байта, при том что валидных данных всего 3 × 24 = 72 байта. Эффективность ~19%.

Хуже: итерация шла в hash order (порядок probing), который зависит от рандомизированного PYTHONHASHSEED. Каждый запуск программы давал разный порядок ключей. Это часто удивляло разработчиков: «почему dict.keys() непредсказуем?» — потому что hash function рандомизирована.

Compact layout (PEP 468) — dk_indices + dk_entries

PEP 468 разделяет dict на два массива разного размера и плотности:

• dk_indices — sparse массив (размер ~3·N для load factor 2/3), содержит индексы в dk_entries. Это где идёт hash lookup и probing. Значения — int1/int2/int4/int8 (1, 2, 4 или 8 байт) в зависимости от размера dict (для маленького dict — 1 байт на index).
• dk_entries — dense массив (hash, key, value) triples (24 байт × N), без holes (insertion-ordered).

Lookup алгоритм:

1. i = hash & mask
2. entry_idx = dk_indices[i]
3. if entry_idx == DKIX_EMPTY: not found; if collision -> probe next slot in dk_indices
4. else: ep = dk_entries[entry_idx]; check ep.hash == hash && ep.key == key

Cite: Objects/dictobject.c, PyDictKeysObject struct, макросы DK_LOG_SIZE, DK_SIZE, DK_IXSIZE (выбор 1/2/4/8-byte index в зависимости от размера).

Memory savings — конкретный расчёт

Для dict из 10 записей:

Old layout (pre-3.6):

• table size = 32 slots (load factor 1/3, округлено до 2^5)
• 32 × 24 = 768 байт для самой таблицы
• Эффективность: 240 / 768 = 31%

Compact layout (3.6+):

• dk_indices: 16 slots × 1 byte = 16 байт (load factor 2/3, размер 16 — следующая 2^k)
• dk_entries: 10 × 24 = 240 байт
• Total: 256 байт
• Эффективность: 240 / 256 = 94%

Savings: 768 - 256 = 512 байт = ~67% для small dict. Для больших dict savings становятся меньше (dk_indices использует 2/4-byte indices), но всегда заметные (~30-50%).

import sys
print(sys.getsizeof({}))                       # ~64 байта (header only)
print(sys.getsizeof({'a': 1}))                 # ~184 байта (после первого insert)
print(sys.getsizeof({i: i for i in range(10)})) # значительно меньше чем 32 * 24 + header

Cite: Objects/dictobject.c, функции _PyDict_NewKeysForClass, dictresize. Структуры PyDictKeysObject, PyDictKeyEntry.

Insertion order — free side effect

dk_entries — sequential dense array, заполняется в порядке insert’а. Iteration по dict проходит dk_entries linearly (for k in d: это просто for-loop по dk_entries[0..n_used]). Insertion order сохраняется бесплатно — никакой extra structure (ordered linked list, как в Java LinkedHashMap), просто follow-the-storage-order.

d = {}
d['banana'] = 2
d['apple']  = 1
d['cherry'] = 3

print(list(d.keys()))    # ['banana', 'apple', 'cherry'] - insertion order
print(list(d.values()))  # [2, 1, 3]

При delete запись из dk_entries[i] помечается как dummy (entry hash = -1), но сам slot не сдвигается (иначе сломались бы индексы из dk_indices). Если dict стал sparse (много dummies), CPython compact’ит при следующем resize. Поэтому order между insert’ами сохраняется, но после delete + insert новый key добавляется в конец (а не на освобождённое место).

PEP 509 — ma_version_tag

Каждый dict содержит private поле ma_version_tag (64-bit). При любой mutation (insert, delete, update) оно incrementируется. Используется CPython attribute caches (LOAD_GLOBAL, LOAD_ATTR opcodes) для invalidation: bytecode interpreter кеширует результат предыдущего lookup, проверяет ma_version_tag — если не изменился, lookup re-using cached entry. См. PEP 509, внедрено в Python 3.6 одновременно с compact dict.

Ваш Python-код напрямую с ma_version_tag не взаимодействует, но эта оптимизация даёт ~10% speedup на attribute-heavy workloads — что-то знать стоит, если профилируете performance-critical код.

Когда compact layout не оптимален

1. Очень маленькие dicts (1-2 записи). Header overhead доминирует — savings минимальны.

2. Sparse-after-many-deletes. Если большой dict постоянно теряет записи через del, dk_entries накапливает dummies. CPython compact’ит при resize, но между resize’ами memory может быть waste’д.

3. Shared keys (PEP 412). Для атрибутов instance’ов CPython использует split-keys dict: keys array shared между всеми instance’ами одного класса; каждый instance имеет только values array. Это отдельная оптимизация от compact layout. Cite: PEP 412.

Cross-course context

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

1. PEP 468 разделил layout на dk_indices (sparse, 1/2/4/8-byte indices) + dk_entries (dense, insertion-ordered triples). Реализация: Naoki Inada + Raymond Hettinger, Python 3.6.
2. Memory savings ~30-65% vs old naïve sparse table: для 10-entry dict 768 → 256 байт (savings 67%). Эффективность с 31% до 94%.
3. Insertion order — free side effect: dk_entries заполняется sequentially, iteration просто follow storage order. Python 3.7+ — language guarantee.
4. PEP 509 ma_version_tag — incrementируется при mutation, используется attribute caches для invalidation. Даёт ~10% speedup на attribute-heavy workloads.
5. Cite: Objects/dictobject.c, структура PyDictKeysObject, макросы DK_LOG_SIZE/DK_SIZE/DK_IXSIZE. PEP 468, talk «Modern Dictionaries» (Hettinger 2017).

В уроке M02-05 разберём set — тот же hash table без values, plus операции union/intersection/difference и big-O для них.