Source file
src/runtime/map_benchmark_test.go
1
2
3
4
5 package runtime_test
6
7 import (
8 "fmt"
9 "math/rand"
10 "strconv"
11 "strings"
12 "testing"
13 )
14
15 const size = 10
16
17 func BenchmarkHashStringSpeed(b *testing.B) {
18 strings := make([]string, size)
19 for i := 0; i < size; i++ {
20 strings[i] = fmt.Sprintf("string#%d", i)
21 }
22 sum := 0
23 m := make(map[string]int, size)
24 for i := 0; i < size; i++ {
25 m[strings[i]] = 0
26 }
27 idx := 0
28 b.ResetTimer()
29 for i := 0; i < b.N; i++ {
30 sum += m[strings[idx]]
31 idx++
32 if idx == size {
33 idx = 0
34 }
35 }
36 }
37
38 type chunk [17]byte
39
40 func BenchmarkHashBytesSpeed(b *testing.B) {
41
42 var chunks [size]chunk
43
44 for i := 0; i < size; i++ {
45 chunks[i][0] = byte(i)
46 }
47
48 m := make(map[chunk]int, size)
49 for i, c := range chunks {
50 m[c] = i
51 }
52 idx := 0
53 b.ResetTimer()
54 for i := 0; i < b.N; i++ {
55 if m[chunks[idx]] != idx {
56 b.Error("bad map entry for chunk")
57 }
58 idx++
59 if idx == size {
60 idx = 0
61 }
62 }
63 }
64
65 func BenchmarkHashInt32Speed(b *testing.B) {
66 ints := make([]int32, size)
67 for i := 0; i < size; i++ {
68 ints[i] = int32(i)
69 }
70 sum := 0
71 m := make(map[int32]int, size)
72 for i := 0; i < size; i++ {
73 m[ints[i]] = 0
74 }
75 idx := 0
76 b.ResetTimer()
77 for i := 0; i < b.N; i++ {
78 sum += m[ints[idx]]
79 idx++
80 if idx == size {
81 idx = 0
82 }
83 }
84 }
85
86 func BenchmarkHashInt64Speed(b *testing.B) {
87 ints := make([]int64, size)
88 for i := 0; i < size; i++ {
89 ints[i] = int64(i)
90 }
91 sum := 0
92 m := make(map[int64]int, size)
93 for i := 0; i < size; i++ {
94 m[ints[i]] = 0
95 }
96 idx := 0
97 b.ResetTimer()
98 for i := 0; i < b.N; i++ {
99 sum += m[ints[idx]]
100 idx++
101 if idx == size {
102 idx = 0
103 }
104 }
105 }
106 func BenchmarkHashStringArraySpeed(b *testing.B) {
107 stringpairs := make([][2]string, size)
108 for i := 0; i < size; i++ {
109 for j := 0; j < 2; j++ {
110 stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
111 }
112 }
113 sum := 0
114 m := make(map[[2]string]int, size)
115 for i := 0; i < size; i++ {
116 m[stringpairs[i]] = 0
117 }
118 idx := 0
119 b.ResetTimer()
120 for i := 0; i < b.N; i++ {
121 sum += m[stringpairs[idx]]
122 idx++
123 if idx == size {
124 idx = 0
125 }
126 }
127 }
128
129 func BenchmarkMegMap(b *testing.B) {
130 m := make(map[string]bool)
131 for suffix := 'A'; suffix <= 'G'; suffix++ {
132 m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
133 }
134 key := strings.Repeat("X", 1<<20-1) + "k"
135 b.ResetTimer()
136 for i := 0; i < b.N; i++ {
137 _, _ = m[key]
138 }
139 }
140
141 func BenchmarkMegOneMap(b *testing.B) {
142 m := make(map[string]bool)
143 m[strings.Repeat("X", 1<<20)] = true
144 key := strings.Repeat("Y", 1<<20)
145 b.ResetTimer()
146 for i := 0; i < b.N; i++ {
147 _, _ = m[key]
148 }
149 }
150
151 func BenchmarkMegEqMap(b *testing.B) {
152 m := make(map[string]bool)
153 key1 := strings.Repeat("X", 1<<20)
154 key2 := strings.Repeat("X", 1<<20)
155 m[key1] = true
156 b.ResetTimer()
157 for i := 0; i < b.N; i++ {
158 _, _ = m[key2]
159 }
160 }
161
162 func BenchmarkMegEmptyMap(b *testing.B) {
163 m := make(map[string]bool)
164 key := strings.Repeat("X", 1<<20)
165 b.ResetTimer()
166 for i := 0; i < b.N; i++ {
167 _, _ = m[key]
168 }
169 }
170
171 func BenchmarkMegEmptyMapWithInterfaceKey(b *testing.B) {
172 m := make(map[any]bool)
173 key := strings.Repeat("X", 1<<20)
174 b.ResetTimer()
175 for i := 0; i < b.N; i++ {
176 _, _ = m[key]
177 }
178 }
179
180 func BenchmarkSmallStrMap(b *testing.B) {
181 m := make(map[string]bool)
182 for suffix := 'A'; suffix <= 'G'; suffix++ {
183 m[fmt.Sprint(suffix)] = true
184 }
185 key := "k"
186 b.ResetTimer()
187 for i := 0; i < b.N; i++ {
188 _, _ = m[key]
189 }
190 }
191
192 func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
193 func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
194 func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
195 func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
196
197 func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
198 m := make(map[string]bool)
199 for i := 0; i < 8; i++ {
200 m[strings.Repeat("K", i+1)] = true
201 }
202 key := strings.Repeat("K", keySize)
203 b.ResetTimer()
204 for i := 0; i < b.N; i++ {
205 _ = m[key]
206 }
207 }
208
209 func BenchmarkIntMap(b *testing.B) {
210 m := make(map[int]bool)
211 for i := 0; i < 8; i++ {
212 m[i] = true
213 }
214 b.ResetTimer()
215 for i := 0; i < b.N; i++ {
216 _, _ = m[7]
217 }
218 }
219
220 func BenchmarkMapFirst(b *testing.B) {
221 for n := 1; n <= 16; n++ {
222 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
223 m := make(map[int]bool)
224 for i := 0; i < n; i++ {
225 m[i] = true
226 }
227 b.ResetTimer()
228 for i := 0; i < b.N; i++ {
229 _ = m[0]
230 }
231 })
232 }
233 }
234 func BenchmarkMapMid(b *testing.B) {
235 for n := 1; n <= 16; n++ {
236 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
237 m := make(map[int]bool)
238 for i := 0; i < n; i++ {
239 m[i] = true
240 }
241 b.ResetTimer()
242 for i := 0; i < b.N; i++ {
243 _ = m[n>>1]
244 }
245 })
246 }
247 }
248 func BenchmarkMapLast(b *testing.B) {
249 for n := 1; n <= 16; n++ {
250 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
251 m := make(map[int]bool)
252 for i := 0; i < n; i++ {
253 m[i] = true
254 }
255 b.ResetTimer()
256 for i := 0; i < b.N; i++ {
257 _ = m[n-1]
258 }
259 })
260 }
261 }
262
263 func BenchmarkMapCycle(b *testing.B) {
264
265
266
267 const N = 3127
268 p := rand.New(rand.NewSource(1)).Perm(N)
269 m := map[int]int{}
270 for i := 0; i < N; i++ {
271 m[i] = p[i]
272 }
273 b.ResetTimer()
274 j := 0
275 for i := 0; i < b.N; i++ {
276 j = m[j]
277 }
278 sink = uint64(j)
279 }
280
281
282 func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
283 m := make(map[string]bool)
284
285 for i := 0; i < 64; i++ {
286 m[fmt.Sprintf("some key %d", i)] = true
287 }
288 base := strings.Repeat("x", lookupKeySize-1)
289 key1 := base + "1"
290 key2 := base + "2"
291 b.ResetTimer()
292 for i := 0; i < b.N/4; i++ {
293 _ = m[key1]
294 _ = m[key1]
295 _ = m[key2]
296 _ = m[key2]
297 }
298 }
299
300 func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
301 func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
302
303 func BenchmarkMakeMap(b *testing.B) {
304 b.Run("[Byte]Byte", func(b *testing.B) {
305 var m map[byte]byte
306 for i := 0; i < b.N; i++ {
307 m = make(map[byte]byte, 10)
308 }
309 hugeSink = m
310 })
311 b.Run("[Int]Int", func(b *testing.B) {
312 var m map[int]int
313 for i := 0; i < b.N; i++ {
314 m = make(map[int]int, 10)
315 }
316 hugeSink = m
317 })
318 }
319
320 func BenchmarkNewEmptyMap(b *testing.B) {
321 b.ReportAllocs()
322 for i := 0; i < b.N; i++ {
323 _ = make(map[int]int)
324 }
325 }
326
327 func BenchmarkNewSmallMap(b *testing.B) {
328 b.ReportAllocs()
329 for i := 0; i < b.N; i++ {
330 m := make(map[int]int)
331 m[0] = 0
332 m[1] = 1
333 }
334 }
335
336 func BenchmarkMapIter(b *testing.B) {
337 m := make(map[int]bool)
338 for i := 0; i < 8; i++ {
339 m[i] = true
340 }
341 b.ResetTimer()
342 for i := 0; i < b.N; i++ {
343 for range m {
344 }
345 }
346 }
347
348 func BenchmarkMapIterEmpty(b *testing.B) {
349 m := make(map[int]bool)
350 b.ResetTimer()
351 for i := 0; i < b.N; i++ {
352 for range m {
353 }
354 }
355 }
356
357 func BenchmarkSameLengthMap(b *testing.B) {
358
359
360 m := make(map[string]bool)
361 s1 := "foo" + strings.Repeat("-", 100) + "bar"
362 s2 := "goo" + strings.Repeat("-", 100) + "ber"
363 m[s1] = true
364 m[s2] = true
365 b.ResetTimer()
366 for i := 0; i < b.N; i++ {
367 _ = m[s1]
368 }
369 }
370
371 type BigKey [3]int64
372
373 func BenchmarkBigKeyMap(b *testing.B) {
374 m := make(map[BigKey]bool)
375 k := BigKey{3, 4, 5}
376 m[k] = true
377 for i := 0; i < b.N; i++ {
378 _ = m[k]
379 }
380 }
381
382 type BigVal [3]int64
383
384 func BenchmarkBigValMap(b *testing.B) {
385 m := make(map[BigKey]BigVal)
386 k := BigKey{3, 4, 5}
387 m[k] = BigVal{6, 7, 8}
388 for i := 0; i < b.N; i++ {
389 _ = m[k]
390 }
391 }
392
393 func BenchmarkSmallKeyMap(b *testing.B) {
394 m := make(map[int16]bool)
395 m[5] = true
396 for i := 0; i < b.N; i++ {
397 _ = m[5]
398 }
399 }
400
401 func BenchmarkMapPopulate(b *testing.B) {
402 for size := 1; size < 1000000; size *= 10 {
403 b.Run(strconv.Itoa(size), func(b *testing.B) {
404 b.ReportAllocs()
405 for i := 0; i < b.N; i++ {
406 m := make(map[int]bool)
407 for j := 0; j < size; j++ {
408 m[j] = true
409 }
410 }
411 })
412 }
413 }
414
415 type ComplexAlgKey struct {
416 a, b, c int64
417 _ int
418 d int32
419 _ int
420 e string
421 _ int
422 f, g, h int64
423 }
424
425 func BenchmarkComplexAlgMap(b *testing.B) {
426 m := make(map[ComplexAlgKey]bool)
427 var k ComplexAlgKey
428 m[k] = true
429 for i := 0; i < b.N; i++ {
430 _ = m[k]
431 }
432 }
433
434 func BenchmarkGoMapClear(b *testing.B) {
435 b.Run("Reflexive", func(b *testing.B) {
436 for size := 1; size < 100000; size *= 10 {
437 b.Run(strconv.Itoa(size), func(b *testing.B) {
438 m := make(map[int]int, size)
439 for i := 0; i < b.N; i++ {
440 m[0] = size
441 clear(m)
442 }
443 })
444 }
445 })
446 b.Run("NonReflexive", func(b *testing.B) {
447 for size := 1; size < 100000; size *= 10 {
448 b.Run(strconv.Itoa(size), func(b *testing.B) {
449 m := make(map[float64]int, size)
450 for i := 0; i < b.N; i++ {
451 m[1.0] = size
452 clear(m)
453 }
454 })
455 }
456 })
457 }
458
459 func BenchmarkMapStringConversion(b *testing.B) {
460 for _, length := range []int{32, 64} {
461 b.Run(strconv.Itoa(length), func(b *testing.B) {
462 bytes := make([]byte, length)
463 b.Run("simple", func(b *testing.B) {
464 b.ReportAllocs()
465 m := make(map[string]int)
466 m[string(bytes)] = 0
467 for i := 0; i < b.N; i++ {
468 _ = m[string(bytes)]
469 }
470 })
471 b.Run("struct", func(b *testing.B) {
472 b.ReportAllocs()
473 type stringstruct struct{ s string }
474 m := make(map[stringstruct]int)
475 m[stringstruct{string(bytes)}] = 0
476 for i := 0; i < b.N; i++ {
477 _ = m[stringstruct{string(bytes)}]
478 }
479 })
480 b.Run("array", func(b *testing.B) {
481 b.ReportAllocs()
482 type stringarray [1]string
483 m := make(map[stringarray]int)
484 m[stringarray{string(bytes)}] = 0
485 for i := 0; i < b.N; i++ {
486 _ = m[stringarray{string(bytes)}]
487 }
488 })
489 })
490 }
491 }
492
493 var BoolSink bool
494
495 func BenchmarkMapInterfaceString(b *testing.B) {
496 m := map[any]bool{}
497
498 for i := 0; i < 100; i++ {
499 m[fmt.Sprintf("%d", i)] = true
500 }
501
502 key := (any)("A")
503 b.ResetTimer()
504 for i := 0; i < b.N; i++ {
505 BoolSink = m[key]
506 }
507 }
508 func BenchmarkMapInterfacePtr(b *testing.B) {
509 m := map[any]bool{}
510
511 for i := 0; i < 100; i++ {
512 i := i
513 m[&i] = true
514 }
515
516 key := new(int)
517 b.ResetTimer()
518 for i := 0; i < b.N; i++ {
519 BoolSink = m[key]
520 }
521 }
522
523 var (
524 hintLessThan8 = 7
525 hintGreaterThan8 = 32
526 )
527
528 func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
529 b.ReportAllocs()
530 for i := 0; i < b.N; i++ {
531 _ = make(map[int]int, hintLessThan8)
532 }
533 }
534
535 func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
536 b.ReportAllocs()
537 for i := 0; i < b.N; i++ {
538 _ = make(map[int]int, hintGreaterThan8)
539 }
540 }
541
View as plain text