Python. Внутреннее устройство множеств set и словарей dict. Часть 2 из 2

Часть 1

Содержание

• 1. Эксперимент с производительностью

• 2. Хэши и равенство (equality)

  • 2.1 Коллизии хэша

• 3. Хэш-таблицы в set

  • 3.1. Алгоритм хэш-таблицы

  • 3.2. Практические выводы по тому как работает set

• 4. Хэш-таблицы в dict

  • 4.1. Как компактный dict экономит место и сохраняет порядок

  • 4.2 Алгоритм добавления элементов в компактный dict

  • 4.3. dict с общим доступом к ключам

  • 4.4. Практические выводы по тому как работает dict

• Примечания

4. Хэш-таблицы в dict

Пусть ваши хэши будут уникальными,
у ваших ключей редко возникают коллизии,
а ваши словари всегда будут упорядочены(6).

— Brandon Rhodes
The Dictionary Even Mightier

С 2012 года в реализации типа dict было проведено две крупные оптимизации для сокращения потребления памяти. Первая была предложена в PEP 412 — Key-Sharing Dictionary и реализована в Python 3.3(7). Вторая называется компактный dict и появилась в Python 3.6. Побочным эффектом оптимизации памяти компактного dict стало сохранение порядка вставки ключей. В следующих разделах мы обсудим компактный dict и новую схему совместного использования ключей, именно в таком порядке, для удобства изложения.

4.1. Как компактный dict экономит место и сохраняет порядок

? Это высокоуровневое объяснение реализации dict в Python. Одно из отличий заключается в том, что фактическая полезная доля хэш-таблицы dict составляет ⅓, а не ⅔ как в set. Фактическая доля ⅓ потребовала бы 16 buckets для хранения 4 элементов в моем примере dict, и диаграммы в этом разделе стали бы слишком большими, поэтому я делаю вид, что полезная доля равна ⅔ в этих объяснениях. Один из комментариев в Objects/dictobject.c объясняет, что любая дробь между ⅓ и ⅔ «кажется, хорошо работает на практике».

Рассмотрим dict, содержащий сокращенные названия дней недели с 'Mon' по 'Thu' и количество студентов, записанных на занятия по плаванию в каждый день:

>>> swimmers = {'Mon': 14, 'Tue': 12, 'Wed': 14, 'Thu': 11}

До оптимизации компактного dict хэш-таблица, лежащая в основе словаря swimmers, выглядела бы как на рис. 9. Как видите, в 64-битном Python каждый bucket содержит три 64-битных поля: хэш-код ключа, указатель на объект ключа и указатель на объект значения. Это 24 байта на bucket.

Первые два поля играют ту же роль, что и в реализации set. Чтобы найти ключ, Python вычисляет хэш-код ключа, извлекает индекс из ключа, а затем просматривает хэш-таблицу, чтобы найти bucket с подходящим хэш-кодом и подходящим ключевым объектом. Третье поле обеспечивает основную функцию dict: сопоставление ключа с произвольным значением. Ключ должен быть хэшируемым объектом и алгоритм хэш-таблицы гарантирует, что он будет уникальным в dict. Но значение может быть любым объектом — оно не обязательно должно быть хэшируемым или уникальным.

Raymond Hettinger заметил, что можно добиться значительной экономии, если хэш-код, указатель на ключ и значение хранить в массиве entries, в котором нет пустых строк, а сама хэш-таблица будет представлять собой разреженный массив с гораздо меньшими buckets, содержащими индексы в массиве entries(8). В своем оригинальном сообщении на python-dev Hettinger назвал хэш-таблицу indices (индексы). Ширина buckets в indices меняется по мере роста dict, начиная с 8 бит на bucket (достаточно для индексации до 128 записей), при этом для специальных целей оставляются отрицательные значения, такие как -1 для пустых и -2 для удаленных.

В качестве примера, dict swimmers будет храниться в таком виде, как показано на рис. 10.

