libgo/go/runtime/map_test.go

   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
   5 package runtime_test
   6
   7 import (
   8         "fmt"
   9         "math"
  10         "reflect"
  11         "runtime"
  12         "sort"
  13         "strconv"
  14         "strings"
  15         "sync"
  16         "testing"
  17 )
  18
  19 // negative zero is a good test because:
  20 //  1) 0 and -0 are equal, yet have distinct representations.
  21 //  2) 0 is represented as all zeros, -0 isn't.
  22 // I'm not sure the language spec actually requires this behavior,
  23 // but it's what the current map implementation does.
  24 func TestNegativeZero(t *testing.T) {
  25         m := make(map[float64]bool, 0)
  26
  27         m[+0.0] = true
  28         m[math.Copysign(0.0, -1.0)] = true // should overwrite +0 entry
  29
  30         if len(m) != 1 {
  31                 t.Error("length wrong")
  32         }
  33
  34         for k := range m {
  35                 if math.Copysign(1.0, k) > 0 {
  36                         t.Error("wrong sign")
  37                 }
  38         }
  39
  40         m = make(map[float64]bool, 0)
  41         m[math.Copysign(0.0, -1.0)] = true
  42         m[+0.0] = true // should overwrite -0.0 entry
  43
  44         if len(m) != 1 {
  45                 t.Error("length wrong")
  46         }
  47
  48         for k := range m {
  49                 if math.Copysign(1.0, k) < 0 {
  50                         t.Error("wrong sign")
  51                 }
  52         }
  53 }
  54
  55 // nan is a good test because nan != nan, and nan has
  56 // a randomized hash value.
  57 func TestNan(t *testing.T) {
  58         m := make(map[float64]int, 0)
  59         nan := math.NaN()
  60         m[nan] = 1
  61         m[nan] = 2
  62         m[nan] = 4
  63         if len(m) != 3 {
  64                 t.Error("length wrong")
  65         }
  66         s := 0
  67         for k, v := range m {
  68                 if k == k {
  69                         t.Error("nan disappeared")
  70                 }
  71                 if (v & (v - 1)) != 0 {
  72                         t.Error("value wrong")
  73                 }
  74                 s |= v
  75         }
  76         if s != 7 {
  77                 t.Error("values wrong")
  78         }
  79 }
  80
  81 // Maps aren't actually copied on assignment.
  82 func TestAlias(t *testing.T) {
  83         m := make(map[int]int, 0)
  84         m[0] = 5
  85         n := m
  86         n[0] = 6
  87         if m[0] != 6 {
  88                 t.Error("alias didn't work")
  89         }
  90 }
  91
  92 func TestGrowWithNaN(t *testing.T) {
  93         m := make(map[float64]int, 4)
  94         nan := math.NaN()
  95         m[nan] = 1
  96         m[nan] = 2
  97         m[nan] = 4
  98         cnt := 0
  99         s := 0
 100         growflag := true
 101         for k, v := range m {
 102                 if growflag {
 103                         // force a hashtable resize
 104                         for i := 0; i < 100; i++ {
 105                                 m[float64(i)] = i
 106                         }
 107                         growflag = false
 108                 }
 109                 if k != k {
 110                         cnt++
 111                         s |= v
 112                 }
 113         }
 114         if cnt != 3 {
 115                 t.Error("NaN keys lost during grow")
 116         }
 117         if s != 7 {
 118                 t.Error("NaN values lost during grow")
 119         }
 120 }
 121
 122 type FloatInt struct {
 123         x float64
 124         y int
 125 }
 126
 127 func TestGrowWithNegativeZero(t *testing.T) {
 128         negzero := math.Copysign(0.0, -1.0)
 129         m := make(map[FloatInt]int, 4)
 130         m[FloatInt{0.0, 0}] = 1
 131         m[FloatInt{0.0, 1}] = 2
 132         m[FloatInt{0.0, 2}] = 4
 133         m[FloatInt{0.0, 3}] = 8
 134         growflag := true
 135         s := 0
 136         cnt := 0
 137         negcnt := 0
 138         // The first iteration should return the +0 key.
 139         // The subsequent iterations should return the -0 key.
 140         // I'm not really sure this is required by the spec,
 141         // but it makes sense.
 142         // TODO: are we allowed to get the first entry returned again???
 143         for k, v := range m {
 144                 if v == 0 {
 145                         continue
 146                 } // ignore entries added to grow table
 147                 cnt++
 148                 if math.Copysign(1.0, k.x) < 0 {
 149                         if v&16 == 0 {
 150                                 t.Error("key/value not updated together 1")
 151                         }
 152                         negcnt++
 153                         s |= v & 15
 154                 } else {
 155                         if v&16 == 16 {
 156                                 t.Error("key/value not updated together 2", k, v)
 157                         }
 158                         s |= v
 159                 }
 160                 if growflag {
 161                         // force a hashtable resize
 162                         for i := 0; i < 100; i++ {
 163                                 m[FloatInt{3.0, i}] = 0
 164                         }
 165                         // then change all the entries
 166                         // to negative zero
 167                         m[FloatInt{negzero, 0}] = 1 | 16
 168                         m[FloatInt{negzero, 1}] = 2 | 16
 169                         m[FloatInt{negzero, 2}] = 4 | 16
 170                         m[FloatInt{negzero, 3}] = 8 | 16
 171                         growflag = false
 172                 }
 173         }
 174         if s != 15 {
 175                 t.Error("entry missing", s)
 176         }
 177         if cnt != 4 {
 178                 t.Error("wrong number of entries returned by iterator", cnt)
 179         }
 180         if negcnt != 3 {
 181                 t.Error("update to negzero missed by iteration", negcnt)
 182         }
 183 }
 184
 185 func TestIterGrowAndDelete(t *testing.T) {
 186         m := make(map[int]int, 4)
 187         for i := 0; i < 100; i++ {
 188                 m[i] = i
 189         }
 190         growflag := true
 191         for k := range m {
 192                 if growflag {
 193                         // grow the table
 194                         for i := 100; i < 1000; i++ {
 195                                 m[i] = i
 196                         }
 197                         // delete all odd keys
 198                         for i := 1; i < 1000; i += 2 {
 199                                 delete(m, i)
 200                         }
 201                         growflag = false
 202                 } else {
 203                         if k&1 == 1 {
 204                                 t.Error("odd value returned")
 205                         }
 206                 }
 207         }
 208 }
 209
 210 // make sure old bucket arrays don't get GCd while
 211 // an iterator is still using them.
 212 func TestIterGrowWithGC(t *testing.T) {
 213         m := make(map[int]int, 4)
 214         for i := 0; i < 16; i++ {
 215                 m[i] = i
 216         }
 217         growflag := true
 218         bitmask := 0
 219         for k := range m {
 220                 if k < 16 {
 221                         bitmask |= 1 << uint(k)
 222                 }
 223                 if growflag {
 224                         // grow the table
 225                         for i := 100; i < 1000; i++ {
 226                                 m[i] = i
 227                         }
 228                         // trigger a gc
 229                         runtime.GC()
 230                         growflag = false
 231                 }
 232         }
 233         if bitmask != 1<<16-1 {
 234                 t.Error("missing key", bitmask)
 235         }
 236 }
 237
 238 func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
 239         t.Parallel()
 240         if runtime.GOMAXPROCS(-1) == 1 {
 241                 if runtime.GOARCH == "s390" {
 242                         // Test uses too much address space on 31-bit S390.
 243                         defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(8))
 244                 } else {
 245                         defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
 246                 }
 247         }
 248         numLoop := 10
 249         numGrowStep := 250
 250         numReader := 16
 251         if testing.Short() {
 252                 numLoop, numGrowStep = 2, 100
 253         }
 254         for i := 0; i < numLoop; i++ {
 255                 m := make(map[int]int, 0)
 256                 for gs := 0; gs < numGrowStep; gs++ {
 257                         m[gs] = gs
 258                         var wg sync.WaitGroup
 259                         wg.Add(numReader * 2)
 260                         for nr := 0; nr < numReader; nr++ {
 261                                 go func() {
 262                                         defer wg.Done()
 263                                         for range m {
 264                                         }
 265                                 }()
 266                                 go func() {
 267                                         defer wg.Done()
 268                                         for key := 0; key < gs; key++ {
 269                                                 _ = m[key]
 270                                         }
 271                                 }()
 272                                 if useReflect {
 273                                         wg.Add(1)
 274                                         go func() {
 275                                                 defer wg.Done()
 276                                                 mv := reflect.ValueOf(m)
 277                                                 keys := mv.MapKeys()
 278                                                 for _, k := range keys {
 279                                                         mv.MapIndex(k)
 280                                                 }
 281                                         }()
 282                                 }
 283                         }
 284                         wg.Wait()
 285                 }
 286         }
 287 }
 288
 289 func TestConcurrentReadsAfterGrowth(t *testing.T) {
 290         testConcurrentReadsAfterGrowth(t, false)
 291 }
 292
 293 func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
 294         testConcurrentReadsAfterGrowth(t, true)
 295 }
 296
 297 func TestBigItems(t *testing.T) {
 298         var key [256]string
 299         for i := 0; i < 256; i++ {
 300                 key[i] = "foo"
 301         }
 302         m := make(map[[256]string][256]string, 4)
 303         for i := 0; i < 100; i++ {
 304                 key[37] = fmt.Sprintf("string%02d", i)
 305                 m[key] = key
 306         }
 307         var keys [100]string
 308         var values [100]string
 309         i := 0
 310         for k, v := range m {
 311                 keys[i] = k[37]
 312                 values[i] = v[37]
 313                 i++
 314         }
 315         sort.Strings(keys[:])
 316         sort.Strings(values[:])
 317         for i := 0; i < 100; i++ {
 318                 if keys[i] != fmt.Sprintf("string%02d", i) {
 319                         t.Errorf("#%d: missing key: %v", i, keys[i])
 320                 }
 321                 if values[i] != fmt.Sprintf("string%02d", i) {
 322                         t.Errorf("#%d: missing value: %v", i, values[i])
 323                 }
 324         }
 325 }
 326
 327 func TestMapHugeZero(t *testing.T) {
 328         type T [4000]byte
 329         m := map[int]T{}
 330         x := m[0]
 331         if x != (T{}) {
 332                 t.Errorf("map value not zero")
 333         }
 334         y, ok := m[0]
 335         if ok {
 336                 t.Errorf("map value should be missing")
 337         }
 338         if y != (T{}) {
 339                 t.Errorf("map value not zero")
 340         }
 341 }
 342
 343 type empty struct {
 344 }
 345
 346 func TestEmptyKeyAndValue(t *testing.T) {
 347         a := make(map[int]empty, 4)
 348         b := make(map[empty]int, 4)
 349         c := make(map[empty]empty, 4)
 350         a[0] = empty{}
 351         b[empty{}] = 0
 352         b[empty{}] = 1
 353         c[empty{}] = empty{}
 354
 355         if len(a) != 1 {
 356                 t.Errorf("empty value insert problem")
 357         }
 358         if b[empty{}] != 1 {
 359                 t.Errorf("empty key returned wrong value")
 360         }
 361 }
 362
 363 // Tests a map with a single bucket, with same-lengthed short keys
 364 // ("quick keys") as well as long keys.
 365 func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
 366         testMapLookups(t, map[string]string{
 367                 "x":    "x1val",
 368                 "xx":   "x2val",
 369                 "foo":  "fooval",
 370                 "bar":  "barval", // same key length as "foo"
 371                 "xxxx": "x4val",
 372                 strings.Repeat("x", 128): "longval1",
 373                 strings.Repeat("y", 128): "longval2",
 374         })
 375 }
 376
 377 // Tests a map with a single bucket, with all keys having different lengths.
 378 func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
 379         testMapLookups(t, map[string]string{
 380                 "x":                      "x1val",
 381                 "xx":                     "x2val",
 382                 "foo":                    "fooval",
 383                 "xxxx":                   "x4val",
 384                 "xxxxx":                  "x5val",
 385                 "xxxxxx":                 "x6val",
 386                 strings.Repeat("x", 128): "longval",
 387         })
 388 }
 389
 390 func testMapLookups(t *testing.T, m map[string]string) {
 391         for k, v := range m {
 392                 if m[k] != v {
 393                         t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
 394                 }
 395         }
 396 }
 397
 398 // Tests whether the iterator returns the right elements when
 399 // started in the middle of a grow, when the keys are NaNs.
 400 func TestMapNanGrowIterator(t *testing.T) {
 401         m := make(map[float64]int)
 402         nan := math.NaN()
 403         const nBuckets = 16
 404         // To fill nBuckets buckets takes LOAD * nBuckets keys.
 405         nKeys := int(nBuckets * *runtime.HashLoad)
 406
 407         // Get map to full point with nan keys.
 408         for i := 0; i < nKeys; i++ {
 409                 m[nan] = i
 410         }
 411         // Trigger grow
 412         m[1.0] = 1
 413         delete(m, 1.0)
 414
 415         // Run iterator
 416         found := make(map[int]struct{})
 417         for _, v := range m {
 418                 if v != -1 {
 419                         if _, repeat := found[v]; repeat {
 420                                 t.Fatalf("repeat of value %d", v)
 421                         }
 422                         found[v] = struct{}{}
 423                 }
 424                 if len(found) == nKeys/2 {
 425                         // Halfway through iteration, finish grow.
 426                         for i := 0; i < nBuckets; i++ {
 427                                 delete(m, 1.0)
 428                         }
 429                 }
 430         }
 431         if len(found) != nKeys {
 432                 t.Fatalf("missing value")
 433         }
 434 }
 435
 436 func TestMapIterOrder(t *testing.T) {
 437         for _, n := range [...]int{3, 7, 9, 15} {
 438                 for i := 0; i < 1000; i++ {
 439                         // Make m be {0: true, 1: true, ..., n-1: true}.
 440                         m := make(map[int]bool)
 441                         for i := 0; i < n; i++ {
 442                                 m[i] = true
 443                         }
 444                         // Check that iterating over the map produces at least two different orderings.
 445                         ord := func() []int {
 446                                 var s []int
 447                                 for key := range m {
 448                                         s = append(s, key)
 449                                 }
 450                                 return s
 451                         }
 452                         first := ord()
 453                         ok := false
 454                         for try := 0; try < 100; try++ {
 455                                 if !reflect.DeepEqual(first, ord()) {
 456                                         ok = true
 457                                         break
 458                                 }
 459                         }
 460                         if !ok {
 461                                 t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
 462                                 break
 463                         }
 464                 }
 465         }
 466 }
 467
 468 // Issue 8410
 469 func TestMapSparseIterOrder(t *testing.T) {
 470         // Run several rounds to increase the probability
 471         // of failure. One is not enough.
 472 NextRound:
 473         for round := 0; round < 10; round++ {
 474                 m := make(map[int]bool)
 475                 // Add 1000 items, remove 980.
 476                 for i := 0; i < 1000; i++ {
 477                         m[i] = true
 478                 }
 479                 for i := 20; i < 1000; i++ {
 480                         delete(m, i)
 481                 }
 482
 483                 var first []int
 484                 for i := range m {
 485                         first = append(first, i)
 486                 }
 487
 488                 // 800 chances to get a different iteration order.
 489                 // See bug 8736 for why we need so many tries.
 490                 for n := 0; n < 800; n++ {
 491                         idx := 0
 492                         for i := range m {
 493                                 if i != first[idx] {
 494                                         // iteration order changed.
 495                                         continue NextRound
 496                                 }
 497                                 idx++
 498                         }
 499                 }
 500                 t.Fatalf("constant iteration order on round %d: %v", round, first)
 501         }
 502 }
 503
 504 func TestMapStringBytesLookup(t *testing.T) {
 505         // Use large string keys to avoid small-allocation coalescing,
 506         // which can cause AllocsPerRun to report lower counts than it should.
 507         m := map[string]int{
 508                 "1000000000000000000000000000000000000000000000000": 1,
 509                 "2000000000000000000000000000000000000000000000000": 2,
 510         }
 511         buf := []byte("1000000000000000000000000000000000000000000000000")
 512         if x := m[string(buf)]; x != 1 {
 513                 t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
 514         }
 515         buf[0] = '2'
 516         if x := m[string(buf)]; x != 2 {
 517                 t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
 518         }
 519
 520         t.Skip("does not work on gccgo without better escape analysis")
 521
 522         var x int
 523         n := testing.AllocsPerRun(100, func() {
 524                 x += m[string(buf)]
 525         })
 526         if n != 0 {
 527                 t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
 528         }
 529
 530         x = 0
 531         n = testing.AllocsPerRun(100, func() {
 532                 y, ok := m[string(buf)]
 533                 if !ok {
 534                         panic("!ok")
 535                 }
 536                 x += y
 537         })
 538         if n != 0 {
 539                 t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
 540         }
 541 }
 542
 543 func TestMapLargeKeyNoPointer(t *testing.T) {
 544         const (
 545                 I = 1000
 546                 N = 64
 547         )
 548         type T [N]int
 549         m := make(map[T]int)
 550         for i := 0; i < I; i++ {
 551                 var v T
 552                 for j := 0; j < N; j++ {
 553                         v[j] = i + j
 554                 }
 555                 m[v] = i
 556         }
 557         runtime.GC()
 558         for i := 0; i < I; i++ {
 559                 var v T
 560                 for j := 0; j < N; j++ {
 561                         v[j] = i + j
 562                 }
 563                 if m[v] != i {
 564                         t.Fatalf("corrupted map: want %+v, got %+v", i, m[v])
 565                 }
 566         }
 567 }
 568
 569 func TestMapLargeValNoPointer(t *testing.T) {
 570         const (
 571                 I = 1000
 572                 N = 64
 573         )
 574         type T [N]int
 575         m := make(map[int]T)
 576         for i := 0; i < I; i++ {
 577                 var v T
 578                 for j := 0; j < N; j++ {
 579                         v[j] = i + j
 580                 }
 581                 m[i] = v
 582         }
 583         runtime.GC()
 584         for i := 0; i < I; i++ {
 585                 var v T
 586                 for j := 0; j < N; j++ {
 587                         v[j] = i + j
 588                 }
 589                 v1 := m[i]
 590                 for j := 0; j < N; j++ {
 591                         if v1[j] != v[j] {
 592                                 t.Fatalf("corrupted map: want %+v, got %+v", v, v1)
 593                         }
 594                 }
 595         }
 596 }
 597
 598 // Test that making a map with a large or invalid hint
 599 // doesn't panic. (Issue 19926).
 600 func TestIgnoreBogusMapHint(t *testing.T) {
 601         for _, hint := range []int64{-1, 1 << 62} {
 602                 _ = make(map[int]int, hint)
 603         }
 604 }
 605
 606 var mapSink map[int]int
 607
 608 var mapBucketTests = [...]struct {
 609         n        int // n is the number of map elements
 610         noescape int // number of expected buckets for non-escaping map
 611         escape   int // number of expected buckets for escaping map
 612 }{
 613         {-(1 << 30), 1, 1},
 614         {-1, 1, 1},
 615         {0, 1, 1},
 616         {1, 1, 1},
 617         {8, 1, 1},
 618         {9, 2, 2},
 619         {13, 2, 2},
 620         {14, 4, 4},
 621         {26, 4, 4},
 622 }
 623
 624 func TestMapBuckets(t *testing.T) {
 625         // Test that maps of different sizes have the right number of buckets.
 626         // Non-escaping maps with small buckets (like map[int]int) never
 627         // have a nil bucket pointer due to starting with preallocated buckets
 628         // on the stack. Escaping maps start with a non-nil bucket pointer if
 629         // hint size is above bucketCnt and thereby have more than one bucket.
 630         // These tests depend on bucketCnt and loadFactor* in hashmap.go.
 631         t.Run("mapliteral", func(t *testing.T) {
 632                 for _, tt := range mapBucketTests {
 633                         localMap := map[int]int{}
 634                         // Skip test on gccgo until escape analysis is
 635                         // turned on.
 636                         if runtime.MapBucketsPointerIsNil(localMap) && runtime.Compiler != "gccgo" {
 637                                 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
 638                         }
 639                         for i := 0; i < tt.n; i++ {
 640                                 localMap[i] = i
 641                         }
 642                         if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
 643                                 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
 644                         }
 645                         escapingMap := map[int]int{}
 646                         if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
 647                                 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
 648                         }
 649                         for i := 0; i < tt.n; i++ {
 650                                 escapingMap[i] = i
 651                         }
 652                         if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
 653                                 t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got)
 654                         }
 655                         mapSink = escapingMap
 656                 }
 657         })
 658         t.Run("nohint", func(t *testing.T) {
 659                 for _, tt := range mapBucketTests {
 660                         localMap := make(map[int]int)
 661                         // Skip test on gccgo until escape analysis is
 662                         // turned on.
 663                         if runtime.MapBucketsPointerIsNil(localMap) && runtime.Compiler != "gccgo" {
 664                                 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
 665                         }
 666                         for i := 0; i < tt.n; i++ {
 667                                 localMap[i] = i
 668                         }
 669                         if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
 670                                 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
 671                         }
 672                         escapingMap := make(map[int]int)
 673                         if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
 674                                 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
 675                         }
 676                         for i := 0; i < tt.n; i++ {
 677                                 escapingMap[i] = i
 678                         }
 679                         if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
 680                                 t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
 681                         }
 682                         mapSink = escapingMap
 683                 }
 684         })
 685         t.Run("makemap", func(t *testing.T) {
 686                 for _, tt := range mapBucketTests {
 687                         localMap := make(map[int]int, tt.n)
 688                         // Skip test on gccgo until escape analysis is
 689                         // turned on.
 690                         if runtime.MapBucketsPointerIsNil(localMap) && runtime.Compiler != "gccgo" {
 691                                 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
 692                         }
 693                         for i := 0; i < tt.n; i++ {
 694                                 localMap[i] = i
 695                         }
 696                         if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
 697                                 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
 698                         }
 699                         escapingMap := make(map[int]int, tt.n)
 700                         if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
 701                                 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
 702                         }
 703                         for i := 0; i < tt.n; i++ {
 704                                 escapingMap[i] = i
 705                         }
 706                         if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
 707                                 t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
 708                         }
 709                         mapSink = escapingMap
 710                 }
 711         })
 712         t.Run("makemap64", func(t *testing.T) {
 713                 for _, tt := range mapBucketTests {
 714                         localMap := make(map[int]int, int64(tt.n))
 715                         // Skip test on gccgo until escape analysis is
 716                         // turned on.
 717                         if runtime.MapBucketsPointerIsNil(localMap) && runtime.Compiler != "gccgo" {
 718                                 t.Errorf("no escape: buckets pointer is nil for non-escaping map")
 719                         }
 720                         for i := 0; i < tt.n; i++ {
 721                                 localMap[i] = i
 722                         }
 723                         if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
 724                                 t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
 725                         }
 726                         escapingMap := make(map[int]int, tt.n)
 727                         if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
 728                                 t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
 729                         }
 730                         for i := 0; i < tt.n; i++ {
 731                                 escapingMap[i] = i
 732                         }
 733                         if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
 734                                 t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
 735                         }
 736                         mapSink = escapingMap
 737                 }
 738         })
 739
 740 }
 741
 742 func benchmarkMapPop(b *testing.B, n int) {
 743         m := map[int]int{}
 744         for i := 0; i < b.N; i++ {
 745                 for j := 0; j < n; j++ {
 746                         m[j] = j
 747                 }
 748                 for j := 0; j < n; j++ {
 749                         // Use iterator to pop an element.
 750                         // We want this to be fast, see issue 8412.
 751                         for k := range m {
 752                                 delete(m, k)
 753                                 break
 754                         }
 755                 }
 756         }
 757 }
 758
 759 func BenchmarkMapPop100(b *testing.B)   { benchmarkMapPop(b, 100) }
 760 func BenchmarkMapPop1000(b *testing.B)  { benchmarkMapPop(b, 1000) }
 761 func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) }
 762
 763 var testNonEscapingMapVariable int = 8
 764
 765 func TestNonEscapingMap(t *testing.T) {
 766         t.Skip("does not work on gccgo without better escape analysis")
 767         n := testing.AllocsPerRun(1000, func() {
 768                 m := map[int]int{}
 769                 m[0] = 0
 770         })
 771         if n != 0 {
 772                 t.Fatalf("mapliteral: want 0 allocs, got %v", n)
 773         }
 774         n = testing.AllocsPerRun(1000, func() {
 775                 m := make(map[int]int)
 776                 m[0] = 0
 777         })
 778         if n != 0 {
 779                 t.Fatalf("no hint: want 0 allocs, got %v", n)
 780         }
 781         n = testing.AllocsPerRun(1000, func() {
 782                 m := make(map[int]int, 8)
 783                 m[0] = 0
 784         })
 785         if n != 0 {
 786                 t.Fatalf("with small hint: want 0 allocs, got %v", n)
 787         }
 788         n = testing.AllocsPerRun(1000, func() {
 789                 m := make(map[int]int, testNonEscapingMapVariable)
 790                 m[0] = 0
 791         })
 792         if n != 0 {
 793                 t.Fatalf("with variable hint: want 0 allocs, got %v", n)
 794         }
 795
 796 }
 797
 798 func benchmarkMapAssignInt32(b *testing.B, n int) {
 799         a := make(map[int32]int)
 800         for i := 0; i < b.N; i++ {
 801                 a[int32(i&(n-1))] = i
 802         }
 803 }
 804
 805 func benchmarkMapDeleteInt32(b *testing.B, n int) {
 806         a := make(map[int32]int, n)
 807         b.ResetTimer()
 808         for i := 0; i < b.N; i++ {
 809                 if len(a) == 0 {
 810                         b.StopTimer()
 811                         for j := i; j < i+n; j++ {
 812                                 a[int32(j)] = j
 813                         }
 814                         b.StartTimer()
 815                 }
 816                 delete(a, int32(i))
 817         }
 818 }
 819
 820 func benchmarkMapAssignInt64(b *testing.B, n int) {
 821         a := make(map[int64]int)
 822         for i := 0; i < b.N; i++ {
 823                 a[int64(i&(n-1))] = i
 824         }
 825 }
 826
 827 func benchmarkMapDeleteInt64(b *testing.B, n int) {
 828         a := make(map[int64]int, n)
 829         b.ResetTimer()
 830         for i := 0; i < b.N; i++ {
 831                 if len(a) == 0 {
 832                         b.StopTimer()
 833                         for j := i; j < i+n; j++ {
 834                                 a[int64(j)] = j
 835                         }
 836                         b.StartTimer()
 837                 }
 838                 delete(a, int64(i))
 839         }
 840 }
 841
 842 func benchmarkMapAssignStr(b *testing.B, n int) {
 843         k := make([]string, n)
 844         for i := 0; i < len(k); i++ {
 845                 k[i] = strconv.Itoa(i)
 846         }
 847         b.ResetTimer()
 848         a := make(map[string]int)
 849         for i := 0; i < b.N; i++ {
 850                 a[k[i&(n-1)]] = i
 851         }
 852 }
 853
 854 func benchmarkMapDeleteStr(b *testing.B, n int) {
 855         i2s := make([]string, n)
 856         for i := 0; i < n; i++ {
 857                 i2s[i] = strconv.Itoa(i)
 858         }
 859         a := make(map[string]int, n)
 860         b.ResetTimer()
 861         k := 0
 862         for i := 0; i < b.N; i++ {
 863                 if len(a) == 0 {
 864                         b.StopTimer()
 865                         for j := 0; j < n; j++ {
 866                                 a[i2s[j]] = j
 867                         }
 868                         k = i
 869                         b.StartTimer()
 870                 }
 871                 delete(a, i2s[i-k])
 872         }
 873 }
 874
 875 func runWith(f func(*testing.B, int), v ...int) func(*testing.B) {
 876         return func(b *testing.B) {
 877                 for _, n := range v {
 878                         b.Run(strconv.Itoa(n), func(b *testing.B) { f(b, n) })
 879                 }
 880         }
 881 }
 882
 883 func BenchmarkMapAssign(b *testing.B) {
 884         b.Run("Int32", runWith(benchmarkMapAssignInt32, 1<<8, 1<<16))
 885         b.Run("Int64", runWith(benchmarkMapAssignInt64, 1<<8, 1<<16))
 886         b.Run("Str", runWith(benchmarkMapAssignStr, 1<<8, 1<<16))
 887 }
 888
 889 func BenchmarkMapDelete(b *testing.B) {
 890         b.Run("Int32", runWith(benchmarkMapDeleteInt32, 100, 1000, 10000))
 891         b.Run("Int64", runWith(benchmarkMapDeleteInt64, 100, 1000, 10000))
 892         b.Run("Str", runWith(benchmarkMapDeleteStr, 100, 1000, 10000))
 893 }