Go 1.24 — swiss tables новая реализация map

В Go 1.24 встроенная реализация map была полностью переработана и теперь основана на Swiss Table. В этой статье мы рассмотрим, какие преимущества даёт Swiss Table по сравнению с традиционными хеш‑таблицами.

В приведённом выше графике мы видим заметно различающиеся модели потребления памяти между SwissMap и встроенной картой (map) в Go. Для сравнения также включено потребление памяти массивом, хранящим тот же набор данных. Потребление памяти стандартной реализации структуры данных map — выглядит как ступенчатая функция, поскольку она всегда создаётся с числом бакетов, равным степени двойки. Это связано с классической оптимизацией, основанной на побитовых операциях.

Любой поиск в хеш‑таблице (как с открытым, так и с закрытым хешированием) должен выбрать начальную позицию для своей последовательности пробирования на основе хеша запрашиваемого ключа. Преобразование хеш‑значения в номер бакета или слота обычно выполняется с помощью операции нахождения остатка от деления. Однако операция остатка от деления (%) довольно затратна по числу тактов процессора. Но если делитель — это степень двойки, то операцию% можно заменить на сверхбыструю битовую маску младших n битов. По этой причине многие, если не большинство, хеш‑таблиц ограничены размерами, кратными степеням двойки.

Часто это создаёт незначительный избыточный расход памяти, но при выделении хеш‑таблиц с миллионами элементов влияние становится ощутимым! Как показано на графике выше, стандартная реализация map в Golang в среднем потребляет на 63% больше памяти, чем SwissTable!

Немного истории

Концепция хеш‑таблицы впервые была описана Хансом Петером Луном в 1953 году во внутренней записке IBM. В ней предлагалось ускорить поиск, распределяя элементы по «бакетам» и используя связанный список для разрешения коллизий, когда бакет уже содержит элемент. Сегодня такой метод известен как хеш‑таблица с цепочечным хешированием (chaining).

В 1954 году Джин А. Амдал, Элейн М. Макгроу и Артур Л. Самуэль впервые применили метод «открытой адресации» при программировании компьютера IBM 701. При этом, если бакет уже занят, новый элемент помещается в следующий свободный бакет. Этот метод был формализован и опубликован в 1957 году У. Уэсли Петерсоном в статье «Addressing for Random‑Access Storage». Сегодня это называется открытой адресацией с линейным пробированием (linear probing).

В 2017 году Сэм Бензакен, Алкис Евлогименос, Мэтт Кулукундис и Роман Перепелица из Google представили новый дизайн хеш‑таблиц на C++, названный «Swiss Tables». В 2018 году их реализация была открыта в библиотеке Abseil C++.

Основное отличие в дизайне

Ключевое различие между классической реализацией map в Golang и SwissMap заключается в методе хеширования.

Классическая реализация использует «открытое хеширование» (open hashing), где пары ключ‑значение с одинаковыми хешами группируются в один «бакет». Чтобы найти значение по ключу, сначала выбирается бакет на основе хеша ключа, а затем происходит итерация по всем парам ключ‑значение в этом бакете, пока не будет найдено совпадение.

Одной из ключевых оптимизаций встроенной map в Go является использование «дополнительных битов хеша» (extra hash bits), которые позволяют ускорить проверку равенства при итерации по слотам в бакете.

Перед тем как напрямую сравнивать запрашиваемый ключ с кандидатом, алгоритм поиска сначала сравнивает 8-битный хеш каждого ключа (он независим от хеша бакета), чтобы определить, возможен ли положительный результат. Этот быстрый предварительный тест имеет ложноположительный результат в 1 из 256 случаев, но значительно ускоряет поиск внутри бакета хеш‑таблицы.

Swiss Tables относятся к классу хеш‑таблиц с открытой адресацией (open‑addressed hash table).

В хеш‑таблицах с открытой адресацией все элементы хранятся в едином массиве. Каждое место в этом массиве называется слотом.

Слот, в который должен попасть ключ, определяется хеш‑функцией hash(key).

• Хеш‑функция отображает каждый ключ в целое число,

• Один и тот же ключ всегда получает одно и то же число,

• Разные ключи в идеале должны равномерно распределяться по диапазону чисел.

Ключевая особенность хеш‑таблиц с открытой адресацией — способ разрешения коллизий.

• Если слот уже занят (коллизия), ключ помещается в другое место в массиве.

• Для этого используется последовательность пробирования (probe sequence) — поиск ближайшего свободного слота.

• Поиск продолжается, пока не найдётся пустой слот.

Вот как это работает:

Предположим, у нас есть хеш‑таблица с 16 слотами. В таблице уже хранятся несколько ключей:

Теперь попробуем вставить новый ключ 98.

• Вычисляем hash(98)% 16 = 7.

• Слот 7 пуст, поэтому просто вставляем 98.

Теперь попробуем вставить ключ 25.

• hash(25)% 16 = 3.

• Слот 3 уже занят (ключ 56) → произошла коллизия.

Линейное пробирование (Linear probing)

Для поиска свободного слота мы используем линейное пробирование — оно просто проверяет следующие слоты по порядку.

1. Слот 3 занят (ключ 56).

2. Слот 4 занят (ключ 32).

3. Слот 5 занят (ключ 21).

4. Слот 6 свободен → вставляем ключ 25.

При поиске ключа 25 алгоритм действует так же:

• Начинаем с слота 3 → там ключ 56.

• Идём дальше по слоту 4 → 32.

• Дальше по слоту 5 → 21.

• Наконец, в слоте 6 находим ключ 25.

Увеличение размера хеш-таблицы

В примере выше у нас было 16 слотов. А что, если мы вставим больше 16 элементов?

Когда хеш‑таблица заканчивает свободные слоты, она увеличивает размер, обычно удваивая массив. Все существующие элементы перехешируются и заново вставляются в новый массив. Однако таблицы с открытой адресацией не ждут полного заполнения массива, прежде чем расширяться.
Почему?

• Чем больше заполнен массив, тем длиннее средняя последовательность пробирования.

• В примере с ключом 25 нам пришлось пройти 4 слота, чтобы найти пустой.

• Если останется только 1 пустой слот, в худшем случае придётся сканировать весь массив O(n).

Чтобы этого избежать, хеш‑таблицы вводят порог заполненности (load factor).

• Обычно он составляет 70–90%.

• Когда количество занятых слотов превышает этот порог, таблица расширяется, чтобы избежать слишком длинных последовательностей пробирования.

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%.

Вы можете отключить новую реализацию, установив GOEXPERIMENT=noswissmap во время сборки. Это актуально для старых процессоров в которых не реализован SIMD

источники:
https://www.dolthub.com/blog/2023–03–28-swiss‑map/
https://medium.com/@lordmoma/go-1–24s‑swiss‑tables‑the‑silver‑bullet‑or‑just‑a-shiny‑new‑gadget-8e5f7f37c2a8 
https://go.dev/blog/swisstable