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