Source file src/runtime/map_test.go

Documentation: runtime

     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  	"runtime/internal/sys"
    13  	"sort"
    14  	"strconv"
    15  	"strings"
    16  	"sync"
    17  	"testing"
    18  )
    19  
    20  func 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.
    36  func 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  
    67  func 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.
    88  func 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.
   101  func 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  
   112  func 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  
   129  var sinkAppend bool
   130  
   131  func 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.
   148  func 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  
   158  func 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  
   195  type FloatInt struct {
   196  	x float64
   197  	y int
   198  }
   199  
   200  func 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  
   258  func 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.
   285  func 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  
   314  func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
   315  	t.Parallel()
   316  	if runtime.GOMAXPROCS(-1) == 1 {
   317  		defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
   318  	}
   319  	numLoop := 10
   320  	numGrowStep := 250
   321  	numReader := 16
   322  	if testing.Short() {
   323  		numLoop, numGrowStep = 2, 100
   324  	}
   325  	for i := 0; i < numLoop; i++ {
   326  		m := make(map[int]int, 0)
   327  		for gs := 0; gs < numGrowStep; gs++ {
   328  			m[gs] = gs
   329  			var wg sync.WaitGroup
   330  			wg.Add(numReader * 2)
   331  			for nr := 0; nr < numReader; nr++ {
   332  				go func() {
   333  					defer wg.Done()
   334  					for range m {
   335  					}
   336  				}()
   337  				go func() {
   338  					defer wg.Done()
   339  					for key := 0; key < gs; key++ {
   340  						_ = m[key]
   341  					}
   342  				}()
   343  				if useReflect {
   344  					wg.Add(1)
   345  					go func() {
   346  						defer wg.Done()
   347  						mv := reflect.ValueOf(m)
   348  						keys := mv.MapKeys()
   349  						for _, k := range keys {
   350  							mv.MapIndex(k)
   351  						}
   352  					}()
   353  				}
   354  			}
   355  			wg.Wait()
   356  		}
   357  	}
   358  }
   359  
   360  func TestConcurrentReadsAfterGrowth(t *testing.T) {
   361  	testConcurrentReadsAfterGrowth(t, false)
   362  }
   363  
   364  func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
   365  	testConcurrentReadsAfterGrowth(t, true)
   366  }
   367  
   368  func TestBigItems(t *testing.T) {
   369  	var key [256]string
   370  	for i := 0; i < 256; i++ {
   371  		key[i] = "foo"
   372  	}
   373  	m := make(map[[256]string][256]string, 4)
   374  	for i := 0; i < 100; i++ {
   375  		key[37] = fmt.Sprintf("string%02d", i)
   376  		m[key] = key
   377  	}
   378  	var keys [100]string
   379  	var values [100]string
   380  	i := 0
   381  	for k, v := range m {
   382  		keys[i] = k[37]
   383  		values[i] = v[37]
   384  		i++
   385  	}
   386  	sort.Strings(keys[:])
   387  	sort.Strings(values[:])
   388  	for i := 0; i < 100; i++ {
   389  		if keys[i] != fmt.Sprintf("string%02d", i) {
   390  			t.Errorf("#%d: missing key: %v", i, keys[i])
   391  		}
   392  		if values[i] != fmt.Sprintf("string%02d", i) {
   393  			t.Errorf("#%d: missing value: %v", i, values[i])
   394  		}
   395  	}
   396  }
   397  
   398  func TestMapHugeZero(t *testing.T) {
   399  	type T [4000]byte
   400  	m := map[int]T{}
   401  	x := m[0]
   402  	if x != (T{}) {
   403  		t.Errorf("map value not zero")
   404  	}
   405  	y, ok := m[0]
   406  	if ok {
   407  		t.Errorf("map value should be missing")
   408  	}
   409  	if y != (T{}) {
   410  		t.Errorf("map value not zero")
   411  	}
   412  }
   413  
   414  type empty struct {
   415  }
   416  
   417  func TestEmptyKeyAndValue(t *testing.T) {
   418  	a := make(map[int]empty, 4)
   419  	b := make(map[empty]int, 4)
   420  	c := make(map[empty]empty, 4)
   421  	a[0] = empty{}
   422  	b[empty{}] = 0
   423  	b[empty{}] = 1
   424  	c[empty{}] = empty{}
   425  
   426  	if len(a) != 1 {
   427  		t.Errorf("empty value insert problem")
   428  	}
   429  	if b[empty{}] != 1 {
   430  		t.Errorf("empty key returned wrong value")
   431  	}
   432  }
   433  
   434  // Tests a map with a single bucket, with same-lengthed short keys
   435  // ("quick keys") as well as long keys.
   436  func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
   437  	testMapLookups(t, map[string]string{
   438  		"x":                      "x1val",
   439  		"xx":                     "x2val",
   440  		"foo":                    "fooval",
   441  		"bar":                    "barval", // same key length as "foo"
   442  		"xxxx":                   "x4val",
   443  		strings.Repeat("x", 128): "longval1",
   444  		strings.Repeat("y", 128): "longval2",
   445  	})
   446  }
   447  
   448  // Tests a map with a single bucket, with all keys having different lengths.
   449  func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
   450  	testMapLookups(t, map[string]string{
   451  		"x":                      "x1val",
   452  		"xx":                     "x2val",
   453  		"foo":                    "fooval",
   454  		"xxxx":                   "x4val",
   455  		"xxxxx":                  "x5val",
   456  		"xxxxxx":                 "x6val",
   457  		strings.Repeat("x", 128): "longval",
   458  	})
   459  }
   460  
   461  func testMapLookups(t *testing.T, m map[string]string) {
   462  	for k, v := range m {
   463  		if m[k] != v {
   464  			t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
   465  		}
   466  	}
   467  }
   468  
   469  // Tests whether the iterator returns the right elements when
   470  // started in the middle of a grow, when the keys are NaNs.
   471  func TestMapNanGrowIterator(t *testing.T) {
   472  	m := make(map[float64]int)
   473  	nan := math.NaN()
   474  	const nBuckets = 16
   475  	// To fill nBuckets buckets takes LOAD * nBuckets keys.
   476  	nKeys := int(nBuckets * *runtime.HashLoad)
   477  
   478  	// Get map to full point with nan keys.
   479  	for i := 0; i < nKeys; i++ {
   480  		m[nan] = i
   481  	}
   482  	// Trigger grow
   483  	m[1.0] = 1
   484  	delete(m, 1.0)
   485  
   486  	// Run iterator
   487  	found := make(map[int]struct{})
   488  	for _, v := range m {
   489  		if v != -1 {
   490  			if _, repeat := found[v]; repeat {
   491  				t.Fatalf("repeat of value %d", v)
   492  			}
   493  			found[v] = struct{}{}
   494  		}
   495  		if len(found) == nKeys/2 {
   496  			// Halfway through iteration, finish grow.
   497  			for i := 0; i < nBuckets; i++ {
   498  				delete(m, 1.0)
   499  			}
   500  		}
   501  	}
   502  	if len(found) != nKeys {
   503  		t.Fatalf("missing value")
   504  	}
   505  }
   506  
   507  func TestMapIterOrder(t *testing.T) {
   508  	for _, n := range [...]int{3, 7, 9, 15} {
   509  		for i := 0; i < 1000; i++ {
   510  			// Make m be {0: true, 1: true, ..., n-1: true}.
   511  			m := make(map[int]bool)
   512  			for i := 0; i < n; i++ {
   513  				m[i] = true
   514  			}
   515  			// Check that iterating over the map produces at least two different orderings.
   516  			ord := func() []int {
   517  				var s []int
   518  				for key := range m {
   519  					s = append(s, key)
   520  				}
   521  				return s
   522  			}
   523  			first := ord()
   524  			ok := false
   525  			for try := 0; try < 100; try++ {
   526  				if !reflect.DeepEqual(first, ord()) {
   527  					ok = true
   528  					break
   529  				}
   530  			}
   531  			if !ok {
   532  				t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
   533  				break
   534  			}
   535  		}
   536  	}
   537  }
   538  
   539  // Issue 8410
   540  func TestMapSparseIterOrder(t *testing.T) {
   541  	// Run several rounds to increase the probability
   542  	// of failure. One is not enough.
   543  NextRound:
   544  	for round := 0; round < 10; round++ {
   545  		m := make(map[int]bool)
   546  		// Add 1000 items, remove 980.
   547  		for i := 0; i < 1000; i++ {
   548  			m[i] = true
   549  		}
   550  		for i := 20; i < 1000; i++ {
   551  			delete(m, i)
   552  		}
   553  
   554  		var first []int
   555  		for i := range m {
   556  			first = append(first, i)
   557  		}
   558  
   559  		// 800 chances to get a different iteration order.
   560  		// See bug 8736 for why we need so many tries.
   561  		for n := 0; n < 800; n++ {
   562  			idx := 0
   563  			for i := range m {
   564  				if i != first[idx] {
   565  					// iteration order changed.
   566  					continue NextRound
   567  				}
   568  				idx++
   569  			}
   570  		}
   571  		t.Fatalf("constant iteration order on round %d: %v", round, first)
   572  	}
   573  }
   574  
   575  func TestMapStringBytesLookup(t *testing.T) {
   576  	// Use large string keys to avoid small-allocation coalescing,
   577  	// which can cause AllocsPerRun to report lower counts than it should.
   578  	m := map[string]int{
   579  		"1000000000000000000000000000000000000000000000000": 1,
   580  		"2000000000000000000000000000000000000000000000000": 2,
   581  	}
   582  	buf := []byte("1000000000000000000000000000000000000000000000000")
   583  	if x := m[string(buf)]; x != 1 {
   584  		t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
   585  	}
   586  	buf[0] = '2'
   587  	if x := m[string(buf)]; x != 2 {
   588  		t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
   589  	}
   590  
   591  	var x int
   592  	n := testing.AllocsPerRun(100, func() {
   593  		x += m[string(buf)]
   594  	})
   595  	if n != 0 {
   596  		t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
   597  	}
   598  
   599  	x = 0
   600  	n = testing.AllocsPerRun(100, func() {
   601  		y, ok := m[string(buf)]
   602  		if !ok {
   603  			panic("!ok")
   604  		}
   605  		x += y
   606  	})
   607  	if n != 0 {
   608  		t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
   609  	}
   610  }
   611  
   612  func TestMapLargeKeyNoPointer(t *testing.T) {
   613  	const (
   614  		I = 1000
   615  		N = 64
   616  	)
   617  	type T [N]int
   618  	m := make(map[T]int)
   619  	for i := 0; i < I; i++ {
   620  		var v T
   621  		for j := 0; j < N; j++ {
   622  			v[j] = i + j
   623  		}
   624  		m[v] = i
   625  	}
   626  	runtime.GC()
   627  	for i := 0; i < I; i++ {
   628  		var v T
   629  		for j := 0; j < N; j++ {
   630  			v[j] = i + j
   631  		}
   632  		if m[v] != i {
   633  			t.Fatalf("corrupted map: want %+v, got %+v", i, m[v])
   634  		}
   635  	}
   636  }
   637  
   638  func TestMapLargeValNoPointer(t *testing.T) {
   639  	const (
   640  		I = 1000
   641  		N = 64
   642  	)
   643  	type T [N]int
   644  	m := make(map[int]T)
   645  	for i := 0; i < I; i++ {
   646  		var v T
   647  		for j := 0; j < N; j++ {
   648  			v[j] = i + j
   649  		}
   650  		m[i] = v
   651  	}
   652  	runtime.GC()
   653  	for i := 0; i < I; i++ {
   654  		var v T
   655  		for j := 0; j < N; j++ {
   656  			v[j] = i + j
   657  		}
   658  		v1 := m[i]
   659  		for j := 0; j < N; j++ {
   660  			if v1[j] != v[j] {
   661  				t.Fatalf("corrupted map: want %+v, got %+v", v, v1)
   662  			}
   663  		}
   664  	}
   665  }
   666  
   667  // Test that making a map with a large or invalid hint
   668  // doesn't panic. (Issue 19926).
   669  func TestIgnoreBogusMapHint(t *testing.T) {
   670  	for _, hint := range []int64{-1, 1 << 62} {
   671  		_ = make(map[int]int, hint)
   672  	}
   673  }
   674  
   675  var mapSink map[int]int
   676  
   677  var mapBucketTests = [...]struct {
   678  	n        int // n is the number of map elements
   679  	noescape int // number of expected buckets for non-escaping map
   680  	escape   int // number of expected buckets for escaping map
   681  }{
   682  	{-(1 << 30), 1, 1},
   683  	{-1, 1, 1},
   684  	{0, 1, 1},
   685  	{1, 1, 1},
   686  	{8, 1, 1},
   687  	{9, 2, 2},
   688  	{13, 2, 2},
   689  	{14, 4, 4},
   690  	{26, 4, 4},
   691  }
   692  
   693  func TestMapBuckets(t *testing.T) {
   694  	// Test that maps of different sizes have the right number of buckets.
   695  	// Non-escaping maps with small buckets (like map[int]int) never
   696  	// have a nil bucket pointer due to starting with preallocated buckets
   697  	// on the stack. Escaping maps start with a non-nil bucket pointer if
   698  	// hint size is above bucketCnt and thereby have more than one bucket.
   699  	// These tests depend on bucketCnt and loadFactor* in map.go.
   700  	t.Run("mapliteral", func(t *testing.T) {
   701  		for _, tt := range mapBucketTests {
   702  			localMap := map[int]int{}
   703  			if runtime.MapBucketsPointerIsNil(localMap) {
   704  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   705  			}
   706  			for i := 0; i < tt.n; i++ {
   707  				localMap[i] = i
   708  			}
   709  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   710  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   711  			}
   712  			escapingMap := map[int]int{}
   713  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   714  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   715  			}
   716  			for i := 0; i < tt.n; i++ {
   717  				escapingMap[i] = i
   718  			}
   719  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   720  				t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   721  			}
   722  			mapSink = escapingMap
   723  		}
   724  	})
   725  	t.Run("nohint", func(t *testing.T) {
   726  		for _, tt := range mapBucketTests {
   727  			localMap := make(map[int]int)
   728  			if runtime.MapBucketsPointerIsNil(localMap) {
   729  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   730  			}
   731  			for i := 0; i < tt.n; i++ {
   732  				localMap[i] = i
   733  			}
   734  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   735  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   736  			}
   737  			escapingMap := make(map[int]int)
   738  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   739  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   740  			}
   741  			for i := 0; i < tt.n; i++ {
   742  				escapingMap[i] = i
   743  			}
   744  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   745  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   746  			}
   747  			mapSink = escapingMap
   748  		}
   749  	})
   750  	t.Run("makemap", func(t *testing.T) {
   751  		for _, tt := range mapBucketTests {
   752  			localMap := make(map[int]int, tt.n)
   753  			if runtime.MapBucketsPointerIsNil(localMap) {
   754  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   755  			}
   756  			for i := 0; i < tt.n; i++ {
   757  				localMap[i] = i
   758  			}
   759  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   760  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   761  			}
   762  			escapingMap := make(map[int]int, tt.n)
   763  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   764  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   765  			}
   766  			for i := 0; i < tt.n; i++ {
   767  				escapingMap[i] = i
   768  			}
   769  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   770  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   771  			}
   772  			mapSink = escapingMap
   773  		}
   774  	})
   775  	t.Run("makemap64", func(t *testing.T) {
   776  		for _, tt := range mapBucketTests {
   777  			localMap := make(map[int]int, int64(tt.n))
   778  			if runtime.MapBucketsPointerIsNil(localMap) {
   779  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   780  			}
   781  			for i := 0; i < tt.n; i++ {
   782  				localMap[i] = i
   783  			}
   784  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   785  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   786  			}
   787  			escapingMap := make(map[int]int, tt.n)
   788  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   789  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   790  			}
   791  			for i := 0; i < tt.n; i++ {
   792  				escapingMap[i] = i
   793  			}
   794  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   795  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   796  			}
   797  			mapSink = escapingMap
   798  		}
   799  	})
   800  
   801  }
   802  
   803  func benchmarkMapPop(b *testing.B, n int) {
   804  	m := map[int]int{}
   805  	for i := 0; i < b.N; i++ {
   806  		for j := 0; j < n; j++ {
   807  			m[j] = j
   808  		}
   809  		for j := 0; j < n; j++ {
   810  			// Use iterator to pop an element.
   811  			// We want this to be fast, see issue 8412.
   812  			for k := range m {
   813  				delete(m, k)
   814  				break
   815  			}
   816  		}
   817  	}
   818  }
   819  
   820  func BenchmarkMapPop100(b *testing.B)   { benchmarkMapPop(b, 100) }
   821  func BenchmarkMapPop1000(b *testing.B)  { benchmarkMapPop(b, 1000) }
   822  func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) }
   823  
   824  var testNonEscapingMapVariable int = 8
   825  
   826  func TestNonEscapingMap(t *testing.T) {
   827  	n := testing.AllocsPerRun(1000, func() {
   828  		m := map[int]int{}
   829  		m[0] = 0
   830  	})
   831  	if n != 0 {
   832  		t.Fatalf("mapliteral: want 0 allocs, got %v", n)
   833  	}
   834  	n = testing.AllocsPerRun(1000, func() {
   835  		m := make(map[int]int)
   836  		m[0] = 0
   837  	})
   838  	if n != 0 {
   839  		t.Fatalf("no hint: want 0 allocs, got %v", n)
   840  	}
   841  	n = testing.AllocsPerRun(1000, func() {
   842  		m := make(map[int]int, 8)
   843  		m[0] = 0
   844  	})
   845  	if n != 0 {
   846  		t.Fatalf("with small hint: want 0 allocs, got %v", n)
   847  	}
   848  	n = testing.AllocsPerRun(1000, func() {
   849  		m := make(map[int]int, testNonEscapingMapVariable)
   850  		m[0] = 0
   851  	})
   852  	if n != 0 {
   853  		t.Fatalf("with variable hint: want 0 allocs, got %v", n)
   854  	}
   855  
   856  }
   857  
   858  func benchmarkMapAssignInt32(b *testing.B, n int) {
   859  	a := make(map[int32]int)
   860  	for i := 0; i < b.N; i++ {
   861  		a[int32(i&(n-1))] = i
   862  	}
   863  }
   864  
   865  func benchmarkMapOperatorAssignInt32(b *testing.B, n int) {
   866  	a := make(map[int32]int)
   867  	for i := 0; i < b.N; i++ {
   868  		a[int32(i&(n-1))] += i
   869  	}
   870  }
   871  
   872  func benchmarkMapAppendAssignInt32(b *testing.B, n int) {
   873  	a := make(map[int32][]int)
   874  	b.ReportAllocs()
   875  	b.ResetTimer()
   876  	for i := 0; i < b.N; i++ {
   877  		key := int32(i & (n - 1))
   878  		a[key] = append(a[key], i)
   879  	}
   880  }
   881  
   882  func benchmarkMapDeleteInt32(b *testing.B, n int) {
   883  	a := make(map[int32]int, n)
   884  	b.ResetTimer()
   885  	for i := 0; i < b.N; i++ {
   886  		if len(a) == 0 {
   887  			b.StopTimer()
   888  			for j := i; j < i+n; j++ {
   889  				a[int32(j)] = j
   890  			}
   891  			b.StartTimer()
   892  		}
   893  		delete(a, int32(i))
   894  	}
   895  }
   896  
   897  func benchmarkMapAssignInt64(b *testing.B, n int) {
   898  	a := make(map[int64]int)
   899  	for i := 0; i < b.N; i++ {
   900  		a[int64(i&(n-1))] = i
   901  	}
   902  }
   903  
   904  func benchmarkMapOperatorAssignInt64(b *testing.B, n int) {
   905  	a := make(map[int64]int)
   906  	for i := 0; i < b.N; i++ {
   907  		a[int64(i&(n-1))] += i
   908  	}
   909  }
   910  
   911  func benchmarkMapAppendAssignInt64(b *testing.B, n int) {
   912  	a := make(map[int64][]int)
   913  	b.ReportAllocs()
   914  	b.ResetTimer()
   915  	for i := 0; i < b.N; i++ {
   916  		key := int64(i & (n - 1))
   917  		a[key] = append(a[key], i)
   918  	}
   919  }
   920  
   921  func benchmarkMapDeleteInt64(b *testing.B, n int) {
   922  	a := make(map[int64]int, n)
   923  	b.ResetTimer()
   924  	for i := 0; i < b.N; i++ {
   925  		if len(a) == 0 {
   926  			b.StopTimer()
   927  			for j := i; j < i+n; j++ {
   928  				a[int64(j)] = j
   929  			}
   930  			b.StartTimer()
   931  		}
   932  		delete(a, int64(i))
   933  	}
   934  }
   935  
   936  func benchmarkMapAssignStr(b *testing.B, n int) {
   937  	k := make([]string, n)
   938  	for i := 0; i < len(k); i++ {
   939  		k[i] = strconv.Itoa(i)
   940  	}
   941  	b.ResetTimer()
   942  	a := make(map[string]int)
   943  	for i := 0; i < b.N; i++ {
   944  		a[k[i&(n-1)]] = i
   945  	}
   946  }
   947  
   948  func benchmarkMapOperatorAssignStr(b *testing.B, n int) {
   949  	k := make([]string, n)
   950  	for i := 0; i < len(k); i++ {
   951  		k[i] = strconv.Itoa(i)
   952  	}
   953  	b.ResetTimer()
   954  	a := make(map[string]string)
   955  	for i := 0; i < b.N; i++ {
   956  		key := k[i&(n-1)]
   957  		a[key] += key
   958  	}
   959  }
   960  
   961  func benchmarkMapAppendAssignStr(b *testing.B, n int) {
   962  	k := make([]string, n)
   963  	for i := 0; i < len(k); i++ {
   964  		k[i] = strconv.Itoa(i)
   965  	}
   966  	a := make(map[string][]string)
   967  	b.ReportAllocs()
   968  	b.ResetTimer()
   969  	for i := 0; i < b.N; i++ {
   970  		key := k[i&(n-1)]
   971  		a[key] = append(a[key], key)
   972  	}
   973  }
   974  
   975  func benchmarkMapDeleteStr(b *testing.B, n int) {
   976  	i2s := make([]string, n)
   977  	for i := 0; i < n; i++ {
   978  		i2s[i] = strconv.Itoa(i)
   979  	}
   980  	a := make(map[string]int, n)
   981  	b.ResetTimer()
   982  	k := 0
   983  	for i := 0; i < b.N; i++ {
   984  		if len(a) == 0 {
   985  			b.StopTimer()
   986  			for j := 0; j < n; j++ {
   987  				a[i2s[j]] = j
   988  			}
   989  			k = i
   990  			b.StartTimer()
   991  		}
   992  		delete(a, i2s[i-k])
   993  	}
   994  }
   995  
   996  func benchmarkMapDeletePointer(b *testing.B, n int) {
   997  	i2p := make([]*int, n)
   998  	for i := 0; i < n; i++ {
   999  		i2p[i] = new(int)
  1000  	}
  1001  	a := make(map[*int]int, n)
  1002  	b.ResetTimer()
  1003  	k := 0
  1004  	for i := 0; i < b.N; i++ {
  1005  		if len(a) == 0 {
  1006  			b.StopTimer()
  1007  			for j := 0; j < n; j++ {
  1008  				a[i2p[j]] = j
  1009  			}
  1010  			k = i
  1011  			b.StartTimer()
  1012  		}
  1013  		delete(a, i2p[i-k])
  1014  	}
  1015  }
  1016  
  1017  func runWith(f func(*testing.B, int), v ...int) func(*testing.B) {
  1018  	return func(b *testing.B) {
  1019  		for _, n := range v {
  1020  			b.Run(strconv.Itoa(n), func(b *testing.B) { f(b, n) })
  1021  		}
  1022  	}
  1023  }
  1024  
  1025  func BenchmarkMapAssign(b *testing.B) {
  1026  	b.Run("Int32", runWith(benchmarkMapAssignInt32, 1<<8, 1<<16))
  1027  	b.Run("Int64", runWith(benchmarkMapAssignInt64, 1<<8, 1<<16))
  1028  	b.Run("Str", runWith(benchmarkMapAssignStr, 1<<8, 1<<16))
  1029  }
  1030  
  1031  func BenchmarkMapOperatorAssign(b *testing.B) {
  1032  	b.Run("Int32", runWith(benchmarkMapOperatorAssignInt32, 1<<8, 1<<16))
  1033  	b.Run("Int64", runWith(benchmarkMapOperatorAssignInt64, 1<<8, 1<<16))
  1034  	b.Run("Str", runWith(benchmarkMapOperatorAssignStr, 1<<8, 1<<16))
  1035  }
  1036  
  1037  func BenchmarkMapAppendAssign(b *testing.B) {
  1038  	b.Run("Int32", runWith(benchmarkMapAppendAssignInt32, 1<<8, 1<<16))
  1039  	b.Run("Int64", runWith(benchmarkMapAppendAssignInt64, 1<<8, 1<<16))
  1040  	b.Run("Str", runWith(benchmarkMapAppendAssignStr, 1<<8, 1<<16))
  1041  }
  1042  
  1043  func BenchmarkMapDelete(b *testing.B) {
  1044  	b.Run("Int32", runWith(benchmarkMapDeleteInt32, 100, 1000, 10000))
  1045  	b.Run("Int64", runWith(benchmarkMapDeleteInt64, 100, 1000, 10000))
  1046  	b.Run("Str", runWith(benchmarkMapDeleteStr, 100, 1000, 10000))
  1047  	b.Run("Pointer", runWith(benchmarkMapDeletePointer, 100, 1000, 10000))
  1048  }
  1049  
  1050  func TestDeferDeleteSlow(t *testing.T) {
  1051  	ks := []complex128{0, 1, 2, 3}
  1052  
  1053  	m := make(map[interface{}]int)
  1054  	for i, k := range ks {
  1055  		m[k] = i
  1056  	}
  1057  	if len(m) != len(ks) {
  1058  		t.Errorf("want %d elements, got %d", len(ks), len(m))
  1059  	}
  1060  
  1061  	func() {
  1062  		for _, k := range ks {
  1063  			defer delete(m, k)
  1064  		}
  1065  	}()
  1066  	if len(m) != 0 {
  1067  		t.Errorf("want 0 elements, got %d", len(m))
  1068  	}
  1069  }
  1070  
  1071  // TestIncrementAfterDeleteValueInt and other test Issue 25936.
  1072  // Value types int, int32, int64 are affected. Value type string
  1073  // works as expected.
  1074  func TestIncrementAfterDeleteValueInt(t *testing.T) {
  1075  	const key1 = 12
  1076  	const key2 = 13
  1077  
  1078  	m := make(map[int]int)
  1079  	m[key1] = 99
  1080  	delete(m, key1)
  1081  	m[key2]++
  1082  	if n2 := m[key2]; n2 != 1 {
  1083  		t.Errorf("incremented 0 to %d", n2)
  1084  	}
  1085  }
  1086  
  1087  func TestIncrementAfterDeleteValueInt32(t *testing.T) {
  1088  	const key1 = 12
  1089  	const key2 = 13
  1090  
  1091  	m := make(map[int]int32)
  1092  	m[key1] = 99
  1093  	delete(m, key1)
  1094  	m[key2]++
  1095  	if n2 := m[key2]; n2 != 1 {
  1096  		t.Errorf("incremented 0 to %d", n2)
  1097  	}
  1098  }
  1099  
  1100  func TestIncrementAfterDeleteValueInt64(t *testing.T) {
  1101  	const key1 = 12
  1102  	const key2 = 13
  1103  
  1104  	m := make(map[int]int64)
  1105  	m[key1] = 99
  1106  	delete(m, key1)
  1107  	m[key2]++
  1108  	if n2 := m[key2]; n2 != 1 {
  1109  		t.Errorf("incremented 0 to %d", n2)
  1110  	}
  1111  }
  1112  
  1113  func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) {
  1114  	const key1 = ""
  1115  	const key2 = "x"
  1116  
  1117  	m := make(map[string]int)
  1118  	m[key1] = 99
  1119  	delete(m, key1)
  1120  	m[key2] += 1
  1121  	if n2 := m[key2]; n2 != 1 {
  1122  		t.Errorf("incremented 0 to %d", n2)
  1123  	}
  1124  }
  1125  
  1126  func TestIncrementAfterDeleteKeyValueString(t *testing.T) {
  1127  	const key1 = ""
  1128  	const key2 = "x"
  1129  
  1130  	m := make(map[string]string)
  1131  	m[key1] = "99"
  1132  	delete(m, key1)
  1133  	m[key2] += "1"
  1134  	if n2 := m[key2]; n2 != "1" {
  1135  		t.Errorf("appended '1' to empty (nil) string, got %s", n2)
  1136  	}
  1137  }
  1138  
  1139  // TestIncrementAfterBulkClearKeyStringValueInt tests that map bulk
  1140  // deletion (mapclear) still works as expected. Note that it was not
  1141  // affected by Issue 25936.
  1142  func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) {
  1143  	const key1 = ""
  1144  	const key2 = "x"
  1145  
  1146  	m := make(map[string]int)
  1147  	m[key1] = 99
  1148  	for k := range m {
  1149  		delete(m, k)
  1150  	}
  1151  	m[key2]++
  1152  	if n2 := m[key2]; n2 != 1 {
  1153  		t.Errorf("incremented 0 to %d", n2)
  1154  	}
  1155  }
  1156  
  1157  func TestMapTombstones(t *testing.T) {
  1158  	m := map[int]int{}
  1159  	const N = 10000
  1160  	// Fill a map.
  1161  	for i := 0; i < N; i++ {
  1162  		m[i] = i
  1163  	}
  1164  	runtime.MapTombstoneCheck(m)
  1165  	// Delete half of the entries.
  1166  	for i := 0; i < N; i += 2 {
  1167  		delete(m, i)
  1168  	}
  1169  	runtime.MapTombstoneCheck(m)
  1170  	// Add new entries to fill in holes.
  1171  	for i := N; i < 3*N/2; i++ {
  1172  		m[i] = i
  1173  	}
  1174  	runtime.MapTombstoneCheck(m)
  1175  	// Delete everything.
  1176  	for i := 0; i < 3*N/2; i++ {
  1177  		delete(m, i)
  1178  	}
  1179  	runtime.MapTombstoneCheck(m)
  1180  }
  1181  
  1182  type canString int
  1183  
  1184  func (c canString) String() string {
  1185  	return fmt.Sprintf("%d", int(c))
  1186  }
  1187  
  1188  func TestMapInterfaceKey(t *testing.T) {
  1189  	// Test all the special cases in runtime.typehash.
  1190  	type GrabBag struct {
  1191  		f32  float32
  1192  		f64  float64
  1193  		c64  complex64
  1194  		c128 complex128
  1195  		s    string
  1196  		i0   interface{}
  1197  		i1   interface {
  1198  			String() string
  1199  		}
  1200  		a [4]string
  1201  	}
  1202  
  1203  	m := map[interface{}]bool{}
  1204  	// Put a bunch of data in m, so that a bad hash is likely to
  1205  	// lead to a bad bucket, which will lead to a missed lookup.
  1206  	for i := 0; i < 1000; i++ {
  1207  		m[i] = true
  1208  	}
  1209  	m[GrabBag{f32: 1.0}] = true
  1210  	if !m[GrabBag{f32: 1.0}] {
  1211  		panic("f32 not found")
  1212  	}
  1213  	m[GrabBag{f64: 1.0}] = true
  1214  	if !m[GrabBag{f64: 1.0}] {
  1215  		panic("f64 not found")
  1216  	}
  1217  	m[GrabBag{c64: 1.0i}] = true
  1218  	if !m[GrabBag{c64: 1.0i}] {
  1219  		panic("c64 not found")
  1220  	}
  1221  	m[GrabBag{c128: 1.0i}] = true
  1222  	if !m[GrabBag{c128: 1.0i}] {
  1223  		panic("c128 not found")
  1224  	}
  1225  	m[GrabBag{s: "foo"}] = true
  1226  	if !m[GrabBag{s: "foo"}] {
  1227  		panic("string not found")
  1228  	}
  1229  	m[GrabBag{i0: "foo"}] = true
  1230  	if !m[GrabBag{i0: "foo"}] {
  1231  		panic("interface{} not found")
  1232  	}
  1233  	m[GrabBag{i1: canString(5)}] = true
  1234  	if !m[GrabBag{i1: canString(5)}] {
  1235  		panic("interface{String() string} not found")
  1236  	}
  1237  	m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true
  1238  	if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] {
  1239  		panic("array not found")
  1240  	}
  1241  }
  1242  

View as plain text