summaryrefslogtreecommitdiffstats
path: root/src/runtime/map_benchmark_test.go
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/runtime/map_benchmark_test.go535
1 files changed, 535 insertions, 0 deletions
diff --git a/src/runtime/map_benchmark_test.go b/src/runtime/map_benchmark_test.go
new file mode 100644
index 0000000..b46d2a4
--- /dev/null
+++ b/src/runtime/map_benchmark_test.go
@@ -0,0 +1,535 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package runtime_test
+
+import (
+ "fmt"
+ "math/rand"
+ "strconv"
+ "strings"
+ "testing"
+)
+
+const size = 10
+
+func BenchmarkHashStringSpeed(b *testing.B) {
+ strings := make([]string, size)
+ for i := 0; i < size; i++ {
+ strings[i] = fmt.Sprintf("string#%d", i)
+ }
+ sum := 0
+ m := make(map[string]int, size)
+ for i := 0; i < size; i++ {
+ m[strings[i]] = 0
+ }
+ idx := 0
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ sum += m[strings[idx]]
+ idx++
+ if idx == size {
+ idx = 0
+ }
+ }
+}
+
+type chunk [17]byte
+
+func BenchmarkHashBytesSpeed(b *testing.B) {
+ // a bunch of chunks, each with a different alignment mod 16
+ var chunks [size]chunk
+ // initialize each to a different value
+ for i := 0; i < size; i++ {
+ chunks[i][0] = byte(i)
+ }
+ // put into a map
+ m := make(map[chunk]int, size)
+ for i, c := range chunks {
+ m[c] = i
+ }
+ idx := 0
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ if m[chunks[idx]] != idx {
+ b.Error("bad map entry for chunk")
+ }
+ idx++
+ if idx == size {
+ idx = 0
+ }
+ }
+}
+
+func BenchmarkHashInt32Speed(b *testing.B) {
+ ints := make([]int32, size)
+ for i := 0; i < size; i++ {
+ ints[i] = int32(i)
+ }
+ sum := 0
+ m := make(map[int32]int, size)
+ for i := 0; i < size; i++ {
+ m[ints[i]] = 0
+ }
+ idx := 0
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ sum += m[ints[idx]]
+ idx++
+ if idx == size {
+ idx = 0
+ }
+ }
+}
+
+func BenchmarkHashInt64Speed(b *testing.B) {
+ ints := make([]int64, size)
+ for i := 0; i < size; i++ {
+ ints[i] = int64(i)
+ }
+ sum := 0
+ m := make(map[int64]int, size)
+ for i := 0; i < size; i++ {
+ m[ints[i]] = 0
+ }
+ idx := 0
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ sum += m[ints[idx]]
+ idx++
+ if idx == size {
+ idx = 0
+ }
+ }
+}
+func BenchmarkHashStringArraySpeed(b *testing.B) {
+ stringpairs := make([][2]string, size)
+ for i := 0; i < size; i++ {
+ for j := 0; j < 2; j++ {
+ stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
+ }
+ }
+ sum := 0
+ m := make(map[[2]string]int, size)
+ for i := 0; i < size; i++ {
+ m[stringpairs[i]] = 0
+ }
+ idx := 0
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ sum += m[stringpairs[idx]]
+ idx++
+ if idx == size {
+ idx = 0
+ }
+ }
+}
+
+func BenchmarkMegMap(b *testing.B) {
+ m := make(map[string]bool)
+ for suffix := 'A'; suffix <= 'G'; suffix++ {
+ m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
+ }
+ key := strings.Repeat("X", 1<<20-1) + "k"
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, _ = m[key]
+ }
+}
+
+func BenchmarkMegOneMap(b *testing.B) {
+ m := make(map[string]bool)
+ m[strings.Repeat("X", 1<<20)] = true
+ key := strings.Repeat("Y", 1<<20)
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, _ = m[key]
+ }
+}
+
+func BenchmarkMegEqMap(b *testing.B) {
+ m := make(map[string]bool)
+ key1 := strings.Repeat("X", 1<<20)
+ key2 := strings.Repeat("X", 1<<20) // equal but different instance
+ m[key1] = true
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, _ = m[key2]
+ }
+}
+
+func BenchmarkMegEmptyMap(b *testing.B) {
+ m := make(map[string]bool)
+ key := strings.Repeat("X", 1<<20)
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, _ = m[key]
+ }
+}
+
+func BenchmarkSmallStrMap(b *testing.B) {
+ m := make(map[string]bool)
+ for suffix := 'A'; suffix <= 'G'; suffix++ {
+ m[fmt.Sprint(suffix)] = true
+ }
+ key := "k"
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, _ = m[key]
+ }
+}
+
+func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
+func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
+func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
+func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
+
+func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
+ m := make(map[string]bool)
+ for i := 0; i < 8; i++ {
+ m[strings.Repeat("K", i+1)] = true
+ }
+ key := strings.Repeat("K", keySize)
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _ = m[key]
+ }
+}
+
+func BenchmarkIntMap(b *testing.B) {
+ m := make(map[int]bool)
+ for i := 0; i < 8; i++ {
+ m[i] = true
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, _ = m[7]
+ }
+}
+
+func BenchmarkMapFirst(b *testing.B) {
+ for n := 1; n <= 16; n++ {
+ b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
+ m := make(map[int]bool)
+ for i := 0; i < n; i++ {
+ m[i] = true
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _ = m[0]
+ }
+ })
+ }
+}
+func BenchmarkMapMid(b *testing.B) {
+ for n := 1; n <= 16; n++ {
+ b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
+ m := make(map[int]bool)
+ for i := 0; i < n; i++ {
+ m[i] = true
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _ = m[n>>1]
+ }
+ })
+ }
+}
+func BenchmarkMapLast(b *testing.B) {
+ for n := 1; n <= 16; n++ {
+ b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
+ m := make(map[int]bool)
+ for i := 0; i < n; i++ {
+ m[i] = true
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _ = m[n-1]
+ }
+ })
+ }
+}
+
+func BenchmarkMapCycle(b *testing.B) {
+ // Arrange map entries to be a permutation, so that
+ // we hit all entries, and one lookup is data dependent
+ // on the previous lookup.
+ const N = 3127
+ p := rand.New(rand.NewSource(1)).Perm(N)
+ m := map[int]int{}
+ for i := 0; i < N; i++ {
+ m[i] = p[i]
+ }
+ b.ResetTimer()
+ j := 0
+ for i := 0; i < b.N; i++ {
+ j = m[j]
+ }
+ sink = uint64(j)
+}
+
+// Accessing the same keys in a row.
+func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
+ m := make(map[string]bool)
+ // At least bigger than a single bucket:
+ for i := 0; i < 64; i++ {
+ m[fmt.Sprintf("some key %d", i)] = true
+ }
+ base := strings.Repeat("x", lookupKeySize-1)
+ key1 := base + "1"
+ key2 := base + "2"
+ b.ResetTimer()
+ for i := 0; i < b.N/4; i++ {
+ _ = m[key1]
+ _ = m[key1]
+ _ = m[key2]
+ _ = m[key2]
+ }
+}
+
+func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
+func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
+
+func BenchmarkMakeMap(b *testing.B) {
+ b.Run("[Byte]Byte", func(b *testing.B) {
+ var m map[byte]byte
+ for i := 0; i < b.N; i++ {
+ m = make(map[byte]byte, 10)
+ }
+ hugeSink = m
+ })
+ b.Run("[Int]Int", func(b *testing.B) {
+ var m map[int]int
+ for i := 0; i < b.N; i++ {
+ m = make(map[int]int, 10)
+ }
+ hugeSink = m
+ })
+}
+
+func BenchmarkNewEmptyMap(b *testing.B) {
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ _ = make(map[int]int)
+ }
+}
+
+func BenchmarkNewSmallMap(b *testing.B) {
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ m := make(map[int]int)
+ m[0] = 0
+ m[1] = 1
+ }
+}
+
+func BenchmarkMapIter(b *testing.B) {
+ m := make(map[int]bool)
+ for i := 0; i < 8; i++ {
+ m[i] = true
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ for range m {
+ }
+ }
+}
+
+func BenchmarkMapIterEmpty(b *testing.B) {
+ m := make(map[int]bool)
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ for range m {
+ }
+ }
+}
+
+func BenchmarkSameLengthMap(b *testing.B) {
+ // long strings, same length, differ in first few
+ // and last few bytes.
+ m := make(map[string]bool)
+ s1 := "foo" + strings.Repeat("-", 100) + "bar"
+ s2 := "goo" + strings.Repeat("-", 100) + "ber"
+ m[s1] = true
+ m[s2] = true
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _ = m[s1]
+ }
+}
+
+type BigKey [3]int64
+
+func BenchmarkBigKeyMap(b *testing.B) {
+ m := make(map[BigKey]bool)
+ k := BigKey{3, 4, 5}
+ m[k] = true
+ for i := 0; i < b.N; i++ {
+ _ = m[k]
+ }
+}
+
+type BigVal [3]int64
+
+func BenchmarkBigValMap(b *testing.B) {
+ m := make(map[BigKey]BigVal)
+ k := BigKey{3, 4, 5}
+ m[k] = BigVal{6, 7, 8}
+ for i := 0; i < b.N; i++ {
+ _ = m[k]
+ }
+}
+
+func BenchmarkSmallKeyMap(b *testing.B) {
+ m := make(map[int16]bool)
+ m[5] = true
+ for i := 0; i < b.N; i++ {
+ _ = m[5]
+ }
+}
+
+func BenchmarkMapPopulate(b *testing.B) {
+ for size := 1; size < 1000000; size *= 10 {
+ b.Run(strconv.Itoa(size), func(b *testing.B) {
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ m := make(map[int]bool)
+ for j := 0; j < size; j++ {
+ m[j] = true
+ }
+ }
+ })
+ }
+}
+
+type ComplexAlgKey struct {
+ a, b, c int64
+ _ int
+ d int32
+ _ int
+ e string
+ _ int
+ f, g, h int64
+}
+
+func BenchmarkComplexAlgMap(b *testing.B) {
+ m := make(map[ComplexAlgKey]bool)
+ var k ComplexAlgKey
+ m[k] = true
+ for i := 0; i < b.N; i++ {
+ _ = m[k]
+ }
+}
+
+func BenchmarkGoMapClear(b *testing.B) {
+ b.Run("Reflexive", func(b *testing.B) {
+ for size := 1; size < 100000; size *= 10 {
+ b.Run(strconv.Itoa(size), func(b *testing.B) {
+ m := make(map[int]int, size)
+ for i := 0; i < b.N; i++ {
+ m[0] = size // Add one element so len(m) != 0 avoiding fast paths.
+ for k := range m {
+ delete(m, k)
+ }
+ }
+ })
+ }
+ })
+ b.Run("NonReflexive", func(b *testing.B) {
+ for size := 1; size < 100000; size *= 10 {
+ b.Run(strconv.Itoa(size), func(b *testing.B) {
+ m := make(map[float64]int, size)
+ for i := 0; i < b.N; i++ {
+ m[1.0] = size // Add one element so len(m) != 0 avoiding fast paths.
+ for k := range m {
+ delete(m, k)
+ }
+ }
+ })
+ }
+ })
+}
+
+func BenchmarkMapStringConversion(b *testing.B) {
+ for _, length := range []int{32, 64} {
+ b.Run(strconv.Itoa(length), func(b *testing.B) {
+ bytes := make([]byte, length)
+ b.Run("simple", func(b *testing.B) {
+ b.ReportAllocs()
+ m := make(map[string]int)
+ m[string(bytes)] = 0
+ for i := 0; i < b.N; i++ {
+ _ = m[string(bytes)]
+ }
+ })
+ b.Run("struct", func(b *testing.B) {
+ b.ReportAllocs()
+ type stringstruct struct{ s string }
+ m := make(map[stringstruct]int)
+ m[stringstruct{string(bytes)}] = 0
+ for i := 0; i < b.N; i++ {
+ _ = m[stringstruct{string(bytes)}]
+ }
+ })
+ b.Run("array", func(b *testing.B) {
+ b.ReportAllocs()
+ type stringarray [1]string
+ m := make(map[stringarray]int)
+ m[stringarray{string(bytes)}] = 0
+ for i := 0; i < b.N; i++ {
+ _ = m[stringarray{string(bytes)}]
+ }
+ })
+ })
+ }
+}
+
+var BoolSink bool
+
+func BenchmarkMapInterfaceString(b *testing.B) {
+ m := map[any]bool{}
+
+ for i := 0; i < 100; i++ {
+ m[fmt.Sprintf("%d", i)] = true
+ }
+
+ key := (any)("A")
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ BoolSink = m[key]
+ }
+}
+func BenchmarkMapInterfacePtr(b *testing.B) {
+ m := map[any]bool{}
+
+ for i := 0; i < 100; i++ {
+ i := i
+ m[&i] = true
+ }
+
+ key := new(int)
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ BoolSink = m[key]
+ }
+}
+
+var (
+ hintLessThan8 = 7
+ hintGreaterThan8 = 32
+)
+
+func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ _ = make(map[int]int, hintLessThan8)
+ }
+}
+
+func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ _ = make(map[int]int, hintGreaterThan8)
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-28 20:50:49 +0000