Замеры для статьи «Карта в Go: Swiss Table, порядок обхода и цена промаха»

Файл	Что делает
layout.go	восемь наблюдений без единого замера времени: карта как указатель, сколько бывает порядков обхода, nil-карта, почему нельзя взять адрес элемента, что делает delete с памятью, что даёт подсказка размера, порог 128 байт у ключа, какие типы годятся в ключи
cost_test.go	цена: поиск по типу ключа, промах против попадания, построение с подсказкой и без, обход, плотные ключи против среза
nankey.go	NaN как ключ: сколько записей после N вставок, что возвращает поиск, что делает delete и что — clear. Ни одного замера времени
ab.sh	старая реализация карты против новой на одной машине: GOEXPERIMENT=noswissmap
contract.go, contract.sh	что карта обещает: ноль вместо ошибки, форма с двумя результатами, nil-карта, и отдельно — что отвергает компилятор на несравнимом ключе
controlword.go	управляющее слово: четыре шага, которыми восемь сравнений становятся одним, на настоящих байтах и со сверкой с честным перебором
insert.go	путь вставки: как хеш делится на H1 и H2, где применяется каждая половина, пять сценариев вставки со сверкой с настоящей картой
groupindex.go	откуда берётся номер группы: таблица как массив групп, h1 & (N − 1) и какие именно биты хеша становятся индексом; что делает с номером рост таблицы; цена пересечения бит метки и номера
growth.go	расширение карты наблюдением за памятью, а не по описанию
concurrent.go, race.sh	что происходит при одновременном доступе без синхронизации
practice.go	ответы к задачам урока — прогоном, а не рассуждением

Каталог — отдельный модуль Go, поэтому замеры запускаются из него:

go run bench/gomap/layout.go        # работает и из корня
go run bench/gomap/nankey.go
go run bench/gomap/insert.go
go run bench/gomap/groupindex.go
go run bench/gomap/controlword.go
cd bench/gomap
go test -run '^$' -bench . -benchmem .
./ab.sh

layout.go помечен //go:build ignore — он package main, а рядом лежит тест пакета gomap, и без метки go test ./... спотыкался бы о два пакета в одном каталоге.

Что здесь важно прочитать правильно

Главное — не наносекунды. Оно в layout.go: порядок обхода не случаен, а провёрнут; delete не возвращает память; подсказка размера уменьшает не карту, а мусор. Это утверждения о поведении, и проверяются они сравнением, а не секундомером.

По времени сопоставляются только строки внутри одного блока cost_test.go. В каждом блоке все строки дают одинаковый результат, отличается лишь способ. Блоки друг с другом не сопоставляются.

ab.sh — единственное место, где сравниваются две сборки, и это законно ровно потому, что отличается один флаг. Компилятор, машина и сам замер те же. Строка cpu: печатается для каждого прогона намеренно: на виртуальной машине частота плавает, и если она в раундах разная, раунд надо выбросить, а не считать разницу.

Что получилось (go1.24.7 linux/amd64, Intel Xeon 2.10GHz)

Устройство

Из internal/abi и internal/runtime/maps:

константа	значение	что это
SwissMapGroupSlots	8	слотов в группе; на группу один 8-байтовый управляющий блок
maxAvgGroupLoad	7	предел заполнения перед ростом — 7 из 8, то есть 87,5 %
maxTableCapacity	1024	больше этого таблица не растёт целиком, а делится надвое
SwissMapMaxKeyBytes	128	ключ крупнее хранится не в слоте, а по указателю
SwissMapMaxElemBytes	128	то же для значения

unsafe.Sizeof(map[int]int{}) = 8 байт: в переменной лежит один указатель. Для сравнения: срез — 24 байта, строка — 16.

Вставка: где применяется H1, а где H2 (insert.go)

Хеш режется по седьмому биту, и половины не пересекаются:

	биты	где применяется
h1 = h >> 7	старшие 57	номер стартовой группы (h1 & mask) и семя треугольного пути
h2 = h & 0x7f	младшие 7	ложится в управляющий байт слота как метка

