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 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 1020func 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 1026func 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 1032func 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 1038func 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} 1043 1044func TestDeferDeleteSlow(t *testing.T) { 1045 ks := []complex128{0, 1, 2, 3} 1046 1047 m := make(map[interface{}]int) 1048 for i, k := range ks { 1049 m[k] = i 1050 } 1051 if len(m) != len(ks) { 1052 t.Errorf("want %d elements, got %d", len(ks), len(m)) 1053 } 1054 1055 func() { 1056 for _, k := range ks { 1057 defer delete(m, k) 1058 } 1059 }() 1060 if len(m) != 0 { 1061 t.Errorf("want 0 elements, got %d", len(m)) 1062 } 1063} 1064 1065// TestIncrementAfterDeleteValueInt and other test Issue 25936. 1066// Value types int, int32, int64 are affected. Value type string 1067// works as expected. 1068func TestIncrementAfterDeleteValueInt(t *testing.T) { 1069 const key1 = 12 1070 const key2 = 13 1071 1072 m := make(map[int]int) 1073 m[key1] = 99 1074 delete(m, key1) 1075 m[key2]++ 1076 if n2 := m[key2]; n2 != 1 { 1077 t.Errorf("incremented 0 to %d", n2) 1078 } 1079} 1080 1081func TestIncrementAfterDeleteValueInt32(t *testing.T) { 1082 const key1 = 12 1083 const key2 = 13 1084 1085 m := make(map[int]int32) 1086 m[key1] = 99 1087 delete(m, key1) 1088 m[key2]++ 1089 if n2 := m[key2]; n2 != 1 { 1090 t.Errorf("incremented 0 to %d", n2) 1091 } 1092} 1093 1094func TestIncrementAfterDeleteValueInt64(t *testing.T) { 1095 const key1 = 12 1096 const key2 = 13 1097 1098 m := make(map[int]int64) 1099 m[key1] = 99 1100 delete(m, key1) 1101 m[key2]++ 1102 if n2 := m[key2]; n2 != 1 { 1103 t.Errorf("incremented 0 to %d", n2) 1104 } 1105} 1106 1107func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) { 1108 const key1 = "" 1109 const key2 = "x" 1110 1111 m := make(map[string]int) 1112 m[key1] = 99 1113 delete(m, key1) 1114 m[key2] += 1 1115 if n2 := m[key2]; n2 != 1 { 1116 t.Errorf("incremented 0 to %d", n2) 1117 } 1118} 1119 1120func TestIncrementAfterDeleteKeyValueString(t *testing.T) { 1121 const key1 = "" 1122 const key2 = "x" 1123 1124 m := make(map[string]string) 1125 m[key1] = "99" 1126 delete(m, key1) 1127 m[key2] += "1" 1128 if n2 := m[key2]; n2 != "1" { 1129 t.Errorf("appended '1' to empty (nil) string, got %s", n2) 1130 } 1131} 1132 1133// TestIncrementAfterBulkClearKeyStringValueInt tests that map bulk 1134// deletion (mapclear) still works as expected. Note that it was not 1135// affected by Issue 25936. 1136func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) { 1137 const key1 = "" 1138 const key2 = "x" 1139 1140 m := make(map[string]int) 1141 m[key1] = 99 1142 for k := range m { 1143 delete(m, k) 1144 } 1145 m[key2]++ 1146 if n2 := m[key2]; n2 != 1 { 1147 t.Errorf("incremented 0 to %d", n2) 1148 } 1149} 1150 1151func TestMapTombstones(t *testing.T) { 1152 m := map[int]int{} 1153 const N = 10000 1154 // Fill a map. 1155 for i := 0; i < N; i++ { 1156 m[i] = i 1157 } 1158 runtime.MapTombstoneCheck(m) 1159 // Delete half of the entries. 1160 for i := 0; i < N; i += 2 { 1161 delete(m, i) 1162 } 1163 runtime.MapTombstoneCheck(m) 1164 // Add new entries to fill in holes. 1165 for i := N; i < 3*N/2; i++ { 1166 m[i] = i 1167 } 1168 runtime.MapTombstoneCheck(m) 1169 // Delete everything. 1170 for i := 0; i < 3*N/2; i++ { 1171 delete(m, i) 1172 } 1173 runtime.MapTombstoneCheck(m) 1174} 1175 1176type canString int 1177 1178func (c canString) String() string { 1179 return fmt.Sprintf("%d", int(c)) 1180} 1181 1182func TestMapInterfaceKey(t *testing.T) { 1183 // Test all the special cases in runtime.typehash. 1184 type GrabBag struct { 1185 f32 float32 1186 f64 float64 1187 c64 complex64 1188 c128 complex128 1189 s string 1190 i0 interface{} 1191 i1 interface { 1192 String() string 1193 } 1194 a [4]string 1195 } 1196 1197 m := map[interface{}]bool{} 1198 // Put a bunch of data in m, so that a bad hash is likely to 1199 // lead to a bad bucket, which will lead to a missed lookup. 1200 for i := 0; i < 1000; i++ { 1201 m[i] = true 1202 } 1203 m[GrabBag{f32: 1.0}] = true 1204 if !m[GrabBag{f32: 1.0}] { 1205 panic("f32 not found") 1206 } 1207 m[GrabBag{f64: 1.0}] = true 1208 if !m[GrabBag{f64: 1.0}] { 1209 panic("f64 not found") 1210 } 1211 m[GrabBag{c64: 1.0i}] = true 1212 if !m[GrabBag{c64: 1.0i}] { 1213 panic("c64 not found") 1214 } 1215 m[GrabBag{c128: 1.0i}] = true 1216 if !m[GrabBag{c128: 1.0i}] { 1217 panic("c128 not found") 1218 } 1219 m[GrabBag{s: "foo"}] = true 1220 if !m[GrabBag{s: "foo"}] { 1221 panic("string not found") 1222 } 1223 m[GrabBag{i0: "foo"}] = true 1224 if !m[GrabBag{i0: "foo"}] { 1225 panic("interface{} not found") 1226 } 1227 m[GrabBag{i1: canString(5)}] = true 1228 if !m[GrabBag{i1: canString(5)}] { 1229 panic("interface{String() string} not found") 1230 } 1231 m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true 1232 if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] { 1233 panic("array not found") 1234 } 1235} 1236