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

View as plain text