Hashmap(map) according to Golang. Part 2

Hi all. We continue to implement the hashmap from the Go 1.19 sources. In the second part, we will look at generic keys and map growth. We will learn what non-reflexive keys are, how iteration occurs during growth, and a little about boxed hashing.

Part 1

Some definitions from the last part:

• bucket – a data structure that stores keys, values ​​and tophash;

• growth – when a certain threshold of values ​​in the bucket (on average) is reached, growth begins to maintain a constant speed of operations with the map. Memory is allocated for x2 buckets;

• evacuation – in the process of growth, old buckets are “evacuated” to a new place.

generic keys

We hash everything moving Comparable:

Out of the box, Go does not provide access to the hashing functions that are used in map. However, there is progress in this direction – in go 1.19 the maphash package had added functions Bytes And String for hashing an array of bytes and a string, respectively. But this is not enough to use generic keys in our map. We will use magic, which you can read about Here.

dolthub/maphash or how to get to the hash function from runtime

The Go compiler generates a hash function for each type of key we use in our code. You can find it in the following structure maptype:

runtime/type.go

type maptype struct {
    /* ... */
	// function for hashing keys (ptr to key, seed) -> hash
	hasher     func(unsafe.Pointer, uintptr) uintptr
    /* ... */
}

You can get to it using type casting and a package unsafe:

dolthub/maphash/runtime.go

func getRuntimeHasher[K comparable]() (h hashfn, seed uintptr) {
	a := any(make(map[K]struct{})) // создаем мапу с нужным типом ключа
	i := (*mapiface)(unsafe.Pointer(&a)) // приводим к нашей структуре, которая идентична тому что под капотом
	h, seed = i.typ.hasher, uintptr(i.val.hash0) // забираем работу компилятора
	return
}

type mapiface struct {
	typ *maptype
	val *hmap
}

// go/src/runtime/type.go
type maptype struct {
    /* ... */
	hasher func(unsafe.Pointer, uintptr) uintptr // заветная функция хеширования
    /* ... */
}

// go/src/runtime/map.go
type hmap struct {
    /* ... */
}

We get the following function for hashing for comparable types:

func (h Hasher[K]) Hash(key K) uint64 // K - comparable

Why use magic?

Hashing under the hood uses whenever possible AES processor instructions. This will run faster (in theory) than pure Go code.

We add ourselves. Now creating a map looks like this:

type hmap[K comparable, V any] struct {
    /* ... */
	hasher  maphash.Hasher[K]
    /* ... */
}

func New[K comparable, V any](size int) Hashmap[K, V] {
	h := new(hmap[K, V])

	B := uint8(0)
	for overLoadFactor(size, B) {
		B++
	}
	h.B = B

	h.buckets = make([]bucket[K, V], bucketsNum(h.B))

    /* новый код */
	h.hasher = maphash.NewHasher[K]() // новый хэшер для comparable типов

	return h
}

// использование 
func (h *hmap[K, V]) locateBucket(key K) (tophash uint8, targetBucket uint64) {
	hash := h.hasher.Hash(key)
    /* ... */
}

About non-reflexive keys

These are called keys that are not equal to themselves – x != x. Go has them.

We can use NaN as a key in a map with some caveats:

• each time you add an element with this key, a new element will be created;

• you can get to the value by such a key only when iterating;

• cannot be removed;

• the hash from such a key is always different, so the elements will be scattered across different buckets.

  m := make(map[float64]int)
  for i := 0; i < 4; i++ {
      m[math.NaN()] = i
  }
  fmt.Println(m)             // map[NaN:1 NaN:0 NaN:3 NaN:2]
  fmt.Println(m[math.NaN()]) // 0

Evacuation

Map growth starts in two cases:

• buckets are more than ~80% full on average. In this case, the number of buckets is doubled;

• and a special case (not coded) – the number of overflow buckets is approximately equal to the number of buckets themselves.

Unlike, for example, Python And Java in Go, map growth is gradual. Each time before adding or deleting an element, data is transferred from 1-2 buckets.

For growth, we need several new fields:

type hmap[K comparable, V any] struct {
	len int // количество реальных значений в мапе
	B   uint8 // log_2 от количества бакетов
	buckets []bucket[K, V] // слайс бакетов
	hasher  maphash.Hasher[K] // функция хэширования из рантайма

    /* новые поля */
	oldbuckets   *[]bucket[K, V] // слайс старых бакетов
	numEvacuated uint64 // счетчик прогресса роста. все бакеты меньше этого значения эвакуированы
}

