1// Copyright 2013 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4package runtime_test
5
6import (
7	"fmt"
8	"strings"
9	"testing"
10)
11
12const size = 10
13
14func BenchmarkHashStringSpeed(b *testing.B) {
15	strings := make([]string, size)
16	for i := 0; i < size; i++ {
17		strings[i] = fmt.Sprintf("string#%d", i)
18	}
19	sum := 0
20	m := make(map[string]int, size)
21	for i := 0; i < size; i++ {
22		m[strings[i]] = 0
23	}
24	idx := 0
25	b.ResetTimer()
26	for i := 0; i < b.N; i++ {
27		sum += m[strings[idx]]
28		idx++
29		if idx == size {
30			idx = 0
31		}
32	}
33}
34
35type chunk [17]byte
36
37func BenchmarkHashBytesSpeed(b *testing.B) {
38	// a bunch of chunks, each with a different alignment mod 16
39	var chunks [size]chunk
40	// initialize each to a different value
41	for i := 0; i < size; i++ {
42		chunks[i][0] = byte(i)
43	}
44	// put into a map
45	m := make(map[chunk]int, size)
46	for i, c := range chunks {
47		m[c] = i
48	}
49	idx := 0
50	b.ResetTimer()
51	for i := 0; i < b.N; i++ {
52		if m[chunks[idx]] != idx {
53			b.Error("bad map entry for chunk")
54		}
55		idx++
56		if idx == size {
57			idx = 0
58		}
59	}
60}
61
62func BenchmarkHashInt32Speed(b *testing.B) {
63	ints := make([]int32, size)
64	for i := 0; i < size; i++ {
65		ints[i] = int32(i)
66	}
67	sum := 0
68	m := make(map[int32]int, size)
69	for i := 0; i < size; i++ {
70		m[ints[i]] = 0
71	}
72	idx := 0
73	b.ResetTimer()
74	for i := 0; i < b.N; i++ {
75		sum += m[ints[idx]]
76		idx++
77		if idx == size {
78			idx = 0
79		}
80	}
81}
82
83func BenchmarkHashInt64Speed(b *testing.B) {
84	ints := make([]int64, size)
85	for i := 0; i < size; i++ {
86		ints[i] = int64(i)
87	}
88	sum := 0
89	m := make(map[int64]int, size)
90	for i := 0; i < size; i++ {
91		m[ints[i]] = 0
92	}
93	idx := 0
94	b.ResetTimer()
95	for i := 0; i < b.N; i++ {
96		sum += m[ints[idx]]
97		idx++
98		if idx == size {
99			idx = 0
100		}
101	}
102}
103func BenchmarkHashStringArraySpeed(b *testing.B) {
104	stringpairs := make([][2]string, size)
105	for i := 0; i < size; i++ {
106		for j := 0; j < 2; j++ {
107			stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
108		}
109	}
110	sum := 0
111	m := make(map[[2]string]int, size)
112	for i := 0; i < size; i++ {
113		m[stringpairs[i]] = 0
114	}
115	idx := 0
116	b.ResetTimer()
117	for i := 0; i < b.N; i++ {
118		sum += m[stringpairs[idx]]
119		idx++
120		if idx == size {
121			idx = 0
122		}
123	}
124}
125
126func BenchmarkMegMap(b *testing.B) {
127	m := make(map[string]bool)
128	for suffix := 'A'; suffix <= 'G'; suffix++ {
129		m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
130	}
131	key := strings.Repeat("X", 1<<20-1) + "k"
132	b.ResetTimer()
133	for i := 0; i < b.N; i++ {
134		_, _ = m[key]
135	}
136}
137
138func BenchmarkMegOneMap(b *testing.B) {
139	m := make(map[string]bool)
140	m[strings.Repeat("X", 1<<20)] = true
141	key := strings.Repeat("Y", 1<<20)
142	b.ResetTimer()
143	for i := 0; i < b.N; i++ {
144		_, _ = m[key]
145	}
146}
147
148func BenchmarkMegEqMap(b *testing.B) {
149	m := make(map[string]bool)
150	key1 := strings.Repeat("X", 1<<20)
151	key2 := strings.Repeat("X", 1<<20) // equal but different instance
152	m[key1] = true
153	b.ResetTimer()
154	for i := 0; i < b.N; i++ {
155		_, _ = m[key2]
156	}
157}
158
159func BenchmarkMegEmptyMap(b *testing.B) {
160	m := make(map[string]bool)
161	key := strings.Repeat("X", 1<<20)
162	b.ResetTimer()
163	for i := 0; i < b.N; i++ {
164		_, _ = m[key]
165	}
166}
167
168func BenchmarkSmallStrMap(b *testing.B) {
169	m := make(map[string]bool)
170	for suffix := 'A'; suffix <= 'G'; suffix++ {
171		m[fmt.Sprint(suffix)] = true
172	}
173	key := "k"
174	b.ResetTimer()
175	for i := 0; i < b.N; i++ {
176		_, _ = m[key]
177	}
178}
179
180func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
181func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
182func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
183func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
184
185func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
186	m := make(map[string]bool)
187	for i := 0; i < 8; i++ {
188		m[strings.Repeat("K", i+1)] = true
189	}
190	key := strings.Repeat("K", keySize)
191	b.ResetTimer()
192	for i := 0; i < b.N; i++ {
193		_ = m[key]
194	}
195}
196
197func BenchmarkIntMap(b *testing.B) {
198	m := make(map[int]bool)
199	for i := 0; i < 8; i++ {
200		m[i] = true
201	}
202	b.ResetTimer()
203	for i := 0; i < b.N; i++ {
204		_, _ = m[7]
205	}
206}
207
208// Accessing the same keys in a row.
209func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
210	m := make(map[string]bool)
211	// At least bigger than a single bucket:
212	for i := 0; i < 64; i++ {
213		m[fmt.Sprintf("some key %d", i)] = true
214	}
215	base := strings.Repeat("x", lookupKeySize-1)
216	key1 := base + "1"
217	key2 := base + "2"
218	b.ResetTimer()
219	for i := 0; i < b.N/4; i++ {
220		_ = m[key1]
221		_ = m[key1]
222		_ = m[key2]
223		_ = m[key2]
224	}
225}
226
227func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
228func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
229
230func BenchmarkNewEmptyMap(b *testing.B) {
231	b.ReportAllocs()
232	for i := 0; i < b.N; i++ {
233		_ = make(map[int]int)
234	}
235}
236
237func BenchmarkMapIter(b *testing.B) {
238	m := make(map[int]bool)
239	for i := 0; i < 8; i++ {
240		m[i] = true
241	}
242	b.ResetTimer()
243	for i := 0; i < b.N; i++ {
244		for _, _ = range m {
245		}
246	}
247}
248
249func BenchmarkMapIterEmpty(b *testing.B) {
250	m := make(map[int]bool)
251	b.ResetTimer()
252	for i := 0; i < b.N; i++ {
253		for _, _ = range m {
254		}
255	}
256}
257
258func BenchmarkSameLengthMap(b *testing.B) {
259	// long strings, same length, differ in first few
260	// and last few bytes.
261	m := make(map[string]bool)
262	s1 := "foo" + strings.Repeat("-", 100) + "bar"
263	s2 := "goo" + strings.Repeat("-", 100) + "ber"
264	m[s1] = true
265	m[s2] = true
266	b.ResetTimer()
267	for i := 0; i < b.N; i++ {
268		_ = m[s1]
269	}
270}
271