Предполагая 64-битную сборку CPython, наш 4-элементный dict swimmers занял бы 192 байта памяти в старой схеме: 24 байта на bucket, умноженные на 8 строк. Эквивалентный компактный dict использует 104 байта: 96 байт в записях (24 * 4), плюс 8 байт для buckets в индексах, сконфигурированных как массив из 8 байт.

В следующем разделе описывается, как используются эти два массива.

4.2 Алгоритм добавления элементов в компактный dict

Шаг 0: установите индексы

Таблица индексов изначально задается в виде массива байтов со знаком с 8 buckets, каждый из которых инициализируется значением -1, что означает «пустой bucket«. До 5 из этих buckets в конечном итоге будут содержать индексы строк в массиве entries, оставляя ⅓ из них с -1. Другой массив, entries, будет содержать данные ключ/значение с теми же тремя полями, что и в старой схеме, но в порядке вставки.

Шаг 1: вычисление хэш-кода для ключа

Чтобы добавить пару ключ-значение ('Mon', 14) в dict swimmers, Python сначала вызывает hash('Mon'), чтобы вычислить хэш-код этого ключа.

Шаг 2: поиск записей по индексам

Python вычисляет hash('Mon') % len(indices). В нашем примере это 3. Смещение 3 в indices содержит -1, это пустой bucket.

Шаг 3: помещаем ключ-значение в записи, обновляя индексы

Массив entries пуст, поэтому следующее доступное смещение в нем — 0. Python помещает 0 по смещению 3 в indices и сохраняет хэш-код ключа, указатель на объект ключа 'Mon' и указатель на значение int 14 по смещению 0 в entries. На рис. 11 показано состояние массивов, когда значение swimmers равно {'Mon': 14}.

Шаги для следующего элемента

Добавить ('Tue', 12) к swimmers:

1. Вычислить хэш-код ключа 'Tue'.

2. Вычислите смещение в индексах, как hash('Tue') % len(indices). Это 2. В indices[2] есть -1. Пока что коллизий нет.

3. Поместим следующее доступное смещение записи, 1, в indices[2], затем сохраним запись в entries[1].

Теперь состояние выглядит так, как показано на рис. 12. Обратите внимание, что entries хранит пары ключ-значение в порядке вставки.

Шаги при коллизии

1. Вычислить хэш-код ключа 'Wed'.

2. Теперь hash('Wed') % len(indices) равно 3. В indices[3] есть 0, указывающий на существующую запись. Посмотрите на хэш-код в entries[0]. Это хэш-код для 'Mon', который, как оказалось, отличается от хэш-кода для 'Wed'. Это несовпадение сигнализирует о коллизии. Проверить следующий индекс: indices[4]. Это -1, поэтому его можно использовать.

3. Сделать indices[4] = 2, потому что 2 — это следующее доступное смещение в entries. Затем заполните entries[2], как обычно.

После добавления ('Wed', 14) у нас есть рис. 13

Как растет компактный dict

Напомню, что изначально buckets в массиве indices имеют размер 8 байтов со знаком, что достаточно для хранения смещений до 5 записей, при этом ⅓ buckets остаются пустыми. Когда в dict добавляется 6-й элемент, indices релоцируют 16 buckets — достаточно для 10 смещений. Размер indices удваивается по мере необходимости, сохраняя при этом байты со знаком, пока не придет время добавить 129-й элемент в dict. В этот момент массив indices содержит 256 8-битных байтов. Однако, одного байта со знаком недостаточно для хранения смещений после 128 записей, поэтому массив indices перестраивается на 256 16-битных buckets для хранения целых чисел со знаком, достаточно широких для представления смещений 32768 строк в таблице entries. Следующее изменение размера происходит при 171-м добавлении, когда indices становятся более чем на ⅔ заполненными. Тогда количество buckets в indices удваивается до 512, но каждый bucket по прежнему имеет ширину 16 бит. В общем, массив indices растет за счет удвоения числа buckets, а также — реже — за счет удвоения ширины каждого bucket, чтобы вместить растущее число строк в entries.