Ни один бит не участвует в обеих ролях: совпадение метки ничего не говорит о группе, а номер группы ничего не говорит о метке.

Комментарий в group.go здесь расходится с кодом. Строка про занятый слот

full: 0 h h h h h h h  // h represents the H1 hash bits

называет H1, а код рядом пишет в управляющий байт H2: PutSlot делает g.ctrls().set(i, ctrl(h2(hash))), поиск зовёт matchH2(h2(hash)), и map.go над самой функцией h2 поясняет — «These are used as an occupied control byte» (пер.: «Они используются как управляющий байт занятого слота»). В байте лежит H2; проверено на go1.24.7.

Пять сценариев вставки, все на настоящих хешах FNV-1a и с полной трассой:

сценарий	что показывает
в стартовой группе есть место	один шаг: свободный слот — конец пути
метка совпала, ключ чужой	ложное совпадение стоит одного полного сравнения, поиск продолжается в той же группе
ключ уже есть	значение переписывается на месте, нового слота не появляется, len не растёт
стартовая группа занята целиком	путь идёт дальше по треугольной последовательности
по дороге удалённый слот	путь не останавливается на нём: место запоминается, поиск идёт до свободного слота, и только тогда ключ кладётся в запомненный удалённый

Последняя строка — то, ради чего написана программа. Вставка не может занять первое подвернувшееся место: пока не встретился свободный слот, неизвестно, нет ли этого ключа дальше по пути. Поэтому вставка нового ключа стоит полного поиска промаха, а не «нашли дырку и положили».

Перенос алгоритма проверяется в самой программе: битовые формулы сверяются с честным перебором на 200 000 случайных групп (расхождений 0), треугольный путь — с утверждением исходника, что он обходит каждую группу ровно один раз (проверено для 4, 8, 16, 64 и 1024 групп), а наблюдаемая часть — с настоящей map[string]int по len на семи операциях (расхождений 0).

Хеш-функция взята FNV-1a, а не картина: внутренний хеш карты сеется случайно при её создании и снаружи не воспроизводится. Таблица сокращена до 4 групп по 8 слотов — сокращена только ширина, не правила.

Порядок обхода

Одна и та же карта, 2000 обходов, считаем число РАЗЛИЧНЫХ порядков:

n	различных порядков	обходов
3	3	2 000
6	6	2 000
8	8	2 000
9	9	2 000
16	16	2 000
896	896	20 000
897	1 174	20 000

До 896 записей — ровно n, а не n!. Все порядки при этом сдвиги одной и той же последовательности: [0 1 2], [1 2 0], [2 0 1].

Граница считается из констант: maxTableCapacity = 1024, коэффициент заполнения 7/8, то есть 896 записей — последняя длина, при которой карта помещается в ОДНУ таблицу. На 897 у итератора появляется второе независимое смещение, по директории таблиц (it.dirOffset), и правило кончается. Замеренная граница совпала с расчётной точно.

Сама последовательность у каждого запуска программы своя: карта засевает хеш при старте. Постоянно другое — что внутри одного запуска порядки отличаются только сдвигом.

Память

Миллион записей map[int]int, живая куча:

момент	куча	len
до начала	0,1 МБ	—
миллион записей	36,0 МБ	1 000 000
после delete всех ключей	36,0 МБ	0
после clear(m)	36,0 МБ	0
после m = make(map[int]int)	0,1 МБ	0

Подсказка размера, миллион записей:

	выделено всего	выделений	осталось жить
без подсказки	75 407 864 б	8 188	37 776 744 б
make(map, n)	37 832 960 б	4 101	37 832 752 б
отношение	×1,99	×2,00	×1,00

Готовая карта одинакова. Экономятся не байты в ней, а промежуточные таблицы.

Порог размера ключа, 10 000 записей:

ключ	выделено	выделений	на запись
[120]byte	2 228 912 б	34	222,9 б
[128]byte	2 359 984 б	34	236,0 б
[136]byte	1 735 600 б	10 034	173,6 б

За порогом выделений становится по одному на каждый ключ, а байт — меньше: слоты в группе резервируются все восемь сразу, а вынесенный ключ выделяется ровно по размеру.

