[Перевод] 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)
Для поиска свободного слота мы используем линейное пробирование — оно просто проверяет следующие слоты по порядку.
Слот 3 занят (ключ 56).
Слот 4 занят (ключ 32).
Слот 5 занят (ключ 21).
Слот 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).
Вставка работает следующим образом
Вычисляем хеш (hash (key)) и разбиваем его на две части: верхние 57 бит (называемые h1) и нижние 7 бит (называемые h2).
Верхние биты (h1) используются для выбора первой группы для рассмотрения: h1% 2 в данном случае, так как есть только 2 группы.
Внутри группы все слоты равноправны для хранения ключа. Сначала мы проверяем, содержит ли какой‑либо слот уже этот ключ — если да, то это обновление, а не новая вставка.
Если ни один слот не содержит ключ, то ищем пустой слот для его размещения.
Если свободных слотов нет, продолжаем последовательность пробирования, переходя к следующей группе.
Шаг 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
