blob: d0becc9ddb859654e6d524143ef5e8b8b6114065 [file] [log] [blame]
// 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[interface{}]bool{}
for i := 0; i < 100; i++ {
m[fmt.Sprintf("%d", i)] = true
}
key := (interface{})("A")
b.ResetTimer()
for i := 0; i < b.N; i++ {
BoolSink = m[key]
}
}
func BenchmarkMapInterfacePtr(b *testing.B) {
m := map[interface{}]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)
}
}