Цена, N = 100 000

Блок 1 — найти ключ, который есть:

тип ключа	ns/op
int64	18,06
[2]int64	24,95
string	28,19

Блок 2 — промах против попадания и форма запроса. Все четыре строки в одном блоке намеренно: брать «попадание» из блока 1 и «попадание с запятой» отсюда было бы сравнением через границу блока.

что	ns/op
попадание, v := m[k]	17,83
попадание, v, ok := m[k]	18,43
промах, v := m[k]	28,62
промах, v, ok := m[k]	28,44

Форма с запятой не стоит ничего — на промахе разница даже в другую сторону. А промах дороже попадания в 1,6 раза, и это следствие устройства: поиск останавливается, только найдя группу со свободным слотом.

Блок 3 — построить карту из 100 000 записей:

	ns/op	B/op	allocs/op
make(map[int64]int)	5 423 978	4 729 886	532
make(map[int64]int, N)	2 760 050	2 364 769	258

Блок 4 — обойти 100 000 значений и просуммировать:

	ns/op
карта	855 702
срез (та же задача, плотные ключи)	37 434

Блок 5 — прочитать одно значение по плотному целому ключу:

	ns/op
карта	15,55
срез	1,12

От прогона к прогону (три прогона по 2 с): блок 1 — 17,81–18,37 / 24,79–24,99 / 27,46–28,25; блок 2 — 17,75–18,11 и 18,40–18,84 у попаданий, 28,57–28,76 и 28,28–28,89 у промахов; блок 3 — 5 420 612–5 506 708 и 2 740 518–2 816 191; блок 4 — 855 535–856 652 и 36 697–37 482. Столбцы B/op и allocs/op не менялись.

Старая реализация против новой

ab.sh, четыре чередующихся раунда, одна машина, строка cpu: во всех раундах совпала:

операция	Swiss Table (по умолчанию)	старая (noswissmap)
попадание, int64, форма v, ok :=	17,95–18,88	35,22–36,58	новая быстрее вдвое
попадание, string	25,59–28,14	51,89–54,70	новая быстрее вдвое
промах, int64	28,96–29,66	20,57–21,71	новая медленнее в 1,4 раза
обход 100 000 записей	847 706–893 851	1 046 614–1 079 682	новая быстрее на ~25 %

Замер один и тот же, компилятор один и тот же, отличается флаг сборки.

Наблюдения layout.go

• Карта — указатель, поэтому вставка внутри функции видна снаружи; у среза добавление в той же ситуации не видно.
• Порядок обхода — сдвиг, а не перестановка: различных порядков ровно n — до 896 записей, то есть пока карта помещается в одну таблицу.
• nil-карта: чтение, len, range и delete работают; паникует только запись.
• Адрес элемента взять нельзя — при росте таблица перестраивается целиком и записи переезжают.
• delete и clear не возвращают память — только замена карты.
• Подсказка размера вдвое уменьшает выделенное по дороге и не меняет размер готовой карты.
• Порог 128 байт переносит ключ из слота в отдельное выделение.
• Ключом может быть любой сравнимый тип; у map[any]T сравнимость проверяется в рантайме, и несравнимое значение даёт панику hash of unhashable type.

Что не подтвердилось

Расхожее «карта в Go — это бакеты по 8 элементов с цепочкой переполнения» описывает реализацию до Go 1.24. Она никуда не делась, но включается флагом: GOEXPERIMENT=noswissmap. По умолчанию с 1.24 работает Swiss Table.

И вторая половина расхожего — «новая реализация быстрее». Быстрее не всё: на промахе она медленнее старой в 1,4 раза, и это воспроизводится в каждом раунде. Механизм разный: в старой карте промах смотрит один бакет и кончается там же, если цепочки переполнения нет, а в Swiss Table он обязан идти до группы со свободным слотом. То, что делает попадание быстрым, делает промах длинным. Оговорка в блоге команды Go стоит: «some edge cases do regress compared to Go 1.23». Здесь этот случай назван поимённо и измерен. Оговорка к самому измерению тоже нужна: это одна форма карты (map[int64]int, 100 000 записей, ключи подряд), а цена промаха зависит от заполнения таблицы и от того, как разложены ключи.

