Golang map и Swiss Table

Swiss Table — это усовершенствованная версия хеш‑таблицы с открытой адресацией. Давайте разберёмся, чем она лучше классической реализации.

Как и прежде, данные хранятся в едином массиве. Однако теперь массив разбивается на логические группы по 8 слотов (возможны и более крупные размеры групп).

Кроме того, каждая группа сопровождается 64-битным управляющим словом (control word), которое содержит метаданные.

• Каждый из восьми байт управляющего слова соответствует одному из 8 слотов в группе.
• Значение каждого байта указывает, является ли слот пустым, удалённым или занятым.
• Если он используется, байт содержит 7 младших бит хеша для ключа этого слота (так называемого h2).

Вставка работает следующим образом

1. Вычисляем хеш (hash(key)) и разбиваем его на две части: верхние 57 бит (называемые h1) и нижние 7 бит (называемые h2).
2. Верхние биты (h1) используются для выбора первой группы для рассмотрения: h1% 2 в данном случае, так как есть только 2 группы.
3. Внутри группы все слоты равноправны для хранения ключа. Сначала мы проверяем, содержит ли какой‑либо слот уже этот ключ — если да, то это обновление, а не новая вставка.
4. Если ни один слот не содержит ключ, то ищем пустой слот для его размещения.
5. Если свободных слотов нет, продолжаем последовательность пробирования, переходя к следующей группе.

Шаг 3 — это момент, когда происходит «магия» Swiss Table. Нам нужно проверить, содержит ли какой‑либо слот в группе искомый ключ. Наивный подход — выполнить линейный поиск и сравнить все 8 ключей. Однако управляющее слово (control word) позволяет сделать это более эффективно.

Каждый байт в управляющем слове содержит нижние 7 бит хеша (h2) для соответствующего слота. Если мы определим, какие байты в управляющем слове содержат искомый h2, у нас появится набор кандидатов на совпадение.

Другими словами, мы хотим выполнить побайтовое сравнение на равенство внутри управляющего слова. Например, если мы ищем ключ 32, у которого h2 = 89, то операция, которую мы хотим выполнить, будет выглядеть следующим образом.

Только во втором слоте (значение 89) возможно совпадение.

Эта операция выполняется аппаратно с помощью SIMD (Single Instruction, Multiple Data).

• Одна операция проверяет все 8 слотов параллельно.
• Если SIMD недоступен, алгоритм использует комбинацию обычных арифметических и битовых операций.

В результате мы получаем набор кандидатных слотов.

• Слоты, где h2 не совпадает, не могут содержать нужный ключ, поэтому их можно пропустить.
• Слоты, где h2 совпадает, являются потенциальными совпадениями, но нам всё равно нужно сравнить весь ключ, так как возможны коллизии (вероятность коллизии для 7-битного хеша — 1/128, что довольно мало).

Эта операция очень мощная, так как мы фактически выполняем 8 шагов последовательного поиска одновременно, в параллельном режиме. Это ускоряет поиск и вставку, уменьшая среднее число необходимых сравнений.

Итоги

Такое улучшение процесса пробирования позволило увеличить максимальный коэффициент загрузки для хеш‑таблиц Swiss Table по сравнению с предыдущими реализациями, что снижает средний объем потребляемой памяти.

• Операции чтения и записи в map с более чем 1024 элементами стали быстрее примерно на 30%.
• Запись в заранее выделенные map стала быстрее примерно на 35%.
• Итерация ускорилась в среднем на 10%, а для map с небольшим числом записей относительно размера — до 60%.

Взято с: https://telegra.ph/Go-124—swiss-tables-novaya-realizaciya-map-03-13