Swiss Tables в Go: поиск быстрее, а delete в больших map - до 2.4 раза медленнее
Перемерил ассоциативные массивы на Mac mini M4 Pro и сверил ключевые цифры с M4 Max: встроенный map Go до и после Swiss Tables, семь классических схем хеш-таблиц, деревья, конкурентные карты и Map/Object в Node, Bun, Safari и Brave. Одна методика на Go и JS, чужие бенчмарки - как есть рядом.
С чего началось
В Go 1.24 встроенный map переписали на Swiss Tables. Команда Go в посте о переходе осторожна. На микробенчмарках операции с map стали до 60% быстрее, чем в Go 1.23. Выигрыш сильно зависит от операции, и “some edge cases do regress compared to Go 1.23”. На полных приложениях время CPU в среднем улучшилось примерно на 1.5%.
В пересказах осталась только первая цифра: “up to 60% faster”, на Хабре - “чтение и запись в map с более чем 1024 элементами стали быстрее примерно на 30%”. Истории из продакшена сдержаннее. Datadog на больших map сэкономил около 70% памяти. DoltHub сравнил новую map со своей dolthub/swiss (820 звёзд). На их нагрузке встроенная оказалась “even a bit faster”, и библиотеку они заархивировали.
Какие именно случаи регрессируют, в посте команды Go не сказано. Это я и хотел выяснить.
Я собирал материал про ассоциативные массивы вообще: какие схемы бывают, что лежит в Go, что в JS-движках, чем пользоваться под конкурентной нагрузкой. И быстро упёрся в то, что цифры в источниках несравнимы между собой. Разные машины, разные ключи, у кого-то минимум из повторов, у кого-то среднее, у кого-то в замер попал генератор случайных чисел.
Поэтому всё перемерил сам, на одной машине и одной методикой.
Стенд
Главное правило - ничего не переписывать, если реализация уже есть. Мой код - только обвязка и одна общая методика. Библиотеки взяты как есть из их репозиториев. У двух других источников есть оговорки:
- Схемы хеш-таблиц - из go-hashtable-shootout. Репозиторий малоизвестный: 0 звёзд, создан в июне 2026. Я взял его, потому что других мест, где все семь схем на Go написаны под одним интерфейсом и проверены фаззингом против встроенной map, не нашёл. Популярные сравнения схем есть только для C++: martinus/map_benchmark (323 звезды) и hash-table-shootout (104). Поэтому выводы shootout я не цитирую, а перемеряю.
- Конкурентная нагрузка - байт в байт из go-concurrent-map-bench (66 звёзд). Его написал автор xsync. Учитывайте это, когда xsync окажется первым.
Методика одна на Go и JS: N различных целых ключей в случайном порядке (mulberry32, seed 42), строковые ключи key-%010d от тех же чисел, ещё N отсутствующих ключей для промахов. Тест проверяет, что Go и JS получают побитно одинаковые ключи и одинаковый поток операций.
| метрика | что это |
|---|---|
| insert | заполнить пустую таблицу, без подсказки размера |
| insert_hint | то же с подсказкой размера (только Go) |
| lookup_hit / lookup_miss | поиск присутствующих / отсутствующих ключей |
| iterate | полный проход |
| delete | удалить все ключи из заполненной таблицы |
| mixed | 50% get, 30% put, 20% delete, четверть - по отсутствующим ключам |
| mem | байт на элемент по приросту живой кучи после GC |
Каждая реализация - в своём процессе, в браузере - в своём Worker: иначе JIT видит полиморфные вызовы и мерит сам себя. Перед каждым замером GC, не меньше миллиона операций, семь повторов, в таблицах медиана.
| компонент | что стоит |
|---|---|
| машина | Mac mini, Apple M4 Pro, 12 ядер (8 performance + 4 efficiency), 24 GB |
| ОС | macOS 27.0.1, питание от сети, Energy Mode - High Power |
| Go | 1.23.12 (бакеты), 1.25.8 (Swiss и GOEXPERIMENT=noswissmap), 1.27.1 |
| JS | Node 24.19.0 (V8 13.6), Bun 1.4.3, Safari 27.0.1, Brave 155.1.97.57 |
| сверка | MacBook Pro, Apple M4 Max, 16 ядер (12 + 4), 48 GB, macOS 26.5.2, High Power |
Все таблицы ниже - с Mac mini, прогон целиком. На M4 Max я выборочно перемерил то, что вызывало сомнения: встроенный map, хеш-таблицы при 1 и 10 млн, Node и Bun при 1 млн, конкурентные карты на 1 и 16 ядрах. Где эти цифры есть, они стоят рядом для сверки. Почему вообще понадобилась вторая машина - в конце, в граблях методики.
Весь стенд лежит на github.com/haiodo/map-bench, чужие бенчмарки подключены сабмодулями. Одна команда - и вы повторяете всё на своей машине.
Встроенный map: контрольная группа
Сравнивать Go 1.23 с Go 1.27 в лоб - значит сравнивать map вместе с компилятором и рантаймом за три релиза. Поэтому в середине стоит контроль: Go 1.25 с GOEXPERIMENT=noswissmap. Тот же компилятор, что и у Go 1.25, но старая map на бакетах.
Контроль совпал с Go 1.23: 89% метрик в пределах 5%, крайние расхождения от -14% до +16%, без общего знака. Swiss-столбцы расходятся на десятки процентов и в разы. Значит, всё, что меняется дальше, - это сама map.
Флаг, кстати, живёт недолго: в 1.27 его уже нет.
Малые map: всё как обещали
N = 1000, int-ключи:
| метрика | Go 1.23 | Go 1.27 | изменение | M4 Max |
|---|---|---|---|---|
| mixed | 19.2 | 10.9 | -43% | -48% |
| insert_hint | 16.2 | 6.97 | -57% | -58% |
| lookup_miss | 5.11 | 4.40 | -14% | -14% |
| delete | 17.7 | 16.6 | -7% | -13% |
| mem, B/элемент | 41.1 | 37.0 | -10% | -10% |
Время в нс на операцию, в последнем столбце - изменение на M4 Max.
Со строковыми ключами ещё ярче: промах 16.1 → 5.40 нс, втрое быстрее (на M4 Max 17.9 → 5.6). Swiss Table проверяет группу из 8 слотов разом по байтам метаданных (7 бит хеша на слот) и не лезет в сами ключи, пока они не совпали. На промахе до сравнения строк дело почти не доходит.
На малых map Swiss Tables - честное ускорение. До сих пор статьи правы.
Большие map: поиск быстрее, delete медленнее
N = 1 млн и 10 млн, int-ключи:
| метрика | N | Go 1.23 | Go 1.27 | изменение | M4 Max |
|---|---|---|---|---|---|
| lookup_hit | 1 млн | 25.2 | 18.7 | -26% | -32% |
| lookup_miss | 1 млн | 22.5 | 14.8 | -34% | -23% |
| delete | 1 млн | 31.0 | 50.4 | +62% | +77% |
| lookup_hit | 10 млн | 34.3 | 29.2 | -15% | -21% |
| lookup_miss | 10 млн | 35.1 | 25.8 | -26% | -26% |
| delete | 10 млн | 45.0 | 107.8 | +140% | +127% |
| insert_hint | 10 млн | 48.8 | 79.1 | +62% | +55% |
| mem, B/элемент | 10 млн | 32.2 | 30.3 | -6% | -6% |
Поиск быстрее и здесь: попадания на 15-26%, промахи на 26-34%, со строковыми ключами промахи - на 43-50%. Но удаление на больших map медленнее в 1.6-2.4 раза, со строковыми ключами - в 1.6-1.8. Вставка с подсказкой размера медленнее на 8-62%. На M4 Max знак везде тот же, величина расходится не больше чем на 15 процентных пунктов.
Что большие map в Swiss Tables страдают от кэша, знает и команда Go. Michael Pratt из команды рантайма завёл issue #70835 “runtime: map cold cache improvements”. Если map не в кэше, обращение идёт через map, каталог, таблицу, control word и слот, и на каждом шаге можно промахнуться. В том же issue bboreham пишет, что Prometheus на Go 1.24 стал тратить больше CPU там, где обращается к большой map. В #71368 - другая сторона той же раскладки: map[int64]struct{} из-за выравнивания занимает 16 байт на слот. valyala связал с этим падение скорости на map с миллионами элементов при переходе с 1.23 на 1.24.
Исправление - хранить в группе сначала все ключи, потом все значения (GOEXPERIMENT=mapsplitgroup). В августе 2026 его включили по умолчанию, в issue стоит веха Go 1.28. Я мерил 1.27, так что следующий релиз стоит перемерить. Про замедление delete отдельного issue я не нашёл: эта цифра пока держится только на моих замерах.
Цифра против всех статей, поэтому я ей не поверил и перемерил без своего харнесса. Голый map[uint64]uint64, go test -bench, удаление всех ключей в случайном порядке:
| N | Go 1.23 | Go 1.27 |
|---|---|---|
| 1000 | 20.6 нс | 13.7 нс |
| 1 млн | 28.5 нс | 42.3 нс |
Подтвердилось. На малой map удаление ускорилось, на большой - замедлилось на 48%. В харнессе разница больше (+62%) - почему, я не разбирал, - но знак тот же.
Почему другие бенчмарки показывают ускорение delete
Если искать на GitHub бенчмарки Swiss Tables в Go 1.24, попадается TFMV/go-map. Звёзд у него ноль, а вывод бодрый:
| операция | Go 1.23 | Go 1.24 | вывод бенчмарка |
|---|---|---|---|
| Insert | 70.60 ms | 47.41 ms | 32.8% faster |
| Lookup | 54.34 ns | 38.54 ns | 29.1% faster |
| Delete | 25.08 ns | 15.21 ns | 39.4% faster |
Я запустил его как есть. На моей машине он тоже показывает ускорение: delete 14.8 → 8.9 нс. Смотрим код:
func BenchmarkMapDelete(b *testing.B) {
testMap := generateTestData(numElements) // 1 000 000 элементов
b.ResetTimer()
for i := 0; i < b.N; i++ {
delete(testMap, rand.Intn(numElements))
}
}Map на миллион элементов, удаление случайного ключа b.N раз. А b.N у меня вышел 72 миллиона на Go 1.23 и 121 миллион на Go 1.27. Map пустеет примерно после 14 миллионов удалений.
То есть больше 80% замера - это delete из пустой map. Причём на Go 1.27 доля пустых удалений ещё больше, потому что b.N почти вдвое больше. Бенчмарк меряет не удаление, а то, как быстро рантайм понимает, что удалять нечего.
Остальные два замера тоже с особенностями. Insert - последовательные ключи 0...N-1 без подсказки размера. Lookup - только попадания, и в замер входит rand.Intn из общего источника.
Ничего злонамеренного тут нет: это обычный бенчмарк, написанный за вечер. У него ноль звёзд, и в других источниках я его цифр не встретил. Но разбор показательный: прежде чем цитировать чужой бенчмарк, стоит открыть его код и посмотреть, кто его написал.
Свои таблицы
Swiss Table - не единственная схема. go-hashtable-shootout реализует семь: цепочки, линейное и квадратичное пробирование, Robin Hood, hopscotch, cuckoo и свою Swiss. Плюс библиотеки и упорядоченные структуры. N = 1 млн, int-ключи, Go 1.27:
| реализация | insert | lookup_hit | lookup_miss | delete | mixed | mem, B |
|---|---|---|---|---|---|---|
| go/map | 43.8 | 18.1 | 15.0 | 52.0 | 52.8 | 37.8 |
| dolthub/swiss | 39.7 | 21.0 | 7.10 | 23.1 | 38.6 | 35.7 |
| cockroachdb/swiss | 51.8 | 19.6 | 16.3 | 40.5 | 51.2 | 37.8 |
| tidwall/hashmap (Robin Hood) | 59.7 | 25.7 | 34.5 | 36.5 | 54.1 | 50.3 |
| shootout/linear | 40.2 | 14.0 | 13.2 | 8.69 | 33.6 | 35.7 |
| shootout/swiss | 21.5 | 12.7 | 3.61 | 13.4 | 26.6 | 35.7 |
| shootout/cuckoo | 71.2 | 16.4 | 21.2 | 15.7 | 35.9 | 100.7 |
| tidwall/btree | 145.3 | 144.8 | 142.5 | 146.1 | 189.5 | 24.7 |
| plar/art | 142.7 | 74.2 | 77.5 | 111.2 | 311.9 | 116.2 |
| huandu/skiplist | 820.9 | 892.6 | 1209.0 | 772.2 | 1260.9 | 128.3 |
Схемы из shootout обгоняют встроенную map почти везде, особенно на удалении: 9-22 нс против 52.0. Но сравнение неравное. Они знают только uint64 и хешируют дешёвым fmix64. Встроенная map - generic и хеширует AES-хешем со случайным сидом, чтобы никто снаружи не подобрал вам ключи с коллизиями. Это потолок самописной таблицы под один тип, а не повод заменить map.
Из generic-библиотек встроенную map заметно обгоняет dolthub/swiss: промах вдвое быстрее (7.10 против 15.0), удаление в 2.3 раза (23.1 против 52.0), а на 10 миллионах без подсказки размера и вставка быстрее (53.4 против 88.9). Попадания у неё медленнее: 21.0 против 18.1, на 10 миллионах - 43.4 против 28.7. cockroachdb/swiss выигрывает только удаление (40.5 против 52.0). На M4 Max соотношения те же.
С историей DoltHub это сходится. Сами они использовали dolthub/swiss для больших map, в которые почти только добавляют, и на этой нагрузке встроенная map оказалась не хуже. У меня выигрыш dolthub/swiss приходится на удаление и промахи, а попадания у неё медленнее.
Остальное - для полноты картины. Cuckoo платит за быстрый поиск сотней байт на элемент. B-дерево - самое компактное (24.7 байта), но в восемь раз медленнее на поиске. Skip list медленнее B-дерева во всём и съедает в пять раз больше памяти. Если нужна упорядоченность - берите B-дерево.
Конкурентные карты
Нагрузка из go-concurrent-map-bench без изменений. Я добавил то, что пишут руками: map под Mutex и под RWMutex, 256 шардов на stdlib и concurrent-swiss-map. Млн операций в секунду на всю программу, N = 1 млн, int-ключи:
| реализация | 100% чтений, 1 ядро | 12 ядер | 75% чтений, 1 ядро | 12 ядер |
|---|---|---|---|---|
| xsync.MapOf | 18.0 | 150.2 | 15.2 | 127.1 |
| haxmap | 10.4 | 95.2 | 6.5 | 47.5 |
| 256 шардов на stdlib | 17.1 | 89.0 | 13.9 | 42.4 |
| sync.Map | 5.7 | 50.9 | 5.1 | 51.0 |
| orcaman/concurrent-map | 18.6 | 43.7 | 15.5 | 20.5 |
| concurrent-swiss-map | 14.2 | 32.8 | 12.6 | 18.2 |
| map + RWMutex | 20.6 | 7.6 | 16.8 | 9.0 |
| map + Mutex | 20.8 | 4.7 | 17.1 | 4.2 |
На одном ядре map под мьютексом - лучший выбор. На двенадцати - в 30 раз хуже лидера. Уже на четырёх ядрах map + Mutex даёт 6.7 млн операций в секунду против 20.8 на одном.
RWMutex не спасает даже при 100% чтений. Каждый читатель пишет в общий счётчик, и эта кэш-линия гуляет между ядрами.
На многих ядрах xsync - лидер во всех режимах. Напомню оговорку: нагрузку и xsync писал один автор. Независимых популярных бенчмарков конкурентных map на Go я не нашёл, у найденных по одной звезде. Цифры в README haxmap тоже авторские. sync.Map медленнее всех на одном ядре, зато масштабируется и при 25% записей обходит самодельные шарды (51.0 против 42.4). А 256 шардов на map + RWMutex - простая обёртка над stdlib - дают 59% от xsync на чистом чтении. Если тащить зависимость не хочется, это разумный компромисс.
На M4 Max с 16 ядрами картина та же, а разрыв больше. При 100% чтений xsync даёт 322.7 млн операций в секунду, map + Mutex - 4.6, то есть в 70 раз меньше. Шарды дают 44% от xsync, и при 25% записей sync.Map их тоже обходит (88.5 против 53.7).
И поправка на железо: 12 ядер у M4 Pro - это 8 производительных и 4 энергоэффективных. Поэтому от 8 к 12 ядрам рост у всех меньше линейного: у xsync - со 132.4 до 150.2.
Go против JS
Тот же поток операций в JS: Map и Object в Node, Bun, Safari и Brave. N = 1 млн, строковые ключи:
| операция | Node 24 | Bun 1.4 | Safari 27 | Brave 155 | Go 1.27 |
|---|---|---|---|---|---|
| Map insert | 102.9 | 64.1 | 57.4 | 46.8 | 84.5 |
| Map lookup_hit | 79.3 | 30.9 | 40.1 | 22.9 | 29.5 |
| Map lookup_miss | 174.3 | 42.4 | 59.3 | 23.0 | 22.3 |
| Map mixed | 234.8 | 100.6 | 96.0 | 150.5 | 104.9 |
| Map mem, B/элемент | 29.4 | 54.5 | - | - | 55.8 |
Go не выигрывает у JS-движков по поиску. Brave находит строковые ключи быстрее go/map (22.9 против 29.5 нс), Bun идёт вровень. На int-ключах быстрее Go уже Bun и Safari: 12.0 и 15.8 против 18.1 нс. Со строковыми ключами Go лучше всех только на промахах, и то вровень с Brave. А по памяти Map в Node компактнее встроенной map Go.
Самое странное здесь - Node и Brave. Движок один и тот же, V8, а поиск по строкам в Node в 3.5-7.6 раза медленнее. Это не шум: три отдельных процесса Node на M4 Max дали 70-73 нс на попадание, на mini - 79. Различаются версия V8 (в Node 13.6, в Brave новее), сборка (Node без pointer compression) и среда (процесс против Worker). Что из этого даёт разницу, я пока не знаю.
Object - не Map
Две вещи, которые стоит знать до того, как использовать Object как словарь.
Проход по Object с целыми ключами стоит 215-300 нс на элемент во всех четырёх движках. Это в 30-130 раз дороже прохода по Map. Похоже, дело в спецификации: for...in обязан выдавать целочисленные ключи по возрастанию, а разреженные индексы движки держат в словаре без порядка. Одинаковая цена в четырёх разных движках на это и намекает, но профилем я это не проверял.
Со строковыми ключами в V8 проход тоже дорогой: 130-150 нс против 9 в JavaScriptCore. Почему - не разбирал.
А вот это я нашёл случайно, когда прогон завис на полчаса.
8388606 0.00 ms
8388607 1023.74 ms
8388608 1028.52 ms
8388609 1059.21 msВ V8 после 2^23 - 1 = 8 388 607 строковых свойств каждая следующая вставка в Object занимает секунду. В стеке зависшего процесса - Runtime_AddDictionaryProperty и BaseNameDictionary::IterationIndices с сортировкой всех свойств. Судя по порогу, под порядковый номер свойства в словаре отведено 23 бита. Номера кончаются, и V8 перенумеровывает все свойства - на каждой вставке. Десять миллионов ключей так вставлялись бы около 19 дней.
В Bun десять миллионов строковых ключей вставляются в Object по 153 нс на ключ. В Map такого предела нет.
Грабли методики
Режим питания - часть стенда. Первый полный прогон шёл на M4 Max в Energy Mode “Automatic” и параллельно с другой работой. Повторы внутри процесса сходились, и по разбросу ничего не было видно. Но перепроверка в High Power дала другие цифры: delete на Go 1.27 при миллионе int-ключей - +77% к Go 1.23 вместо +118%, xsync на 16 ядрах - 322.7 млн операций в секунду вместо 188.8. Какой из двух факторов дал искажение, я не разделял. Поэтому всё перемерено на отдельной машине в High Power, а с M4 Max в статье только перепроверка, тоже в High Power.
Браузер разный от запуска к запуску. Safari на промахе Map при 10 тысячах int-ключей в двух запусках Worker дал 9.5-9.7 нс, в трёх других - 2.7-3.0. Внутри запуска повторы сходились. На M4 Max так же прыгал Brave: Map mixed 538 нс в одном запуске против 144-154 в пяти следующих. Поэтому в браузере каждая конфигурация запускается в пяти свежих Worker, и в таблице - медиана медиан. В Node такого разброса нет.
Headless и окно - одно и то же. Проверил на M4 Max Brave в окне против headless: в пределах 10%, кроме чтения Map с int-ключами (окно на 25-30% быстрее).
SMI. Int-ключи у меня - до 2^31. В Node это небольшие целые, которые V8 хранит прямо в указателе. А в Chromium включён pointer compression, и такие числа там только до 2^30. Значит, в Brave примерно половина моих int-ключей - объекты в куче. Поэтому int-ключи в Node и Brave сравниваются не в равных условиях, строковые - в равных. В следующем прогоне ключи будут до 2^30.
Set в V8 тоже конечный. Генератор ключей держал множество “уже было” в одном Set, и на 20 миллионах ключей упал с RangeError: Set maximum size exceeded. Предел - 2^24. Пришлось разбить на 16 множеств.
Минимум против медианы. go-hashtable-shootout берёт минимум из повторов, я - медиану. На машине с фоновой нагрузкой они расходились до трёх раз.
Что я забрал себе
Swiss Tables ускоряют поиск и малые map, но не удаление в больших. Если у вас большие map с частыми удалениями, обновление до 1.24+ может замедлить их в 1.6-2.4 раза. Перед обновлением мерьте свою нагрузку.
Режим питания и фон - часть методики. Повторы внутри процесса сходятся и в режиме Automatic, а цифры при этом уезжают на десятки процентов.
Чужой бенчмарк сначала читать, потом цитировать. “+39% на delete” оказались удалением из пустой map. И смотреть, кто его написал: у этого бенчмарка ноль звёзд, а у бенчмарка конкурентных map автор тот же, что у победителя.
Под конкурентной нагрузкой map + мьютекс перестаёт работать уже на четырёх ядрах. Готовая библиотека (xsync) или хотя бы шарды.
Object как словарь - только для малых и статичных наборов ключей. Проход по целым ключам на два порядка дороже Map, а в V8 у строковых ключей есть потолок в 8.4 миллиона.
В браузере одного запуска мало. Повторы внутри запуска сходятся, а между запусками цифра прыгает в разы.
Повторить
Стенд полностью в репозитории: github.com/haiodo/map-bench.
git clone --recursive https://github.com/haiodo/map-bench && cd map-bench
./run.sh && python3 parse.pyТаблицы этой статьи лежат в results-mini/tables.md, окружение - в results-mini/env.txt, находки и оговорки - в FINDINGS.md. В results/ - первый прогон на M4 Max в режиме Automatic и перепроверка в High Power (results/check/). Прогоните на своей машине - и пришлите цифры, особенно с x86 и Linux.