NaN как ключ (nankey.go)

Запись, которую нельзя ни найти, ни перезаписать, ни удалить, и которая накапливается при каждой вставке.

Первоисточник №1 — спецификация Go, раздел Comparison operators:

Floating-point types are comparable and ordered. Two floating-point values are compared as defined by the IEEE 754 standard.

(пер.: «Типы с плавающей точкой сравнимы и упорядочены. Два значения с плавающей точкой сравниваются так, как определено стандартом IEEE 754».)

IEEE 754 определяет NaN как значение, не равное ничему, включая само себя. Отсюда всё остальное: карта ищет ключ по равенству, а ключ не равен сам себе.

Первоисточник №2 — спецификация Go, раздел Map types:

The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice.

(пер.: «Операторы сравнения == и != должны быть полностью определены для операндов типа ключа; поэтому тип ключа не должен быть функцией, картой или срезом».)

float64 этому требованию удовлетворяет — операторы определены. Определены, но не рефлексивны, и на это карта не рассчитана. Требование спецификации запрещает срезы и карты, но NaN не запрещает.

Первоисточник №3 — комментарий в рантайме, $(go env GOROOT)/src/runtime/alg.go:93:

// NOTE: Because NaN != NaN, a map can contain any // number of (mostly useless) entries keyed with NaNs. // To avoid long hash chains, we assign a random number // as the hash value for a NaN.

(пер.: «ЗАМЕЧАНИЕ: поскольку NaN != NaN, карта может содержать любое число (по большей части бесполезных) записей с ключами-NaN. Чтобы избежать длинных цепочек хеша, мы назначаем NaN случайное число в качестве значения хеша».)

Это ключевая цитата: накопление дубликатов — не побочный эффект и не дефект, а известное и задокументированное поведение. Рантайм лишь смягчает последствия, раздавая NaN случайный хеш, чтобы они не собирались в одну цепочку. Видно это прямо в f64hash там же: case f != f: return c1 * (c0 ^ h ^ uintptr(rand())).

Первоисточник №4 — $(go env GOROOT)/src/internal/runtime/maps/table.go:634, про то, что с такой записью можно сделать:

// One exception is keys that don't // compare equal to themselves (e.g., // NaN). These keys cannot be looked // up, so getWithKey will fail even if // the key exists. // // However, we are in luck because such // keys cannot be updated and they // cannot be deleted except with clear.

(пер.: «Исключение — ключи, которые не сравниваются равными сами себе (например, NaN). Такие ключи невозможно найти, поэтому getWithKey потерпит неудачу, даже если ключ существует. Однако нам везёт, потому что такие ключи нельзя обновить и нельзя удалить иначе как через clear».)

Здесь названы сразу три следствия и один выход: не найти, не обновить, не удалить — кроме как clear. Всё четыре проверены прогоном.

Прогон целиком:

=== 0. Исходное свойство ===
  math.NaN() == math.NaN() : false
  nan == nan (одна переменная): false
  math.IsNaN(nan): true

=== 1. N вставок одного и того же NaN ===
  после m[nan] = 1 → len(m) = 1
  после m[nan] = 2 → len(m) = 2
  после m[nan] = 3 → len(m) = 3
  после m[nan] = 4 → len(m) = 4
  после m[nan] = 5 → len(m) = 5

  итог: 5 вставок дали 5 записей
  обычный ключ на его месте дал бы одну: присваивание по
  существующему ключу перезаписывает, но «существующий» —
  это найденный по ==, а найти NaN нельзя.

=== 2. Что возвращает поиск ===
  m[nan]        → значение 0, найдено false
  m[math.NaN()] → значение 0, найдено false
  не помогает даже та же самая переменная: сравнение всё равно
  идёт по ==, а оно ложно.

=== 3. Что делает delete ===
  len до delete: 5
  len после двух delete: 5
  delete не паникует и не сообщает об ошибке — он просто не
  находит, что удалять.

