Привет, Хабр! Меня зовут Владимир Марунин, я ведущий разработчик в команде Clatch. Сегодня расскажу о новых мапах в Go 1.24: разберем изменения, посмотрим, что было и что стало. О мапах часто спрашивают на собеседованиях, а еще без них нельзя просто так взять и написать программу на Go — так что, надеюсь, тема будет полезной и интересной.
Этот текст — расширенная версия моего доклада с митапа МТС True Tech Go. Если больше нравится слушать, а не читать, можно сразу переходить по ссылке. Поехали!
Что происходит
В феврале 2025 года вышла новая версия языка Go 1.24. В ней много изменений, в том числе поменялась имплементация одного из встроенных типов — map.
На Хабре это не первая публикация на тему. Вот тут — перевод вводной статьи. Еще мне понравилась публикация Go 1.24: принципы работы и преимущества обновленной map — вышло полезно, но есть неточности: в исходном коде я видел другие константы. Еще пара полезных ссылок:
Go на GitHub — тикет на включение новых мап;
Faster Go maps with Swiss Tables — анонс новых мап в блоге Go.
Ну и немного справки. Если хотите оставить старую имплементацию, выставите при сборке переменную окружения GOEXPERIMENT=noswissmap.
С вводными закончили — поехали дальше!
Немного теории
Мапы обычно реализуют двумя методами:
Через деревья — бинарные или B-Tree, Trie. В этом случае время операций поиска, вставки и удаления будет O(log N), где N — количество элементов.
Через хеш-таблицы. И это наш случай! Время операций поиска, вставки и удаления будет O(1). Если быть совсем точным, то O(len(key)). В процессе ключи сравниваются: если ключи (строки) длинные, это может занять время.
Обычно хеш-таблица — это просто массив/слайс длины 2N. Чтобы найти данные по ключу, вычисляется хеш-функция от ключа, берется N первых или последних бит — это и есть индекс в массиве.
Хеш-функция
Для хеш-таблицы нам нужна хеш-функция, которая преобразует ключ любого типа в целочисленное значение. А вот что требуется от универсальной хеш-функции:
она должна возвращать одно и то же значение для одного и того же ключа;
быстро вычисляться;
значения хеш-функции должны быть равновероятными;
для близких по значению ключей должны возвращаться разные значения хеш-функции.
То есть значения хеш-функции можно рассматривать как некое псевдослучайное число, а для описания вероятности коллизии применить математический аппарат. На всякий поясню, что коллизия — это когда у двух разных ключей одинаковое значение хеш-функции. В теории вероятностей это называется парадоксом дней рождения, в «Википедии» об этом есть неплохой текст.
Примерная формула вероятности коллизии:
где n — количество занятых элементов, а d — количество слотов.
Математика дает нам два факта:
в таблице обязательно будут коллизии;
вероятность коллизии 64-битного хеша слишком велика, чтобы пренебречь ею в реальных программах.
Теперь возникает вопрос: что делать с коллизиями?
Закрытая адресация или метод списков
В хеш-таблице хранятся не сами значения, а списки ключей и значений. Мы быстро вычисляем хеш, находим список и проходим его, сравнивая ключи из списка с требуемым.
Операции вставки и удаления — это просто вставка и удаление еще одного элемента в односвязанный список.
Открытая адресация
В хеш-таблице хранятся именно пары «ключ-значение». Если мы хотим сохранить значение в уже занятую ячейку, то по определенным правилам пробуем следующие, пока не найдем свободную.
Этот процесс называется probing. Есть несколько алгоритмов, например линейный, когда мы просто берем следующую ячейку, или квадратичный, когда прыжок каждый раз увеличивается на один.
При таком подходе мы не можем просто удалить элемент — иначе могут разорваться цепочки поиска. Так что удаленный элемент помечаем специальным маркером tombstone — он означает, что тут ничего нет и нужно искать дальше.
Рост мапы
Чем больше элементов в мапе, тем хуже она работает. При закрытой адресации у нас растут списки, и время поиска становится линейным. При открытой мы делаем все больше прыжков при пробинге, а если loadFactor достигнет 100%, то вставить новые элементы будет невозможно.
В какой-то момент мы должны увеличить размер хеш-таблицы. Обычно размер табличек 2N , так что нам нужно создать новую хеш-таблицу размера 2N+1 и перенести туда все данные. Для больших мап это долгая операция, и тут есть три стратегии:
мапа не растет, и тогда программист выделяет мапу достаточного размера заранее;
мапа растет за время операции вставки, и некоторые вставки очень долгие;
данные переносятся в новую мапу в фоне — это процесс эвакуации.
Еще полезные ссылки
В январе 2025 года, прямо перед релизом Go1.24, появилась публикация Optimal Bounds for Open Addressing Without Reordering. Авторы нашли теоретические ограничения сложности для поиска в зависимости от loadFactor и показали оптимальный алгоритм пробинга. На Хабре есть материал, где автор разбирает результаты этой работы. И еще один, в котором уже другой автор приходит к выводу, что значительного прироста производительности не будет.
Думаю, время их рассудит, и если подход стоящий, у нас будут новые мапы.
Обратно к практике
Сначала немного истории появления Swiss Tables:
2017 год — Matt Kulukundis представил доклад на CppCon про новую быструю реализацию map на C++;
2018 год — реализация была включена в C++-библиотеку abseil.io;
2019 год — с 1.36 включены в Rust;
2022 год — разработчик из ByteDance с логином zhangyunhao116 открыл тикет и предложил SwissTable в Go;
2024 год — к работе присоединяется petermattis, разработчик из CocroachDB;
февраль 2025 года — релиз Go1.24 в прод.
Теперь посмотрим, что представляли из себя мапы до Go1.24.
Мапы до Go1.24
Фактически у нас была двухуровневая структура — бакет и хеш-таблица списков этих бакетов. Раскрою подробнее:
Закрытая адресация, список бакетов. Бакет — это 8 пар «ключ/значение» с метаданными.
Мапа росла сама — каждый раз вдвое. И не возвращала память, выделенную под хеш-таблицу, даже если удалить почти все элементы. Мапа могла только расти.
У нас был процесс эвакуации, и это давало еще x1,5 потребления памяти.
Был случайный порядок итерации по мапе.
Нельзя было взять указатель на значение в мапе.
loadFactor = 6,5/8 или 81,25%.
Порядок итерации по мапе был намеренно сделан непредсказуемым. Обход таблицы шел по возрастанию значения хеш-функции, но она сама была непредсказуемой, и начало итерации всегда выбиралось случайно. Эти мапы с нами давно, и в сети есть много контента с разбором, как они работают.
Мапы в Go1.24
Давайте посмотрим, что интересного есть у нас сейчас:
Трехуровневая структура, каталог хеш-таблиц групп.
Хеш-таблица с закрытой адресацией — каталог.
Хеш-таблицы с открытой адресацией.
Мапа растет сама. Скачок потребления памяти не очень большой, но память мапа не возвращает.
Нет процесса эвакуации, рост за время одной операции вставки.
Для ускорения поиска используется SIMD.
Случайный порядок итерации по мапе.
Нельзя взять указатель на значение в мапе.
loadFactor = 7/8 или 87,5%.
Хеш-функция
Хеш-функция внутри называется memhash. Ей передается указатель на начало структуры и размер в байтах, на выходе получаем 64-битный хеш. Если тип данных содержит указатели, например строки, то на этапе компиляции строится функция, которая будет рекурсивно вызывать memhash для всех указателей.
У нас хеш-функция с seed. При создании мапы генерируется случайное число и хранится в мапе, оно же каждый раз передается на вход memhash. Seed случаен, поэтому подобрать данные так, чтобы сломать мапу, практически невозможно. При следующем запуске будет уже другой seed и другие значения хешей.
В Go используется два алгоритма для хеш-функции: AES, если есть аппаратная поддержка, и wyhash, если на платформе нет аппаратного AES. Хеш-функции можно использовать и в своем коде — они доступны в пакете hash.maphash.
Хеш для использования в мапах делятся на две группы:
h1 — это старшие 57 бит. Младшие биты h1 адресуют слот в хеш-таблице, а старшие h1 — слот в каталоге.
h2 — младшие 7. Используются в группе слотов.
Слот
Слот — это просто структура из двух полей, ключ и значение. Группа — это уже 8 слотов плюс метаинформация, то есть ctrl в коде. Каждый слот дает 1 байт метаинформации — так набирается 8 байт (как раз uint64) на группу.
Какие значения может принимать контрольный байт:
0x 80 — слот пустой;
0x254 — слот удален, tombstone (был занят, но потом удалили);
от 0x00 до 0x7F — слот занят, и в младших семи битах записаны 7 бит h2.
Если старший бит — единица, то слот свободен, ни разу не использовался или был занят и потом удален. Если ноль — слот занят. На практике ситуация, когда в группе есть empty и tombstone, встречаться не должна.
При помощи SIMD-инструкций мы можем быстрее обрабатывать ctrl. Если SIMD на платформе нет, магия битовых масок все равно ускоряет процесс.
Метаинформация позволяет быстро находить подходящие занятые слоты, то есть те слоты, у которых совпадают последние 7 бит хеша. Так мы отбрасываем 127/128 занятых слотов и только у 1/128 полностью сравниваем ключ.
Хеш-таблица
Хеш-таблица у нас с открытой адресацией, квадратичным пробированием.
Поиск. Стартовую ячейку мы выбираем по последним битам h1, а потом начинаем искать ключ в таблице. Ищем, пока не найдем нужный ключ или группу с пустым слотом — это значит, что такого ключа нет.
Удаление ключа. Запускаем обычный поиск ключа. Если находим ключ, удаляем его из группы. Если в группе есть пустые элементы, помечаем этот слот пустым. Если нет, помечаем слот как удаленный.
Мы не знаем, какие цепочки поиска проходят через эту группу. Поэтому если пометим слот как пустой, группа станет последней в поиске, а это может сломать нам другой поиск. Так что только tombstone.
Вставка. Запускаем обычный поиск ключа. Если ключ уже есть в мапе, просто изменяем значение. Если нет, записываем на первое свободное место. Тут есть одна небольшая оптимизация: при поиске мы запоминаем позицию (группу и слот) первого tombstone и, если она есть, записываем новое значение в него, а не в пустой слот.
Рост хеш-таблицы. Таблица растет, когда LoadFactor превышает ⅞. В LoadFactor входят не только занятые слоты, но и tombstone. Теоретически может быть ситуация, когда в таблице нет занятых полей, а она забита на 7/8 tombstone.
В любом случае при росте выделяется память x2 для новой таблицы. Старые данные переносятся на новое место, а все tombstone вычищаются. Все это происходит в момент вставки, и операция может быть довольно долгой. Чтобы одна операция не занимала слишком много времени, у нас есть ограничение на размер хеш-таблицы в 1 024 слота, или 128 групп. Если нам мало 1 024 слота, таблица сплитится на две, и обе добавляются в каталог.
Каталог (Directory)
Это самая верхняя структура в иерархии — по факту хеш-таблица с закрытой адресацией, но с некоторой оптимизацией.
Размер тоже 2^N, ячейку мы выбираем по первым битам h1, о которых уже писал выше.
// directory (globalDepth=2)
// +----+
// | 00 | --\
// +----+ +--> table (localDepth=1)
// | 01 | --/
// +----+
// | 10 | ------> table (localDepth=2)
// +----+
// | 11 | ------> table (localDepth=2)
// +----+На одну хеш-таблицу могут ссылаться несколько ячеек из каталога, поэтому при сплите хеш-таблицы мы записываем указатели на новые таблички в каталог.
В худшем случае за время одной вставки у нас будут выполнены такие операции:
сплит хеш-таблицы на 2 и перенос данных в них;
удвоение каталога и перенос указателей.
Каталог не сокращается, так что можно считать эту сложность как амортизированное O(1). То есть одна конкретная операция вставки может быть очень долгой, но это компенсируется тем, что остальные быстрые и в среднем время одной операции не зависит от размера мапы. В случае роста слайсов происходит то же самое.
Итераторы
Поведение итераторов в новых мапах не поменялось, а вот реализация разная. Именно из-за сложности имплементации итераторов хеш-таблицы могут только расти.
Принципы итераторов по мапе:
Случайный порядок итерации. Под капотом идет итерация по хеш-таблицам по слотам, но случайный seed делает этот порядок непредсказуемым. К тому же начало и конец итерации тоже выбираются случайно. То есть два последовательных for range по мапе дадут элементы в том же порядке, но с разным началом.
Удаленные ключи не возвращаются. Если в процессе итерации кто-то отредактирует мапу — удалит ключ, он не вернется из итератора. Для этого делается повторный запрос в мапу перед возвратом из итератора и проверяется, есть ли такой ключ.
Возвращаются измененные значения. Если в процессе итерации кто-то отредактирует мапу — изменит значение по ключу, то итератор вернет измененное значение. Для этого делается повторный запрос в мапу перед возвратом из итератора и высчитывается актуальное значение.
Добавленные значения могут попасть в итератор, а могут и не попасть. Тут никаких гарантий. Под капотом идет итерация по таблице, и если хеш нового ключа попадет в ту часть, которая не обработана итератором, то ключ/значение вернутся.
Бенчмарки
В блоге Go написано, что новые мапы быстрее:
В тикете приводится 357 бенчмарков. Что получается в агрегированном виде:
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%.
С одной стороны, 357 — это очень много. С другой — наоборот. Тут важно, какой профиль нагрузки и почему именно такое тестирование. У меня пока нет ответов на эти вопросы.
Я сделал свой бенчмарк по потреблению памяти. Он показывает, как работают мапы:
m := make(map[int]int)
for i := 0; i < 100_000_000; i++ {
m[i] = i
if i%100_000 == 0 {
reportMem(strconv.Itoa(i))
}
}Прокомментирую, что у нас получилось. В мапу складываются инты от 0 до 100 млн. Виден процесс эвакуации на старых мапах. Рост x3, потом по мере обращения к данным они переезжают в новую мапу, и один x возвращается. Еще виден небольшой рост потребления памяти прямо перед ступенькой, это коллизии в старой мапе. Какие-то ячейки пустые, а где-то образуются цепочки. Каждый элемент цепочки тоже потребляет память, и это видно на графике.
В новых мапах заметен скачок потребления памяти x2, но он довольно плавный даже на очень больших мапах.
Что в новых мапах хорошего и не очень
Начнем с преимуществ:
Лучше используется память. Выше LoadFactor, нет потребления на цепочки и на эвакуацию.
Быстрее работают. 1,5% — именно так и выглядит технический прогресс, рост на проценты при каждом релизе. С другой стороны, мне не очевидно, почему именно 1,5%.
Теперь недостатки:
Мапы не отдают память, хотя могли бы. Можно было бы объединять таблицы в каталоге (пустые) и делать rehash, а не только рост.
Есть баг, когда map[int]int{} потребляет столько же памяти, сколько и map[int]struct{}{}.
Не на всех платформах используются SIMD, даже если они есть.
Некоторые вставки в мапу могут быть очень долгими. Это критично, если нужно гарантированно быстрое время ответа. В некоторых задачах без этого никуда (тот же HFT), но обычно их не пишут на Go.
Тем не менее достижения Computer Science приезжают в Go, и это не может не радовать. Есть куча мест для доработок, и я надеюсь, в ближайших версиях мапы станут быстрее и лучше. Запасаемся попкорном терпением и наблюдаем!