Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: consider growing map on iteration #51410

Closed
TocarIP opened this issue Mar 1, 2022 · 1 comment
Closed

runtime: consider growing map on iteration #51410

TocarIP opened this issue Mar 1, 2022 · 1 comment

Comments

@TocarIP
Copy link
Contributor

TocarIP commented Mar 1, 2022

What version of Go are you using (go version)?

$ go version
go version go1.18-pre10 linux/amd64

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/usr/local/google/home/tokarip/.cache/go-build"
GOENV="/usr/local/google/home/tokarip/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/usr/local/google/home/tokarip/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"

What did you do?

Currently map amortizes the growth over several inserts/deletes. This means that if we do several inserts to get map into a "growing" state and than never insert/delete anything and just iterate through map we get much higher cost of iteration, because in the "growing" state we are doing extra hashing (line 934 in map.go hash := t.hasher(k, uintptr(h.hash0)). Consider the following benchmark that adds X strings into a map and than iterates over them a lot:

//go:noinline
func iter(m map[string]string) int {
        ret := 0
        for _, a := range m { 
                ret += len(a)
        }
        return ret 
}

func BenchmarkMap(b *testing.B) {
        minSize := 50
        maxSize := 60
        for size := minSize; size < maxSize; size++ {
                b.Run(fmt.Sprintf("input_size_%d", size), func(b *testing.B) {
                        m := make(map[string]string)
                        for i := 0; i < size; i++ {
                                key := make([]byte, 300)
                                value := make([]byte, 300)
                                rand.Read(key)
                                rand.Read(value)
                                m[string(key)] = string(value)
                        }
                        x := 0
                        for i := 0; i < b.N; i++ {
                                x += iter(m)
                        }
                })
        }
}

What did you expect to see?

Stable cost of iteration, growing linearly with the number of elements.

What did you see instead?

For some numbers of elements, performance is 4-5x worse:

BenchmarkMap/input_size_50-12               538ns ± 3%
BenchmarkMap/input_size_51-12               532ns ± 5%
BenchmarkMap/input_size_52-12               549ns ± 2%
BenchmarkMap/input_size_53-12              2.31µs ± 6%
BenchmarkMap/input_size_54-12              1.93µs ±13%
BenchmarkMap/input_size_55-12              1.53µs ±26%
BenchmarkMap/input_size_56-12              1.20µs ±27%
BenchmarkMap/input_size_57-12               675ns ± 1%
BenchmarkMap/input_size_58-12               680ns ± 3%
BenchmarkMap/input_size_59-12               689ns ± 3%

Adding size to make fixed the issue, but this is still a cause of a significant and unexpected performance cliff. So growing map on iterations makes sense to avoid performance cliffs like this.

@randall77
Copy link
Contributor

I think this is a dup of #19094. Or at least, read and iterate are similar enough that it's probably the same fix for both.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants