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

View as plain text