На этом мы закончим обзор реализации компактного dict. Я опустил много деталей, но теперь давайте рассмотрим другую оптимизацию для экономии места в dict — совместное использование ключей.

4.3. dict с общим доступом к ключам

Экземпляры пользовательских классов хранят свои атрибуты в атрибуте — __dict__(9), который представляет собой обычный dict. Экземпляр __dict__ сопоставляет имена атрибутов со значениями атрибутов. Чаще всего все экземпляры имеют одинаковые атрибуты с разными значениями. Когда это происходит, два из трех полей в таблице записей для каждого экземпляра имеют одинаковое содержимое: хэш-код имени атрибута и указатель на имя атрибута. Только указатель на значение атрибута отличается.

В PEP 412 — Key-Sharing Dictionary Mark Shannon предложил разделить хранение dict-ов, используемых в качестве экземпляров __dict__, таким образом, чтобы каждый хэш-код атрибута и указатель хранились только один раз, связанный с классом, а значения атрибутов хранились в параллельных массивах указателей, прикрепленных к каждому экземпляру.

Возьмем класс Movie, в котором все экземпляры имеют одинаковые атрибуты 'title', 'release', 'directors' и 'actors', на рис. 14 показана организация совместного использования ключей в разделенном dict — также реализованном с помощью новой компактной схемы.

В PEP 412 были введены термины combined-table для обсуждения старой схемы и split-table для предлагаемой оптимизации.

combined-table по-прежнему используется по умолчанию, когда вы создаете dict с помощью литерального синтаксиса или вызываете dict(). split-table dict создается для заполнения специального атрибута __dict__ экземпляра, когда он является первым экземпляром класса. Таблица ключей (рис. 14) затем кэшируется в объекте класса. Это позволяет использовать тот факт, по большей части в объектно-ориентированном коде Python все атрибуты экземпляра назначаются в методе __init__. Первый экземпляр (и все последующие) будет хранить только свой собственный массив значений. Если экземпляр получает новый атрибут, не найденный в таблице общих ключей, то __dict__ этого экземпляра преобразуется в форму combined-table. Однако если этот экземпляр является единственным в своем классе, то __dict__ преобразуется обратно в split-table, поскольку предполагается, что последующие экземпляры будут иметь тот же набор атрибутов и совместное использование ключей будет полезным.

Структура PyDictObject, представляющая dict в исходном коде CPython, одинакова как для dict с combined-table, так и для dict со split-table . Когда dict преобразуется из одной схемы в другую, изменения происходят в полях PyDictObject, с помощью других внутренних структур данных.

4.4. Практические последствия работы dict

• Ключи должны быть хэшируемыми объектами. Они должны реализовывать соответствующие методы __hash__ и __eq__ («Python. К вершинам мастерства» 2-е изд. — Словари и множества — Что значит «хэшируемый»?, стр. 105).

• Поиск по ключу выполняется почти так же быстро, как поиск элементов в set.

• Упорядочивание элементов сохраняется в таблице записей — это было реализовано в CPython 3.6, а в 3.7 стало официальной функцией языка.

• Чтобы сэкономить память, не создавайте атрибуты экземпляра вне метода __init__. Если все атрибуты экземпляра будут созданы в __init__, то в __dict__ ваших экземпляров будет использоваться схема split-table, разделяя те же индексы и массив ключевых записей, которые хранятся вместе с классом.

Примечания

6. Доклад на PyCon 2017: https://youtu.be/66P5FMkWoVU?t=56

7. Это было до того, как я начал писать 1-е издание Fluent Python, но я это пропустил.

8. Иронично, что buckets в хэш-таблице здесь не содержат хэш-кодов, а только индексы к массиву записей, где находятся хэш-коды. Но концептуально массив индексов действительно является хэш-таблицей в этой реализации, даже если в его buckets нет хэшей.

9. Если у класса нет атрибута __slots__.

↑ К содержанию