Source file
src/runtime/map_test.go
1
2
3
4
5 package runtime_test
6
7 import (
8 "fmt"
9 "internal/abi"
10 "internal/goarch"
11 "math"
12 "reflect"
13 "runtime"
14 "sort"
15 "strconv"
16 "strings"
17 "sync"
18 "testing"
19 )
20
21 func TestHmapSize(t *testing.T) {
22
23
24
25 var hmapSize = uintptr(8 + 5*goarch.PtrSize)
26 if runtime.RuntimeHmapSize != hmapSize {
27 t.Errorf("sizeof(runtime.hmap{})==%d, want %d", runtime.RuntimeHmapSize, hmapSize)
28 }
29
30 }
31
32
33
34
35
36
37
38 func TestNegativeZero(t *testing.T) {
39 m := make(map[float64]bool, 0)
40
41 m[+0.0] = true
42 m[math.Copysign(0.0, -1.0)] = true
43
44 if len(m) != 1 {
45 t.Error("length wrong")
46 }
47
48 for k := range m {
49 if math.Copysign(1.0, k) > 0 {
50 t.Error("wrong sign")
51 }
52 }
53
54 m = make(map[float64]bool, 0)
55 m[math.Copysign(0.0, -1.0)] = true
56 m[+0.0] = true
57
58 if len(m) != 1 {
59 t.Error("length wrong")
60 }
61
62 for k := range m {
63 if math.Copysign(1.0, k) < 0 {
64 t.Error("wrong sign")
65 }
66 }
67 }
68
69 func testMapNan(t *testing.T, m map[float64]int) {
70 if len(m) != 3 {
71 t.Error("length wrong")
72 }
73 s := 0
74 for k, v := range m {
75 if k == k {
76 t.Error("nan disappeared")
77 }
78 if (v & (v - 1)) != 0 {
79 t.Error("value wrong")
80 }
81 s |= v
82 }
83 if s != 7 {
84 t.Error("values wrong")
85 }
86 }
87
88
89
90 func TestMapAssignmentNan(t *testing.T) {
91 m := make(map[float64]int, 0)
92 nan := math.NaN()
93
94
95 m[nan] = 1
96 m[nan] = 2
97 m[nan] = 4
98 testMapNan(t, m)
99 }
100
101
102
103 func TestMapOperatorAssignmentNan(t *testing.T) {
104 m := make(map[float64]int, 0)
105 nan := math.NaN()
106
107
108 m[nan] += 1
109 m[nan] += 2
110 m[nan] += 4
111 testMapNan(t, m)
112 }
113
114 func TestMapOperatorAssignment(t *testing.T) {
115 m := make(map[int]int, 0)
116
117
118
119
120 m[0] = 12345
121 m[0] += 67890
122 m[0] /= 123
123 m[0] %= 456
124
125 const want = (12345 + 67890) / 123 % 456
126 if got := m[0]; got != want {
127 t.Errorf("got %d, want %d", got, want)
128 }
129 }
130
131 var sinkAppend bool
132
133 func TestMapAppendAssignment(t *testing.T) {
134 m := make(map[int][]int, 0)
135
136 m[0] = nil
137 m[0] = append(m[0], 12345)
138 m[0] = append(m[0], 67890)
139 sinkAppend, m[0] = !sinkAppend, append(m[0], 123, 456)
140 a := []int{7, 8, 9, 0}
141 m[0] = append(m[0], a...)
142
143 want := []int{12345, 67890, 123, 456, 7, 8, 9, 0}
144 if got := m[0]; !reflect.DeepEqual(got, want) {
145 t.Errorf("got %v, want %v", got, want)
146 }
147 }
148
149
150 func TestAlias(t *testing.T) {
151 m := make(map[int]int, 0)
152 m[0] = 5
153 n := m
154 n[0] = 6
155 if m[0] != 6 {
156 t.Error("alias didn't work")
157 }
158 }
159
160 func TestGrowWithNaN(t *testing.T) {
161 m := make(map[float64]int, 4)
162 nan := math.NaN()
163
164
165
166 m[nan] = 1
167 m[nan] = 2
168 m[nan] += 4
169
170 cnt := 0
171 s := 0
172 growflag := true
173 for k, v := range m {
174 if growflag {
175
176 for i := 0; i < 50; i++ {
177 m[float64(i)] = i
178 }
179 for i := 50; i < 100; i++ {
180 m[float64(i)] += i
181 }
182 growflag = false
183 }
184 if k != k {
185 cnt++
186 s |= v
187 }
188 }
189 if cnt != 3 {
190 t.Error("NaN keys lost during grow")
191 }
192 if s != 7 {
193 t.Error("NaN values lost during grow")
194 }
195 }
196
197 type FloatInt struct {
198 x float64
199 y int
200 }
201
202 func TestGrowWithNegativeZero(t *testing.T) {
203 negzero := math.Copysign(0.0, -1.0)
204 m := make(map[FloatInt]int, 4)
205 m[FloatInt{0.0, 0}] = 1
206 m[FloatInt{0.0, 1}] += 2
207 m[FloatInt{0.0, 2}] += 4
208 m[FloatInt{0.0, 3}] = 8
209 growflag := true
210 s := 0
211 cnt := 0
212 negcnt := 0
213
214
215
216
217
218 for k, v := range m {
219 if v == 0 {
220 continue
221 }
222 cnt++
223 if math.Copysign(1.0, k.x) < 0 {
224 if v&16 == 0 {
225 t.Error("key/value not updated together 1")
226 }
227 negcnt++
228 s |= v & 15
229 } else {
230 if v&16 == 16 {
231 t.Error("key/value not updated together 2", k, v)
232 }
233 s |= v
234 }
235 if growflag {
236
237 for i := 0; i < 100; i++ {
238 m[FloatInt{3.0, i}] = 0
239 }
240
241
242 m[FloatInt{negzero, 0}] = 1 | 16
243 m[FloatInt{negzero, 1}] = 2 | 16
244 m[FloatInt{negzero, 2}] = 4 | 16
245 m[FloatInt{negzero, 3}] = 8 | 16
246 growflag = false
247 }
248 }
249 if s != 15 {
250 t.Error("entry missing", s)
251 }
252 if cnt != 4 {
253 t.Error("wrong number of entries returned by iterator", cnt)
254 }
255 if negcnt != 3 {
256 t.Error("update to negzero missed by iteration", negcnt)
257 }
258 }
259
260 func TestIterGrowAndDelete(t *testing.T) {
261 m := make(map[int]int, 4)
262 for i := 0; i < 100; i++ {
263 m[i] = i
264 }
265 growflag := true
266 for k := range m {
267 if growflag {
268
269 for i := 100; i < 1000; i++ {
270 m[i] = i
271 }
272
273 for i := 1; i < 1000; i += 2 {
274 delete(m, i)
275 }
276 growflag = false
277 } else {
278 if k&1 == 1 {
279 t.Error("odd value returned")
280 }
281 }
282 }
283 }
284
285
286
287 func TestIterGrowWithGC(t *testing.T) {
288 m := make(map[int]int, 4)
289 for i := 0; i < 8; i++ {
290 m[i] = i
291 }
292 for i := 8; i < 16; i++ {
293 m[i] += i
294 }
295 growflag := true
296 bitmask := 0
297 for k := range m {
298 if k < 16 {
299 bitmask |= 1 << uint(k)
300 }
301 if growflag {
302
303 for i := 100; i < 1000; i++ {
304 m[i] = i
305 }
306
307 runtime.GC()
308 growflag = false
309 }
310 }
311 if bitmask != 1<<16-1 {
312 t.Error("missing key", bitmask)
313 }
314 }
315
316 func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
317 t.Parallel()
318 if runtime.GOMAXPROCS(-1) == 1 {
319 defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
320 }
321 numLoop := 10
322 numGrowStep := 250
323 numReader := 16
324 if testing.Short() {
325 numLoop, numGrowStep = 2, 100
326 }
327 for i := 0; i < numLoop; i++ {
328 m := make(map[int]int, 0)
329 for gs := 0; gs < numGrowStep; gs++ {
330 m[gs] = gs
331 var wg sync.WaitGroup
332 wg.Add(numReader * 2)
333 for nr := 0; nr < numReader; nr++ {
334 go func() {
335 defer wg.Done()
336 for range m {
337 }
338 }()
339 go func() {
340 defer wg.Done()
341 for key := 0; key < gs; key++ {
342 _ = m[key]
343 }
344 }()
345 if useReflect {
346 wg.Add(1)
347 go func() {
348 defer wg.Done()
349 mv := reflect.ValueOf(m)
350 keys := mv.MapKeys()
351 for _, k := range keys {
352 mv.MapIndex(k)
353 }
354 }()
355 }
356 }
357 wg.Wait()
358 }
359 }
360 }
361
362 func TestConcurrentReadsAfterGrowth(t *testing.T) {
363 testConcurrentReadsAfterGrowth(t, false)
364 }
365
366 func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
367 testConcurrentReadsAfterGrowth(t, true)
368 }
369
370 func TestBigItems(t *testing.T) {
371 var key [256]string
372 for i := 0; i < 256; i++ {
373 key[i] = "foo"
374 }
375 m := make(map[[256]string][256]string, 4)
376 for i := 0; i < 100; i++ {
377 key[37] = fmt.Sprintf("string%02d", i)
378 m[key] = key
379 }
380 var keys [100]string
381 var values [100]string
382 i := 0
383 for k, v := range m {
384 keys[i] = k[37]
385 values[i] = v[37]
386 i++
387 }
388 sort.Strings(keys[:])
389 sort.Strings(values[:])
390 for i := 0; i < 100; i++ {
391 if keys[i] != fmt.Sprintf("string%02d", i) {
392 t.Errorf("#%d: missing key: %v", i, keys[i])
393 }
394 if values[i] != fmt.Sprintf("string%02d", i) {
395 t.Errorf("#%d: missing value: %v", i, values[i])
396 }
397 }
398 }
399
400 func TestMapHugeZero(t *testing.T) {
401 type T [4000]byte
402 m := map[int]T{}
403 x := m[0]
404 if x != (T{}) {
405 t.Errorf("map value not zero")
406 }
407 y, ok := m[0]
408 if ok {
409 t.Errorf("map value should be missing")
410 }
411 if y != (T{}) {
412 t.Errorf("map value not zero")
413 }
414 }
415
416 type empty struct {
417 }
418
419 func TestEmptyKeyAndValue(t *testing.T) {
420 a := make(map[int]empty, 4)
421 b := make(map[empty]int, 4)
422 c := make(map[empty]empty, 4)
423 a[0] = empty{}
424 b[empty{}] = 0
425 b[empty{}] = 1
426 c[empty{}] = empty{}
427
428 if len(a) != 1 {
429 t.Errorf("empty value insert problem")
430 }
431 if b[empty{}] != 1 {
432 t.Errorf("empty key returned wrong value")
433 }
434 }
435
436
437
438 func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
439 testMapLookups(t, map[string]string{
440 "x": "x1val",
441 "xx": "x2val",
442 "foo": "fooval",
443 "bar": "barval",
444 "xxxx": "x4val",
445 strings.Repeat("x", 128): "longval1",
446 strings.Repeat("y", 128): "longval2",
447 })
448 }
449
450
451 func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
452 testMapLookups(t, map[string]string{
453 "x": "x1val",
454 "xx": "x2val",
455 "foo": "fooval",
456 "xxxx": "x4val",
457 "xxxxx": "x5val",
458 "xxxxxx": "x6val",
459 strings.Repeat("x", 128): "longval",
460 })
461 }
462
463 func testMapLookups(t *testing.T, m map[string]string) {
464 for k, v := range m {
465 if m[k] != v {
466 t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
467 }
468 }
469 }
470
471
472
473 func TestMapNanGrowIterator(t *testing.T) {
474 m := make(map[float64]int)
475 nan := math.NaN()
476 const nBuckets = 16
477
478 nKeys := int(nBuckets * runtime.HashLoad)
479
480
481 for i := 0; i < nKeys; i++ {
482 m[nan] = i
483 }
484
485 m[1.0] = 1
486 delete(m, 1.0)
487
488
489 found := make(map[int]struct{})
490 for _, v := range m {
491 if v != -1 {
492 if _, repeat := found[v]; repeat {
493 t.Fatalf("repeat of value %d", v)
494 }
495 found[v] = struct{}{}
496 }
497 if len(found) == nKeys/2 {
498
499 for i := 0; i < nBuckets; i++ {
500 delete(m, 1.0)
501 }
502 }
503 }
504 if len(found) != nKeys {
505 t.Fatalf("missing value")
506 }
507 }
508
509 func TestMapIterOrder(t *testing.T) {
510 sizes := []int{3, 7, 9, 15}
511 if abi.MapBucketCountBits >= 5 {
512
513 t.Fatalf("This test becomes flaky if abi.MapBucketCountBits(=%d) is 5 or larger", abi.MapBucketCountBits)
514 }
515 for _, n := range sizes {
516 for i := 0; i < 1000; i++ {
517
518 m := make(map[int]bool)
519 for i := 0; i < n; i++ {
520 m[i] = true
521 }
522
523 ord := func() []int {
524 var s []int
525 for key := range m {
526 s = append(s, key)
527 }
528 return s
529 }
530 first := ord()
531 ok := false
532 for try := 0; try < 100; try++ {
533 if !reflect.DeepEqual(first, ord()) {
534 ok = true
535 break
536 }
537 }
538 if !ok {
539 t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
540 break
541 }
542 }
543 }
544 }
545
546
547 func TestMapSparseIterOrder(t *testing.T) {
548
549
550 NextRound:
551 for round := 0; round < 10; round++ {
552 m := make(map[int]bool)
553
554 for i := 0; i < 1000; i++ {
555 m[i] = true
556 }
557 for i := 20; i < 1000; i++ {
558 delete(m, i)
559 }
560
561 var first []int
562 for i := range m {
563 first = append(first, i)
564 }
565
566
567
568 for n := 0; n < 800; n++ {
569 idx := 0
570 for i := range m {
571 if i != first[idx] {
572
573 continue NextRound
574 }
575 idx++
576 }
577 }
578 t.Fatalf("constant iteration order on round %d: %v", round, first)
579 }
580 }
581
582 func TestMapStringBytesLookup(t *testing.T) {
583
584
585 m := map[string]int{
586 "1000000000000000000000000000000000000000000000000": 1,
587 "2000000000000000000000000000000000000000000000000": 2,
588 }
589 buf := []byte("1000000000000000000000000000000000000000000000000")
590 if x := m[string(buf)]; x != 1 {
591 t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
592 }
593 buf[0] = '2'
594 if x := m[string(buf)]; x != 2 {
595 t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
596 }
597
598 var x int
599 n := testing.AllocsPerRun(100, func() {
600 x += m[string(buf)]
601 })
602 if n != 0 {
603 t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
604 }
605
606 x = 0
607 n = testing.AllocsPerRun(100, func() {
608 y, ok := m[string(buf)]
609 if !ok {
610 panic("!ok")
611 }
612 x += y
613 })
614 if n != 0 {
615 t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
616 }
617 }
618
619 func TestMapLargeKeyNoPointer(t *testing.T) {
620 const (
621 I = 1000
622 N = 64
623 )
624 type T [N]int
625 m := make(map[T]int)
626 for i := 0; i < I; i++ {
627 var v T
628 for j := 0; j < N; j++ {
629 v[j] = i + j
630 }
631 m[v] = i
632 }
633 runtime.GC()
634 for i := 0; i < I; i++ {
635 var v T
636 for j := 0; j < N; j++ {
637 v[j] = i + j
638 }
639 if m[v] != i {
640 t.Fatalf("corrupted map: want %+v, got %+v", i, m[v])
641 }
642 }
643 }
644
645 func TestMapLargeValNoPointer(t *testing.T) {
646 const (
647 I = 1000
648 N = 64
649 )
650 type T [N]int
651 m := make(map[int]T)
652 for i := 0; i < I; i++ {
653 var v T
654 for j := 0; j < N; j++ {
655 v[j] = i + j
656 }
657 m[i] = v
658 }
659 runtime.GC()
660 for i := 0; i < I; i++ {
661 var v T
662 for j := 0; j < N; j++ {
663 v[j] = i + j
664 }
665 v1 := m[i]
666 for j := 0; j < N; j++ {
667 if v1[j] != v[j] {
668 t.Fatalf("corrupted map: want %+v, got %+v", v, v1)
669 }
670 }
671 }
672 }
673
674
675
676 func TestIgnoreBogusMapHint(t *testing.T) {
677 for _, hint := range []int64{-1, 1 << 62} {
678 _ = make(map[int]int, hint)
679 }
680 }
681
682 const bs = abi.MapBucketCount
683
684
685
686
687
688 const (
689 belowOverflow = bs * 3 / 2
690 atOverflow = belowOverflow + bs/8
691 )
692
693 var mapBucketTests = [...]struct {
694 n int
695 noescape int
696 escape int
697 }{
698 {-(1 << 30), 1, 1},
699 {-1, 1, 1},
700 {0, 1, 1},
701 {1, 1, 1},
702 {bs, 1, 1},
703 {bs + 1, 2, 2},
704 {belowOverflow, 2, 2},
705 {atOverflow + 1, 4, 4},
706
707 {2 * belowOverflow, 4, 4},
708 {2*atOverflow + 1, 8, 8},
709
710 {4 * belowOverflow, 8, 8},
711 {4*atOverflow + 1, 16, 16},
712 }
713
714 func TestMapBuckets(t *testing.T) {
715
716
717
718
719
720
721 t.Run("mapliteral", func(t *testing.T) {
722 for _, tt := range mapBucketTests {
723 localMap := map[int]int{}
724 if runtime.MapBucketsPointerIsNil(localMap) {
725 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
726 }
727 for i := 0; i < tt.n; i++ {
728 localMap[i] = i
729 }
730 if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
731 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
732 }
733 escapingMap := runtime.Escape(map[int]int{})
734 if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
735 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
736 }
737 for i := 0; i < tt.n; i++ {
738 escapingMap[i] = i
739 }
740 if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
741 t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got)
742 }
743 }
744 })
745 t.Run("nohint", func(t *testing.T) {
746 for _, tt := range mapBucketTests {
747 localMap := make(map[int]int)
748 if runtime.MapBucketsPointerIsNil(localMap) {
749 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
750 }
751 for i := 0; i < tt.n; i++ {
752 localMap[i] = i
753 }
754 if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
755 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
756 }
757 escapingMap := runtime.Escape(make(map[int]int))
758 if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
759 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
760 }
761 for i := 0; i < tt.n; i++ {
762 escapingMap[i] = i
763 }
764 if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
765 t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
766 }
767 }
768 })
769 t.Run("makemap", func(t *testing.T) {
770 for _, tt := range mapBucketTests {
771 localMap := make(map[int]int, tt.n)
772 if runtime.MapBucketsPointerIsNil(localMap) {
773 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
774 }
775 for i := 0; i < tt.n; i++ {
776 localMap[i] = i
777 }
778 if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
779 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
780 }
781 escapingMap := runtime.Escape(make(map[int]int, tt.n))
782 if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
783 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
784 }
785 for i := 0; i < tt.n; i++ {
786 escapingMap[i] = i
787 }
788 if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
789 t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
790 }
791 }
792 })
793 t.Run("makemap64", func(t *testing.T) {
794 for _, tt := range mapBucketTests {
795 localMap := make(map[int]int, int64(tt.n))
796 if runtime.MapBucketsPointerIsNil(localMap) {
797 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
798 }
799 for i := 0; i < tt.n; i++ {
800 localMap[i] = i
801 }
802 if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
803 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
804 }
805 escapingMap := runtime.Escape(make(map[int]int, tt.n))
806 if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
807 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
808 }
809 for i := 0; i < tt.n; i++ {
810 escapingMap[i] = i
811 }
812 if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
813 t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
814 }
815 }
816 })
817
818 }
819
820 func benchmarkMapPop(b *testing.B, n int) {
821 m := map[int]int{}
822 for i := 0; i < b.N; i++ {
823 for j := 0; j < n; j++ {
824 m[j] = j
825 }
826 for j := 0; j < n; j++ {
827
828
829 for k := range m {
830 delete(m, k)
831 break
832 }
833 }
834 }
835 }
836
837 func BenchmarkMapPop100(b *testing.B) { benchmarkMapPop(b, 100) }
838 func BenchmarkMapPop1000(b *testing.B) { benchmarkMapPop(b, 1000) }
839 func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) }
840
841 var testNonEscapingMapVariable int = 8
842
843 func TestNonEscapingMap(t *testing.T) {
844 n := testing.AllocsPerRun(1000, func() {
845 m := map[int]int{}
846 m[0] = 0
847 })
848 if n != 0 {
849 t.Fatalf("mapliteral: want 0 allocs, got %v", n)
850 }
851 n = testing.AllocsPerRun(1000, func() {
852 m := make(map[int]int)
853 m[0] = 0
854 })
855 if n != 0 {
856 t.Fatalf("no hint: want 0 allocs, got %v", n)
857 }
858 n = testing.AllocsPerRun(1000, func() {
859 m := make(map[int]int, 8)
860 m[0] = 0
861 })
862 if n != 0 {
863 t.Fatalf("with small hint: want 0 allocs, got %v", n)
864 }
865 n = testing.AllocsPerRun(1000, func() {
866 m := make(map[int]int, testNonEscapingMapVariable)
867 m[0] = 0
868 })
869 if n != 0 {
870 t.Fatalf("with variable hint: want 0 allocs, got %v", n)
871 }
872
873 }
874
875 func benchmarkMapAssignInt32(b *testing.B, n int) {
876 a := make(map[int32]int)
877 for i := 0; i < b.N; i++ {
878 a[int32(i&(n-1))] = i
879 }
880 }
881
882 func benchmarkMapOperatorAssignInt32(b *testing.B, n int) {
883 a := make(map[int32]int)
884 for i := 0; i < b.N; i++ {
885 a[int32(i&(n-1))] += i
886 }
887 }
888
889 func benchmarkMapAppendAssignInt32(b *testing.B, n int) {
890 a := make(map[int32][]int)
891 b.ReportAllocs()
892 b.ResetTimer()
893 for i := 0; i < b.N; i++ {
894 key := int32(i & (n - 1))
895 a[key] = append(a[key], i)
896 }
897 }
898
899 func benchmarkMapDeleteInt32(b *testing.B, n int) {
900 a := make(map[int32]int, n)
901 b.ResetTimer()
902 for i := 0; i < b.N; i++ {
903 if len(a) == 0 {
904 b.StopTimer()
905 for j := i; j < i+n; j++ {
906 a[int32(j)] = j
907 }
908 b.StartTimer()
909 }
910 delete(a, int32(i))
911 }
912 }
913
914 func benchmarkMapAssignInt64(b *testing.B, n int) {
915 a := make(map[int64]int)
916 for i := 0; i < b.N; i++ {
917 a[int64(i&(n-1))] = i
918 }
919 }
920
921 func benchmarkMapOperatorAssignInt64(b *testing.B, n int) {
922 a := make(map[int64]int)
923 for i := 0; i < b.N; i++ {
924 a[int64(i&(n-1))] += i
925 }
926 }
927
928 func benchmarkMapAppendAssignInt64(b *testing.B, n int) {
929 a := make(map[int64][]int)
930 b.ReportAllocs()
931 b.ResetTimer()
932 for i := 0; i < b.N; i++ {
933 key := int64(i & (n - 1))
934 a[key] = append(a[key], i)
935 }
936 }
937
938 func benchmarkMapDeleteInt64(b *testing.B, n int) {
939 a := make(map[int64]int, n)
940 b.ResetTimer()
941 for i := 0; i < b.N; i++ {
942 if len(a) == 0 {
943 b.StopTimer()
944 for j := i; j < i+n; j++ {
945 a[int64(j)] = j
946 }
947 b.StartTimer()
948 }
949 delete(a, int64(i))
950 }
951 }
952
953 func benchmarkMapAssignStr(b *testing.B, n int) {
954 k := make([]string, n)
955 for i := 0; i < len(k); i++ {
956 k[i] = strconv.Itoa(i)
957 }
958 b.ResetTimer()
959 a := make(map[string]int)
960 for i := 0; i < b.N; i++ {
961 a[k[i&(n-1)]] = i
962 }
963 }
964
965 func benchmarkMapOperatorAssignStr(b *testing.B, n int) {
966 k := make([]string, n)
967 for i := 0; i < len(k); i++ {
968 k[i] = strconv.Itoa(i)
969 }
970 b.ResetTimer()
971 a := make(map[string]string)
972 for i := 0; i < b.N; i++ {
973 key := k[i&(n-1)]
974 a[key] += key
975 }
976 }
977
978 func benchmarkMapAppendAssignStr(b *testing.B, n int) {
979 k := make([]string, n)
980 for i := 0; i < len(k); i++ {
981 k[i] = strconv.Itoa(i)
982 }
983 a := make(map[string][]string)
984 b.ReportAllocs()
985 b.ResetTimer()
986 for i := 0; i < b.N; i++ {
987 key := k[i&(n-1)]
988 a[key] = append(a[key], key)
989 }
990 }
991
992 func benchmarkMapDeleteStr(b *testing.B, n int) {
993 i2s := make([]string, n)
994 for i := 0; i < n; i++ {
995 i2s[i] = strconv.Itoa(i)
996 }
997 a := make(map[string]int, n)
998 b.ResetTimer()
999 k := 0
1000 for i := 0; i < b.N; i++ {
1001 if len(a) == 0 {
1002 b.StopTimer()
1003 for j := 0; j < n; j++ {
1004 a[i2s[j]] = j
1005 }
1006 k = i
1007 b.StartTimer()
1008 }
1009 delete(a, i2s[i-k])
1010 }
1011 }
1012
1013 func benchmarkMapDeletePointer(b *testing.B, n int) {
1014 i2p := make([]*int, n)
1015 for i := 0; i < n; i++ {
1016 i2p[i] = new(int)
1017 }
1018 a := make(map[*int]int, n)
1019 b.ResetTimer()
1020 k := 0
1021 for i := 0; i < b.N; i++ {
1022 if len(a) == 0 {
1023 b.StopTimer()
1024 for j := 0; j < n; j++ {
1025 a[i2p[j]] = j
1026 }
1027 k = i
1028 b.StartTimer()
1029 }
1030 delete(a, i2p[i-k])
1031 }
1032 }
1033
1034 func runWith(f func(*testing.B, int), v ...int) func(*testing.B) {
1035 return func(b *testing.B) {
1036 for _, n := range v {
1037 b.Run(strconv.Itoa(n), func(b *testing.B) { f(b, n) })
1038 }
1039 }
1040 }
1041
1042 func BenchmarkMapAssign(b *testing.B) {
1043 b.Run("Int32", runWith(benchmarkMapAssignInt32, 1<<8, 1<<16))
1044 b.Run("Int64", runWith(benchmarkMapAssignInt64, 1<<8, 1<<16))
1045 b.Run("Str", runWith(benchmarkMapAssignStr, 1<<8, 1<<16))
1046 }
1047
1048 func BenchmarkMapOperatorAssign(b *testing.B) {
1049 b.Run("Int32", runWith(benchmarkMapOperatorAssignInt32, 1<<8, 1<<16))
1050 b.Run("Int64", runWith(benchmarkMapOperatorAssignInt64, 1<<8, 1<<16))
1051 b.Run("Str", runWith(benchmarkMapOperatorAssignStr, 1<<8, 1<<16))
1052 }
1053
1054 func BenchmarkMapAppendAssign(b *testing.B) {
1055 b.Run("Int32", runWith(benchmarkMapAppendAssignInt32, 1<<8, 1<<16))
1056 b.Run("Int64", runWith(benchmarkMapAppendAssignInt64, 1<<8, 1<<16))
1057 b.Run("Str", runWith(benchmarkMapAppendAssignStr, 1<<8, 1<<16))
1058 }
1059
1060 func BenchmarkMapDelete(b *testing.B) {
1061 b.Run("Int32", runWith(benchmarkMapDeleteInt32, 100, 1000, 10000))
1062 b.Run("Int64", runWith(benchmarkMapDeleteInt64, 100, 1000, 10000))
1063 b.Run("Str", runWith(benchmarkMapDeleteStr, 100, 1000, 10000))
1064 b.Run("Pointer", runWith(benchmarkMapDeletePointer, 100, 1000, 10000))
1065 }
1066
1067 func TestDeferDeleteSlow(t *testing.T) {
1068 ks := []complex128{0, 1, 2, 3}
1069
1070 m := make(map[any]int)
1071 for i, k := range ks {
1072 m[k] = i
1073 }
1074 if len(m) != len(ks) {
1075 t.Errorf("want %d elements, got %d", len(ks), len(m))
1076 }
1077
1078 func() {
1079 for _, k := range ks {
1080 defer delete(m, k)
1081 }
1082 }()
1083 if len(m) != 0 {
1084 t.Errorf("want 0 elements, got %d", len(m))
1085 }
1086 }
1087
1088
1089
1090
1091 func TestIncrementAfterDeleteValueInt(t *testing.T) {
1092 const key1 = 12
1093 const key2 = 13
1094
1095 m := make(map[int]int)
1096 m[key1] = 99
1097 delete(m, key1)
1098 m[key2]++
1099 if n2 := m[key2]; n2 != 1 {
1100 t.Errorf("incremented 0 to %d", n2)
1101 }
1102 }
1103
1104 func TestIncrementAfterDeleteValueInt32(t *testing.T) {
1105 const key1 = 12
1106 const key2 = 13
1107
1108 m := make(map[int]int32)
1109 m[key1] = 99
1110 delete(m, key1)
1111 m[key2]++
1112 if n2 := m[key2]; n2 != 1 {
1113 t.Errorf("incremented 0 to %d", n2)
1114 }
1115 }
1116
1117 func TestIncrementAfterDeleteValueInt64(t *testing.T) {
1118 const key1 = 12
1119 const key2 = 13
1120
1121 m := make(map[int]int64)
1122 m[key1] = 99
1123 delete(m, key1)
1124 m[key2]++
1125 if n2 := m[key2]; n2 != 1 {
1126 t.Errorf("incremented 0 to %d", n2)
1127 }
1128 }
1129
1130 func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) {
1131 const key1 = ""
1132 const key2 = "x"
1133
1134 m := make(map[string]int)
1135 m[key1] = 99
1136 delete(m, key1)
1137 m[key2] += 1
1138 if n2 := m[key2]; n2 != 1 {
1139 t.Errorf("incremented 0 to %d", n2)
1140 }
1141 }
1142
1143 func TestIncrementAfterDeleteKeyValueString(t *testing.T) {
1144 const key1 = ""
1145 const key2 = "x"
1146
1147 m := make(map[string]string)
1148 m[key1] = "99"
1149 delete(m, key1)
1150 m[key2] += "1"
1151 if n2 := m[key2]; n2 != "1" {
1152 t.Errorf("appended '1' to empty (nil) string, got %s", n2)
1153 }
1154 }
1155
1156
1157
1158
1159 func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) {
1160 const key1 = ""
1161 const key2 = "x"
1162
1163 m := make(map[string]int)
1164 m[key1] = 99
1165 for k := range m {
1166 delete(m, k)
1167 }
1168 m[key2]++
1169 if n2 := m[key2]; n2 != 1 {
1170 t.Errorf("incremented 0 to %d", n2)
1171 }
1172 }
1173
1174 func TestMapTombstones(t *testing.T) {
1175 m := map[int]int{}
1176 const N = 10000
1177
1178 for i := 0; i < N; i++ {
1179 m[i] = i
1180 }
1181 runtime.MapTombstoneCheck(m)
1182
1183 for i := 0; i < N; i += 2 {
1184 delete(m, i)
1185 }
1186 runtime.MapTombstoneCheck(m)
1187
1188 for i := N; i < 3*N/2; i++ {
1189 m[i] = i
1190 }
1191 runtime.MapTombstoneCheck(m)
1192
1193 for i := 0; i < 3*N/2; i++ {
1194 delete(m, i)
1195 }
1196 runtime.MapTombstoneCheck(m)
1197 }
1198
1199 type canString int
1200
1201 func (c canString) String() string {
1202 return fmt.Sprintf("%d", int(c))
1203 }
1204
1205 func TestMapInterfaceKey(t *testing.T) {
1206
1207 type GrabBag struct {
1208 f32 float32
1209 f64 float64
1210 c64 complex64
1211 c128 complex128
1212 s string
1213 i0 any
1214 i1 interface {
1215 String() string
1216 }
1217 a [4]string
1218 }
1219
1220 m := map[any]bool{}
1221
1222
1223 for i := 0; i < 1000; i++ {
1224 m[i] = true
1225 }
1226 m[GrabBag{f32: 1.0}] = true
1227 if !m[GrabBag{f32: 1.0}] {
1228 panic("f32 not found")
1229 }
1230 m[GrabBag{f64: 1.0}] = true
1231 if !m[GrabBag{f64: 1.0}] {
1232 panic("f64 not found")
1233 }
1234 m[GrabBag{c64: 1.0i}] = true
1235 if !m[GrabBag{c64: 1.0i}] {
1236 panic("c64 not found")
1237 }
1238 m[GrabBag{c128: 1.0i}] = true
1239 if !m[GrabBag{c128: 1.0i}] {
1240 panic("c128 not found")
1241 }
1242 m[GrabBag{s: "foo"}] = true
1243 if !m[GrabBag{s: "foo"}] {
1244 panic("string not found")
1245 }
1246 m[GrabBag{i0: "foo"}] = true
1247 if !m[GrabBag{i0: "foo"}] {
1248 panic("interface{} not found")
1249 }
1250 m[GrabBag{i1: canString(5)}] = true
1251 if !m[GrabBag{i1: canString(5)}] {
1252 panic("interface{String() string} not found")
1253 }
1254 m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true
1255 if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] {
1256 panic("array not found")
1257 }
1258 }
1259
View as plain text