Swiss Tables в Go 1.24

Как было раньше: bucket-based map

Вплоть до Go 1.23 стандартная map в Go реализовывалась как хеш-таблица с цепочками коллизий на основе связанных списков.

Структура данных

• Хеш-таблица разделена на бакеты (buckets), каждый из которых вмещает до 8 пар ключ–значение.
• Бакеты организованы в два массива: один - для хеш-префиксов (tophash), второй - для самих данных (keys / values), хранящихся интерливом (interleaved layout). Это улучшает кэш-локальность при последовательном сканировании.

Почему именно 8? Это компромисс между локальностью данных и издержками на рост таблицы. При среднем заполнении >6.5 элементов на бакет запускается инкрементальная эвакуация (incremental grow), чтобы сохранить амортизированную сложность O(1).

Алгоритм вставки

1. Ключ проходит через хеш-функцию (memhash, strhash и т.д. - в зависимости от типа).
2. Остаток от деления хеша на число бакетов (hash % nbuckets) даёт индекс целевого бакета.
3. Внутри бакета:
   • Если ячейка свободна - записываем туда хеш-префикс (tophash = hash >> (64-8)) и пару ключ–значение.
   • Если ячейка занята, но с тем же tophash - проверяем полное равенство ключей.
   • При коллизии и переполнении бакета (>8 элементов) создаётся оверфлоу-бакет, связанный через указатель - получается linked list оверфлоу-бакетов.

Проблемы старой реализации

• Плохая локальность при поиске
  В худшем случае приходится «прыгать» по памяти через оверфлоу-бакеты. Это разрушает spatial locality и плохо ложится на CPU prefetcher.

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

• Фрагментация памяти
  Оверфлоу-бакеты аллоцируются отдельно, что увеличивает давление на аллокатор и снижает плотность данных.

Как стало теперь: Swiss Tables

Начиная с Go 1.24, стандартная map перешла на реализацию на основе Swiss Tables - структуры, придуманной в Google и впервые применённой в Abseil (C++), а позже - в Rust (hashbrown), Java (fastutil) и Python (начиная с 3.6 для dict, в модифицированном виде).

Дизайн-обсуждение: https://github.com/golang/go/issues/54766

Почему не раньше? Swiss Tables заметно сложнее в реализации, особенно в контексте Go: нужно аккуратно управлять памятью, не хранить указатели в метаданных (совместимость с GC), и сохранить корректное поведение при конкурентном доступе. Только к 2025 году инфраструктура рантайма Go стала достаточно зрелой для безопасного внедрения.

Основные идеи Swiss Tables

1. Группы вместо бакетов

Память делится на группы по 8 слотов, выровненные по границе кэш-линии (64 байта). Каждая группа - это единый плотный блок, содержащий:

• 8 × 1-байтных control bytes
• 8 × пар ключ–значение (интерливом)

2. Control byte - ключ к скорости

Для каждого слота хранится 1 байт:

• 0x80 - слот пуст (empty)
• 0x00 - слот удалён (tombstone)
• 0x01..0x7F - значение h2 (младшие 7 бит хеша)

Это позволяет загружать control-байты группы одним чтением и выполнять SIMD-сканирование:

• x86-64: PSHUFB
• ARM64: tbl

За одну инструкцию можно проверить сразу 8 слотов.

3. Поиск без ветвлений

При поиске ключа:

1. Вычисляем хеш ключа.
2. Делим его на:
   • h1 = hash >> 7
   • h2 = hash & 0x7F
3. Начальная группа определяется как h1 % num_groups.
4. Далее выполняется линейное пробирование (linear probing):
   • Внутри группы SIMD-ом ищутся слоты с совпадающим h2.
   • При совпадении проверяется полное равенство ключа.
   • Если встречается empty-слот - поиск завершается: ключа в таблице нет.

Никаких связанных списков. Никаких оверфлоу-бакетов. Только плотные массивы и последовательный доступ к памяти.

Алгоритм вставки

1. Хешируем ключ → получаем 64-битный hash.
2. Вычисляем h1 и h2.
3. Определяем стартовую группу.
4. В цикле:
   • Загружаем control-байты группы.
   • SIMD-поиском находим:
     • либо слот с совпадающим h2
     • либо первый empty слот
   • При совпадении h2 проверяем ключ и обновляем значение.
   • При empty - вставляем новый элемент и записываем h2 в control byte.
   • Если группа полностью занята - переходим к следующей.

Цена такого подхода - чуть более сложная логика вставки и роста таблицы, но она с лихвой окупается кэш-локальностью.

Преимущества

По данным релиз-ноута Go 1.24:

• map[int]int get: ~+210% throughput
• map[string]int set: ~+170% throughput
• Пиковое потребление памяти: ~-12% на больших мапах

Что не изменилось?

• Интерфейс: make(map[K]V), m[k] = v, delete(m, k) - без изменений.
• Порядок итерации по-прежнему не определён и может отличаться между запусками.
• map остаётся не потокобезопасной: гонки приводят к панике или неопределённому поведению.
• Внутреннее представление map по-прежнему не является стабильным ABI для unsafe-кода.