Map в Golang после перехода на Swiss Tables

Gabor Koos об изменениях во внутреннем устройстве map, вошедших в релиз Golang 1.24: хеш-таблицу на базе бакетов с цепочками переполнения заменили архитектурой, основанной на Swiss Tables из Abseil. Внешний интерфейс языка остался прежним - map[K]V, make, обращение по индексу, delete, range работают как и раньше. Изменение заметно только в профилировщике.

Как была устроена прежняя реализация

Каждая map владела массивом бакетов (buckets). В каждом бакете помещалось до 8 пар ключ-значение, а также массив tophash, позволявший отсекать несовпадающие слоты до выполнения дорогого сравнения ключей. Если бакет переполнялся, выделялся ещё один и связывался в цепочку:

type bmap struct {   // bucket with 8 slots
	tophash  [8]uint8
	keys     [8]K
	values   [8]V
	overflow *bmap
}

Эта схема была вполне рабочей. Она поддерживала инкрементальный рост: при изменении размера map сохраняла оба массива бакетов и постепенно переносила старые бакеты по мере обращения к ним, избавляя от необходимости оплачивать полный rehash в рамках одного вызова. Платить приходилось локальностью данных. Как только горячие бакеты начинали порождать цепочки переполнения, поиск превращался в проход по указателям в несвязных областях памяти, а практический предел коэффициента заполнения (load factor) упирался примерно в 81% (около 6.5 из 8 слотов), после чего коллизии и необходимость роста становились слишком накладными.

В чём отличие Swiss Tables

Здесь две идеи: компактные метаданные для каждого слота и непрерывные группы. Ключ хешируется один раз, а полученный хеш делится на две части: h1 выбирает начальную группу, а h2 становится коротким отпечатком (fingerprint), который сохраняется в контрольном байте вместе с состоянием слота (пустой, удалён, занят). Группа состоит из 8 слотов с 8 упакованными контрольными байтами, так что одна быстрая операция считывает состояние и отпечатки сразу для всех слотов группы.

При таком подходе поиск никогда не читает байты самого ключа наугад:

g = startGroup(h1)
for {
	matches = matchFingerprint(ctrl[g], h2)
	for each pos in matches {
		if keys[g][pos] == key { return vals[g][pos] }
	}
	if hasEmpty(ctrl[g]) { return not found }
	g = nextGroup(g)
}

Условие остановки hasEmpty гарантирует корректность, а не просто скорость: в открытой адресации обнаружение пустого слота доказывает, что ключ никогда не вставлялся по этой цепочке проб, иначе при вставке был бы занят именно этот слот. Удаление не выполняет сжатие на месте - оно записывает tombstone-маркер, поскольку немедленное сжатие делает единичные удаления дорогими и может нарушить непрерывность цепочки проб. Расплата за это наступает позже: скопление tombstone-маркеров удлиняет цепочки проб вплоть до шага расширения или реорганизации.

Поскольку обход остаётся линейным сканированием компактных метаданных, рабочий коэффициент заполнения вырастает ближе к 90% (для групп из 8 слотов обычно называют цифру 87.5%). Это снижает накладные расходы в пересчёте на элемент и сокращает число расширений при том же количестве ключей.

Важно, что Golang не использует SIMD для сканирования контрольных байтов, как это делает реализация Abseil на C++ под x86. Согласно README в cockroachdb/swiss, переход в ассемблер Golang внутри цикла проб влечёт ощутимые накладные расходы на вызов функции, поэтому в runtime используется SWAR (SIMD within a register). Выигрыш даёт именно локальность данных, а не векторные инструкции - в точности как в false-sharing-alignment-128, где наблюдаемый эффект от компоновки кэш-линий целиком зависит от поведения нижележащей микроархитектуры.

Специфика реализации в Golang

Прямой перенос Abseil не подошёл бы. Классические таблицы с открытой адресацией растут за счёт выделения таблицы большего размера с полной повторной вставкой всех элементов, а горячий путь обработки запросов не может позволить себе периодический полный rehash всей таблицы. Поэтому хранилище разбито на несколько небольших таблиц в стиле Swiss Tables под управлением директории - концептуально это расширяемое хеширование (extendible hashing): старшие биты хеша выбирают сегмент, пробы выполняются внутри него, а при превышении порога делится только этот сегмент и обновляется запись в директории. Рост остаётся локальным, перемещение памяти ограничено разделяемым сегментом, а обновление директории обходится дёшево.

