Comments 7
Спасибо, интересно!
Довольно интересная статья, мне понравилось её читать. Кажется, где-то уже видел про Swiss Table в golang, но здесь всё довольно подробно.
Немного странно читать переведенные в лоб термины "с открытой адресацией", как будто на русском эти термины не передают никакого смысла, который в них был заложен (а был ли?).
Ну и хотелось бы подробнее узнать о том, почему Swiss Table увеличивается теперь не на степени двойки, если судить по графику из начала статьи.
По разделу «Incremental Growth» в https://go.dev/blog/swisstable я понял, что размер Go-шной Swiss Table может вырасти максимум на 1024 за раз. А «не Swiss Table» реализация в Go удваивает своей размер: https://github.com/golang/go/blob/b70244ff7a043786c211775b68259de6104ff91c/src/runtime/map_noswiss.go#L1118, поэтому и такой график.
Я так понимаю, ускорение только из-за того, что много коллизий в реализации хеш функции.
При нормальном хешировании - нужна была бы очень большая мапа чтобы дойти до бакетов, и прирост скорости конечно был бы - но не существенно (edge cases)
Спасибо за ссылки! Не видел про ограничения на 1024 раньше.
Хочу отметить, что прочитал в одном блоге, что такой рост размера с сохранением скорости возможен благодаря замене функции остатка от деления (a % b) на функцию вида (a * b) >> 32, которая также выдает число в промежутке [0, b).
Интересно, что это нечто похожее на то, как компилятор оптимизирует деление. По крайней мере подобные конструкции я видел при декомпиляции программ с делением. Однако там a и b не соответствовали в обеих функциях, а здесь соответствие необходимо.
На M1 у новой map наблюдаются проблемы в многопоточном режиме доступа
package main
import (
"sync"
"testing"
)
func BenchmarkMap(b *testing.B) {
b.Run("map", func(b *testing.B) {
var (
wg sync.WaitGroup
mu sync.RWMutex
)
m := map[int]int{}
for i := range b.N {
wg.Add(1)
go func() {
mu.Lock()
m[i] = i
mu.Unlock()
wg.Done()
}()
}
wg.Wait()
})
}
Swiss Map -
go test -v ./ -bench=BenchmarkMap
goos: darwin
goarch: arm64
pkg: test
cpu: Apple M1
BenchmarkMap
BenchmarkMap/map
BenchmarkMap/map-8 2043374 622.9 ns/op
PASS
ok test 2.088s
Swiss map - 1 CPU
GOMAXPROCS=1 go test -v ./ -bench=BenchmarkMap
goos: darwin
goarch: arm64
pkg: test
cpu: Apple M1
BenchmarkMap
BenchmarkMap/map
BenchmarkMap/map 2083174 545.1 ns/op
PASS
ok test 2.384s
Old Map
GOEXPERIMENT=noswissmap go test -v ./ -bench=BenchmarkMap
goos: darwin
goarch: arm64
pkg: test
cpu: Apple M1
BenchmarkMap
BenchmarkMap/map
BenchmarkMap/map-8 2166986 511.3 ns/op
PASS
ok test 2.296s
Old map - 1 CPU
GOMAXPROCS=1 GOEXPERIMENT=noswissmap go test -v ./ -bench=BenchmarkMap
goos: darwin
goarch: arm64
pkg: test
cpu: Apple M1
BenchmarkMap
BenchmarkMap/map
BenchmarkMap/map 2067202 574.8 ns/op
PASS
ok test 1.963s
Go 1.24 — swiss tables новая реализация map