Один из самых популярных вопросов на собесах. Так много статей в интернете, так мало правильных ответов!
Сегодня будем разбирать.
Базовое устройство
Если вы не смотрели классический доклад Реймонда Хеттингера про устройство словарей в Python3.6+, то нужно срочно посмотреть. Там он рассказывает про устройство хеш-таблицы, проблему хеш конфликтов, сохранение порядка вставки и даже про кеш линии процессора.
Давайте попробуем для начала понять, что за хеш-таблица, и где она.
typedef struct {
PyObject ob_base;
Py_ssize_t ma_used; // number of keys
uint64_t _ma_watcher_tag; // dict watchers
PyDictKeysObject *ma_keys;
PyDictValues *ma_values;
} PyDictObject;
Пока вроде бы все ожидаемо: структура словаря хранит в себе базовый класс, количество ключей, "watchers" (обсудим позже), ключи, значения.
Как выглядят сами ключи?
struct _dictkeysobject {
Py_ssize_t dk_refcnt; // own refcount
uint8_t dk_log2_size; // key size
uint8_t dk_kind;
#ifdef Py_GIL_DISABLED
PyMutex dk_mutex; // protect shared keys
#endif
uint32_t dk_version; // version number
Py_ssize_t dk_usable; // number of usable entries in dk_entries
Py_ssize_t dk_nentries; // number of used entries
char dk_indices[]; // actual hashtable
};
А вот теперь посмотрим на возможные инварианты словарей:
-
ma_keys->dk_kind может быть одним из трех значений: general (как мы все привыкли), unicode (оптимизация для словарей только с str ключами), split (оптимизация для `instance.__dict__`)- Если
ma_keys->dk_kind != DICT_KEYS_SPLIT, то ma_values == NULL- Если
ma_keys->dk_kind == DICT_KEYS_SPLIT, то ma_values != NULLНу и сами split значения:
struct _dictvalues {
uint8_t capacity;
uint8_t size;
uint8_t embedded;
uint8_t valid;
PyObject *values[1];
};
Важные оптимизации
- Ключи могут быть оптимизированы под
str (`DICT_KEYS_UNICODE`), тогда происходит важное: мы начинаем использовать PyDictUnicodeEntry вместо PyDictEntry, у первого нет хранения hash. Что делает его меньше в размере:
sys.getsizeof({'a': 1}) # 184
sys.getsizeof({1: 1}) # 224
- Словарь может быть "разделен" с
DICT_KEYS_SPLIT, тогда ключи и значения хранятся отдельно. Зачем? Обычно все объекты одного класса имеют одинаковый набор ключей CACHED_KEYS(Py_TYPE(obj)). Что позволяет нам переиспользовать один "shared" объект ключей для всех инстансов. Данная оптимизация использует str ключи внутри в том числе- Еще одна оптимизация рядом для
instance.__dict__ (работает по-умолчанию, для всех типов с Py_TPFLAGS_INLINE_VALUES и Py_TPFLAGS_MANAGED_DICT): ma_values->embedded. Такие "словари" хранятся прямо в памяти самого объекта (не более 16 объектов): PyObject header | object fields | PyDictValues header | values[0..capacity-1]На чем я вчера и погорел, когда дизайнил свою C-API функцию
PyDict_AsFrozenDictAndClear.Такие словари можно "материализовать" в обычные:
instance.__dict__ как раз вызовет такую машинерию при обращении. Словарь и instance.__dict__ - отличаются примерно всем внутри до материализации.Важные детали реализации
- У ключей есть свой refcount. Потому что ключи могут переиспользоваться в разных словарях, но они не
PyObject *. В CPython есть много отдельных refcount штук. Если интересно, могу подробнее рассказать.- А Py_EMPTY_KEYS вообще бесмертный объект
- DictWatcher'ы и
_ma_watcher_tag нужны, чтобы управлять Tier 1 speciailizing оптимизациями. Изменился объект или тип? Watcher скинет статистику для данного объекта в интерпретаторе. Аналогично и dk_version - для использования в качестве ключа для кеша в JIT- PyFrozenDict устроен точно так же, только сразу хранит в себе
ma_hash, для быстрого хешированияЧто мы не успели обсудить в 1 части? Саму хештаблицу, логику увеличения памяти под ключи, поиск по хешу и логику сравнения значений с одинаковым хешом, какие бывают слоты, локи для FT.
Обсуждение: Узнали ли вы что-то новое о словарях? Были ли у вас такие вопросы на собесе?