Такая сегментация также решает две задачи, не связанные со скоростью. Порядок итерации в Golang намеренно не зафиксирован, но он не произволен: runtime не может возвращать частично перезаписанное состояние или терять элементы, которые должны быть видны. Поэтому итераторы привязаны к версионированию внутри map и метаданным обхода, которые сохраняют корректность при переносе элементов во время расщепления сегментов. Кроме того, ключи и значения могут содержать указатели, поэтому любое перемещение обязано оставаться корректным с точки зрения write barrier; малый шаг переноса снижает область воздействия каждой записи под барьером.

Цифры и разрыв между ними

В сводке от Michael Pratt в трекере (golang/go#54766) указано: чтение и запись в больших map ускорились примерно на 30-35%, итерация - в среднем на 10% и до ~60% на слабо заполненных больших map, а среднее геометрическое ускорение в наборе тестов Sweet на реальных приложениях составило около 1.5%. В описании релиза 1.24 в среднем 2-3% снижения нагрузки на CPU приписаны оптимизациям runtime в целом, куда входят и map.

Разница между 30% и 1.5% показательна. Микротесты удерживают одну операцию горячей в кэше; реальные сервисы тратят время на парсинг, системные вызовы, границы RPC, планировщик и работу GC, поэтому выигрыш от map размывается, если только операции с ними не доминируют в профиле. В работе Cloudflare над кэшем DNS этот разрыв оказался меньше: 56% на запись в бенчмарке, 42-43% в resident memory (big-pineapple-dns-cache-layout). Команда Golang пошла дальше и подвергла сомнению собственные бенчмарки в #70700, указав на удобные для предсказателя переходов шаблоны ключей, размеры map в виде степеней двойки и накладные расходы самого тестового фреймворка как на искажающие факторы. Переработка бенчмарков заметно изменила наблюдаемые цифры. Одно из исправлений по итогам этой работы улучшило задержку попадания в кэш для маленьких map с непредсказуемыми ключами примерно в 1.7 раза (с ~25 нс до 14 нс), а промахов - примерно в 1.3 раза.

В python-dict-quadratic-time показана та же сторона проблемы с памятью в Python: словарь замедляется в девять раз в пересчёте на ключ при переходе от минимального размера к максимальному без смены алгоритма, просто потому что на миллионе записей обращения перестают попадать в кэш.

По памяти заявлено сокращение потребления на 0-25% в зависимости от нагрузки, что закономерно следует из более плотного заполнения и отказа от цепочек переполнения.

Задокументированы и регрессии. В открытом issue #70835 отслеживается поведение при холодном кэше: дополнительная адресация через директорию и множественные аллокации могут сделать промах дороже, чем раньше; бенчмарк Prometheus в этом обсуждении показал больший расход CPU на runtime.mapaccess1_fast64 в версии 1.24.2 по сравнению с 1.23 для соответствующего профиля нагрузки. Эксперимент с флагом GOEXPERIMENT=mapsplitgroup, разделяющий ключи и значения внутри группы, как раз проверяется для решения этой проблемы. Отдельно в #70617 отмечено, что clear(m) требует времени, пропорционального выделенному размеру таблицы, для map, которые были большими, а затем опустели.

Что это означает на практике

Весь план действий сводится к обновлению версии; код менять не нужно. Честный вывод из этих цифр: сервисы с преобладанием поиска или вставки в средних и больших map получают бесплатное ускорение, а профили с доминированием холодных промахов, сильно разреженных огромных map или плотных циклов clear/повторного использования требуют измерений, а не слепой веры в прирост.

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

m := make(map[string]int)
for {
    populate(m)
    process(m)
    clear(m)   // cheap when m is consistently sized; not when m grew once and shrank
}

А горячие пути с преобладанием удалений нагружают обработку tombstone-маркеров в каждой группе проб, получая меньше выгоды по сравнению с чистым чтением или вставкой. Ни один из этих случаев не требует вмешательства в код ради корректности - они лишь ограничивают потенциальный выигрыш.

Символы, за которыми стоит следить в CPU-профиле: runtime.mapaccess1, runtime.mapassign и runtime.mapiterinit. Прямой способ оценить эффект для собственного кода - сравнить результаты через go tool pprof между сборками на 1.23 и 1.24+. Принцип "измеряй, а не экстраполируй" применяется в go-bounds-checks-unsafe на куда меньшем масштабе, и ровно по этой же причине полезно прочитать compiler-codegen-luck, прежде чем доверять дельте в отдельном микротесте. В golang-green-tea-gc эта ловушка видна особенно отчётливо: новый сборщик мусора срезает треть времени выполнения, при этом доля промахов в L3-кэше удваивается или растёт ещё сильнее, потому что исчезли как раз те чтения, которые L3 и так успевал отдавать.