Source file src/runtime/map_benchmark_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  	"encoding/binary"
     9  	"flag"
    10  	"fmt"
    11  	"math/rand"
    12  	"runtime"
    13  	"slices"
    14  	"strconv"
    15  	"strings"
    16  	"testing"
    17  	"unsafe"
    18  )
    19  
    20  var mapbench = flag.Bool("mapbench", false, "enable the full set of map benchmark variants")
    21  
    22  const size = 10
    23  
    24  func BenchmarkHashStringSpeed(b *testing.B) {
    25  	strings := make([]string, size)
    26  	for i := 0; i < size; i++ {
    27  		strings[i] = fmt.Sprintf("string#%d", i)
    28  	}
    29  	sum := 0
    30  	m := make(map[string]int, size)
    31  	for i := 0; i < size; i++ {
    32  		m[strings[i]] = 0
    33  	}
    34  	idx := 0
    35  	b.ResetTimer()
    36  	for i := 0; i < b.N; i++ {
    37  		sum += m[strings[idx]]
    38  		idx++
    39  		if idx == size {
    40  			idx = 0
    41  		}
    42  	}
    43  }
    44  
    45  type chunk [17]byte
    46  
    47  func BenchmarkHashBytesSpeed(b *testing.B) {
    48  	// a bunch of chunks, each with a different alignment mod 16
    49  	var chunks [size]chunk
    50  	// initialize each to a different value
    51  	for i := 0; i < size; i++ {
    52  		chunks[i][0] = byte(i)
    53  	}
    54  	// put into a map
    55  	m := make(map[chunk]int, size)
    56  	for i, c := range chunks {
    57  		m[c] = i
    58  	}
    59  	idx := 0
    60  	b.ResetTimer()
    61  	for i := 0; i < b.N; i++ {
    62  		if m[chunks[idx]] != idx {
    63  			b.Error("bad map entry for chunk")
    64  		}
    65  		idx++
    66  		if idx == size {
    67  			idx = 0
    68  		}
    69  	}
    70  }
    71  
    72  func BenchmarkHashInt32Speed(b *testing.B) {
    73  	ints := make([]int32, size)
    74  	for i := 0; i < size; i++ {
    75  		ints[i] = int32(i)
    76  	}
    77  	sum := 0
    78  	m := make(map[int32]int, size)
    79  	for i := 0; i < size; i++ {
    80  		m[ints[i]] = 0
    81  	}
    82  	idx := 0
    83  	b.ResetTimer()
    84  	for i := 0; i < b.N; i++ {
    85  		sum += m[ints[idx]]
    86  		idx++
    87  		if idx == size {
    88  			idx = 0
    89  		}
    90  	}
    91  }
    92  
    93  func BenchmarkHashInt64Speed(b *testing.B) {
    94  	ints := make([]int64, size)
    95  	for i := 0; i < size; i++ {
    96  		ints[i] = int64(i)
    97  	}
    98  	sum := 0
    99  	m := make(map[int64]int, size)
   100  	for i := 0; i < size; i++ {
   101  		m[ints[i]] = 0
   102  	}
   103  	idx := 0
   104  	b.ResetTimer()
   105  	for i := 0; i < b.N; i++ {
   106  		sum += m[ints[idx]]
   107  		idx++
   108  		if idx == size {
   109  			idx = 0
   110  		}
   111  	}
   112  }
   113  func BenchmarkHashStringArraySpeed(b *testing.B) {
   114  	stringpairs := make([][2]string, size)
   115  	for i := 0; i < size; i++ {
   116  		for j := 0; j < 2; j++ {
   117  			stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
   118  		}
   119  	}
   120  	sum := 0
   121  	m := make(map[[2]string]int, size)
   122  	for i := 0; i < size; i++ {
   123  		m[stringpairs[i]] = 0
   124  	}
   125  	idx := 0
   126  	b.ResetTimer()
   127  	for i := 0; i < b.N; i++ {
   128  		sum += m[stringpairs[idx]]
   129  		idx++
   130  		if idx == size {
   131  			idx = 0
   132  		}
   133  	}
   134  }
   135  
   136  func BenchmarkMegMap(b *testing.B) {
   137  	m := make(map[string]bool)
   138  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   139  		m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
   140  	}
   141  	key := strings.Repeat("X", 1<<20-1) + "k"
   142  	b.ResetTimer()
   143  	for i := 0; i < b.N; i++ {
   144  		_, _ = m[key]
   145  	}
   146  }
   147  
   148  func BenchmarkMegOneMap(b *testing.B) {
   149  	m := make(map[string]bool)
   150  	m[strings.Repeat("X", 1<<20)] = true
   151  	key := strings.Repeat("Y", 1<<20)
   152  	b.ResetTimer()
   153  	for i := 0; i < b.N; i++ {
   154  		_, _ = m[key]
   155  	}
   156  }
   157  
   158  func BenchmarkMegEqMap(b *testing.B) {
   159  	m := make(map[string]bool)
   160  	key1 := strings.Repeat("X", 1<<20)
   161  	key2 := strings.Repeat("X", 1<<20) // equal but different instance
   162  	m[key1] = true
   163  	b.ResetTimer()
   164  	for i := 0; i < b.N; i++ {
   165  		_, _ = m[key2]
   166  	}
   167  }
   168  
   169  func BenchmarkMegEmptyMap(b *testing.B) {
   170  	m := make(map[string]bool)
   171  	key := strings.Repeat("X", 1<<20)
   172  	b.ResetTimer()
   173  	for i := 0; i < b.N; i++ {
   174  		_, _ = m[key]
   175  	}
   176  }
   177  
   178  func BenchmarkMegEmptyMapWithInterfaceKey(b *testing.B) {
   179  	m := make(map[any]bool)
   180  	key := strings.Repeat("X", 1<<20)
   181  	b.ResetTimer()
   182  	for i := 0; i < b.N; i++ {
   183  		_, _ = m[key]
   184  	}
   185  }
   186  
   187  func BenchmarkSmallStrMap(b *testing.B) {
   188  	m := make(map[string]bool)
   189  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   190  		m[fmt.Sprint(suffix)] = true
   191  	}
   192  	key := "k"
   193  	b.ResetTimer()
   194  	for i := 0; i < b.N; i++ {
   195  		_, _ = m[key]
   196  	}
   197  }
   198  
   199  func BenchmarkMapStringKeysEight_16(b *testing.B)  { benchmarkMapStringKeysEight(b, 16) }
   200  func BenchmarkMapStringKeysEight_32(b *testing.B)  { benchmarkMapStringKeysEight(b, 32) }
   201  func BenchmarkMapStringKeysEight_64(b *testing.B)  { benchmarkMapStringKeysEight(b, 64) }
   202  func BenchmarkMapStringKeysEight_128(b *testing.B) { benchmarkMapStringKeysEight(b, 128) }
   203  func BenchmarkMapStringKeysEight_256(b *testing.B) { benchmarkMapStringKeysEight(b, 256) }
   204  func BenchmarkMapStringKeysEight_1M(b *testing.B)  { benchmarkMapStringKeysEight(b, 1<<20) }
   205  
   206  func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
   207  	m := make(map[string]bool)
   208  	for i := 0; i < 8; i++ {
   209  		m[strings.Repeat("K", i+1)] = true
   210  	}
   211  	key := strings.Repeat("K", keySize)
   212  	b.ResetTimer()
   213  	for i := 0; i < b.N; i++ {
   214  		_ = m[key]
   215  	}
   216  }
   217  
   218  func BenchmarkMapFirst(b *testing.B) {
   219  	for n := 1; n <= 16; n++ {
   220  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   221  			m := make(map[int]bool)
   222  			for i := 0; i < n; i++ {
   223  				m[i] = true
   224  			}
   225  			b.ResetTimer()
   226  			for i := 0; i < b.N; i++ {
   227  				_ = m[0]
   228  			}
   229  		})
   230  	}
   231  }
   232  func BenchmarkMapMid(b *testing.B) {
   233  	for n := 1; n <= 16; n++ {
   234  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   235  			m := make(map[int]bool)
   236  			for i := 0; i < n; i++ {
   237  				m[i] = true
   238  			}
   239  			b.ResetTimer()
   240  			for i := 0; i < b.N; i++ {
   241  				_ = m[n>>1]
   242  			}
   243  		})
   244  	}
   245  }
   246  func BenchmarkMapLast(b *testing.B) {
   247  	for n := 1; n <= 16; n++ {
   248  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   249  			m := make(map[int]bool)
   250  			for i := 0; i < n; i++ {
   251  				m[i] = true
   252  			}
   253  			b.ResetTimer()
   254  			for i := 0; i < b.N; i++ {
   255  				_ = m[n-1]
   256  			}
   257  		})
   258  	}
   259  }
   260  
   261  func cyclicPermutation(n int) []int {
   262  	// From https://crypto.stackexchange.com/questions/51787/creating-single-cycle-permutations
   263  	p := rand.New(rand.NewSource(1)).Perm(n)
   264  	inc := make([]int, n)
   265  	pInv := make([]int, n)
   266  	for i := 0; i < n; i++ {
   267  		inc[i] = (i + 1) % n
   268  		pInv[p[i]] = i
   269  	}
   270  	res := make([]int, n)
   271  	for i := 0; i < n; i++ {
   272  		res[i] = pInv[inc[p[i]]]
   273  	}
   274  
   275  	// Test result.
   276  	j := 0
   277  	for i := 0; i < n-1; i++ {
   278  		j = res[j]
   279  		if j == 0 {
   280  			panic("got back to 0 too early")
   281  		}
   282  	}
   283  	j = res[j]
   284  	if j != 0 {
   285  		panic("didn't get back to 0")
   286  	}
   287  	return res
   288  }
   289  
   290  func BenchmarkMapCycle(b *testing.B) {
   291  	// Arrange map entries to be a permutation, so that
   292  	// we hit all entries, and one lookup is data dependent
   293  	// on the previous lookup.
   294  	const N = 3127
   295  	p := cyclicPermutation(N)
   296  	m := map[int]int{}
   297  	for i := 0; i < N; i++ {
   298  		m[i] = p[i]
   299  	}
   300  	b.ResetTimer()
   301  	j := 0
   302  	for i := 0; i < b.N; i++ {
   303  		j = m[j]
   304  	}
   305  	sink = uint64(j)
   306  }
   307  
   308  // Accessing the same keys in a row.
   309  func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
   310  	m := make(map[string]bool)
   311  	// At least bigger than a single bucket:
   312  	for i := 0; i < 64; i++ {
   313  		m[fmt.Sprintf("some key %d", i)] = true
   314  	}
   315  	base := strings.Repeat("x", lookupKeySize-1)
   316  	key1 := base + "1"
   317  	key2 := base + "2"
   318  	b.ResetTimer()
   319  	for i := 0; i < b.N/4; i++ {
   320  		_ = m[key1]
   321  		_ = m[key1]
   322  		_ = m[key2]
   323  		_ = m[key2]
   324  	}
   325  }
   326  
   327  func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
   328  func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
   329  
   330  func BenchmarkMakeMap(b *testing.B) {
   331  	b.Run("[Byte]Byte", func(b *testing.B) {
   332  		var m map[byte]byte
   333  		for i := 0; i < b.N; i++ {
   334  			m = make(map[byte]byte, 10)
   335  		}
   336  		hugeSink = m
   337  	})
   338  	b.Run("[Int]Int", func(b *testing.B) {
   339  		var m map[int]int
   340  		for i := 0; i < b.N; i++ {
   341  			m = make(map[int]int, 10)
   342  		}
   343  		hugeSink = m
   344  	})
   345  }
   346  
   347  func BenchmarkNewEmptyMap(b *testing.B) {
   348  	b.ReportAllocs()
   349  	for i := 0; i < b.N; i++ {
   350  		_ = make(map[int]int)
   351  	}
   352  }
   353  
   354  func BenchmarkNewSmallMap(b *testing.B) {
   355  	b.ReportAllocs()
   356  	for i := 0; i < b.N; i++ {
   357  		m := make(map[int]int)
   358  		m[0] = 0
   359  		m[1] = 1
   360  	}
   361  }
   362  
   363  func BenchmarkSameLengthMap(b *testing.B) {
   364  	// long strings, same length, differ in first few
   365  	// and last few bytes.
   366  	m := make(map[string]bool)
   367  	s1 := "foo" + strings.Repeat("-", 100) + "bar"
   368  	s2 := "goo" + strings.Repeat("-", 100) + "ber"
   369  	m[s1] = true
   370  	m[s2] = true
   371  	b.ResetTimer()
   372  	for i := 0; i < b.N; i++ {
   373  		_ = m[s1]
   374  	}
   375  }
   376  
   377  func BenchmarkSmallKeyMap(b *testing.B) {
   378  	m := make(map[int16]bool)
   379  	m[5] = true
   380  	for i := 0; i < b.N; i++ {
   381  		_ = m[5]
   382  	}
   383  }
   384  
   385  func BenchmarkMapPopulate(b *testing.B) {
   386  	for size := 1; size < 1000000; size *= 10 {
   387  		b.Run(strconv.Itoa(size), func(b *testing.B) {
   388  			b.ReportAllocs()
   389  			for i := 0; i < b.N; i++ {
   390  				m := make(map[int]bool)
   391  				for j := 0; j < size; j++ {
   392  					m[j] = true
   393  				}
   394  			}
   395  		})
   396  	}
   397  }
   398  
   399  type ComplexAlgKey struct {
   400  	a, b, c int64
   401  	_       int
   402  	d       int32
   403  	_       int
   404  	e       string
   405  	_       int
   406  	f, g, h int64
   407  }
   408  
   409  func BenchmarkComplexAlgMap(b *testing.B) {
   410  	m := make(map[ComplexAlgKey]bool)
   411  	var k ComplexAlgKey
   412  	m[k] = true
   413  	for i := 0; i < b.N; i++ {
   414  		_ = m[k]
   415  	}
   416  }
   417  
   418  func BenchmarkGoMapClear(b *testing.B) {
   419  	b.Run("Reflexive", func(b *testing.B) {
   420  		for size := 1; size < 100000; size *= 10 {
   421  			b.Run(strconv.Itoa(size), func(b *testing.B) {
   422  				m := make(map[int]int, size)
   423  				for i := 0; i < b.N; i++ {
   424  					m[0] = size // Add one element so len(m) != 0 avoiding fast paths.
   425  					clear(m)
   426  				}
   427  			})
   428  		}
   429  	})
   430  	b.Run("NonReflexive", func(b *testing.B) {
   431  		for size := 1; size < 100000; size *= 10 {
   432  			b.Run(strconv.Itoa(size), func(b *testing.B) {
   433  				m := make(map[float64]int, size)
   434  				for i := 0; i < b.N; i++ {
   435  					m[1.0] = size // Add one element so len(m) != 0 avoiding fast paths.
   436  					clear(m)
   437  				}
   438  			})
   439  		}
   440  	})
   441  }
   442  
   443  func BenchmarkMapStringConversion(b *testing.B) {
   444  	for _, length := range []int{32, 64} {
   445  		b.Run(strconv.Itoa(length), func(b *testing.B) {
   446  			bytes := make([]byte, length)
   447  			b.Run("simple", func(b *testing.B) {
   448  				b.ReportAllocs()
   449  				m := make(map[string]int)
   450  				m[string(bytes)] = 0
   451  				for i := 0; i < b.N; i++ {
   452  					_ = m[string(bytes)]
   453  				}
   454  			})
   455  			b.Run("struct", func(b *testing.B) {
   456  				b.ReportAllocs()
   457  				type stringstruct struct{ s string }
   458  				m := make(map[stringstruct]int)
   459  				m[stringstruct{string(bytes)}] = 0
   460  				for i := 0; i < b.N; i++ {
   461  					_ = m[stringstruct{string(bytes)}]
   462  				}
   463  			})
   464  			b.Run("array", func(b *testing.B) {
   465  				b.ReportAllocs()
   466  				type stringarray [1]string
   467  				m := make(map[stringarray]int)
   468  				m[stringarray{string(bytes)}] = 0
   469  				for i := 0; i < b.N; i++ {
   470  					_ = m[stringarray{string(bytes)}]
   471  				}
   472  			})
   473  		})
   474  	}
   475  }
   476  
   477  var BoolSink bool
   478  
   479  func BenchmarkMapInterfaceString(b *testing.B) {
   480  	m := map[any]bool{}
   481  
   482  	for i := 0; i < 100; i++ {
   483  		m[fmt.Sprintf("%d", i)] = true
   484  	}
   485  
   486  	key := (any)("A")
   487  	b.ResetTimer()
   488  	for i := 0; i < b.N; i++ {
   489  		BoolSink = m[key]
   490  	}
   491  }
   492  func BenchmarkMapInterfacePtr(b *testing.B) {
   493  	m := map[any]bool{}
   494  
   495  	for i := 0; i < 100; i++ {
   496  		i := i
   497  		m[&i] = true
   498  	}
   499  
   500  	key := new(int)
   501  	b.ResetTimer()
   502  	for i := 0; i < b.N; i++ {
   503  		BoolSink = m[key]
   504  	}
   505  }
   506  
   507  var (
   508  	hintLessThan8    = 7
   509  	hintGreaterThan8 = 32
   510  )
   511  
   512  func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
   513  	b.ReportAllocs()
   514  	for i := 0; i < b.N; i++ {
   515  		_ = make(map[int]int, hintLessThan8)
   516  	}
   517  }
   518  
   519  func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
   520  	b.ReportAllocs()
   521  	for i := 0; i < b.N; i++ {
   522  		_ = make(map[int]int, hintGreaterThan8)
   523  	}
   524  }
   525  
   526  func benchSizes(f func(b *testing.B, n int)) func(*testing.B) {
   527  	var cases = []int{
   528  		0,
   529  		6,
   530  		12,
   531  		18,
   532  		24,
   533  		30,
   534  		64,
   535  		128,
   536  		256,
   537  		512,
   538  		1024,
   539  		2048,
   540  		4096,
   541  		8192,
   542  		1 << 16,
   543  		1 << 18,
   544  		1 << 20,
   545  		1 << 22,
   546  	}
   547  
   548  	// Cases enabled by default. Set -mapbench for the remainder.
   549  	//
   550  	// With the other type combinations, there are literally thousands of
   551  	// variations. It take too long to run all of these as part of
   552  	// builders.
   553  	byDefault := map[int]bool{
   554  		6:       true,
   555  		64:      true,
   556  		1 << 16: true,
   557  	}
   558  
   559  	return func(b *testing.B) {
   560  		for _, n := range cases {
   561  			b.Run("len="+strconv.Itoa(n), func(b *testing.B) {
   562  				if !*mapbench && !byDefault[n] {
   563  					b.Skip("Skipped because -mapbench=false")
   564  				}
   565  
   566  				f(b, n)
   567  			})
   568  		}
   569  	}
   570  }
   571  func smallBenchSizes(f func(b *testing.B, n int)) func(*testing.B) {
   572  	return func(b *testing.B) {
   573  		for n := 1; n <= 8; n++ {
   574  			b.Run("len="+strconv.Itoa(n), func(b *testing.B) {
   575  				f(b, n)
   576  			})
   577  		}
   578  	}
   579  }
   580  
   581  // A 16 byte type.
   582  type smallType [16]byte
   583  
   584  // A 512 byte type.
   585  type mediumType [1 << 9]byte
   586  
   587  // A 4KiB type.
   588  type bigType [1 << 12]byte
   589  
   590  type mapBenchmarkKeyType interface {
   591  	int32 | int64 | string | smallType | mediumType | bigType | *int32
   592  }
   593  
   594  type mapBenchmarkElemType interface {
   595  	mapBenchmarkKeyType | []int32
   596  }
   597  
   598  func genIntValues[T int | int32 | int64](start, end int) []T {
   599  	vals := make([]T, 0, end-start)
   600  	for i := start; i < end; i++ {
   601  		vals = append(vals, T(i))
   602  	}
   603  	return vals
   604  }
   605  
   606  func genStringValues(start, end int) []string {
   607  	vals := make([]string, 0, end-start)
   608  	for i := start; i < end; i++ {
   609  		vals = append(vals, strconv.Itoa(i))
   610  	}
   611  	return vals
   612  }
   613  
   614  func genSmallValues(start, end int) []smallType {
   615  	vals := make([]smallType, 0, end-start)
   616  	for i := start; i < end; i++ {
   617  		var v smallType
   618  		binary.NativeEndian.PutUint64(v[:], uint64(i))
   619  		vals = append(vals, v)
   620  	}
   621  	return vals
   622  }
   623  
   624  func genMediumValues(start, end int) []mediumType {
   625  	vals := make([]mediumType, 0, end-start)
   626  	for i := start; i < end; i++ {
   627  		var v mediumType
   628  		binary.NativeEndian.PutUint64(v[:], uint64(i))
   629  		vals = append(vals, v)
   630  	}
   631  	return vals
   632  }
   633  
   634  func genBigValues(start, end int) []bigType {
   635  	vals := make([]bigType, 0, end-start)
   636  	for i := start; i < end; i++ {
   637  		var v bigType
   638  		binary.NativeEndian.PutUint64(v[:], uint64(i))
   639  		vals = append(vals, v)
   640  	}
   641  	return vals
   642  }
   643  
   644  func genPtrValues[T any](start, end int) []*T {
   645  	// Start and end don't mean much. Each pointer by definition has a
   646  	// unique identity.
   647  	vals := make([]*T, 0, end-start)
   648  	for i := start; i < end; i++ {
   649  		v := new(T)
   650  		vals = append(vals, v)
   651  	}
   652  	return vals
   653  }
   654  
   655  func genIntSliceValues[T int | int32 | int64](start, end int) [][]T {
   656  	vals := make([][]T, 0, end-start)
   657  	for i := start; i < end; i++ {
   658  		vals = append(vals, []T{T(i)})
   659  	}
   660  	return vals
   661  }
   662  
   663  func genValues[T mapBenchmarkElemType](start, end int) []T {
   664  	var t T
   665  	switch any(t).(type) {
   666  	case int32:
   667  		return any(genIntValues[int32](start, end)).([]T)
   668  	case int64:
   669  		return any(genIntValues[int64](start, end)).([]T)
   670  	case string:
   671  		return any(genStringValues(start, end)).([]T)
   672  	case smallType:
   673  		return any(genSmallValues(start, end)).([]T)
   674  	case mediumType:
   675  		return any(genMediumValues(start, end)).([]T)
   676  	case bigType:
   677  		return any(genBigValues(start, end)).([]T)
   678  	case *int32:
   679  		return any(genPtrValues[int32](start, end)).([]T)
   680  	case []int32:
   681  		return any(genIntSliceValues[int32](start, end)).([]T)
   682  	default:
   683  		panic("unreachable")
   684  	}
   685  }
   686  
   687  // Avoid inlining to force a heap allocation.
   688  //
   689  //go:noinline
   690  func newSink[T mapBenchmarkElemType]() *T {
   691  	return new(T)
   692  }
   693  
   694  // Return a new maps filled with keys and elems. Both slices must be the same length.
   695  func fillMap[K mapBenchmarkKeyType, E mapBenchmarkElemType](keys []K, elems []E) map[K]E {
   696  	m := make(map[K]E, len(keys))
   697  	for i := range keys {
   698  		m[keys[i]] = elems[i]
   699  	}
   700  	return m
   701  }
   702  
   703  func iterCount(b *testing.B, n int) int {
   704  	// Divide b.N by n so that the ns/op reports time per element,
   705  	// not time per full map iteration. This makes benchmarks of
   706  	// different map sizes more comparable.
   707  	//
   708  	// If size is zero we still need to do iterations.
   709  	if n == 0 {
   710  		return b.N
   711  	}
   712  	return b.N / n
   713  }
   714  
   715  func checkAllocSize[K, E any](b *testing.B, n int) {
   716  	var k K
   717  	size := uint64(n) * uint64(unsafe.Sizeof(k))
   718  	var e E
   719  	size += uint64(n) * uint64(unsafe.Sizeof(e))
   720  
   721  	if size >= 1<<30 {
   722  		b.Skipf("Total key+elem size %d exceeds 1GiB", size)
   723  	}
   724  }
   725  
   726  func benchmarkMapIter[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   727  	checkAllocSize[K, E](b, n)
   728  	k := genValues[K](0, n)
   729  	e := genValues[E](0, n)
   730  	m := fillMap(k, e)
   731  	iterations := iterCount(b, n)
   732  	sinkK := newSink[K]()
   733  	sinkE := newSink[E]()
   734  	b.ResetTimer()
   735  
   736  	for i := 0; i < iterations; i++ {
   737  		for k, e := range m {
   738  			*sinkK = k
   739  			*sinkE = e
   740  		}
   741  	}
   742  }
   743  
   744  func BenchmarkMapIter(b *testing.B) {
   745  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapIter[int32, int32]))
   746  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapIter[int64, int64]))
   747  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapIter[string, string]))
   748  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapIter[smallType, int32]))
   749  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapIter[mediumType, int32]))
   750  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapIter[bigType, int32]))
   751  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapIter[bigType, bigType]))
   752  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapIter[int32, bigType]))
   753  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapIter[*int32, int32]))
   754  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapIter[int32, *int32]))
   755  }
   756  
   757  func benchmarkMapIterLowLoad[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   758  	// Only insert one entry regardless of map size.
   759  	k := genValues[K](0, 1)
   760  	e := genValues[E](0, 1)
   761  
   762  	m := make(map[K]E, n)
   763  	for i := range k {
   764  		m[k[i]] = e[i]
   765  	}
   766  
   767  	iterations := iterCount(b, n)
   768  	sinkK := newSink[K]()
   769  	sinkE := newSink[E]()
   770  	b.ResetTimer()
   771  
   772  	for i := 0; i < iterations; i++ {
   773  		for k, e := range m {
   774  			*sinkK = k
   775  			*sinkE = e
   776  		}
   777  	}
   778  }
   779  
   780  func BenchmarkMapIterLowLoad(b *testing.B) {
   781  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapIterLowLoad[int32, int32]))
   782  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapIterLowLoad[int64, int64]))
   783  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapIterLowLoad[string, string]))
   784  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[smallType, int32]))
   785  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[mediumType, int32]))
   786  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[bigType, int32]))
   787  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapIterLowLoad[bigType, bigType]))
   788  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapIterLowLoad[int32, bigType]))
   789  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapIterLowLoad[*int32, int32]))
   790  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapIterLowLoad[int32, *int32]))
   791  }
   792  
   793  func benchmarkMapAccessHit[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   794  	if n == 0 {
   795  		b.Skip("can't access empty map")
   796  	}
   797  	checkAllocSize[K, E](b, n)
   798  	k := genValues[K](0, n)
   799  	e := genValues[E](0, n)
   800  	m := fillMap(k, e)
   801  	sink := newSink[E]()
   802  	b.ResetTimer()
   803  
   804  	for i := 0; i < b.N; i++ {
   805  		*sink = m[k[i%n]]
   806  	}
   807  }
   808  
   809  func BenchmarkMapAccessHit(b *testing.B) {
   810  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAccessHit[int32, int32]))
   811  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAccessHit[int64, int64]))
   812  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAccessHit[string, string]))
   813  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAccessHit[smallType, int32]))
   814  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAccessHit[mediumType, int32]))
   815  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAccessHit[bigType, int32]))
   816  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAccessHit[bigType, bigType]))
   817  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAccessHit[int32, bigType]))
   818  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAccessHit[*int32, int32]))
   819  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAccessHit[int32, *int32]))
   820  }
   821  
   822  var sinkOK bool
   823  
   824  func benchmarkMapAccessMiss[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   825  	checkAllocSize[K, E](b, n)
   826  	k := genValues[K](0, n)
   827  	e := genValues[E](0, n)
   828  	m := fillMap(k, e)
   829  	if n == 0 { // Create a lookup values for empty maps.
   830  		n = 1
   831  	}
   832  	w := genValues[K](n, 2*n)
   833  	b.ResetTimer()
   834  
   835  	var ok bool
   836  	for i := 0; i < b.N; i++ {
   837  		_, ok = m[w[i%n]]
   838  	}
   839  
   840  	sinkOK = ok
   841  }
   842  
   843  func BenchmarkMapAccessMiss(b *testing.B) {
   844  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAccessMiss[int32, int32]))
   845  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAccessMiss[int64, int64]))
   846  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAccessMiss[string, string]))
   847  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAccessMiss[smallType, int32]))
   848  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAccessMiss[mediumType, int32]))
   849  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAccessMiss[bigType, int32]))
   850  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAccessMiss[bigType, bigType]))
   851  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAccessMiss[int32, bigType]))
   852  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAccessMiss[*int32, int32]))
   853  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAccessMiss[int32, *int32]))
   854  }
   855  
   856  // Assign to a key that already exists.
   857  func benchmarkMapAssignExists[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   858  	if n == 0 {
   859  		b.Skip("can't assign to existing keys in empty map")
   860  	}
   861  	checkAllocSize[K, E](b, n)
   862  	k := genValues[K](0, n)
   863  	e := genValues[E](0, n)
   864  	m := fillMap(k, e)
   865  	b.ResetTimer()
   866  
   867  	for i := 0; i < b.N; i++ {
   868  		m[k[i%n]] = e[i%n]
   869  	}
   870  }
   871  
   872  func BenchmarkMapAssignExists(b *testing.B) {
   873  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignExists[int32, int32]))
   874  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignExists[int64, int64]))
   875  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignExists[string, string]))
   876  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignExists[smallType, int32]))
   877  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignExists[mediumType, int32]))
   878  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignExists[bigType, int32]))
   879  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignExists[bigType, bigType]))
   880  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignExists[int32, bigType]))
   881  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignExists[*int32, int32]))
   882  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignExists[int32, *int32]))
   883  }
   884  
   885  // Fill a map of size n with no hint. Time is per-key. A new map is created
   886  // every n assignments.
   887  //
   888  // TODO(prattmic): Results don't make much sense if b.N < n.
   889  // TODO(prattmic): Measure distribution of assign time to reveal the grow
   890  // latency.
   891  func benchmarkMapAssignFillNoHint[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   892  	if n == 0 {
   893  		b.Skip("can't create empty map via assignment")
   894  	}
   895  	checkAllocSize[K, E](b, n)
   896  	k := genValues[K](0, n)
   897  	e := genValues[E](0, n)
   898  	b.ResetTimer()
   899  
   900  	var m map[K]E
   901  	for i := 0; i < b.N; i++ {
   902  		if i%n == 0 {
   903  			m = make(map[K]E)
   904  		}
   905  		m[k[i%n]] = e[i%n]
   906  	}
   907  }
   908  
   909  func BenchmarkMapAssignFillNoHint(b *testing.B) {
   910  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[int32, int32]))
   911  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillNoHint[int64, int64]))
   912  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillNoHint[string, string]))
   913  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[smallType, int32]))
   914  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[mediumType, int32]))
   915  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[bigType, int32]))
   916  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillNoHint[bigType, bigType]))
   917  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillNoHint[int32, bigType]))
   918  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[*int32, int32]))
   919  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillNoHint[int32, *int32]))
   920  }
   921  
   922  // Identical to benchmarkMapAssignFillNoHint, but additionally measures the
   923  // latency of each mapassign to report tail latency due to map grow.
   924  func benchmarkMapAssignGrowLatency[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   925  	if n == 0 {
   926  		b.Skip("can't create empty map via assignment")
   927  	}
   928  	checkAllocSize[K, E](b, n)
   929  	k := genValues[K](0, n)
   930  	e := genValues[E](0, n)
   931  
   932  	// Store the run time of each mapassign. Keeping the full data rather
   933  	// than a histogram provides higher precision. b.N tends to be <10M, so
   934  	// the memory requirement isn't too bad.
   935  	sample := make([]int64, b.N)
   936  
   937  	b.ResetTimer()
   938  
   939  	var m map[K]E
   940  	for i := 0; i < b.N; i++ {
   941  		if i%n == 0 {
   942  			m = make(map[K]E)
   943  		}
   944  		start := runtime.Nanotime()
   945  		m[k[i%n]] = e[i%n]
   946  		end := runtime.Nanotime()
   947  		sample[i] = end - start
   948  	}
   949  
   950  	b.StopTimer()
   951  
   952  	slices.Sort(sample)
   953  	// TODO(prattmic): Grow is so rare that even p99.99 often doesn't
   954  	// display a grow case. Switch to a more direct measure of grow cases
   955  	// only?
   956  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.5)]), "p50-ns/op")
   957  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.99)]), "p99-ns/op")
   958  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.999)]), "p99.9-ns/op")
   959  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.9999)]), "p99.99-ns/op")
   960  	b.ReportMetric(float64(sample[len(sample)-1]), "p100-ns/op")
   961  }
   962  
   963  func BenchmarkMapAssignGrowLatency(b *testing.B) {
   964  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[int32, int32]))
   965  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignGrowLatency[int64, int64]))
   966  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignGrowLatency[string, string]))
   967  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[smallType, int32]))
   968  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[mediumType, int32]))
   969  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[bigType, int32]))
   970  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignGrowLatency[bigType, bigType]))
   971  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignGrowLatency[int32, bigType]))
   972  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[*int32, int32]))
   973  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignGrowLatency[int32, *int32]))
   974  }
   975  
   976  // Fill a map of size n with size hint. Time is per-key. A new map is created
   977  // every n assignments.
   978  //
   979  // TODO(prattmic): Results don't make much sense if b.N < n.
   980  func benchmarkMapAssignFillHint[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   981  	if n == 0 {
   982  		b.Skip("can't create empty map via assignment")
   983  	}
   984  	checkAllocSize[K, E](b, n)
   985  	k := genValues[K](0, n)
   986  	e := genValues[E](0, n)
   987  	b.ResetTimer()
   988  
   989  	var m map[K]E
   990  	for i := 0; i < b.N; i++ {
   991  		if i%n == 0 {
   992  			m = make(map[K]E, n)
   993  		}
   994  		m[k[i%n]] = e[i%n]
   995  	}
   996  }
   997  
   998  func BenchmarkMapAssignFillHint(b *testing.B) {
   999  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillHint[int32, int32]))
  1000  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillHint[int64, int64]))
  1001  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillHint[string, string]))
  1002  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[smallType, int32]))
  1003  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[mediumType, int32]))
  1004  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[bigType, int32]))
  1005  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillHint[bigType, bigType]))
  1006  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillHint[int32, bigType]))
  1007  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillHint[*int32, int32]))
  1008  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillHint[int32, *int32]))
  1009  }
  1010  
  1011  // Fill a map of size n, reusing the same map. Time is per-key. The map is
  1012  // cleared every n assignments.
  1013  //
  1014  // TODO(prattmic): Results don't make much sense if b.N < n.
  1015  func benchmarkMapAssignFillClear[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
  1016  	if n == 0 {
  1017  		b.Skip("can't create empty map via assignment")
  1018  	}
  1019  	checkAllocSize[K, E](b, n)
  1020  	k := genValues[K](0, n)
  1021  	e := genValues[E](0, n)
  1022  	m := fillMap(k, e)
  1023  	b.ResetTimer()
  1024  
  1025  	for i := 0; i < b.N; i++ {
  1026  		if i%n == 0 {
  1027  			clear(m)
  1028  		}
  1029  		m[k[i%n]] = e[i%n]
  1030  	}
  1031  }
  1032  
  1033  func BenchmarkMapAssignFillClear(b *testing.B) {
  1034  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillClear[int32, int32]))
  1035  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillClear[int64, int64]))
  1036  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillClear[string, string]))
  1037  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[smallType, int32]))
  1038  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[mediumType, int32]))
  1039  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[bigType, int32]))
  1040  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillClear[bigType, bigType]))
  1041  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillClear[int32, bigType]))
  1042  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillClear[*int32, int32]))
  1043  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillClear[int32, *int32]))
  1044  }
  1045  
  1046  // Modify values using +=.
  1047  func benchmarkMapAssignAddition[K mapBenchmarkKeyType, E int32 | int64 | string](b *testing.B, n int) {
  1048  	if n == 0 {
  1049  		b.Skip("can't modify empty map via assignment")
  1050  	}
  1051  	checkAllocSize[K, E](b, n)
  1052  	k := genValues[K](0, n)
  1053  	e := genValues[E](0, n)
  1054  	m := fillMap(k, e)
  1055  	b.ResetTimer()
  1056  
  1057  	for i := 0; i < b.N; i++ {
  1058  		m[k[i%n]] += e[i%n]
  1059  	}
  1060  }
  1061  
  1062  func BenchmarkMapAssignAddition(b *testing.B) {
  1063  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignAddition[int32, int32]))
  1064  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignAddition[int64, int64]))
  1065  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignAddition[string, string]))
  1066  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignAddition[smallType, int32]))
  1067  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignAddition[mediumType, int32]))
  1068  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignAddition[bigType, int32]))
  1069  }
  1070  
  1071  // Modify values append.
  1072  func benchmarkMapAssignAppend[K mapBenchmarkKeyType](b *testing.B, n int) {
  1073  	if n == 0 {
  1074  		b.Skip("can't modify empty map via append")
  1075  	}
  1076  	checkAllocSize[K, []int32](b, n)
  1077  	k := genValues[K](0, n)
  1078  	e := genValues[[]int32](0, n)
  1079  	m := fillMap(k, e)
  1080  	b.ResetTimer()
  1081  
  1082  	for i := 0; i < b.N; i++ {
  1083  		m[k[i%n]] = append(m[k[i%n]], e[i%n][0])
  1084  	}
  1085  }
  1086  
  1087  func BenchmarkMapAssignAppend(b *testing.B) {
  1088  	b.Run("Key=int32/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[int32]))
  1089  	b.Run("Key=int64/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[int64]))
  1090  	b.Run("Key=string/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[string]))
  1091  }
  1092  
  1093  func benchmarkMapDelete[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
  1094  	if n == 0 {
  1095  		b.Skip("can't delete from empty map")
  1096  	}
  1097  	checkAllocSize[K, E](b, n)
  1098  	k := genValues[K](0, n)
  1099  	e := genValues[E](0, n)
  1100  	m := fillMap(k, e)
  1101  	b.ResetTimer()
  1102  
  1103  	for i := 0; i < b.N; i++ {
  1104  		if len(m) == 0 {
  1105  			// We'd like to StopTimer while refilling the map, but
  1106  			// it is way too expensive and thus makes the benchmark
  1107  			// take a long time. See https://go.dev/issue/20875.
  1108  			for j := range k {
  1109  				m[k[j]] = e[j]
  1110  			}
  1111  		}
  1112  		delete(m, k[i%n])
  1113  	}
  1114  }
  1115  
  1116  func BenchmarkMapDelete(b *testing.B) {
  1117  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapDelete[int32, int32]))
  1118  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapDelete[int64, int64]))
  1119  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapDelete[string, string]))
  1120  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapDelete[smallType, int32]))
  1121  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapDelete[mediumType, int32]))
  1122  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapDelete[bigType, int32]))
  1123  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapDelete[bigType, bigType]))
  1124  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapDelete[int32, bigType]))
  1125  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapDelete[*int32, int32]))
  1126  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapDelete[int32, *int32]))
  1127  }
  1128  
  1129  // Use iterator to pop an element. We want this to be fast, see
  1130  // https://go.dev/issue/8412.
  1131  func benchmarkMapPop[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
  1132  	if n == 0 {
  1133  		b.Skip("can't delete from empty map")
  1134  	}
  1135  	checkAllocSize[K, E](b, n)
  1136  	k := genValues[K](0, n)
  1137  	e := genValues[E](0, n)
  1138  	m := fillMap(k, e)
  1139  	b.ResetTimer()
  1140  
  1141  	for i := 0; i < b.N; i++ {
  1142  		if len(m) == 0 {
  1143  			// We'd like to StopTimer while refilling the map, but
  1144  			// it is way too expensive and thus makes the benchmark
  1145  			// take a long time. See https://go.dev/issue/20875.
  1146  			for j := range k {
  1147  				m[k[j]] = e[j]
  1148  			}
  1149  		}
  1150  		for key := range m {
  1151  			delete(m, key)
  1152  			break
  1153  		}
  1154  	}
  1155  }
  1156  
  1157  func BenchmarkMapPop(b *testing.B) {
  1158  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapPop[int32, int32]))
  1159  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapPop[int64, int64]))
  1160  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapPop[string, string]))
  1161  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapPop[smallType, int32]))
  1162  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapPop[mediumType, int32]))
  1163  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapPop[bigType, int32]))
  1164  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapPop[bigType, bigType]))
  1165  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapPop[int32, bigType]))
  1166  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapPop[*int32, int32]))
  1167  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapPop[int32, *int32]))
  1168  }
  1169  
  1170  func BenchmarkMapDeleteLargeKey(b *testing.B) {
  1171  	m := map[string]int{}
  1172  	for i := range 9 {
  1173  		m[fmt.Sprintf("%d", i)] = i
  1174  	}
  1175  	key := strings.Repeat("*", 10000)
  1176  	for range b.N {
  1177  		delete(m, key)
  1178  	}
  1179  }
  1180  
  1181  func BenchmarkMapSmallAccessHit(b *testing.B) {
  1182  	b.Run("Key=int32/Elem=int32", smallBenchSizes(benchmarkMapAccessHit[int32, int32]))
  1183  	b.Run("Key=int64/Elem=int64", smallBenchSizes(benchmarkMapAccessHit[int64, int64]))
  1184  	b.Run("Key=string/Elem=string", smallBenchSizes(benchmarkMapAccessHit[string, string]))
  1185  }
  1186  func BenchmarkMapSmallAccessMiss(b *testing.B) {
  1187  	b.Run("Key=int32/Elem=int32", smallBenchSizes(benchmarkMapAccessMiss[int32, int32]))
  1188  	b.Run("Key=int64/Elem=int64", smallBenchSizes(benchmarkMapAccessMiss[int64, int64]))
  1189  	b.Run("Key=string/Elem=string", smallBenchSizes(benchmarkMapAccessMiss[string, string]))
  1190  }
  1191  

View as plain text