Как устроен механизм оптимизации словарей Compact Dict (PEP 468), принятый в Python 3.6+? Как разделение словаря на два массива — массив хэшей/индексов и массив пар «ключ—значение» — позволило сократить потребление памяти структурами данных на 20–25% и гарантировать сохранение порядка вставки?

Compact dict разделяет разреженную таблицу индексов и плотные записи элементов, уменьшая пустые затраты памяти. Порядок вставки в CPython 3.6 был свойством реализации, а с Python 3.7 стал гарантией языка.

Индексная таблица направляет поиск к плотной записи ключа и значения; размер индекса может быть меньше полного набора указателей. Новые записи добавляются последовательно, поэтому обход отражает вставку. Формулировка про отдельный «массив хэшей» неточна: устройство записей зависит от вида словаря. PEP 468 посвящён порядку **kwargs, а не самостоятельной спецификации всего compact dict. Процент экономии зависит от размера и содержимого словаря, фиксированные 20–25% не гарантированы.

Источник: mail.python.org.