=== 4. Записи на месте, и их видно перебором ===
  запись 1: ключ IsNaN=true, k==k → false, значение 1
  запись 2: ключ IsNaN=true, k==k → false, значение 2
  запись 3: ключ IsNaN=true, k==k → false, значение 3
  запись 4: ключ IsNaN=true, k==k → false, значение 4
  запись 5: ключ IsNaN=true, k==k → false, значение 5
  перебор нашёл 5 записей
  то есть память они занимают, значения хранят, а достучаться
  до них по ключу нельзя. Под нагрузкой, где NaN приходит из
  данных (0.0/0.0, math.Sqrt(-1), разбор "NaN"), карта растёт
  без предела, и ни одна запись из неё не переиспользуется.

=== 5. Единственный штатный способ убрать: clear ===
  len до clear: 5
  len после clear(m): 0
  ровно то, что написано в рантайме: "cannot be deleted
  except with clear".

=== 6. Контроль: карта следует == буквально, и там, где == ===
    ведёт себя нормально, странностей нет ===
  0.0 == -0.0: true
  после m[+0]=1 и m[-0]=2 → len = 1, m[0] = 2
  +0 и -0 равны по IEEE 754, поэтому это ОДНА запись, и вторая
  вставка перезаписала первую. Карта не «сломана» на float —
  она честно следует ==. Ломается ровно то место, где == 
  перестаёт быть рефлексивным, и это только NaN.

=== 7. Как с этим жить ===
  отсекать NaN на входе:
    NaN отвергнут проверкой math.IsNaN
    NaN отвергнут проверкой math.IsNaN
  len(safe) = 2 — ровно столько, сколько годных ключей

Что показал прогон:

действие	результат
5 вставок одного и того же nan	len(m) = 5
m[nan]	0, false
m[math.NaN()]	0, false
delete(m, nan) дважды	len не изменился: 5 → 5
перебор range	находит все 5 записей, значения 1…5 целы
clear(m)	len = 0

Четыре вещи, которые стоит различать:

1. Не помогает та же самая переменная. m[nan] с тем же nan, которым клали, всё равно даёт false: сравнение идёт по ==, а оно ложно независимо от того, откуда взялось значение.
2. delete молчит. Он не паникует и ничего не возвращает — просто не находит, что удалять. Ошибка не проявляется никак.
3. Записи живые. Перебором они видны, значения целы, память занята. То есть это утечка с полностью рабочим на вид кодом: под нагрузкой, где NaN приходит из данных (0.0/0.0, math.Sqrt(-1), разбор строки "NaN"), карта растёт без предела и ни одна запись не переиспользуется.
4. clear работает — ровно как обещает комментарий рантайма.

Контроль, который стоит прочитать. Блок 6 прогона показывает +0 и -0: по IEEE 754 они равны, и карта делает из них ОДНУ запись, вторая вставка перезаписывает первую (len = 1, m[0] = 2). То есть карта не «сломана» на float — она честно следует ==. Ломается ровно то место, где == перестаёт быть рефлексивным, и это только NaN.

Лечение — отсекать NaN на входе через math.IsNaN, блок 7.

Источники

• Go 1.24 Release Notes, раздел Runtime — https://go.dev/doc/go1.24
• Faster Go maps with Swiss Tables (блог команды Go) — https://go.dev/blog/swisstable
• internal/runtime/maps/map.go, вводный комментарий пакета — https://go.dev/src/internal/runtime/maps/map.go
• internal/runtime/maps/group.go и table.go — константы maxAvgGroupLoad и maxTableCapacity
• internal/abi/map_swiss.go — SwissMapGroupSlots, SwissMapMaxKeyBytes
• Спецификация Go, разделы Map types и Comparison operators — https://go.dev/ref/spec
• runtime/alg.go — комментарий про ключи-NaN и f64hash — https://go.dev/src/runtime/alg.go
• internal/runtime/maps/table.go — «cannot be deleted except with clear» — https://go.dev/src/internal/runtime/maps/table.go
• Abseil, Swiss Tables design notes — https://abseil.io/about/design/swisstables