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