Новая реализация map в Go 1.24: Смотрим под капот14.03.2025 00:01

Введение

В версии Go 1.24 разработчики кардинально изменили внутреннюю реализацию map, перейдя с традиционного механизма цепочек бакетов на Swiss Table. Этот новый подход улучшает производительность, снижает использование памяти и делает операции с map более эффективными. В этой статье мы не будем смотреть принципиальную разницу в подходах, это вы можете прочитать в оригинальной статье или переводе на хабре. Я же хочу быстро посмотреть изменения в коде, включая создание map, поиск элементов, обработку коллизий и выделение памяти.

Создание map

Старая реализация (до Go 1.24)

В предыдущих версиях Go структура hmap управляла массивом бакетов, в которых хранились ключи и значения. Вот основные поля структуры: 

// hmap в Go <= 1.23
 type hmap struct {
    count       int
    B           uint8   // log2(число бакетов)
    buckets     unsafe.Pointer
    oldbuckets  unsafe.Pointer
    noverflow   uint16  // количество overflow-бакетов
    ...
}

При создании map через make(map) выполнялась функция makemap, которая выделяла массив бакетов размером 2^B: 

// Старый runtime.makemap
B := uint8(0)
for overLoadFactor(hint, B) {
    B++
}
h.B = B
if h.B != 0 {
    h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
    if nextOverflow != nil {
        h.extra = new(mapextra)
        h.extra.nextOverflow = nextOverflow
    }
}

Эта модель предусматривала жестко заданный размер бакетов и overflow-цепочки для разрешения коллизий.

Новая реализация (Go 1.24)

В новой версии Go хранилище map управляется структурой Map, в которой бакеты заменены на группы, а вместо B и buckets теперь используется директория таблиц: 

// Новая структура Map в Go 1.24
type Map struct {
    used         uint64
    seed         uint64
    dirPtr       unsafe.Pointer  // Указатель на массив таблиц
    dirLen       uint64
    globalDepth  uint8
    globalShift  uint8
    writing      bool
    clearSeq     uint32
}

Вместо фиксированного массива бакетов теперь возможны несколько таблиц, управляющихся через директорию (dirPtr). При создании маленьких map (до 8 элементов) аллокация памяти откладывается до первой вставки. В остальных случаях используется следующий алгоритм: 

// Новый maps.NewMap
if hint <= abi.SwissMapGroupSlots {
    return m  // малый словарь – отложим аллокацию до вставки
}
…
dirSize := (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity
dirSize, _ = alignUpPow2(dirSize)
directory := make([]*table, dirSize)
for i := range directory {
    directory[i] = newTable(mt, uint64(targetCapacity)/dirSize, i, m.globalDepth)
}
m.dirPtr = unsafe.Pointer(&directory[0])
m.dirLen = len(directory)

Теперь, вместо выделения единого массива бакетов, создается несколько таблиц в зависимости от требуемой емкости.

Поиск элементов в map

Старая реализация (до Go 1.24)

Ранее поиск ключа использовал комбинацию хеша и цепочек бакетов. Индекс бакета определялся младшими битами хеша, а tophash (старшие 8 бит) помогал ускорить фильтрацию записей: 

hash := t.Hasher(key, uintptr(h.hash0))
b := (*bmap)(add(h.buckets, (hash & m)*uintptr(t.BucketSize)))
...
for ; b != nil; b = b.overflow(t) {
    for i := uintptr(0); i < abi.OldMapBucketCount; i++ {
        if b.tophash[i] != top {
            if b.tophash[i] == emptyRest {
                break
            }
            continue
        }
        if t.Key.Equal(key, add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))) {
            return valuePointer, true
        }
    }
}
return nil, false  // не найден

Поиск мог затрагивать несколько бакетов, если ключ находился в overflow-бакете.

Новая реализация (Go 1.24)

В новой реализации используется открытая адресация и пробирование. Хеш делится на H1 (57 бит) и H2 (7 бит). H1 определяет группу,  H2 сохраняется в контрольном байте и позволяет быстро фильтровать записи: 

// Новый поиск в Swiss Table (Go 1.24)
h2 := uint8(h2(hash))
ctrls := *g.ctrls()
for i := uintptr(0); i < abi.SwissMapGroupSlots; i++ {
    c := uint8(ctrls)
    ctrls >>= 8
    if c != h2 {
        continue
    }
    slotKey := g.key(typ, i)
    if typ.Key.Equal(key, slotKey) {
        return slotKey, g.elem(typ, i), true
    }
}
return nil, nil, false

Swiss Table позволяет проверять 8 записей за шаг, что ускоряет поиск.

Разрешение коллизий

До Go 1.24: overflow-бакеты

При коллизиях использовались overflow-бакеты: 

type bmap struct {
    tophash [8]uint8
    keys    [8]keyType
    values  [8]valueType
    overflow *bmap
}

Go 1.24: пробирование

Теперь используется квадратичное пробирование: при коллизии ключ ищется в следующей группе, а удаленные элементы помечаются специальным значением (deleted), чтобы не разрывать цепочку поиска.

Итоги

  • В новой реализации map используется Swiss Table, что значительно улучшает производительность и снижает потребление памяти.

  • В поиске применяется пробирование, а не цепочки overflow-бакетов.

  • Коллизии теперь решаются с помощью открытой адресации, а не выделения новых бакетов.

  • При росте map теперь могут добавляться новые таблицы вместо удвоения всей структуры.

Рисунок 1. Результаты бенчмарков
Рисунок 1. Результаты бенчмарков

Если посмотреть на результаты бенчмарков, то можем увидеть благодаря этим изменениям, операции с map стали быстрее на 10–20%.

© Habrahabr.ru