Go: составной ключ вместо вложенных map

Когда нужно хранить данные по двум или более ключам, первое, что приходит в голову — вложенные map: map[string]map[int]bool. Это работает, но у подхода есть проблемы. Ниже покажу, чем map[CompositeKey]bool со структурой-ключом лучше, приложу бенчмарки и посмотрю, что происходит внутри рантайма.

Проблема: вложенные map

Допустим, нужно хранить информацию о правах пользователей по имени и ID роли. Типичный подход:

// Вложенная map: для каждой вставки нужна проверка на nil
m := make(map[string]map[int]string)

if m["alice"] == nil {
    m["alice"] = make(map[int]string)
}
m["alice"][1] = "admin"

if m["bob"] == nil {
    m["bob"] = make(map[int]string)
}
m["bob"][2] = "user"

Каждый раз при вставке приходится проверять, инициализирована ли вложенная map. Забыли проверку — получили panic: assignment to entry in nil map.

Решение: составной ключ

type UserRole struct {
    Name string
    ID   int
}

m := make(map[UserRole]string)

// Вставка — один вызов, никаких проверок
m[UserRole{"alice", 1}] = "admin"
m[UserRole{"bob", 2}] = "user"

Код проще, проверка на nil не нужна. Но кроме удобства есть ещё и разница в производительности. Проверим.

Бенчмарки

Тестовые данные: 10 000 записей, 1 000 уникальных имён (внешний ключ), ID в диапазоне 0-999. Окружение: Go 1.24.10, Linux, AMD Ryzen 5 PRO 4650U. Каждый бенчмарк запущен 3 раза с benchtime=2s.

Для сравнения добавил третий подход — конкатенацию строк (map[string]bool с ключом вида "alice:42"). Его тоже нередко используют.

Вставка

func BenchmarkInsert_Nested(b *testing.B) {
    keys := generateKeys(10000, 1000)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        m := make(map[string]map[int]bool)
        for _, k := range keys {
            if m[k.Name] == nil {
                m[k.Name] = make(map[int]bool)
            }
            m[k.Name][k.ID] = true
        }
    }
}

func BenchmarkInsert_Composite(b *testing.B) {
    keys := generateKeys(10000, 1000)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        m := make(map[CompositeKey]bool)
        for _, k := range keys {
            m[k] = true
        }
    }
}

На первый взгляд вложенные map вставляют быстрее по ns/op. Но обратите внимание на количество аллокаций: 4 151 против 79 — разница в 52 раза. Каждая аллокация — это объект, который сборщик мусора должен отслеживать.

Конкатенация строк — худший вариант по всем метрикам: и медленнее (на каждую вставку создаётся новая строка), и аллокаций больше всех (19 058). Ещё теряется типобезопасность — ключ "alice:42" это просто строка, компилятор не поймает ошибку, если перепутать порядок полей или забыть разделитель.

Чтение (lookup)

func BenchmarkLookup_Nested(b *testing.B) {
    // ... заполняем map ...
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        for _, k := range keys {
            _ = m[k.Name][k.ID]
        }
    }
}

func BenchmarkLookup_Composite(b *testing.B) {
    // ... заполняем map ...
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        for _, k := range keys {
            _ = m[k]
        }
    }
}

Составной ключ читает на ~17% быстрее. Логично: один хеш и один поиск по бакетам вместо двух.

Удаление

Тут тоже ~15% в пользу составного ключа. Та же механика — одна операция вместо двух.

Высокая кардинальность внешнего ключа

Что будет, если уникальных имён не 1 000, а 5 000 (при тех же 10 000 записях)? Вложенный подход создаст ~5 000 внутренних map, в каждой всего по 2 записи.

При высокой кардинальности внешнего ключа составной ключ быстрее уже на ~24%, а количество аллокаций отличается в 111 раз. Причина: каждая внутренняя map — это отдельный объект hmap в куче со своим массивом бакетов.

Нагрузка на сборщик мусора

Проверим нагрузку на GC: создадим 100 структур по 1 000 записей и вызовем runtime.GC() вручную:

func BenchmarkGC_Nested(b *testing.B) {
    keys := generateKeys(1000, 100)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        maps := make([]map[string]map[int]bool, 100)
        for j := range maps {
            m := make(map[string]map[int]bool)
            for _, k := range keys {
                if m[k.Name] == nil {
                    m[k.Name] = make(map[int]bool)
                }
                m[k.Name][k.ID] = true
            }
            maps[j] = m
        }
        runtime.GC()
    }
}

Вложенные map здесь формально быстрее по ns/op — меньше суммарный объём данных в бакетах, GC обходит их быстрее. Но аллокаций они создают в 19 раз больше. На практике, когда хип большой и аллокаций много, именно количество живых объектов определяет длительность пауз GC.

GC в Go обходит все живые объекты в куче. Чем больше объектов — тем дольше фаза маркировки. Тысяча мелких map — это тысяча заголовков hmap плюс столько же массивов бакетов, и каждый из них GC должен пометить как живой.

Что происходит при lookup

Разберём, что конкретно делает рантайм при обращении к map.

Вложенная map: два поиска

При вызове m[k.Name][k.ID] рантайм выполняет два независимых поиска.

Сначала — по внешней map: вычисляет хеш строки k.Name, находит нужный бакет, перебирает слоты (сравнивая tophash, затем сам ключ) и возвращает указатель на значение — внутреннюю map.

Потом — по внутренней: разыменовывает указатель (это переход в другую область памяти, возможный cache miss), вычисляет хеш числа k.ID, снова находит бакет, перебирает слоты и возвращает значение.

Получается два вычисления хеша, два обхода бакетов и один переход по указателю между двумя независимыми структурами в куче.

Составной ключ: один поиск

При вызове m[CompositeKey{k.Name, k.ID}] рантайм вычисляет один хеш (компилятор генерирует функцию, которая хеширует оба поля за один проход), находит один бакет, сравнивает tophash, сравнивает ключ целиком и возвращает значение.

Один хеш, один обход, никаких промежуточных указателей.

Cache locality

17% разницы при lookup — это не только «один хеш вместо двух». Тут ещё играет роль расположение данных в памяти.

Одна map с 10 000 записей хранит бакеты в одном непрерывном массиве. При последовательном обходе CPU подгружает соседние бакеты в кэш L1/L2, и следующие обращения попадают в уже загруженные кэш-линии.

Тысяча вложенных map — это тысяча отдельных массивов бакетов, разбросанных по куче. Переход от внешней map к внутренней — это переход по указателю в произвольное место памяти. Prefetcher CPU не может угадать, куда мы пойдём дальше, и каждый такой переход — потенциальный cache miss.

На маленьких данных это не заметно — всё помещается в кэш. Но чем больше данных и чем чаще обращения к разным внешним ключам, тем сильнее бьёт cache miss от вложенных map.

Устройство map в рантайме Go

Посмотрим в исходники и разберёмся, из чего складывается overhead.

Структура hmap (Go <= 1.23)

Каждая map в Go — это указатель на структуру hmap:

// src/runtime/map.go
type hmap struct {
    count     int            // количество элементов
    flags     uint8
    B         uint8          // log2 количества бакетов
    noverflow uint16         // количество overflow-бакетов
    hash0     uint32         // seed для хеш-функции

    buckets    unsafe.Pointer // массив из 2^B бакетов
    oldbuckets unsafe.Pointer // старые бакеты (при росте)
    nevacuate  uintptr        // прогресс эвакуации

    extra *mapextra           // overflow-бакеты для GC
}

На 64-битной системе sizeof(hmap) == 48 байт. Это подтверждается assert’ом в компиляторе: 8 + 5*types.PtrSize.

Бакеты (bmap)

Каждый бакет хранит до 8 пар ключ-значение:

// src/runtime/map.go
type bmap struct {
    tophash [8]uint8 // старшие 8 бит хеша каждого ключа
    // далее идут 8 ключей, 8 значений, указатель на overflow-бакет
    // (добавляются компилятором)
}

Реальная раскладка в памяти:

[ tophash[8] ][ key0..key7 ][ val0..val7 ][ *overflow ]
   8 байт       8 * keySize    8 * valSize    8 байт

Ключи упакованы вместе, значения — вместе. Это сделано для минимизации выравнивания. Например, для map[int64]int8 раскладка key/val/key/val потратила бы 7 байт на padding в каждой паре.

Swiss Tables (Go >= 1.24)

С Go 1.24 map переведены на Swiss Tables. Структура изменилась, но суть та же: каждая map — отдельный объект в куче со своим заголовком (48 байт) и массивом групп.

Вместо цепочек overflow-бакетов используется открытая адресация с квадратичным пробированием по группам. Каждая группа хранит 8 слотов и 8-байтное контрольное слово, где каждый байт содержит младшие 7 бит хеша (H2):

Контрольный байт:
  empty:   0x80 (10000000)
  deleted: 0xFE (11111110)
  full:    0hhhhhhh (H2 — младшие 7 бит хеша)

Поиск по 8 слотам группы выполняется параллельно через побитовые операции над uint64. Это быстрее, чем последовательное сравнение tophash[i] в классической реализации.

Откуда берётся overhead вложенных map

Что создаётся при map[string]map[int]bool с 1 000 внешних ключей:

1 001 заголовок — это 1 001 отдельная аллокация в куче. Массивы бакетов — ещё столько же. Аллокатор Go округляет размер до ближайшего size class, так что маленькие map расходуют память неэффективно.

Хеш-функции для struct-ключей

Компилятор Go генерирует хеш-функцию для каждого типа, используемого как ключ map. Для структуры CompositeKey{Name string, ID int} компилятор создаёт функцию, которая последовательно хеширует каждое поле (strhash для строки, memhash64 для int) и комбинирует результаты.

На x86-64 с AES-NI используются аппаратно-ускоренные хеш-функции (aeshash, aeshashstr), так что хеширование составного ключа по скорости почти не отличается от двух отдельных хешей.

Для структур из фиксированных по размеру полей (например, struct{X, Y int}) компилятор может сделать один вызов memhash по всей памяти структуры — это ещё быстрее, чем хеширование полей по отдельности.

Когда вложенные map оправданы

Составной ключ не всегда лучше. Иногда вложенные map удобнее.

Если часто нужно получить все значения по внешнему ключу (m["alice"]), вложенная map даёт это бесплатно. С составным ключом придётся перебирать всю map.

Если map[string]map[int]struct{} логически представляет Set<int> для каждого имени и вы передаёте эти set’ы дальше по коду — вложенная структура логичнее.

Ну и если внешних ключей мало (десятки), overhead от вложенных map просто не заметен.

Есть и ограничение: все поля структуры-ключа должны быть comparable. Слайсы, map и функции в качестве полей использовать нельзя — компилятор не сгенерирует для них хеш-функцию и оператор сравнения. Если в ключе нужен слайс, придётся конвертировать его в строку или использовать массив фиксированной длины.

Итог

Если итерация по одному из ключей не нужна — берите составной ключ. Он проще, быстрее и избавляет от nil map panic. Чем больше уникальных внешних ключей, тем заметнее разница.

Теги:

• golang