Growth training:

// выделяем память под новые бакеты, увеличиваем счетчик количества бакетов
func (m *hmap[K, V]) startGrowth() {
	oldBuckets := m.buckets
	m.B++ // растем только на увеличение
	m.buckets = make([]bucket[K, V], bucketsNum(m.B))
	m.oldbuckets = &oldBuckets
	m.numEvacuated = 0
}

This is what the evacuation and growth trigger looks like in the method Put:

func (h *hmap[K, V]) Put(key K, value V) {
	tophash, targetBucket := h.locateBucket(key)

    // проверяем "триггер" роста если кол-во элементов в бакете увеличится
	if !h.isGrowing() && overLoadFactor(h.len+1, h.B) {
		h.startGrowth()
	}

	// сначала эвакуируем нужный бакет
	if h.isGrowing() {
		h.growWork(targetBucket)
	}

	if h.buckets[targetBucket].Put(key, tophash, value) {
		h.len++
	}
}

Also, during growth, we check if the bucket was evacuated before looking for a value from there:

func (h *hmap[K, V]) Get2(key K) (V, bool) {
	tophash, targetBucket := h.locateBucket(key)

	b := &h.buckets[targetBucket]

	if h.isGrowing() {
		oldB := &(*h.oldbuckets)[targetBucket&h.oldBucketMask()] // берем старый бакет
		if !oldB.isEvacuated() { // если он еще не эвакуировался, то ищем значение в нем
			b = oldB
		}
	}

	return b.Get(key, tophash)
}

Proper evacuation

The algorithm itself is simple (practically) – we go through all the elements in the bucket, select a new bucket and transfer the key, value and tophash.

Where to move

As the map grows, the number of buckets doubles. If we divide the slice of new buckets into two halves, then for each element inside the old bucket there are two ways this is the way – either in the first half or in the second. And if you count every half of the new buckets separate slice, then we can say that within such a half, the bucket index for the element will not change.

Buckets from different halves are stored in an auxiliary structure. We also keep the index of the next free space there.

// evacDst вспомогательная структура для эвакуации бакета
type evacDst[K comparable, V any] struct {
	b *bucket[K, V] // ссылка но новый бакет
	i uint          // индекс следующего свободного места в бакете
}

// храним ссылки на два новых бакета, в которые будут переноситься данные из текущего
halfs := [2]evacDst[K, V]{
    {b: &m.buckets[oldbucket]}, // oldBucket равен номеру старого бакета, который хотим эвакуировать
    {b: &m.buckets[oldbucket+newBit]}, // newBit равен кол-ву старых бакетов
}

Half is selected using the hash of the key and the new mask bit. When growing, a bit is added to the new mask, which decides whether the result of the operation will change hash&mask or not.

newBit := m.numOldBuckets()
hash := m.hasher.Hash(*key)
var useSecond uint8
if hash&newBit != 0 {
    useSecond = 1
}

Full evacuation cycle:

newBit := m.numOldBuckets()
/* ... */
for ; b != nil; b = b.overflow {
    // итерируемся по старому бакету
    for i := 0; i < bucketSize; i++ {
        top := b.tophash[i]

        // используем флаги tophash для проверки пустых ячеек
        if isCellEmpty(top) {
            b.tophash[i] = evacuatedEmpty
            continue
        }

        key := &b.keys[i]
        value := &b.values[i]

        // опять берем хэш от ключа
        hash := m.hasher.Hash(*key)

        // флаг использования второй половины новых бакетов
        var useSecond uint8

        // проверяем зависит ли местоположение элемента от нового бита
        if hash&newBit != 0 {
            useSecond = 1
        }

        // evacuatedFirst, evacuatedSecond - константные флаги для массива tophash показывающие в какую половину переехал элемент
        // evacuatedFirst + useSecond == evaluatedSecond
        b.tophash[i] = evacuatedFirst + useSecond

        //выбираем нужный бакет
        dst := &halfs[useSecond]
        // проверяем кол-во элементов
        if dst.i == bucketSize {
            dst.b = newOverflow(dst.b) // если нужно создаем overflow
            dst.i = 0
        }
        // добавляем элемент по конкретному индексу
        dst.b.putAt(*key, top, *value, dst.i)
        dst.i++
    }
}

The original algorithm has the following check:

if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
    throw("bad evacuatedN")
}

It happens when moving each element. In my opinion, this is strange, since constants cannot be redefined, and one check at compile time would be enough. I replaced it with this check:

