runtime: consider growing map on iteration

[TocarIP]

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]

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.