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

Введение

В версии 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 теперь могут добавляться новые таблицы вместо удвоения всей структуры.

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