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

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

Transcript

1. Новые мапы в Go 1.24 Митап в Lamoda 25.04.25
2. МАРУНИН ВЛАДИМИР МТС Диджитал Backend разработчик
3. { Обычные мапы
4. 4 Новые мапы в Go 1.24 Релиз в феврале 2025 Базовая структура Спрашивают на собеседованиях Можно выключить GOEXPERIMENT=noswissmap
5. { Немножко теории
6. 6 Деревья поиска Хеш-таблицы map[key] = value map, dict, ассоциативный массив
7. 7 ХЕШ-ФУНКЦИЯ • Одно и то же значение для ключа • Значения похожи на случайное число • Вероятность хоть одной коллизии • Для 64 битной хешфункции p=10^-6 при 1,6 млн ключей • Парадокс близнецов
8. 8 Что делать с коллизиями (закрытая адресация) Таблица списков Проверяем список последовательно Добавление, удаление как в списке
9. 9 Что делать с коллизиями (открытая адресация) Все элементы в таблице Поиск пока не найдём пустую ячейку Для удаления специальный статус Tombstone
10. 10 Что делать с коллизиями Рост мапы Чем больше loadFactor, тем больше коллизий и дольше операции, 100% недостижим Мапа не растёт сама Мапа перестраивается во время очередной вставки Эвакуация. Мапа перестраивается во время обращений
11. 11 А что говорит наука? В январе 2025 года вышла статья Optimal Bounds for Open Addressing Without Reordering Mart´ın Farach-Colton , Andrew Krapivin, William Kuszmaul https://arxiv.org/abs/2501.02305v2 В ней доказали пределы эффективности для жадных алгоритмов И показали что эти оценки можно улучшить для нежадных алгоритмов Ждём новую версию мап через несколько лет?
12. { Назад к практике
13. 13 История появления SwissMap в Go 2017 Представлены на конференции cppcon 2018 имплементация в C++ библиотеке abseil C 1.36 (2019) включены в Rust В 2022 разработчик из ByteDance предложил мапы В 2024 подключился разработчик из CocroachDB Февраль 2025 Go 1.24 релиз
14. 14 МАПЫ ДО GO1.24 Закрытая адресация, список бакетов Рост памяти в 2 раза и не возвращает память при уменьшении мапы Процесс эвакуации (ещё x1.5 к потреблению памяти) Случайный порядок итерации по мапе Нельзя взять указатель на значение в мапе Load Factor 6,5/8 (81,25%)
15. 15 МАПЫ С 1.24 Каталог хеш-таблиц групп слотов Память не возвращает, но нет скачков Использует SIMD для ускорения Нет эвакуации Нельзя взять указатель на значение LoadFactor 7/8 (87,5%)
16. 16 ХЕШ-ФУНКЦИЯ • Аппаратный AES или программный wyhash • Seed определяется случайно при создании мапы • Определяется для типа при компиляции • Рекурсивно идёт по указателям • 64 бита, 57 бит h1 + 7 бит h2
17. 17 ГРУППА • Слот это пара ключ и значение • Группа из 8 слотов • Слот может быть пустой, удалённый и занятый • 64 бита метаданные (8 слотов за одну операцию), обрабатываются SIMD инструкциями
18. 18 ХЕШ-ТАБЛИЦА (поиск) • Открытая адресация с quadratic probing • Выбор группы по последним битам h1 • Сравниваем всю группу по метаданным, если совпадение то по ключам • Пока не найдено переходим на группу n+=1, потом n+=2 и т.д • Конец поиска только если есть свободные слоты в группе (не tombstone)
19. 19 ХЕШ-ТАБЛИЦА (удаление) • Открытая адресация с quadratic probing • Поиск ключа • Если в группе с ключом есть пустые слоты – ставим пустой, иначе tombstone
20. 20 ХЕШ-ТАБЛИЦА (вставка) • Открытая адресация с quadratic probing • Поиск ключа • Конец поиска если дошли до группы с пустым слотом • Добавляем элемент в пустой слот • Оптимизация, если в цепочки были tombstone – заполняем первый из них
21. 21 ХЕШ-ТАБЛИЦА (рост) • LoadFactor 7/8 (87,5%) (свободных не менее 1/8) • Рост таблицы в 2 раза, перенос данных сразу • Максимум 1024 слотов (128 групп) • При переполнении таблицы сплит на 2 таблицы
22. 22 Каталог (DIRECTORY) • Массив размером 2^N, элементы – ссылки на хеш-таблицы • Выбор по первым N битам h1 • Таблица может быть в нескольких нодах
23. 23 ИТЕРАТОРЫ • Случайный порядок итерации • Случайный порядок начала итератора • Удалённые ключи не возвращать • Возвращать изменённые значения • Добавленные значения могут вернуться, а могут и не вернуться
24. 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%.
25. 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%
26. 26 БЕНЧМАРКИ (память)
27. 27 Лучше используется память Чуть быстрее работают (1,5%) Есть заделы для оптимизации Нет эвакуации SwissTable в Go 1.24, ЧТО ХОРОШЕГО
28. 28 Не отдают память, а могли бы Местами работают медленнее Баг с map[int]struct{} (потребление памяти) Не на всех платформах SIMD SwissTable в Go 1.24, ЧТО ПЛОХОГО Некоторые вставки - долгие
29. { sync.Map
30. 30 Новые sync.Map в Go 1.24 Не спрашивают на собеседованиях Можно выключить GOEXPERIMENT=nosynchashtriemap Конкуретнтный доступ без блокировок Лучше если ключи создаются единожды Лучше если у горутин disjoint set of keys Подумайте, может лучше map+RWMutex
31. 31 История появления sync.Map в Go Добавлены в go1.9 Пакет uniq в go1.23 Своя реализация HashTrieMap для пакета uniq Оказалось, что эта HashTrieMap работает быстрее Февраль 2025 Go 1.24 релиз
32. 32 sync.Map • Trie от хеша, 4 бита на уровень • Листья – список ключ-значение • Основа atomic.Pointer • Все чтения без mutex • Все правки с mutex максимально низко в дереве • В самом низу список ключ-значение
33. 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 }
34. 34 Свойства sync.Map Сама инициализируется Возвращают память Хешфункция из пакета hash.maphash, random seed Итерация по порядку хешей
35. 35 БЕНЧМАРКИ (скорость) • По тестам авторов • The load-hit case is slightly slower due to Swiss Tables improving the performance of the old sync.Map • Ускорение по всем тестам ~50% • Удаление существующих ключей гораздо дольше • Разброс результатов гораздо меньше
36. 36 БЕНЧМАРКИ (память)
37. 37 Быстрее работают Возвращают память Все чтения без блокировки Время запроса не зависит от размера мапы sync.Map что изменилось
38. 38 Достижения CS доехали и до Go Мапы работают теперь быстрее Есть что доработать (SIMD, память, баги) Всегда можно сделать свои мапы Выводы На переход на 1.24 не влияет никак