Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Новые мапы в Go. Вова Марунин, Clatch, МТС

Новые мапы в Go. Вова Марунин, Clatch, МТС

В свежем релизе Go 1.24 поменялась имплементация базового типа map и библиотечного sync.Map. В рамках доклада мы разберём каждый из этих типов, рассмотрим, как они устроены под капотом, как работают основные операции (вставка, удаление) и узнаем, что изменилось в релизе Go 1.24 (спойлер: всё). А также поймем, откуда пришли эти изменения, как было раньше, и что есть теперь.

Lamoda Tech

May 06, 2025

Transcript

41 slides
  1. 4 Новые мапы в Go 1.24 Релиз в феврале 2025

    Базовая структура Спрашивают на собеседованиях Можно выключить GOEXPERIMENT=noswissmap
  2. 7 ХЕШ-ФУНКЦИЯ • Одно и то же значение для ключа

    • Значения похожи на случайное число • Вероятность хоть одной коллизии • Для 64 битной хешфункции p=10^-6 при 1,6 млн ключей • Парадокс близнецов
  3. 8 Что делать с коллизиями (закрытая адресация) Таблица списков Проверяем

    список последовательно Добавление, удаление как в списке
  4. 9 Что делать с коллизиями (открытая адресация) Все элементы в

    таблице Поиск пока не найдём пустую ячейку Для удаления специальный статус Tombstone
  5. 10 Что делать с коллизиями Рост мапы Чем больше loadFactor,

    тем больше коллизий и дольше операции, 100% недостижим Мапа не растёт сама Мапа перестраивается во время очередной вставки Эвакуация. Мапа перестраивается во время обращений
  6. 11 А что говорит наука? В январе 2025 года вышла

    статья Optimal Bounds for Open Addressing Without Reordering Mart´ın Farach-Colton , Andrew Krapivin, William Kuszmaul https://arxiv.org/abs/2501.02305v2 В ней доказали пределы эффективности для жадных алгоритмов И показали что эти оценки можно улучшить для нежадных алгоритмов Ждём новую версию мап через несколько лет?
  7. 13 История появления SwissMap в Go 2017 Представлены на конференции

    cppcon 2018 имплементация в C++ библиотеке abseil C 1.36 (2019) включены в Rust В 2022 разработчик из ByteDance предложил мапы В 2024 подключился разработчик из CocroachDB Февраль 2025 Go 1.24 релиз
  8. 14 МАПЫ ДО GO1.24 Закрытая адресация, список бакетов Рост памяти

    в 2 раза и не возвращает память при уменьшении мапы Процесс эвакуации (ещё x1.5 к потреблению памяти) Случайный порядок итерации по мапе Нельзя взять указатель на значение в мапе Load Factor 6,5/8 (81,25%)
  9. 15 МАПЫ С 1.24 Каталог хеш-таблиц групп слотов Память не

    возвращает, но нет скачков Использует SIMD для ускорения Нет эвакуации Нельзя взять указатель на значение LoadFactor 7/8 (87,5%)
  10. 16 ХЕШ-ФУНКЦИЯ • Аппаратный AES или программный wyhash • Seed

    определяется случайно при создании мапы • Определяется для типа при компиляции • Рекурсивно идёт по указателям • 64 бита, 57 бит h1 + 7 бит h2
  11. 17 ГРУППА • Слот это пара ключ и значение •

    Группа из 8 слотов • Слот может быть пустой, удалённый и занятый • 64 бита метаданные (8 слотов за одну операцию), обрабатываются SIMD инструкциями
  12. 18 ХЕШ-ТАБЛИЦА (поиск) • Открытая адресация с quadratic probing •

    Выбор группы по последним битам h1 • Сравниваем всю группу по метаданным, если совпадение то по ключам • Пока не найдено переходим на группу n+=1, потом n+=2 и т.д • Конец поиска только если есть свободные слоты в группе (не tombstone)
  13. 19 ХЕШ-ТАБЛИЦА (удаление) • Открытая адресация с quadratic probing •

    Поиск ключа • Если в группе с ключом есть пустые слоты – ставим пустой, иначе tombstone
  14. 20 ХЕШ-ТАБЛИЦА (вставка) • Открытая адресация с quadratic probing •

    Поиск ключа • Конец поиска если дошли до группы с пустым слотом • Добавляем элемент в пустой слот • Оптимизация, если в цепочки были tombstone – заполняем первый из них
  15. 21 ХЕШ-ТАБЛИЦА (рост) • LoadFactor 7/8 (87,5%) (свободных не менее

    1/8) • Рост таблицы в 2 раза, перенос данных сразу • Максимум 1024 слотов (128 групп) • При переполнении таблицы сплит на 2 таблицы
  16. 22 Каталог (DIRECTORY) • Массив размером 2^N, элементы – ссылки

    на хеш-таблицы • Выбор по первым N битам h1 • Таблица может быть в нескольких нодах
  17. 23 ИТЕРАТОРЫ • Случайный порядок итерации • Случайный порядок начала

    итератора • Удалённые ключи не возвращать • Возвращать изменённые значения • Добавленные значения могут вернуться, а могут и не вернуться
  18. 24 БЕНЧМАРКИ • По тестам авторов всё хорошо, прирост производительности

    на единицы-десятки процентов • map operations are up to 60% faster than in Go 1.23 • Overall, in full application benchmarks, we found a geometric mean CPU time improvement of around 1.5%.
  19. 25 БЕНЧМАРКИ (скорость) 357 бенчмарков в тикете (линукс, amd64 Xeon,

    меньше - лучше) • MapIter от -15% до 0% • MapIterLowLoad от -57% до +20% • MapIterGrow от -22% до -10% • MapGetHit от -35% до +23% (хуже работает на больших мапах) • MapGetMiss от -55% до 0% • MapPutGrow от -12% до +21% (почти везде swiss хуже) • MapPutPreAllocate от -40% до +45% (swiss везде быстрее, но на больших мапах замедление) • MapPutReuse от -40% до +53% (swiss везде быстрее, но на больших мапах замедление) • MapPutDelete от -24% до +30%
  20. 27 Лучше используется память Чуть быстрее работают (1,5%) Есть заделы

    для оптимизации Нет эвакуации SwissTable в Go 1.24, ЧТО ХОРОШЕГО
  21. 28 Не отдают память, а могли бы Местами работают медленнее

    Баг с map[int]struct{} (потребление памяти) Не на всех платформах SIMD SwissTable в Go 1.24, ЧТО ПЛОХОГО Некоторые вставки - долгие
  22. 30 Новые sync.Map в Go 1.24 Не спрашивают на собеседованиях

    Можно выключить GOEXPERIMENT=nosynchashtriemap Конкуретнтный доступ без блокировок Лучше если ключи создаются единожды Лучше если у горутин disjoint set of keys Подумайте, может лучше map+RWMutex
  23. 31 История появления sync.Map в Go Добавлены в go1.9 Пакет

    uniq в go1.23 Своя реализация HashTrieMap для пакета uniq Оказалось, что эта HashTrieMap работает быстрее Февраль 2025 Go 1.24 релиз
  24. 32 sync.Map • Trie от хеша, 4 бита на уровень

    • Листья – список ключ-значение • Основа atomic.Pointer • Все чтения без mutex • Все правки с mutex максимально низко в дереве • В самом низу список ключ-значение
  25. 33 sync.Map код type node[K comparable, V any] struct {

    isEntry bool } // 16 children. type indirect[K comparable, V any] struct { node[K, V] dead atomic.Bool mu Mutex // Protects mutation to children and any children that are entry nodes. parent *indirect[K, V] children [nChildren]atomic.Pointer[node[K, V]] } type entry[K comparable, V any] struct { node[K, V] overflow atomic.Pointer[entry[K, V]] // Overflow for hash collisions. key K value V }
  26. 35 БЕНЧМАРКИ (скорость) • По тестам авторов • The load-hit

    case is slightly slower due to Swiss Tables improving the performance of the old sync.Map • Ускорение по всем тестам ~50% • Удаление существующих ключей гораздо дольше • Разброс результатов гораздо меньше
  27. 37 Быстрее работают Возвращают память Все чтения без блокировки Время

    запроса не зависит от размера мапы sync.Map что изменилось
  28. 38 Достижения CS доехали и до Go Мапы работают теперь

    быстрее Есть что доработать (SIMD, память, баги) Всегда можно сделать свои мапы Выводы На переход на 1.24 не влияет никак

More Decks by Lamoda Tech

Other Decks in Technology