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