Source file
src/runtime/map_benchmark_test.go
1
2
3
4
5 package runtime_test
6
7 import (
8 "encoding/binary"
9 "flag"
10 "fmt"
11 "math/rand"
12 "runtime"
13 "slices"
14 "strconv"
15 "strings"
16 "testing"
17 "unsafe"
18 )
19
20 var mapbench = flag.Bool("mapbench", false, "enable the full set of map benchmark variants")
21
22 const size = 10
23
24 func BenchmarkHashStringSpeed(b *testing.B) {
25 strings := make([]string, size)
26 for i := 0; i < size; i++ {
27 strings[i] = fmt.Sprintf("string#%d", i)
28 }
29 sum := 0
30 m := make(map[string]int, size)
31 for i := 0; i < size; i++ {
32 m[strings[i]] = 0
33 }
34 idx := 0
35 b.ResetTimer()
36 for i := 0; i < b.N; i++ {
37 sum += m[strings[idx]]
38 idx++
39 if idx == size {
40 idx = 0
41 }
42 }
43 }
44
45 type chunk [17]byte
46
47 func BenchmarkHashBytesSpeed(b *testing.B) {
48
49 var chunks [size]chunk
50
51 for i := 0; i < size; i++ {
52 chunks[i][0] = byte(i)
53 }
54
55 m := make(map[chunk]int, size)
56 for i, c := range chunks {
57 m[c] = i
58 }
59 idx := 0
60 b.ResetTimer()
61 for i := 0; i < b.N; i++ {
62 if m[chunks[idx]] != idx {
63 b.Error("bad map entry for chunk")
64 }
65 idx++
66 if idx == size {
67 idx = 0
68 }
69 }
70 }
71
72 func BenchmarkHashInt32Speed(b *testing.B) {
73 ints := make([]int32, size)
74 for i := 0; i < size; i++ {
75 ints[i] = int32(i)
76 }
77 sum := 0
78 m := make(map[int32]int, size)
79 for i := 0; i < size; i++ {
80 m[ints[i]] = 0
81 }
82 idx := 0
83 b.ResetTimer()
84 for i := 0; i < b.N; i++ {
85 sum += m[ints[idx]]
86 idx++
87 if idx == size {
88 idx = 0
89 }
90 }
91 }
92
93 func BenchmarkHashInt64Speed(b *testing.B) {
94 ints := make([]int64, size)
95 for i := 0; i < size; i++ {
96 ints[i] = int64(i)
97 }
98 sum := 0
99 m := make(map[int64]int, size)
100 for i := 0; i < size; i++ {
101 m[ints[i]] = 0
102 }
103 idx := 0
104 b.ResetTimer()
105 for i := 0; i < b.N; i++ {
106 sum += m[ints[idx]]
107 idx++
108 if idx == size {
109 idx = 0
110 }
111 }
112 }
113 func BenchmarkHashStringArraySpeed(b *testing.B) {
114 stringpairs := make([][2]string, size)
115 for i := 0; i < size; i++ {
116 for j := 0; j < 2; j++ {
117 stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
118 }
119 }
120 sum := 0
121 m := make(map[[2]string]int, size)
122 for i := 0; i < size; i++ {
123 m[stringpairs[i]] = 0
124 }
125 idx := 0
126 b.ResetTimer()
127 for i := 0; i < b.N; i++ {
128 sum += m[stringpairs[idx]]
129 idx++
130 if idx == size {
131 idx = 0
132 }
133 }
134 }
135
136 func BenchmarkMegMap(b *testing.B) {
137 m := make(map[string]bool)
138 for suffix := 'A'; suffix <= 'G'; suffix++ {
139 m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
140 }
141 key := strings.Repeat("X", 1<<20-1) + "k"
142 b.ResetTimer()
143 for i := 0; i < b.N; i++ {
144 _, _ = m[key]
145 }
146 }
147
148 func BenchmarkMegOneMap(b *testing.B) {
149 m := make(map[string]bool)
150 m[strings.Repeat("X", 1<<20)] = true
151 key := strings.Repeat("Y", 1<<20)
152 b.ResetTimer()
153 for i := 0; i < b.N; i++ {
154 _, _ = m[key]
155 }
156 }
157
158 func BenchmarkMegEqMap(b *testing.B) {
159 m := make(map[string]bool)
160 key1 := strings.Repeat("X", 1<<20)
161 key2 := strings.Repeat("X", 1<<20)
162 m[key1] = true
163 b.ResetTimer()
164 for i := 0; i < b.N; i++ {
165 _, _ = m[key2]
166 }
167 }
168
169 func BenchmarkMegEmptyMap(b *testing.B) {
170 m := make(map[string]bool)
171 key := strings.Repeat("X", 1<<20)
172 b.ResetTimer()
173 for i := 0; i < b.N; i++ {
174 _, _ = m[key]
175 }
176 }
177
178 func BenchmarkMegEmptyMapWithInterfaceKey(b *testing.B) {
179 m := make(map[any]bool)
180 key := strings.Repeat("X", 1<<20)
181 b.ResetTimer()
182 for i := 0; i < b.N; i++ {
183 _, _ = m[key]
184 }
185 }
186
187 func BenchmarkSmallStrMap(b *testing.B) {
188 m := make(map[string]bool)
189 for suffix := 'A'; suffix <= 'G'; suffix++ {
190 m[fmt.Sprint(suffix)] = true
191 }
192 key := "k"
193 b.ResetTimer()
194 for i := 0; i < b.N; i++ {
195 _, _ = m[key]
196 }
197 }
198
199 func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
200 func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
201 func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
202 func BenchmarkMapStringKeysEight_128(b *testing.B) { benchmarkMapStringKeysEight(b, 128) }
203 func BenchmarkMapStringKeysEight_256(b *testing.B) { benchmarkMapStringKeysEight(b, 256) }
204 func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
205
206 func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
207 m := make(map[string]bool)
208 for i := 0; i < 8; i++ {
209 m[strings.Repeat("K", i+1)] = true
210 }
211 key := strings.Repeat("K", keySize)
212 b.ResetTimer()
213 for i := 0; i < b.N; i++ {
214 _ = m[key]
215 }
216 }
217
218 func BenchmarkMapFirst(b *testing.B) {
219 for n := 1; n <= 16; n++ {
220 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
221 m := make(map[int]bool)
222 for i := 0; i < n; i++ {
223 m[i] = true
224 }
225 b.ResetTimer()
226 for i := 0; i < b.N; i++ {
227 _ = m[0]
228 }
229 })
230 }
231 }
232 func BenchmarkMapMid(b *testing.B) {
233 for n := 1; n <= 16; n++ {
234 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
235 m := make(map[int]bool)
236 for i := 0; i < n; i++ {
237 m[i] = true
238 }
239 b.ResetTimer()
240 for i := 0; i < b.N; i++ {
241 _ = m[n>>1]
242 }
243 })
244 }
245 }
246 func BenchmarkMapLast(b *testing.B) {
247 for n := 1; n <= 16; n++ {
248 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
249 m := make(map[int]bool)
250 for i := 0; i < n; i++ {
251 m[i] = true
252 }
253 b.ResetTimer()
254 for i := 0; i < b.N; i++ {
255 _ = m[n-1]
256 }
257 })
258 }
259 }
260
261 func cyclicPermutation(n int) []int {
262
263 p := rand.New(rand.NewSource(1)).Perm(n)
264 inc := make([]int, n)
265 pInv := make([]int, n)
266 for i := 0; i < n; i++ {
267 inc[i] = (i + 1) % n
268 pInv[p[i]] = i
269 }
270 res := make([]int, n)
271 for i := 0; i < n; i++ {
272 res[i] = pInv[inc[p[i]]]
273 }
274
275
276 j := 0
277 for i := 0; i < n-1; i++ {
278 j = res[j]
279 if j == 0 {
280 panic("got back to 0 too early")
281 }
282 }
283 j = res[j]
284 if j != 0 {
285 panic("didn't get back to 0")
286 }
287 return res
288 }
289
290 func BenchmarkMapCycle(b *testing.B) {
291
292
293
294 const N = 3127
295 p := cyclicPermutation(N)
296 m := map[int]int{}
297 for i := 0; i < N; i++ {
298 m[i] = p[i]
299 }
300 b.ResetTimer()
301 j := 0
302 for i := 0; i < b.N; i++ {
303 j = m[j]
304 }
305 sink = uint64(j)
306 }
307
308
309 func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
310 m := make(map[string]bool)
311
312 for i := 0; i < 64; i++ {
313 m[fmt.Sprintf("some key %d", i)] = true
314 }
315 base := strings.Repeat("x", lookupKeySize-1)
316 key1 := base + "1"
317 key2 := base + "2"
318 b.ResetTimer()
319 for i := 0; i < b.N/4; i++ {
320 _ = m[key1]
321 _ = m[key1]
322 _ = m[key2]
323 _ = m[key2]
324 }
325 }
326
327 func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
328 func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
329
330 func BenchmarkMakeMap(b *testing.B) {
331 b.Run("[Byte]Byte", func(b *testing.B) {
332 var m map[byte]byte
333 for i := 0; i < b.N; i++ {
334 m = make(map[byte]byte, 10)
335 }
336 hugeSink = m
337 })
338 b.Run("[Int]Int", func(b *testing.B) {
339 var m map[int]int
340 for i := 0; i < b.N; i++ {
341 m = make(map[int]int, 10)
342 }
343 hugeSink = m
344 })
345 }
346
347 func BenchmarkNewEmptyMap(b *testing.B) {
348 b.ReportAllocs()
349 for i := 0; i < b.N; i++ {
350 _ = make(map[int]int)
351 }
352 }
353
354 func BenchmarkNewSmallMap(b *testing.B) {
355 b.ReportAllocs()
356 for i := 0; i < b.N; i++ {
357 m := make(map[int]int)
358 m[0] = 0
359 m[1] = 1
360 }
361 }
362
363 func BenchmarkSameLengthMap(b *testing.B) {
364
365
366 m := make(map[string]bool)
367 s1 := "foo" + strings.Repeat("-", 100) + "bar"
368 s2 := "goo" + strings.Repeat("-", 100) + "ber"
369 m[s1] = true
370 m[s2] = true
371 b.ResetTimer()
372 for i := 0; i < b.N; i++ {
373 _ = m[s1]
374 }
375 }
376
377 func BenchmarkSmallKeyMap(b *testing.B) {
378 m := make(map[int16]bool)
379 m[5] = true
380 for i := 0; i < b.N; i++ {
381 _ = m[5]
382 }
383 }
384
385 func BenchmarkMapPopulate(b *testing.B) {
386 for size := 1; size < 1000000; size *= 10 {
387 b.Run(strconv.Itoa(size), func(b *testing.B) {
388 b.ReportAllocs()
389 for i := 0; i < b.N; i++ {
390 m := make(map[int]bool)
391 for j := 0; j < size; j++ {
392 m[j] = true
393 }
394 }
395 })
396 }
397 }
398
399 type ComplexAlgKey struct {
400 a, b, c int64
401 _ int
402 d int32
403 _ int
404 e string
405 _ int
406 f, g, h int64
407 }
408
409 func BenchmarkComplexAlgMap(b *testing.B) {
410 m := make(map[ComplexAlgKey]bool)
411 var k ComplexAlgKey
412 m[k] = true
413 for i := 0; i < b.N; i++ {
414 _ = m[k]
415 }
416 }
417
418 func BenchmarkGoMapClear(b *testing.B) {
419 b.Run("Reflexive", func(b *testing.B) {
420 for size := 1; size < 100000; size *= 10 {
421 b.Run(strconv.Itoa(size), func(b *testing.B) {
422 m := make(map[int]int, size)
423 for i := 0; i < b.N; i++ {
424 m[0] = size
425 clear(m)
426 }
427 })
428 }
429 })
430 b.Run("NonReflexive", func(b *testing.B) {
431 for size := 1; size < 100000; size *= 10 {
432 b.Run(strconv.Itoa(size), func(b *testing.B) {
433 m := make(map[float64]int, size)
434 for i := 0; i < b.N; i++ {
435 m[1.0] = size
436 clear(m)
437 }
438 })
439 }
440 })
441 }
442
443 func BenchmarkMapStringConversion(b *testing.B) {
444 for _, length := range []int{32, 64} {
445 b.Run(strconv.Itoa(length), func(b *testing.B) {
446 bytes := make([]byte, length)
447 b.Run("simple", func(b *testing.B) {
448 b.ReportAllocs()
449 m := make(map[string]int)
450 m[string(bytes)] = 0
451 for i := 0; i < b.N; i++ {
452 _ = m[string(bytes)]
453 }
454 })
455 b.Run("struct", func(b *testing.B) {
456 b.ReportAllocs()
457 type stringstruct struct{ s string }
458 m := make(map[stringstruct]int)
459 m[stringstruct{string(bytes)}] = 0
460 for i := 0; i < b.N; i++ {
461 _ = m[stringstruct{string(bytes)}]
462 }
463 })
464 b.Run("array", func(b *testing.B) {
465 b.ReportAllocs()
466 type stringarray [1]string
467 m := make(map[stringarray]int)
468 m[stringarray{string(bytes)}] = 0
469 for i := 0; i < b.N; i++ {
470 _ = m[stringarray{string(bytes)}]
471 }
472 })
473 })
474 }
475 }
476
477 var BoolSink bool
478
479 func BenchmarkMapInterfaceString(b *testing.B) {
480 m := map[any]bool{}
481
482 for i := 0; i < 100; i++ {
483 m[fmt.Sprintf("%d", i)] = true
484 }
485
486 key := (any)("A")
487 b.ResetTimer()
488 for i := 0; i < b.N; i++ {
489 BoolSink = m[key]
490 }
491 }
492 func BenchmarkMapInterfacePtr(b *testing.B) {
493 m := map[any]bool{}
494
495 for i := 0; i < 100; i++ {
496 i := i
497 m[&i] = true
498 }
499
500 key := new(int)
501 b.ResetTimer()
502 for i := 0; i < b.N; i++ {
503 BoolSink = m[key]
504 }
505 }
506
507 var (
508 hintLessThan8 = 7
509 hintGreaterThan8 = 32
510 )
511
512 func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
513 b.ReportAllocs()
514 for i := 0; i < b.N; i++ {
515 _ = make(map[int]int, hintLessThan8)
516 }
517 }
518
519 func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
520 b.ReportAllocs()
521 for i := 0; i < b.N; i++ {
522 _ = make(map[int]int, hintGreaterThan8)
523 }
524 }
525
526 func benchSizes(f func(b *testing.B, n int)) func(*testing.B) {
527 var cases = []int{
528 0,
529 6,
530 12,
531 18,
532 24,
533 30,
534 64,
535 128,
536 256,
537 512,
538 1024,
539 2048,
540 4096,
541 8192,
542 1 << 16,
543 1 << 18,
544 1 << 20,
545 1 << 22,
546 }
547
548
549
550
551
552
553 byDefault := map[int]bool{
554 6: true,
555 64: true,
556 1 << 16: true,
557 }
558
559 return func(b *testing.B) {
560 for _, n := range cases {
561 b.Run("len="+strconv.Itoa(n), func(b *testing.B) {
562 if !*mapbench && !byDefault[n] {
563 b.Skip("Skipped because -mapbench=false")
564 }
565
566 f(b, n)
567 })
568 }
569 }
570 }
571 func smallBenchSizes(f func(b *testing.B, n int)) func(*testing.B) {
572 return func(b *testing.B) {
573 for n := 1; n <= 8; n++ {
574 b.Run("len="+strconv.Itoa(n), func(b *testing.B) {
575 f(b, n)
576 })
577 }
578 }
579 }
580
581
582 type smallType [16]byte
583
584
585 type mediumType [1 << 9]byte
586
587
588 type bigType [1 << 12]byte
589
590 type mapBenchmarkKeyType interface {
591 int32 | int64 | string | smallType | mediumType | bigType | *int32
592 }
593
594 type mapBenchmarkElemType interface {
595 mapBenchmarkKeyType | []int32
596 }
597
598 func genIntValues[T int | int32 | int64](start, end int) []T {
599 vals := make([]T, 0, end-start)
600 for i := start; i < end; i++ {
601 vals = append(vals, T(i))
602 }
603 return vals
604 }
605
606 func genStringValues(start, end int) []string {
607 vals := make([]string, 0, end-start)
608 for i := start; i < end; i++ {
609 vals = append(vals, strconv.Itoa(i))
610 }
611 return vals
612 }
613
614 func genSmallValues(start, end int) []smallType {
615 vals := make([]smallType, 0, end-start)
616 for i := start; i < end; i++ {
617 var v smallType
618 binary.NativeEndian.PutUint64(v[:], uint64(i))
619 vals = append(vals, v)
620 }
621 return vals
622 }
623
624 func genMediumValues(start, end int) []mediumType {
625 vals := make([]mediumType, 0, end-start)
626 for i := start; i < end; i++ {
627 var v mediumType
628 binary.NativeEndian.PutUint64(v[:], uint64(i))
629 vals = append(vals, v)
630 }
631 return vals
632 }
633
634 func genBigValues(start, end int) []bigType {
635 vals := make([]bigType, 0, end-start)
636 for i := start; i < end; i++ {
637 var v bigType
638 binary.NativeEndian.PutUint64(v[:], uint64(i))
639 vals = append(vals, v)
640 }
641 return vals
642 }
643
644 func genPtrValues[T any](start, end int) []*T {
645
646
647 vals := make([]*T, 0, end-start)
648 for i := start; i < end; i++ {
649 v := new(T)
650 vals = append(vals, v)
651 }
652 return vals
653 }
654
655 func genIntSliceValues[T int | int32 | int64](start, end int) [][]T {
656 vals := make([][]T, 0, end-start)
657 for i := start; i < end; i++ {
658 vals = append(vals, []T{T(i)})
659 }
660 return vals
661 }
662
663 func genValues[T mapBenchmarkElemType](start, end int) []T {
664 var t T
665 switch any(t).(type) {
666 case int32:
667 return any(genIntValues[int32](start, end)).([]T)
668 case int64:
669 return any(genIntValues[int64](start, end)).([]T)
670 case string:
671 return any(genStringValues(start, end)).([]T)
672 case smallType:
673 return any(genSmallValues(start, end)).([]T)
674 case mediumType:
675 return any(genMediumValues(start, end)).([]T)
676 case bigType:
677 return any(genBigValues(start, end)).([]T)
678 case *int32:
679 return any(genPtrValues[int32](start, end)).([]T)
680 case []int32:
681 return any(genIntSliceValues[int32](start, end)).([]T)
682 default:
683 panic("unreachable")
684 }
685 }
686
687
688
689
690 func newSink[T mapBenchmarkElemType]() *T {
691 return new(T)
692 }
693
694
695 func fillMap[K mapBenchmarkKeyType, E mapBenchmarkElemType](keys []K, elems []E) map[K]E {
696 m := make(map[K]E, len(keys))
697 for i := range keys {
698 m[keys[i]] = elems[i]
699 }
700 return m
701 }
702
703 func iterCount(b *testing.B, n int) int {
704
705
706
707
708
709 if n == 0 {
710 return b.N
711 }
712 return b.N / n
713 }
714
715 func checkAllocSize[K, E any](b *testing.B, n int) {
716 var k K
717 size := uint64(n) * uint64(unsafe.Sizeof(k))
718 var e E
719 size += uint64(n) * uint64(unsafe.Sizeof(e))
720
721 if size >= 1<<30 {
722 b.Skipf("Total key+elem size %d exceeds 1GiB", size)
723 }
724 }
725
726 func benchmarkMapIter[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
727 checkAllocSize[K, E](b, n)
728 k := genValues[K](0, n)
729 e := genValues[E](0, n)
730 m := fillMap(k, e)
731 iterations := iterCount(b, n)
732 sinkK := newSink[K]()
733 sinkE := newSink[E]()
734 b.ResetTimer()
735
736 for i := 0; i < iterations; i++ {
737 for k, e := range m {
738 *sinkK = k
739 *sinkE = e
740 }
741 }
742 }
743
744 func BenchmarkMapIter(b *testing.B) {
745 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapIter[int32, int32]))
746 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapIter[int64, int64]))
747 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapIter[string, string]))
748 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapIter[smallType, int32]))
749 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapIter[mediumType, int32]))
750 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapIter[bigType, int32]))
751 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapIter[bigType, bigType]))
752 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapIter[int32, bigType]))
753 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapIter[*int32, int32]))
754 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapIter[int32, *int32]))
755 }
756
757 func benchmarkMapIterLowLoad[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
758
759 k := genValues[K](0, 1)
760 e := genValues[E](0, 1)
761
762 m := make(map[K]E, n)
763 for i := range k {
764 m[k[i]] = e[i]
765 }
766
767 iterations := iterCount(b, n)
768 sinkK := newSink[K]()
769 sinkE := newSink[E]()
770 b.ResetTimer()
771
772 for i := 0; i < iterations; i++ {
773 for k, e := range m {
774 *sinkK = k
775 *sinkE = e
776 }
777 }
778 }
779
780 func BenchmarkMapIterLowLoad(b *testing.B) {
781 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapIterLowLoad[int32, int32]))
782 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapIterLowLoad[int64, int64]))
783 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapIterLowLoad[string, string]))
784 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[smallType, int32]))
785 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[mediumType, int32]))
786 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[bigType, int32]))
787 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapIterLowLoad[bigType, bigType]))
788 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapIterLowLoad[int32, bigType]))
789 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapIterLowLoad[*int32, int32]))
790 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapIterLowLoad[int32, *int32]))
791 }
792
793 func benchmarkMapAccessHit[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
794 if n == 0 {
795 b.Skip("can't access empty map")
796 }
797 checkAllocSize[K, E](b, n)
798 k := genValues[K](0, n)
799 e := genValues[E](0, n)
800 m := fillMap(k, e)
801 sink := newSink[E]()
802 b.ResetTimer()
803
804 for i := 0; i < b.N; i++ {
805 *sink = m[k[i%n]]
806 }
807 }
808
809 func BenchmarkMapAccessHit(b *testing.B) {
810 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAccessHit[int32, int32]))
811 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAccessHit[int64, int64]))
812 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAccessHit[string, string]))
813 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAccessHit[smallType, int32]))
814 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAccessHit[mediumType, int32]))
815 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAccessHit[bigType, int32]))
816 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAccessHit[bigType, bigType]))
817 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAccessHit[int32, bigType]))
818 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAccessHit[*int32, int32]))
819 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAccessHit[int32, *int32]))
820 }
821
822 var sinkOK bool
823
824 func benchmarkMapAccessMiss[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
825 checkAllocSize[K, E](b, n)
826 k := genValues[K](0, n)
827 e := genValues[E](0, n)
828 m := fillMap(k, e)
829 if n == 0 {
830 n = 1
831 }
832 w := genValues[K](n, 2*n)
833 b.ResetTimer()
834
835 var ok bool
836 for i := 0; i < b.N; i++ {
837 _, ok = m[w[i%n]]
838 }
839
840 sinkOK = ok
841 }
842
843 func BenchmarkMapAccessMiss(b *testing.B) {
844 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAccessMiss[int32, int32]))
845 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAccessMiss[int64, int64]))
846 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAccessMiss[string, string]))
847 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAccessMiss[smallType, int32]))
848 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAccessMiss[mediumType, int32]))
849 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAccessMiss[bigType, int32]))
850 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAccessMiss[bigType, bigType]))
851 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAccessMiss[int32, bigType]))
852 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAccessMiss[*int32, int32]))
853 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAccessMiss[int32, *int32]))
854 }
855
856
857 func benchmarkMapAssignExists[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
858 if n == 0 {
859 b.Skip("can't assign to existing keys in empty map")
860 }
861 checkAllocSize[K, E](b, n)
862 k := genValues[K](0, n)
863 e := genValues[E](0, n)
864 m := fillMap(k, e)
865 b.ResetTimer()
866
867 for i := 0; i < b.N; i++ {
868 m[k[i%n]] = e[i%n]
869 }
870 }
871
872 func BenchmarkMapAssignExists(b *testing.B) {
873 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignExists[int32, int32]))
874 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignExists[int64, int64]))
875 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignExists[string, string]))
876 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignExists[smallType, int32]))
877 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignExists[mediumType, int32]))
878 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignExists[bigType, int32]))
879 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignExists[bigType, bigType]))
880 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignExists[int32, bigType]))
881 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignExists[*int32, int32]))
882 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignExists[int32, *int32]))
883 }
884
885
886
887
888
889
890
891 func benchmarkMapAssignFillNoHint[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
892 if n == 0 {
893 b.Skip("can't create empty map via assignment")
894 }
895 checkAllocSize[K, E](b, n)
896 k := genValues[K](0, n)
897 e := genValues[E](0, n)
898 b.ResetTimer()
899
900 var m map[K]E
901 for i := 0; i < b.N; i++ {
902 if i%n == 0 {
903 m = make(map[K]E)
904 }
905 m[k[i%n]] = e[i%n]
906 }
907 }
908
909 func BenchmarkMapAssignFillNoHint(b *testing.B) {
910 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[int32, int32]))
911 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillNoHint[int64, int64]))
912 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillNoHint[string, string]))
913 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[smallType, int32]))
914 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[mediumType, int32]))
915 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[bigType, int32]))
916 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillNoHint[bigType, bigType]))
917 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillNoHint[int32, bigType]))
918 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[*int32, int32]))
919 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillNoHint[int32, *int32]))
920 }
921
922
923
924 func benchmarkMapAssignGrowLatency[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
925 if n == 0 {
926 b.Skip("can't create empty map via assignment")
927 }
928 checkAllocSize[K, E](b, n)
929 k := genValues[K](0, n)
930 e := genValues[E](0, n)
931
932
933
934
935 sample := make([]int64, b.N)
936
937 b.ResetTimer()
938
939 var m map[K]E
940 for i := 0; i < b.N; i++ {
941 if i%n == 0 {
942 m = make(map[K]E)
943 }
944 start := runtime.Nanotime()
945 m[k[i%n]] = e[i%n]
946 end := runtime.Nanotime()
947 sample[i] = end - start
948 }
949
950 b.StopTimer()
951
952 slices.Sort(sample)
953
954
955
956 b.ReportMetric(float64(sample[int(float64(len(sample))*0.5)]), "p50-ns/op")
957 b.ReportMetric(float64(sample[int(float64(len(sample))*0.99)]), "p99-ns/op")
958 b.ReportMetric(float64(sample[int(float64(len(sample))*0.999)]), "p99.9-ns/op")
959 b.ReportMetric(float64(sample[int(float64(len(sample))*0.9999)]), "p99.99-ns/op")
960 b.ReportMetric(float64(sample[len(sample)-1]), "p100-ns/op")
961 }
962
963 func BenchmarkMapAssignGrowLatency(b *testing.B) {
964 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[int32, int32]))
965 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignGrowLatency[int64, int64]))
966 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignGrowLatency[string, string]))
967 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[smallType, int32]))
968 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[mediumType, int32]))
969 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[bigType, int32]))
970 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignGrowLatency[bigType, bigType]))
971 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignGrowLatency[int32, bigType]))
972 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[*int32, int32]))
973 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignGrowLatency[int32, *int32]))
974 }
975
976
977
978
979
980 func benchmarkMapAssignFillHint[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
981 if n == 0 {
982 b.Skip("can't create empty map via assignment")
983 }
984 checkAllocSize[K, E](b, n)
985 k := genValues[K](0, n)
986 e := genValues[E](0, n)
987 b.ResetTimer()
988
989 var m map[K]E
990 for i := 0; i < b.N; i++ {
991 if i%n == 0 {
992 m = make(map[K]E, n)
993 }
994 m[k[i%n]] = e[i%n]
995 }
996 }
997
998 func BenchmarkMapAssignFillHint(b *testing.B) {
999 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillHint[int32, int32]))
1000 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillHint[int64, int64]))
1001 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillHint[string, string]))
1002 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[smallType, int32]))
1003 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[mediumType, int32]))
1004 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[bigType, int32]))
1005 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillHint[bigType, bigType]))
1006 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillHint[int32, bigType]))
1007 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillHint[*int32, int32]))
1008 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillHint[int32, *int32]))
1009 }
1010
1011
1012
1013
1014
1015 func benchmarkMapAssignFillClear[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
1016 if n == 0 {
1017 b.Skip("can't create empty map via assignment")
1018 }
1019 checkAllocSize[K, E](b, n)
1020 k := genValues[K](0, n)
1021 e := genValues[E](0, n)
1022 m := fillMap(k, e)
1023 b.ResetTimer()
1024
1025 for i := 0; i < b.N; i++ {
1026 if i%n == 0 {
1027 clear(m)
1028 }
1029 m[k[i%n]] = e[i%n]
1030 }
1031 }
1032
1033 func BenchmarkMapAssignFillClear(b *testing.B) {
1034 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillClear[int32, int32]))
1035 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillClear[int64, int64]))
1036 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillClear[string, string]))
1037 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[smallType, int32]))
1038 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[mediumType, int32]))
1039 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[bigType, int32]))
1040 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillClear[bigType, bigType]))
1041 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillClear[int32, bigType]))
1042 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillClear[*int32, int32]))
1043 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillClear[int32, *int32]))
1044 }
1045
1046
1047 func benchmarkMapAssignAddition[K mapBenchmarkKeyType, E int32 | int64 | string](b *testing.B, n int) {
1048 if n == 0 {
1049 b.Skip("can't modify empty map via assignment")
1050 }
1051 checkAllocSize[K, E](b, n)
1052 k := genValues[K](0, n)
1053 e := genValues[E](0, n)
1054 m := fillMap(k, e)
1055 b.ResetTimer()
1056
1057 for i := 0; i < b.N; i++ {
1058 m[k[i%n]] += e[i%n]
1059 }
1060 }
1061
1062 func BenchmarkMapAssignAddition(b *testing.B) {
1063 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignAddition[int32, int32]))
1064 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignAddition[int64, int64]))
1065 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignAddition[string, string]))
1066 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignAddition[smallType, int32]))
1067 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignAddition[mediumType, int32]))
1068 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignAddition[bigType, int32]))
1069 }
1070
1071
1072 func benchmarkMapAssignAppend[K mapBenchmarkKeyType](b *testing.B, n int) {
1073 if n == 0 {
1074 b.Skip("can't modify empty map via append")
1075 }
1076 checkAllocSize[K, []int32](b, n)
1077 k := genValues[K](0, n)
1078 e := genValues[[]int32](0, n)
1079 m := fillMap(k, e)
1080 b.ResetTimer()
1081
1082 for i := 0; i < b.N; i++ {
1083 m[k[i%n]] = append(m[k[i%n]], e[i%n][0])
1084 }
1085 }
1086
1087 func BenchmarkMapAssignAppend(b *testing.B) {
1088 b.Run("Key=int32/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[int32]))
1089 b.Run("Key=int64/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[int64]))
1090 b.Run("Key=string/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[string]))
1091 }
1092
1093 func benchmarkMapDelete[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
1094 if n == 0 {
1095 b.Skip("can't delete from empty map")
1096 }
1097 checkAllocSize[K, E](b, n)
1098 k := genValues[K](0, n)
1099 e := genValues[E](0, n)
1100 m := fillMap(k, e)
1101 b.ResetTimer()
1102
1103 for i := 0; i < b.N; i++ {
1104 if len(m) == 0 {
1105
1106
1107
1108 for j := range k {
1109 m[k[j]] = e[j]
1110 }
1111 }
1112 delete(m, k[i%n])
1113 }
1114 }
1115
1116 func BenchmarkMapDelete(b *testing.B) {
1117 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapDelete[int32, int32]))
1118 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapDelete[int64, int64]))
1119 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapDelete[string, string]))
1120 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapDelete[smallType, int32]))
1121 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapDelete[mediumType, int32]))
1122 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapDelete[bigType, int32]))
1123 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapDelete[bigType, bigType]))
1124 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapDelete[int32, bigType]))
1125 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapDelete[*int32, int32]))
1126 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapDelete[int32, *int32]))
1127 }
1128
1129
1130
1131 func benchmarkMapPop[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
1132 if n == 0 {
1133 b.Skip("can't delete from empty map")
1134 }
1135 checkAllocSize[K, E](b, n)
1136 k := genValues[K](0, n)
1137 e := genValues[E](0, n)
1138 m := fillMap(k, e)
1139 b.ResetTimer()
1140
1141 for i := 0; i < b.N; i++ {
1142 if len(m) == 0 {
1143
1144
1145
1146 for j := range k {
1147 m[k[j]] = e[j]
1148 }
1149 }
1150 for key := range m {
1151 delete(m, key)
1152 break
1153 }
1154 }
1155 }
1156
1157 func BenchmarkMapPop(b *testing.B) {
1158 b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapPop[int32, int32]))
1159 b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapPop[int64, int64]))
1160 b.Run("Key=string/Elem=string", benchSizes(benchmarkMapPop[string, string]))
1161 b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapPop[smallType, int32]))
1162 b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapPop[mediumType, int32]))
1163 b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapPop[bigType, int32]))
1164 b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapPop[bigType, bigType]))
1165 b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapPop[int32, bigType]))
1166 b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapPop[*int32, int32]))
1167 b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapPop[int32, *int32]))
1168 }
1169
1170 func BenchmarkMapDeleteLargeKey(b *testing.B) {
1171 m := map[string]int{}
1172 for i := range 9 {
1173 m[fmt.Sprintf("%d", i)] = i
1174 }
1175 key := strings.Repeat("*", 10000)
1176 for range b.N {
1177 delete(m, key)
1178 }
1179 }
1180
1181 func BenchmarkMapSmallAccessHit(b *testing.B) {
1182 b.Run("Key=int32/Elem=int32", smallBenchSizes(benchmarkMapAccessHit[int32, int32]))
1183 b.Run("Key=int64/Elem=int64", smallBenchSizes(benchmarkMapAccessHit[int64, int64]))
1184 b.Run("Key=string/Elem=string", smallBenchSizes(benchmarkMapAccessHit[string, string]))
1185 }
1186 func BenchmarkMapSmallAccessMiss(b *testing.B) {
1187 b.Run("Key=int32/Elem=int32", smallBenchSizes(benchmarkMapAccessMiss[int32, int32]))
1188 b.Run("Key=int64/Elem=int64", smallBenchSizes(benchmarkMapAccessMiss[int64, int64]))
1189 b.Run("Key=string/Elem=string", smallBenchSizes(benchmarkMapAccessMiss[string, string]))
1190 }
1191
View as plain text