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  		m[&i] = true
   497  	}
   498  
   499  	key := new(int)
   500  	b.ResetTimer()
   501  	for i := 0; i < b.N; i++ {
   502  		BoolSink = m[key]
   503  	}
   504  }
   505  
   506  var (
   507  	hintLessThan8    = 7
   508  	hintGreaterThan8 = 32
   509  )
   510  
   511  func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
   512  	b.ReportAllocs()
   513  	for i := 0; i < b.N; i++ {
   514  		_ = make(map[int]int, hintLessThan8)
   515  	}
   516  }
   517  
   518  func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
   519  	b.ReportAllocs()
   520  	for i := 0; i < b.N; i++ {
   521  		_ = make(map[int]int, hintGreaterThan8)
   522  	}
   523  }
   524  
   525  func benchSizes(f func(b *testing.B, n int)) func(*testing.B) {
   526  	var cases = []int{
   527  		0,
   528  		6,
   529  		12,
   530  		18,
   531  		24,
   532  		30,
   533  		64,
   534  		128,
   535  		256,
   536  		512,
   537  		1024,
   538  		2048,
   539  		4096,
   540  		8192,
   541  		1 << 16,
   542  		1 << 18,
   543  		1 << 20,
   544  		1 << 22,
   545  	}
   546  
   547  	// Cases enabled by default. Set -mapbench for the remainder.
   548  	//
   549  	// With the other type combinations, there are literally thousands of
   550  	// variations. It take too long to run all of these as part of
   551  	// builders.
   552  	byDefault := map[int]bool{
   553  		6:       true,
   554  		64:      true,
   555  		1 << 16: true,
   556  	}
   557  
   558  	return func(b *testing.B) {
   559  		for _, n := range cases {
   560  			b.Run("len="+strconv.Itoa(n), func(b *testing.B) {
   561  				if !*mapbench && !byDefault[n] {
   562  					b.Skip("Skipped because -mapbench=false")
   563  				}
   564  
   565  				f(b, n)
   566  			})
   567  		}
   568  	}
   569  }
   570  func smallBenchSizes(f func(b *testing.B, n int)) func(*testing.B) {
   571  	return func(b *testing.B) {
   572  		for n := 1; n <= 8; n++ {
   573  			b.Run("len="+strconv.Itoa(n), func(b *testing.B) {
   574  				f(b, n)
   575  			})
   576  		}
   577  	}
   578  }
   579  
   580  // A 16 byte type.
   581  type smallType [16]byte
   582  
   583  // A 512 byte type.
   584  type mediumType [1 << 9]byte
   585  
   586  // A 4KiB type.
   587  type bigType [1 << 12]byte
   588  
   589  type mapBenchmarkKeyType interface {
   590  	int32 | int64 | string | smallType | mediumType | bigType | *int32
   591  }
   592  
   593  type mapBenchmarkElemType interface {
   594  	mapBenchmarkKeyType | []int32
   595  }
   596  
   597  func genIntValues[T int | int32 | int64](start, end int) []T {
   598  	vals := make([]T, 0, end-start)
   599  	for i := start; i < end; i++ {
   600  		vals = append(vals, T(i))
   601  	}
   602  	return vals
   603  }
   604  
   605  func genStringValues(start, end int) []string {
   606  	vals := make([]string, 0, end-start)
   607  	for i := start; i < end; i++ {
   608  		vals = append(vals, strconv.Itoa(i))
   609  	}
   610  	return vals
   611  }
   612  
   613  func genSmallValues(start, end int) []smallType {
   614  	vals := make([]smallType, 0, end-start)
   615  	for i := start; i < end; i++ {
   616  		var v smallType
   617  		binary.NativeEndian.PutUint64(v[:], uint64(i))
   618  		vals = append(vals, v)
   619  	}
   620  	return vals
   621  }
   622  
   623  func genMediumValues(start, end int) []mediumType {
   624  	vals := make([]mediumType, 0, end-start)
   625  	for i := start; i < end; i++ {
   626  		var v mediumType
   627  		binary.NativeEndian.PutUint64(v[:], uint64(i))
   628  		vals = append(vals, v)
   629  	}
   630  	return vals
   631  }
   632  
   633  func genBigValues(start, end int) []bigType {
   634  	vals := make([]bigType, 0, end-start)
   635  	for i := start; i < end; i++ {
   636  		var v bigType
   637  		binary.NativeEndian.PutUint64(v[:], uint64(i))
   638  		vals = append(vals, v)
   639  	}
   640  	return vals
   641  }
   642  
   643  func genPtrValues[T any](start, end int) []*T {
   644  	// Start and end don't mean much. Each pointer by definition has a
   645  	// unique identity.
   646  	vals := make([]*T, 0, end-start)
   647  	for i := start; i < end; i++ {
   648  		v := new(T)
   649  		vals = append(vals, v)
   650  	}
   651  	return vals
   652  }
   653  
   654  func genIntSliceValues[T int | int32 | int64](start, end int) [][]T {
   655  	vals := make([][]T, 0, end-start)
   656  	for i := start; i < end; i++ {
   657  		vals = append(vals, []T{T(i)})
   658  	}
   659  	return vals
   660  }
   661  
   662  func genValues[T mapBenchmarkElemType](start, end int) []T {
   663  	var t T
   664  	switch any(t).(type) {
   665  	case int32:
   666  		return any(genIntValues[int32](start, end)).([]T)
   667  	case int64:
   668  		return any(genIntValues[int64](start, end)).([]T)
   669  	case string:
   670  		return any(genStringValues(start, end)).([]T)
   671  	case smallType:
   672  		return any(genSmallValues(start, end)).([]T)
   673  	case mediumType:
   674  		return any(genMediumValues(start, end)).([]T)
   675  	case bigType:
   676  		return any(genBigValues(start, end)).([]T)
   677  	case *int32:
   678  		return any(genPtrValues[int32](start, end)).([]T)
   679  	case []int32:
   680  		return any(genIntSliceValues[int32](start, end)).([]T)
   681  	default:
   682  		panic("unreachable")
   683  	}
   684  }
   685  
   686  // Avoid inlining to force a heap allocation.
   687  //
   688  //go:noinline
   689  func newSink[T mapBenchmarkElemType]() *T {
   690  	return new(T)
   691  }
   692  
   693  // Return a new maps filled with keys and elems. Both slices must be the same length.
   694  func fillMap[K mapBenchmarkKeyType, E mapBenchmarkElemType](keys []K, elems []E) map[K]E {
   695  	m := make(map[K]E, len(keys))
   696  	for i := range keys {
   697  		m[keys[i]] = elems[i]
   698  	}
   699  	return m
   700  }
   701  
   702  func iterCount(b *testing.B, n int) int {
   703  	// Divide b.N by n so that the ns/op reports time per element,
   704  	// not time per full map iteration. This makes benchmarks of
   705  	// different map sizes more comparable.
   706  	//
   707  	// If size is zero we still need to do iterations.
   708  	if n == 0 {
   709  		return b.N
   710  	}
   711  	return b.N / n
   712  }
   713  
   714  func checkAllocSize[K, E any](b *testing.B, n int) {
   715  	var k K
   716  	size := uint64(n) * uint64(unsafe.Sizeof(k))
   717  	var e E
   718  	size += uint64(n) * uint64(unsafe.Sizeof(e))
   719  
   720  	if size >= 1<<30 {
   721  		b.Skipf("Total key+elem size %d exceeds 1GiB", size)
   722  	}
   723  }
   724  
   725  func benchmarkMapIter[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   726  	checkAllocSize[K, E](b, n)
   727  	k := genValues[K](0, n)
   728  	e := genValues[E](0, n)
   729  	m := fillMap(k, e)
   730  	iterations := iterCount(b, n)
   731  	sinkK := newSink[K]()
   732  	sinkE := newSink[E]()
   733  	b.ResetTimer()
   734  
   735  	for i := 0; i < iterations; i++ {
   736  		for k, e := range m {
   737  			*sinkK = k
   738  			*sinkE = e
   739  		}
   740  	}
   741  }
   742  
   743  func BenchmarkMapIter(b *testing.B) {
   744  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapIter[int32, int32]))
   745  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapIter[int64, int64]))
   746  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapIter[string, string]))
   747  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapIter[smallType, int32]))
   748  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapIter[mediumType, int32]))
   749  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapIter[bigType, int32]))
   750  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapIter[bigType, bigType]))
   751  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapIter[int32, bigType]))
   752  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapIter[*int32, int32]))
   753  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapIter[int32, *int32]))
   754  }
   755  
   756  func benchmarkMapIterLowLoad[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   757  	// Only insert one entry regardless of map size.
   758  	k := genValues[K](0, 1)
   759  	e := genValues[E](0, 1)
   760  
   761  	m := make(map[K]E, n)
   762  	for i := range k {
   763  		m[k[i]] = e[i]
   764  	}
   765  
   766  	iterations := iterCount(b, n)
   767  	sinkK := newSink[K]()
   768  	sinkE := newSink[E]()
   769  	b.ResetTimer()
   770  
   771  	for i := 0; i < iterations; i++ {
   772  		for k, e := range m {
   773  			*sinkK = k
   774  			*sinkE = e
   775  		}
   776  	}
   777  }
   778  
   779  func BenchmarkMapIterLowLoad(b *testing.B) {
   780  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapIterLowLoad[int32, int32]))
   781  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapIterLowLoad[int64, int64]))
   782  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapIterLowLoad[string, string]))
   783  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[smallType, int32]))
   784  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[mediumType, int32]))
   785  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapIterLowLoad[bigType, int32]))
   786  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapIterLowLoad[bigType, bigType]))
   787  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapIterLowLoad[int32, bigType]))
   788  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapIterLowLoad[*int32, int32]))
   789  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapIterLowLoad[int32, *int32]))
   790  }
   791  
   792  func benchmarkMapAccessHit[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   793  	if n == 0 {
   794  		b.Skip("can't access empty map")
   795  	}
   796  	checkAllocSize[K, E](b, n)
   797  	k := genValues[K](0, n)
   798  	e := genValues[E](0, n)
   799  	m := fillMap(k, e)
   800  	sink := newSink[E]()
   801  	b.ResetTimer()
   802  
   803  	for i := 0; i < b.N; i++ {
   804  		*sink = m[k[i%n]]
   805  	}
   806  }
   807  
   808  func BenchmarkMapAccessHit(b *testing.B) {
   809  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAccessHit[int32, int32]))
   810  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAccessHit[int64, int64]))
   811  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAccessHit[string, string]))
   812  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAccessHit[smallType, int32]))
   813  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAccessHit[mediumType, int32]))
   814  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAccessHit[bigType, int32]))
   815  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAccessHit[bigType, bigType]))
   816  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAccessHit[int32, bigType]))
   817  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAccessHit[*int32, int32]))
   818  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAccessHit[int32, *int32]))
   819  }
   820  
   821  var sinkOK bool
   822  
   823  func benchmarkMapAccessMiss[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   824  	checkAllocSize[K, E](b, n)
   825  	k := genValues[K](0, n)
   826  	e := genValues[E](0, n)
   827  	m := fillMap(k, e)
   828  	if n == 0 { // Create a lookup values for empty maps.
   829  		n = 1
   830  	}
   831  	w := genValues[K](n, 2*n)
   832  	b.ResetTimer()
   833  
   834  	var ok bool
   835  	for i := 0; i < b.N; i++ {
   836  		_, ok = m[w[i%n]]
   837  	}
   838  
   839  	sinkOK = ok
   840  }
   841  
   842  func BenchmarkMapAccessMiss(b *testing.B) {
   843  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAccessMiss[int32, int32]))
   844  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAccessMiss[int64, int64]))
   845  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAccessMiss[string, string]))
   846  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAccessMiss[smallType, int32]))
   847  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAccessMiss[mediumType, int32]))
   848  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAccessMiss[bigType, int32]))
   849  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAccessMiss[bigType, bigType]))
   850  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAccessMiss[int32, bigType]))
   851  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAccessMiss[*int32, int32]))
   852  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAccessMiss[int32, *int32]))
   853  }
   854  
   855  // Assign to a key that already exists.
   856  func benchmarkMapAssignExists[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   857  	if n == 0 {
   858  		b.Skip("can't assign to existing keys in empty map")
   859  	}
   860  	checkAllocSize[K, E](b, n)
   861  	k := genValues[K](0, n)
   862  	e := genValues[E](0, n)
   863  	m := fillMap(k, e)
   864  	b.ResetTimer()
   865  
   866  	for i := 0; i < b.N; i++ {
   867  		m[k[i%n]] = e[i%n]
   868  	}
   869  }
   870  
   871  func BenchmarkMapAssignExists(b *testing.B) {
   872  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignExists[int32, int32]))
   873  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignExists[int64, int64]))
   874  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignExists[string, string]))
   875  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignExists[smallType, int32]))
   876  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignExists[mediumType, int32]))
   877  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignExists[bigType, int32]))
   878  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignExists[bigType, bigType]))
   879  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignExists[int32, bigType]))
   880  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignExists[*int32, int32]))
   881  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignExists[int32, *int32]))
   882  }
   883  
   884  // Fill a map of size n with no hint. Time is per-key. A new map is created
   885  // every n assignments.
   886  //
   887  // TODO(prattmic): Results don't make much sense if b.N < n.
   888  // TODO(prattmic): Measure distribution of assign time to reveal the grow
   889  // latency.
   890  func benchmarkMapAssignFillNoHint[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   891  	if n == 0 {
   892  		b.Skip("can't create empty map via assignment")
   893  	}
   894  	checkAllocSize[K, E](b, n)
   895  	k := genValues[K](0, n)
   896  	e := genValues[E](0, n)
   897  	b.ResetTimer()
   898  
   899  	var m map[K]E
   900  	for i := 0; i < b.N; i++ {
   901  		if i%n == 0 {
   902  			m = make(map[K]E)
   903  		}
   904  		m[k[i%n]] = e[i%n]
   905  	}
   906  }
   907  
   908  func BenchmarkMapAssignFillNoHint(b *testing.B) {
   909  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[int32, int32]))
   910  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillNoHint[int64, int64]))
   911  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillNoHint[string, string]))
   912  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[smallType, int32]))
   913  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[mediumType, int32]))
   914  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[bigType, int32]))
   915  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillNoHint[bigType, bigType]))
   916  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillNoHint[int32, bigType]))
   917  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillNoHint[*int32, int32]))
   918  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillNoHint[int32, *int32]))
   919  }
   920  
   921  // Identical to benchmarkMapAssignFillNoHint, but additionally measures the
   922  // latency of each mapassign to report tail latency due to map grow.
   923  func benchmarkMapAssignGrowLatency[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   924  	if n == 0 {
   925  		b.Skip("can't create empty map via assignment")
   926  	}
   927  	checkAllocSize[K, E](b, n)
   928  	k := genValues[K](0, n)
   929  	e := genValues[E](0, n)
   930  
   931  	// Store the run time of each mapassign. Keeping the full data rather
   932  	// than a histogram provides higher precision. b.N tends to be <10M, so
   933  	// the memory requirement isn't too bad.
   934  	sample := make([]int64, b.N)
   935  
   936  	b.ResetTimer()
   937  
   938  	var m map[K]E
   939  	for i := 0; i < b.N; i++ {
   940  		if i%n == 0 {
   941  			m = make(map[K]E)
   942  		}
   943  		start := runtime.Nanotime()
   944  		m[k[i%n]] = e[i%n]
   945  		end := runtime.Nanotime()
   946  		sample[i] = end - start
   947  	}
   948  
   949  	b.StopTimer()
   950  
   951  	slices.Sort(sample)
   952  	// TODO(prattmic): Grow is so rare that even p99.99 often doesn't
   953  	// display a grow case. Switch to a more direct measure of grow cases
   954  	// only?
   955  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.5)]), "p50-ns/op")
   956  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.99)]), "p99-ns/op")
   957  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.999)]), "p99.9-ns/op")
   958  	b.ReportMetric(float64(sample[int(float64(len(sample))*0.9999)]), "p99.99-ns/op")
   959  	b.ReportMetric(float64(sample[len(sample)-1]), "p100-ns/op")
   960  }
   961  
   962  func BenchmarkMapAssignGrowLatency(b *testing.B) {
   963  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[int32, int32]))
   964  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignGrowLatency[int64, int64]))
   965  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignGrowLatency[string, string]))
   966  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[smallType, int32]))
   967  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[mediumType, int32]))
   968  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[bigType, int32]))
   969  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignGrowLatency[bigType, bigType]))
   970  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignGrowLatency[int32, bigType]))
   971  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignGrowLatency[*int32, int32]))
   972  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignGrowLatency[int32, *int32]))
   973  }
   974  
   975  // Fill a map of size n with size hint. Time is per-key. A new map is created
   976  // every n assignments.
   977  //
   978  // TODO(prattmic): Results don't make much sense if b.N < n.
   979  func benchmarkMapAssignFillHint[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
   980  	if n == 0 {
   981  		b.Skip("can't create empty map via assignment")
   982  	}
   983  	checkAllocSize[K, E](b, n)
   984  	k := genValues[K](0, n)
   985  	e := genValues[E](0, n)
   986  	b.ResetTimer()
   987  
   988  	var m map[K]E
   989  	for i := 0; i < b.N; i++ {
   990  		if i%n == 0 {
   991  			m = make(map[K]E, n)
   992  		}
   993  		m[k[i%n]] = e[i%n]
   994  	}
   995  }
   996  
   997  func BenchmarkMapAssignFillHint(b *testing.B) {
   998  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillHint[int32, int32]))
   999  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillHint[int64, int64]))
  1000  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillHint[string, string]))
  1001  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[smallType, int32]))
  1002  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[mediumType, int32]))
  1003  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillHint[bigType, int32]))
  1004  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillHint[bigType, bigType]))
  1005  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillHint[int32, bigType]))
  1006  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillHint[*int32, int32]))
  1007  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillHint[int32, *int32]))
  1008  }
  1009  
  1010  // Fill a map of size n, reusing the same map. Time is per-key. The map is
  1011  // cleared every n assignments.
  1012  //
  1013  // TODO(prattmic): Results don't make much sense if b.N < n.
  1014  func benchmarkMapAssignFillClear[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
  1015  	if n == 0 {
  1016  		b.Skip("can't create empty map via assignment")
  1017  	}
  1018  	checkAllocSize[K, E](b, n)
  1019  	k := genValues[K](0, n)
  1020  	e := genValues[E](0, n)
  1021  	m := fillMap(k, e)
  1022  	b.ResetTimer()
  1023  
  1024  	for i := 0; i < b.N; i++ {
  1025  		if i%n == 0 {
  1026  			clear(m)
  1027  		}
  1028  		m[k[i%n]] = e[i%n]
  1029  	}
  1030  }
  1031  
  1032  func BenchmarkMapAssignFillClear(b *testing.B) {
  1033  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignFillClear[int32, int32]))
  1034  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignFillClear[int64, int64]))
  1035  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignFillClear[string, string]))
  1036  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[smallType, int32]))
  1037  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[mediumType, int32]))
  1038  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignFillClear[bigType, int32]))
  1039  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapAssignFillClear[bigType, bigType]))
  1040  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapAssignFillClear[int32, bigType]))
  1041  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapAssignFillClear[*int32, int32]))
  1042  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapAssignFillClear[int32, *int32]))
  1043  }
  1044  
  1045  // Modify values using +=.
  1046  func benchmarkMapAssignAddition[K mapBenchmarkKeyType, E int32 | int64 | string](b *testing.B, n int) {
  1047  	if n == 0 {
  1048  		b.Skip("can't modify empty map via assignment")
  1049  	}
  1050  	checkAllocSize[K, E](b, n)
  1051  	k := genValues[K](0, n)
  1052  	e := genValues[E](0, n)
  1053  	m := fillMap(k, e)
  1054  	b.ResetTimer()
  1055  
  1056  	for i := 0; i < b.N; i++ {
  1057  		m[k[i%n]] += e[i%n]
  1058  	}
  1059  }
  1060  
  1061  func BenchmarkMapAssignAddition(b *testing.B) {
  1062  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapAssignAddition[int32, int32]))
  1063  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapAssignAddition[int64, int64]))
  1064  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapAssignAddition[string, string]))
  1065  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapAssignAddition[smallType, int32]))
  1066  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapAssignAddition[mediumType, int32]))
  1067  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapAssignAddition[bigType, int32]))
  1068  }
  1069  
  1070  // Modify values append.
  1071  func benchmarkMapAssignAppend[K mapBenchmarkKeyType](b *testing.B, n int) {
  1072  	if n == 0 {
  1073  		b.Skip("can't modify empty map via append")
  1074  	}
  1075  	checkAllocSize[K, []int32](b, n)
  1076  	k := genValues[K](0, n)
  1077  	e := genValues[[]int32](0, n)
  1078  	m := fillMap(k, e)
  1079  	b.ResetTimer()
  1080  
  1081  	for i := 0; i < b.N; i++ {
  1082  		m[k[i%n]] = append(m[k[i%n]], e[i%n][0])
  1083  	}
  1084  }
  1085  
  1086  func BenchmarkMapAssignAppend(b *testing.B) {
  1087  	b.Run("Key=int32/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[int32]))
  1088  	b.Run("Key=int64/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[int64]))
  1089  	b.Run("Key=string/Elem=[]int32", benchSizes(benchmarkMapAssignAppend[string]))
  1090  }
  1091  
  1092  func benchmarkMapDelete[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
  1093  	if n == 0 {
  1094  		b.Skip("can't delete from empty map")
  1095  	}
  1096  	checkAllocSize[K, E](b, n)
  1097  	k := genValues[K](0, n)
  1098  	e := genValues[E](0, n)
  1099  	m := fillMap(k, e)
  1100  	b.ResetTimer()
  1101  
  1102  	for i := 0; i < b.N; i++ {
  1103  		if len(m) == 0 {
  1104  			// We'd like to StopTimer while refilling the map, but
  1105  			// it is way too expensive and thus makes the benchmark
  1106  			// take a long time. See https://go.dev/issue/20875.
  1107  			for j := range k {
  1108  				m[k[j]] = e[j]
  1109  			}
  1110  		}
  1111  		delete(m, k[i%n])
  1112  	}
  1113  }
  1114  
  1115  func BenchmarkMapDelete(b *testing.B) {
  1116  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapDelete[int32, int32]))
  1117  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapDelete[int64, int64]))
  1118  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapDelete[string, string]))
  1119  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapDelete[smallType, int32]))
  1120  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapDelete[mediumType, int32]))
  1121  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapDelete[bigType, int32]))
  1122  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapDelete[bigType, bigType]))
  1123  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapDelete[int32, bigType]))
  1124  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapDelete[*int32, int32]))
  1125  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapDelete[int32, *int32]))
  1126  }
  1127  
  1128  // Use iterator to pop an element. We want this to be fast, see
  1129  // https://go.dev/issue/8412.
  1130  func benchmarkMapPop[K mapBenchmarkKeyType, E mapBenchmarkElemType](b *testing.B, n int) {
  1131  	if n == 0 {
  1132  		b.Skip("can't delete from empty map")
  1133  	}
  1134  	checkAllocSize[K, E](b, n)
  1135  	k := genValues[K](0, n)
  1136  	e := genValues[E](0, n)
  1137  	m := fillMap(k, e)
  1138  	b.ResetTimer()
  1139  
  1140  	for i := 0; i < b.N; i++ {
  1141  		if len(m) == 0 {
  1142  			// We'd like to StopTimer while refilling the map, but
  1143  			// it is way too expensive and thus makes the benchmark
  1144  			// take a long time. See https://go.dev/issue/20875.
  1145  			for j := range k {
  1146  				m[k[j]] = e[j]
  1147  			}
  1148  		}
  1149  		for key := range m {
  1150  			delete(m, key)
  1151  			break
  1152  		}
  1153  	}
  1154  }
  1155  
  1156  func BenchmarkMapPop(b *testing.B) {
  1157  	b.Run("Key=int32/Elem=int32", benchSizes(benchmarkMapPop[int32, int32]))
  1158  	b.Run("Key=int64/Elem=int64", benchSizes(benchmarkMapPop[int64, int64]))
  1159  	b.Run("Key=string/Elem=string", benchSizes(benchmarkMapPop[string, string]))
  1160  	b.Run("Key=smallType/Elem=int32", benchSizes(benchmarkMapPop[smallType, int32]))
  1161  	b.Run("Key=mediumType/Elem=int32", benchSizes(benchmarkMapPop[mediumType, int32]))
  1162  	b.Run("Key=bigType/Elem=int32", benchSizes(benchmarkMapPop[bigType, int32]))
  1163  	b.Run("Key=bigType/Elem=bigType", benchSizes(benchmarkMapPop[bigType, bigType]))
  1164  	b.Run("Key=int32/Elem=bigType", benchSizes(benchmarkMapPop[int32, bigType]))
  1165  	b.Run("Key=*int32/Elem=int32", benchSizes(benchmarkMapPop[*int32, int32]))
  1166  	b.Run("Key=int32/Elem=*int32", benchSizes(benchmarkMapPop[int32, *int32]))
  1167  }
  1168  
  1169  func BenchmarkMapDeleteLargeKey(b *testing.B) {
  1170  	m := map[string]int{}
  1171  	for i := range 9 {
  1172  		m[fmt.Sprintf("%d", i)] = i
  1173  	}
  1174  	key := strings.Repeat("*", 10000)
  1175  	for range b.N {
  1176  		delete(m, key)
  1177  	}
  1178  }
  1179  
  1180  func BenchmarkMapSmallAccessHit(b *testing.B) {
  1181  	b.Run("Key=int32/Elem=int32", smallBenchSizes(benchmarkMapAccessHit[int32, int32]))
  1182  	b.Run("Key=int64/Elem=int64", smallBenchSizes(benchmarkMapAccessHit[int64, int64]))
  1183  	b.Run("Key=string/Elem=string", smallBenchSizes(benchmarkMapAccessHit[string, string]))
  1184  	b.Run("Key=smallType/Elem=int32", smallBenchSizes(benchmarkMapAccessHit[smallType, int32]))
  1185  }
  1186  
  1187  func BenchmarkMapSmallAccessMiss(b *testing.B) {
  1188  	b.Run("Key=int32/Elem=int32", smallBenchSizes(benchmarkMapAccessMiss[int32, int32]))
  1189  	b.Run("Key=int64/Elem=int64", smallBenchSizes(benchmarkMapAccessMiss[int64, int64]))
  1190  	b.Run("Key=string/Elem=string", smallBenchSizes(benchmarkMapAccessMiss[string, string]))
  1191  	b.Run("Key=smallType/Elem=int32", smallBenchSizes(benchmarkMapAccessMiss[smallType, int32]))
  1192  }
  1193  
  1194  func mapAccessZeroBenchmark[K comparable](b *testing.B) {
  1195  	var m map[K]uint64
  1196  	var key K
  1197  	for i := 0; i < b.N; i++ {
  1198  		sink = m[key]
  1199  	}
  1200  }
  1201  
  1202  func BenchmarkMapAccessZero(b *testing.B) {
  1203  	b.Run("Key=int64", mapAccessZeroBenchmark[int64])
  1204  	b.Run("Key=int32", mapAccessZeroBenchmark[int32])
  1205  	b.Run("Key=string", mapAccessZeroBenchmark[string])
  1206  	b.Run("Key=mediumType", mapAccessZeroBenchmark[mediumType])
  1207  	b.Run("Key=bigType", mapAccessZeroBenchmark[bigType])
  1208  }
  1209  
  1210  func mapAccessEmptyBenchmark[K mapBenchmarkKeyType](b *testing.B) {
  1211  	m := make(map[K]uint64)
  1212  	for i, v := range genValues[K](0, 1000) {
  1213  		m[v] = uint64(i)
  1214  	}
  1215  	clear(m)
  1216  	var key K
  1217  	for i := 0; i < b.N; i++ {
  1218  		sink = m[key]
  1219  	}
  1220  }
  1221  
  1222  func BenchmarkMapAccessEmpty(b *testing.B) {
  1223  	b.Run("Key=int64", mapAccessEmptyBenchmark[int64])
  1224  	b.Run("Key=int32", mapAccessEmptyBenchmark[int32])
  1225  	b.Run("Key=string", mapAccessEmptyBenchmark[string])
  1226  	b.Run("Key=mediumType", mapAccessEmptyBenchmark[mediumType])
  1227  	b.Run("Key=bigType", mapAccessEmptyBenchmark[bigType])
  1228  }
  1229  

View as plain text