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  	"fmt"
     9  	"math/rand"
    10  	"strconv"
    11  	"strings"
    12  	"testing"
    13  )
    14  
    15  const size = 10
    16  
    17  func BenchmarkHashStringSpeed(b *testing.B) {
    18  	strings := make([]string, size)
    19  	for i := 0; i < size; i++ {
    20  		strings[i] = fmt.Sprintf("string#%d", i)
    21  	}
    22  	sum := 0
    23  	m := make(map[string]int, size)
    24  	for i := 0; i < size; i++ {
    25  		m[strings[i]] = 0
    26  	}
    27  	idx := 0
    28  	b.ResetTimer()
    29  	for i := 0; i < b.N; i++ {
    30  		sum += m[strings[idx]]
    31  		idx++
    32  		if idx == size {
    33  			idx = 0
    34  		}
    35  	}
    36  }
    37  
    38  type chunk [17]byte
    39  
    40  func BenchmarkHashBytesSpeed(b *testing.B) {
    41  	// a bunch of chunks, each with a different alignment mod 16
    42  	var chunks [size]chunk
    43  	// initialize each to a different value
    44  	for i := 0; i < size; i++ {
    45  		chunks[i][0] = byte(i)
    46  	}
    47  	// put into a map
    48  	m := make(map[chunk]int, size)
    49  	for i, c := range chunks {
    50  		m[c] = i
    51  	}
    52  	idx := 0
    53  	b.ResetTimer()
    54  	for i := 0; i < b.N; i++ {
    55  		if m[chunks[idx]] != idx {
    56  			b.Error("bad map entry for chunk")
    57  		}
    58  		idx++
    59  		if idx == size {
    60  			idx = 0
    61  		}
    62  	}
    63  }
    64  
    65  func BenchmarkHashInt32Speed(b *testing.B) {
    66  	ints := make([]int32, size)
    67  	for i := 0; i < size; i++ {
    68  		ints[i] = int32(i)
    69  	}
    70  	sum := 0
    71  	m := make(map[int32]int, size)
    72  	for i := 0; i < size; i++ {
    73  		m[ints[i]] = 0
    74  	}
    75  	idx := 0
    76  	b.ResetTimer()
    77  	for i := 0; i < b.N; i++ {
    78  		sum += m[ints[idx]]
    79  		idx++
    80  		if idx == size {
    81  			idx = 0
    82  		}
    83  	}
    84  }
    85  
    86  func BenchmarkHashInt64Speed(b *testing.B) {
    87  	ints := make([]int64, size)
    88  	for i := 0; i < size; i++ {
    89  		ints[i] = int64(i)
    90  	}
    91  	sum := 0
    92  	m := make(map[int64]int, size)
    93  	for i := 0; i < size; i++ {
    94  		m[ints[i]] = 0
    95  	}
    96  	idx := 0
    97  	b.ResetTimer()
    98  	for i := 0; i < b.N; i++ {
    99  		sum += m[ints[idx]]
   100  		idx++
   101  		if idx == size {
   102  			idx = 0
   103  		}
   104  	}
   105  }
   106  func BenchmarkHashStringArraySpeed(b *testing.B) {
   107  	stringpairs := make([][2]string, size)
   108  	for i := 0; i < size; i++ {
   109  		for j := 0; j < 2; j++ {
   110  			stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
   111  		}
   112  	}
   113  	sum := 0
   114  	m := make(map[[2]string]int, size)
   115  	for i := 0; i < size; i++ {
   116  		m[stringpairs[i]] = 0
   117  	}
   118  	idx := 0
   119  	b.ResetTimer()
   120  	for i := 0; i < b.N; i++ {
   121  		sum += m[stringpairs[idx]]
   122  		idx++
   123  		if idx == size {
   124  			idx = 0
   125  		}
   126  	}
   127  }
   128  
   129  func BenchmarkMegMap(b *testing.B) {
   130  	m := make(map[string]bool)
   131  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   132  		m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
   133  	}
   134  	key := strings.Repeat("X", 1<<20-1) + "k"
   135  	b.ResetTimer()
   136  	for i := 0; i < b.N; i++ {
   137  		_, _ = m[key]
   138  	}
   139  }
   140  
   141  func BenchmarkMegOneMap(b *testing.B) {
   142  	m := make(map[string]bool)
   143  	m[strings.Repeat("X", 1<<20)] = true
   144  	key := strings.Repeat("Y", 1<<20)
   145  	b.ResetTimer()
   146  	for i := 0; i < b.N; i++ {
   147  		_, _ = m[key]
   148  	}
   149  }
   150  
   151  func BenchmarkMegEqMap(b *testing.B) {
   152  	m := make(map[string]bool)
   153  	key1 := strings.Repeat("X", 1<<20)
   154  	key2 := strings.Repeat("X", 1<<20) // equal but different instance
   155  	m[key1] = true
   156  	b.ResetTimer()
   157  	for i := 0; i < b.N; i++ {
   158  		_, _ = m[key2]
   159  	}
   160  }
   161  
   162  func BenchmarkMegEmptyMap(b *testing.B) {
   163  	m := make(map[string]bool)
   164  	key := strings.Repeat("X", 1<<20)
   165  	b.ResetTimer()
   166  	for i := 0; i < b.N; i++ {
   167  		_, _ = m[key]
   168  	}
   169  }
   170  
   171  func BenchmarkMegEmptyMapWithInterfaceKey(b *testing.B) {
   172  	m := make(map[any]bool)
   173  	key := strings.Repeat("X", 1<<20)
   174  	b.ResetTimer()
   175  	for i := 0; i < b.N; i++ {
   176  		_, _ = m[key]
   177  	}
   178  }
   179  
   180  func BenchmarkSmallStrMap(b *testing.B) {
   181  	m := make(map[string]bool)
   182  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   183  		m[fmt.Sprint(suffix)] = true
   184  	}
   185  	key := "k"
   186  	b.ResetTimer()
   187  	for i := 0; i < b.N; i++ {
   188  		_, _ = m[key]
   189  	}
   190  }
   191  
   192  func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
   193  func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
   194  func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
   195  func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
   196  
   197  func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
   198  	m := make(map[string]bool)
   199  	for i := 0; i < 8; i++ {
   200  		m[strings.Repeat("K", i+1)] = true
   201  	}
   202  	key := strings.Repeat("K", keySize)
   203  	b.ResetTimer()
   204  	for i := 0; i < b.N; i++ {
   205  		_ = m[key]
   206  	}
   207  }
   208  
   209  func BenchmarkIntMap(b *testing.B) {
   210  	m := make(map[int]bool)
   211  	for i := 0; i < 8; i++ {
   212  		m[i] = true
   213  	}
   214  	b.ResetTimer()
   215  	for i := 0; i < b.N; i++ {
   216  		_, _ = m[7]
   217  	}
   218  }
   219  
   220  func BenchmarkMapFirst(b *testing.B) {
   221  	for n := 1; n <= 16; n++ {
   222  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   223  			m := make(map[int]bool)
   224  			for i := 0; i < n; i++ {
   225  				m[i] = true
   226  			}
   227  			b.ResetTimer()
   228  			for i := 0; i < b.N; i++ {
   229  				_ = m[0]
   230  			}
   231  		})
   232  	}
   233  }
   234  func BenchmarkMapMid(b *testing.B) {
   235  	for n := 1; n <= 16; n++ {
   236  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   237  			m := make(map[int]bool)
   238  			for i := 0; i < n; i++ {
   239  				m[i] = true
   240  			}
   241  			b.ResetTimer()
   242  			for i := 0; i < b.N; i++ {
   243  				_ = m[n>>1]
   244  			}
   245  		})
   246  	}
   247  }
   248  func BenchmarkMapLast(b *testing.B) {
   249  	for n := 1; n <= 16; n++ {
   250  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   251  			m := make(map[int]bool)
   252  			for i := 0; i < n; i++ {
   253  				m[i] = true
   254  			}
   255  			b.ResetTimer()
   256  			for i := 0; i < b.N; i++ {
   257  				_ = m[n-1]
   258  			}
   259  		})
   260  	}
   261  }
   262  
   263  func BenchmarkMapCycle(b *testing.B) {
   264  	// Arrange map entries to be a permutation, so that
   265  	// we hit all entries, and one lookup is data dependent
   266  	// on the previous lookup.
   267  	const N = 3127
   268  	p := rand.New(rand.NewSource(1)).Perm(N)
   269  	m := map[int]int{}
   270  	for i := 0; i < N; i++ {
   271  		m[i] = p[i]
   272  	}
   273  	b.ResetTimer()
   274  	j := 0
   275  	for i := 0; i < b.N; i++ {
   276  		j = m[j]
   277  	}
   278  	sink = uint64(j)
   279  }
   280  
   281  // Accessing the same keys in a row.
   282  func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
   283  	m := make(map[string]bool)
   284  	// At least bigger than a single bucket:
   285  	for i := 0; i < 64; i++ {
   286  		m[fmt.Sprintf("some key %d", i)] = true
   287  	}
   288  	base := strings.Repeat("x", lookupKeySize-1)
   289  	key1 := base + "1"
   290  	key2 := base + "2"
   291  	b.ResetTimer()
   292  	for i := 0; i < b.N/4; i++ {
   293  		_ = m[key1]
   294  		_ = m[key1]
   295  		_ = m[key2]
   296  		_ = m[key2]
   297  	}
   298  }
   299  
   300  func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
   301  func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
   302  
   303  func BenchmarkMakeMap(b *testing.B) {
   304  	b.Run("[Byte]Byte", func(b *testing.B) {
   305  		var m map[byte]byte
   306  		for i := 0; i < b.N; i++ {
   307  			m = make(map[byte]byte, 10)
   308  		}
   309  		hugeSink = m
   310  	})
   311  	b.Run("[Int]Int", func(b *testing.B) {
   312  		var m map[int]int
   313  		for i := 0; i < b.N; i++ {
   314  			m = make(map[int]int, 10)
   315  		}
   316  		hugeSink = m
   317  	})
   318  }
   319  
   320  func BenchmarkNewEmptyMap(b *testing.B) {
   321  	b.ReportAllocs()
   322  	for i := 0; i < b.N; i++ {
   323  		_ = make(map[int]int)
   324  	}
   325  }
   326  
   327  func BenchmarkNewSmallMap(b *testing.B) {
   328  	b.ReportAllocs()
   329  	for i := 0; i < b.N; i++ {
   330  		m := make(map[int]int)
   331  		m[0] = 0
   332  		m[1] = 1
   333  	}
   334  }
   335  
   336  func BenchmarkMapIter(b *testing.B) {
   337  	m := make(map[int]bool)
   338  	for i := 0; i < 8; i++ {
   339  		m[i] = true
   340  	}
   341  	b.ResetTimer()
   342  	for i := 0; i < b.N; i++ {
   343  		for range m {
   344  		}
   345  	}
   346  }
   347  
   348  func BenchmarkMapIterEmpty(b *testing.B) {
   349  	m := make(map[int]bool)
   350  	b.ResetTimer()
   351  	for i := 0; i < b.N; i++ {
   352  		for range m {
   353  		}
   354  	}
   355  }
   356  
   357  func BenchmarkSameLengthMap(b *testing.B) {
   358  	// long strings, same length, differ in first few
   359  	// and last few bytes.
   360  	m := make(map[string]bool)
   361  	s1 := "foo" + strings.Repeat("-", 100) + "bar"
   362  	s2 := "goo" + strings.Repeat("-", 100) + "ber"
   363  	m[s1] = true
   364  	m[s2] = true
   365  	b.ResetTimer()
   366  	for i := 0; i < b.N; i++ {
   367  		_ = m[s1]
   368  	}
   369  }
   370  
   371  type BigKey [3]int64
   372  
   373  func BenchmarkBigKeyMap(b *testing.B) {
   374  	m := make(map[BigKey]bool)
   375  	k := BigKey{3, 4, 5}
   376  	m[k] = true
   377  	for i := 0; i < b.N; i++ {
   378  		_ = m[k]
   379  	}
   380  }
   381  
   382  type BigVal [3]int64
   383  
   384  func BenchmarkBigValMap(b *testing.B) {
   385  	m := make(map[BigKey]BigVal)
   386  	k := BigKey{3, 4, 5}
   387  	m[k] = BigVal{6, 7, 8}
   388  	for i := 0; i < b.N; i++ {
   389  		_ = m[k]
   390  	}
   391  }
   392  
   393  func BenchmarkSmallKeyMap(b *testing.B) {
   394  	m := make(map[int16]bool)
   395  	m[5] = true
   396  	for i := 0; i < b.N; i++ {
   397  		_ = m[5]
   398  	}
   399  }
   400  
   401  func BenchmarkMapPopulate(b *testing.B) {
   402  	for size := 1; size < 1000000; size *= 10 {
   403  		b.Run(strconv.Itoa(size), func(b *testing.B) {
   404  			b.ReportAllocs()
   405  			for i := 0; i < b.N; i++ {
   406  				m := make(map[int]bool)
   407  				for j := 0; j < size; j++ {
   408  					m[j] = true
   409  				}
   410  			}
   411  		})
   412  	}
   413  }
   414  
   415  type ComplexAlgKey struct {
   416  	a, b, c int64
   417  	_       int
   418  	d       int32
   419  	_       int
   420  	e       string
   421  	_       int
   422  	f, g, h int64
   423  }
   424  
   425  func BenchmarkComplexAlgMap(b *testing.B) {
   426  	m := make(map[ComplexAlgKey]bool)
   427  	var k ComplexAlgKey
   428  	m[k] = true
   429  	for i := 0; i < b.N; i++ {
   430  		_ = m[k]
   431  	}
   432  }
   433  
   434  func BenchmarkGoMapClear(b *testing.B) {
   435  	b.Run("Reflexive", func(b *testing.B) {
   436  		for size := 1; size < 100000; size *= 10 {
   437  			b.Run(strconv.Itoa(size), func(b *testing.B) {
   438  				m := make(map[int]int, size)
   439  				for i := 0; i < b.N; i++ {
   440  					m[0] = size // Add one element so len(m) != 0 avoiding fast paths.
   441  					clear(m)
   442  				}
   443  			})
   444  		}
   445  	})
   446  	b.Run("NonReflexive", func(b *testing.B) {
   447  		for size := 1; size < 100000; size *= 10 {
   448  			b.Run(strconv.Itoa(size), func(b *testing.B) {
   449  				m := make(map[float64]int, size)
   450  				for i := 0; i < b.N; i++ {
   451  					m[1.0] = size // Add one element so len(m) != 0 avoiding fast paths.
   452  					clear(m)
   453  				}
   454  			})
   455  		}
   456  	})
   457  }
   458  
   459  func BenchmarkMapStringConversion(b *testing.B) {
   460  	for _, length := range []int{32, 64} {
   461  		b.Run(strconv.Itoa(length), func(b *testing.B) {
   462  			bytes := make([]byte, length)
   463  			b.Run("simple", func(b *testing.B) {
   464  				b.ReportAllocs()
   465  				m := make(map[string]int)
   466  				m[string(bytes)] = 0
   467  				for i := 0; i < b.N; i++ {
   468  					_ = m[string(bytes)]
   469  				}
   470  			})
   471  			b.Run("struct", func(b *testing.B) {
   472  				b.ReportAllocs()
   473  				type stringstruct struct{ s string }
   474  				m := make(map[stringstruct]int)
   475  				m[stringstruct{string(bytes)}] = 0
   476  				for i := 0; i < b.N; i++ {
   477  					_ = m[stringstruct{string(bytes)}]
   478  				}
   479  			})
   480  			b.Run("array", func(b *testing.B) {
   481  				b.ReportAllocs()
   482  				type stringarray [1]string
   483  				m := make(map[stringarray]int)
   484  				m[stringarray{string(bytes)}] = 0
   485  				for i := 0; i < b.N; i++ {
   486  					_ = m[stringarray{string(bytes)}]
   487  				}
   488  			})
   489  		})
   490  	}
   491  }
   492  
   493  var BoolSink bool
   494  
   495  func BenchmarkMapInterfaceString(b *testing.B) {
   496  	m := map[any]bool{}
   497  
   498  	for i := 0; i < 100; i++ {
   499  		m[fmt.Sprintf("%d", i)] = true
   500  	}
   501  
   502  	key := (any)("A")
   503  	b.ResetTimer()
   504  	for i := 0; i < b.N; i++ {
   505  		BoolSink = m[key]
   506  	}
   507  }
   508  func BenchmarkMapInterfacePtr(b *testing.B) {
   509  	m := map[any]bool{}
   510  
   511  	for i := 0; i < 100; i++ {
   512  		i := i
   513  		m[&i] = true
   514  	}
   515  
   516  	key := new(int)
   517  	b.ResetTimer()
   518  	for i := 0; i < b.N; i++ {
   519  		BoolSink = m[key]
   520  	}
   521  }
   522  
   523  var (
   524  	hintLessThan8    = 7
   525  	hintGreaterThan8 = 32
   526  )
   527  
   528  func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
   529  	b.ReportAllocs()
   530  	for i := 0; i < b.N; i++ {
   531  		_ = make(map[int]int, hintLessThan8)
   532  	}
   533  }
   534  
   535  func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
   536  	b.ReportAllocs()
   537  	for i := 0; i < b.N; i++ {
   538  		_ = make(map[int]int, hintGreaterThan8)
   539  	}
   540  }
   541  

View as plain text