func _() {
	var x [1]struct{}
	_ = x[evacuatedFirst-2]
	_ = x[evacuatedSecond-3]
}

Iteration

The advantages of such a growth algorithm are that there are no performance drops when evacuating a large amount of data, as if we were doing it in one approach. Of the minuses – you need to take this into account when inserting / deleting / searching for values, and especially when iterating.

For this, there is a separate structure that stores references to the key and value, and the state of the iteration:

type hiter[K comparable, V any] struct {
	key           *K 			  // ключ
	elem          *V 			  // значение
	m             *hmap[K, V]	  // сама мапа
	buckets       *[]bucket[K, V] // массив бакетов по которым итерируемся
	currBktPtr    *bucket[K, V]   // текущий бакет
	startBucket   uint64          // рандомно выбранный начальный бакет
	offset        uint8           // рандомный оффсет, с которого начинается итерация внутри бакета
	wrapped       bool            // сделали круг по массиву бакетов
	B             uint8			  // log_2 от кол-ва бакетов на момент старта итерации
	i             uint8			  // позиция следующего элемента в текущем бакете
	currBucketNum uint64		  // номер текущего бакета
	checkBucket   uint64		  // номер бакета для дополнительной проверки. todo из-за эвакуации иногда приходится смотреть данные сразу в двух бакетах
}

We initialize. This is also where the magic of a “random” sequence of elements happens with each new iteration: a random bucket is selected from which the iteration will begin, and an indent from which elements within each bucket will be returned.

func iterInit[K comparable, V any](m *hmap[K, V]) *hiter[K, V] {
	h := hiter[K, V]{}

	if m == nil || m.len == 0 {
		return &h
	}

	h.m = m
	h.B = m.B
	h.buckets = &m.buckets
	// выбираем рандомный бакет
	h.startBucket = rand.Uint64() & bucketMask(m.B)
	// выбираем позицию, с которой начинается итерация внутри бакета
	h.offset = uint8(uint8(h.startBucket) >> h.B & (bucketSize - 1))
	h.currBucketNum = h.startBucket

	// сразу выполняем одну итерацию
	h.next()

	return &h
}

The iteration algorithm can be divided into two parts:

• a simple case – when the map is not in the process of growth;

• complex – in the process of growth. This will require additional checks.

In the first case, you can simply iterate over the buckets. We enter the state of the iteration into local variables and select the bucket:

b := it.currBktPtr
bucketNum := it.currBucketNum
i := it.i
checkBucket := it.checkBucket
next:
// выбираем следующий бакет
if b == nil {
	if bucketNum == it.startBucket && it.wrapped {
		// конец итерации
		it.key = nil
		it.elem = nil
		return
	}
	checkBucket = noCheck //
	b = &it.m.buckets[bucketNum] // бакет внутри которого будет искать данные

	bucketNum++ // номер след. бакета
	if bucketNum == bucketsNum(it.B) {
		// если "замкнули круг" то проставляем соответствующий флаг
		bucketNum = 0
		it.wrapped = true
	}
	i = 0
}

We iterate:

// bucketSize - константа количества элементов внутри бакета
for ; i < bucketSize; i++ {
	// определяем элемент, который будем переносить, в соответствии с оффсетом
	offI := (i + it.offset) & (bucketSize - 1)
	top := b.tophash[offI]
	// если ячейка пустая
	if isCellEmpty(top) || top == evacuatedEmpty {
		continue
	}
	key := &b.keys[offI]
	elem := &b.values[offI]

	// проставляем значения в структуру итерации
	it.key = key
	it.elem = elem
	// обновляем текущий стейт
	it.currBucketNum = bucketNum
	if it.currBktPtr != b {
		it.currBktPtr = b
	}
	it.i = i + 1
	return
}
// идем в overflow
b = b.overflow
i = 0
goto next // к выбору следующего бакета

In order to iterate in the process of map growth, we will add some changes to the algorithm. When choosing the next bucket x we will take into account that the data from the old bucket oldX may not have evacuated yet and need to start iterating on oldX.

Since there are only two options for transferring elements from the bucket, when passing through the old (not evacuated) oldX bucket, we will return only those elements that go to the bucket x.

Changes in the next bucket selection location:

// если рост еще не завершен, то старые бакеты тоже нужно учитывать
if it.m.isGrowing() && it.B == it.m.B {
	// runtime/map.go:890
	// итерацию начали во время роста. проверяем старый бакет
	// если он еще не эвакуировался, то проходим по нему, и возвращаем только те элементы
	// которые мигрируются в текущий бакет
	oldBucketNum := bucketNum & it.m.oldBucketMask()
	b = &(*it.m.oldbuckets)[oldBucketNum]
	if !b.isEvacuated() {
		checkBucket = bucketNum
	} else {
		// иначе просто итерируемся по bucketNum
		checkBucket = noCheck
		b = &it.m.buckets[bucketNum]
	}
} else {
	checkBucket = noCheck
	b = &it.m.buckets[bucketNum]
}
bucketNum++
if bucketNum == bucketsNum(it.B) {
  // если "замкнули круг" то проставляем соответствующий флаг
  bucketNum = 0
  it.wrapped = true
}
i = 0

We take into account that if we are in the old bucket, then we check whether the element needs to be returned.

Here we take into account the case when key != key (NaN). Since the hash from NaN will be new every time, we need a way to “randomly” transfer. In addition, you need to be able to reproduce such a choice. Therefore, for such values, instead of the hash of the key, tophash is used, namely its last bit, which determines which half the value will be transferred to.

if checkBucket != noCheck && !it.m.sameSizeGrow() {
	// runtime/map.go:925
	// случай когда мы начали итерацию во время роста и он еще не закончился
	// oldbucket слайс еще не эвакуировался. или, как минимум, он не был эвакуирован
	// когда мы начали итерацию.
	// по-этому пропускаем ключи которые попадут в навый бакет на другой позиции
	// (при эвакуации каждый элемент бакета либо остается в бакете по старому индексу либо по новому)
	if key == key {
		hash := it.m.hasher.Hash(*key)
		if hash&bucketMask(it.B) != checkBucket {
			continue
		}
	} else {
		// runtime/map.go:941
		// если ключ не равен себе(NaN) мы выбираем "рандомное" место переноса
		if checkBucket>>(it.B-1) != uint64(b.tophash[offI]&1) {
			continue
		}
	}
}

And the last difference in the algorithm is that we need to check that the iteration element has not moved to another bucket, that is, its tophash is not equal to one of the constants. If the element is still evacuated, then you will have to use the usual search through the function Get().

if (top != evacuatedFirst && top != evacuatedSecond) || key != key {
	// нашли элементы на текущем шаге итерации
	it.key = key
	it.elem = elem
} else {
	// мапа выросла с момента итерации
	// нужные данные для текущего ключа где-то в другом месте
	// этот кейс для случай когда ключ был удален/обновлен или удален и добавлен еще раз.

	re, ok := it.m.Get2(*key)
	if !ok {
		continue // ключ был удален
	}
	it.key = key
	it.elem = &re
}

Data consistency during iteration is guaranteed to us by the following check in the function next(). It saves from a competitive call to the map during iteration, which would lead to an additional evacuation of several buckets.

if it.m.flags&hashWriting != 0 {
	panic("concurrent map iteration and map write")
}

Let’s run the benchmark from the last part, which simply adds N elements to the map with an initial size of 1000. It has become similar to what is under the hood:

go test . -run=^$ -bench ^BenchmarkPutWithOverflow$ -benchmem
goos: darwin
goarch: arm64
pkg: github.com/w1kend/go-map
BenchmarkPutWithOverflow/gen-map__(string_key)10000-8           37374638                29.77 ns/op            0 B/op          0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)10000-8           41619038                27.21 ns/op            0 B/op          0 allocs/op
BenchmarkPutWithOverflow/gen-map__(string_key)100000-8          29636793                34.50 ns/op            0 B/op          0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)100000-8          30507568                34.89 ns/op            0 B/op          0 allocs/op
BenchmarkPutWithOverflow/gen-map__(string_key)1000000-8         14918946                79.41 ns/op            0 B/op          0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)1000000-8         19115414                63.17 ns/op            0 B/op          0 allocs/op
BenchmarkPutWithOverflow/gen-map__(string_key)10000000-8         6472369               267.0 ns/op           212 B/op          0 allocs/op
BenchmarkPutWithOverflow/STD______(string_key)10000000-8         6640574               248.4 ns/op           211 B/op          0 allocs/op

Sources for playing Here. For what? For example, when using the arena from Go 1.20 to store buckets, the performance on the benchmark did not change much (better with 10kk+ elements).

That’s all, thank you for your attention (:

Links

source code

gopher pictures

Hacking Go’s Runtime with Generics