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 BenchmarkSmallStrMap(b *testing.B) {
   172  	m := make(map[string]bool)
   173  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   174  		m[fmt.Sprint(suffix)] = true
   175  	}
   176  	key := "k"
   177  	b.ResetTimer()
   178  	for i := 0; i < b.N; i++ {
   179  		_, _ = m[key]
   180  	}
   181  }
   182  
   183  func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
   184  func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
   185  func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
   186  func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
   187  
   188  func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
   189  	m := make(map[string]bool)
   190  	for i := 0; i < 8; i++ {
   191  		m[strings.Repeat("K", i+1)] = true
   192  	}
   193  	key := strings.Repeat("K", keySize)
   194  	b.ResetTimer()
   195  	for i := 0; i < b.N; i++ {
   196  		_ = m[key]
   197  	}
   198  }
   199  
   200  func BenchmarkIntMap(b *testing.B) {
   201  	m := make(map[int]bool)
   202  	for i := 0; i < 8; i++ {
   203  		m[i] = true
   204  	}
   205  	b.ResetTimer()
   206  	for i := 0; i < b.N; i++ {
   207  		_, _ = m[7]
   208  	}
   209  }
   210  
   211  func BenchmarkMapFirst(b *testing.B) {
   212  	for n := 1; n <= 16; n++ {
   213  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   214  			m := make(map[int]bool)
   215  			for i := 0; i < n; i++ {
   216  				m[i] = true
   217  			}
   218  			b.ResetTimer()
   219  			for i := 0; i < b.N; i++ {
   220  				_ = m[0]
   221  			}
   222  		})
   223  	}
   224  }
   225  func BenchmarkMapMid(b *testing.B) {
   226  	for n := 1; n <= 16; n++ {
   227  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   228  			m := make(map[int]bool)
   229  			for i := 0; i < n; i++ {
   230  				m[i] = true
   231  			}
   232  			b.ResetTimer()
   233  			for i := 0; i < b.N; i++ {
   234  				_ = m[n>>1]
   235  			}
   236  		})
   237  	}
   238  }
   239  func BenchmarkMapLast(b *testing.B) {
   240  	for n := 1; n <= 16; n++ {
   241  		b.Run(fmt.Sprintf("%d", n), func(b *testing.B) {
   242  			m := make(map[int]bool)
   243  			for i := 0; i < n; i++ {
   244  				m[i] = true
   245  			}
   246  			b.ResetTimer()
   247  			for i := 0; i < b.N; i++ {
   248  				_ = m[n-1]
   249  			}
   250  		})
   251  	}
   252  }
   253  
   254  func BenchmarkMapCycle(b *testing.B) {
   255  	// Arrange map entries to be a permutation, so that
   256  	// we hit all entries, and one lookup is data dependent
   257  	// on the previous lookup.
   258  	const N = 3127
   259  	p := rand.New(rand.NewSource(1)).Perm(N)
   260  	m := map[int]int{}
   261  	for i := 0; i < N; i++ {
   262  		m[i] = p[i]
   263  	}
   264  	b.ResetTimer()
   265  	j := 0
   266  	for i := 0; i < b.N; i++ {
   267  		j = m[j]
   268  	}
   269  	sink = uint64(j)
   270  }
   271  
   272  // Accessing the same keys in a row.
   273  func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
   274  	m := make(map[string]bool)
   275  	// At least bigger than a single bucket:
   276  	for i := 0; i < 64; i++ {
   277  		m[fmt.Sprintf("some key %d", i)] = true
   278  	}
   279  	base := strings.Repeat("x", lookupKeySize-1)
   280  	key1 := base + "1"
   281  	key2 := base + "2"
   282  	b.ResetTimer()
   283  	for i := 0; i < b.N/4; i++ {
   284  		_ = m[key1]
   285  		_ = m[key1]
   286  		_ = m[key2]
   287  		_ = m[key2]
   288  	}
   289  }
   290  
   291  func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
   292  func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
   293  
   294  func BenchmarkMakeMap(b *testing.B) {
   295  	b.Run("[Byte]Byte", func(b *testing.B) {
   296  		var m map[byte]byte
   297  		for i := 0; i < b.N; i++ {
   298  			m = make(map[byte]byte, 10)
   299  		}
   300  		hugeSink = m
   301  	})
   302  	b.Run("[Int]Int", func(b *testing.B) {
   303  		var m map[int]int
   304  		for i := 0; i < b.N; i++ {
   305  			m = make(map[int]int, 10)
   306  		}
   307  		hugeSink = m
   308  	})
   309  }
   310  
   311  func BenchmarkNewEmptyMap(b *testing.B) {
   312  	b.ReportAllocs()
   313  	for i := 0; i < b.N; i++ {
   314  		_ = make(map[int]int)
   315  	}
   316  }
   317  
   318  func BenchmarkNewSmallMap(b *testing.B) {
   319  	b.ReportAllocs()
   320  	for i := 0; i < b.N; i++ {
   321  		m := make(map[int]int)
   322  		m[0] = 0
   323  		m[1] = 1
   324  	}
   325  }
   326  
   327  func BenchmarkMapIter(b *testing.B) {
   328  	m := make(map[int]bool)
   329  	for i := 0; i < 8; i++ {
   330  		m[i] = true
   331  	}
   332  	b.ResetTimer()
   333  	for i := 0; i < b.N; i++ {
   334  		for range m {
   335  		}
   336  	}
   337  }
   338  
   339  func BenchmarkMapIterEmpty(b *testing.B) {
   340  	m := make(map[int]bool)
   341  	b.ResetTimer()
   342  	for i := 0; i < b.N; i++ {
   343  		for range m {
   344  		}
   345  	}
   346  }
   347  
   348  func BenchmarkSameLengthMap(b *testing.B) {
   349  	// long strings, same length, differ in first few
   350  	// and last few bytes.
   351  	m := make(map[string]bool)
   352  	s1 := "foo" + strings.Repeat("-", 100) + "bar"
   353  	s2 := "goo" + strings.Repeat("-", 100) + "ber"
   354  	m[s1] = true
   355  	m[s2] = true
   356  	b.ResetTimer()
   357  	for i := 0; i < b.N; i++ {
   358  		_ = m[s1]
   359  	}
   360  }
   361  
   362  type BigKey [3]int64
   363  
   364  func BenchmarkBigKeyMap(b *testing.B) {
   365  	m := make(map[BigKey]bool)
   366  	k := BigKey{3, 4, 5}
   367  	m[k] = true
   368  	for i := 0; i < b.N; i++ {
   369  		_ = m[k]
   370  	}
   371  }
   372  
   373  type BigVal [3]int64
   374  
   375  func BenchmarkBigValMap(b *testing.B) {
   376  	m := make(map[BigKey]BigVal)
   377  	k := BigKey{3, 4, 5}
   378  	m[k] = BigVal{6, 7, 8}
   379  	for i := 0; i < b.N; i++ {
   380  		_ = m[k]
   381  	}
   382  }
   383  
   384  func BenchmarkSmallKeyMap(b *testing.B) {
   385  	m := make(map[int16]bool)
   386  	m[5] = true
   387  	for i := 0; i < b.N; i++ {
   388  		_ = m[5]
   389  	}
   390  }
   391  
   392  func BenchmarkMapPopulate(b *testing.B) {
   393  	for size := 1; size < 1000000; size *= 10 {
   394  		b.Run(strconv.Itoa(size), func(b *testing.B) {
   395  			b.ReportAllocs()
   396  			for i := 0; i < b.N; i++ {
   397  				m := make(map[int]bool)
   398  				for j := 0; j < size; j++ {
   399  					m[j] = true
   400  				}
   401  			}
   402  		})
   403  	}
   404  }
   405  
   406  type ComplexAlgKey struct {
   407  	a, b, c int64
   408  	_       int
   409  	d       int32
   410  	_       int
   411  	e       string
   412  	_       int
   413  	f, g, h int64
   414  }
   415  
   416  func BenchmarkComplexAlgMap(b *testing.B) {
   417  	m := make(map[ComplexAlgKey]bool)
   418  	var k ComplexAlgKey
   419  	m[k] = true
   420  	for i := 0; i < b.N; i++ {
   421  		_ = m[k]
   422  	}
   423  }
   424  
   425  func BenchmarkGoMapClear(b *testing.B) {
   426  	b.Run("Reflexive", func(b *testing.B) {
   427  		for size := 1; size < 100000; size *= 10 {
   428  			b.Run(strconv.Itoa(size), func(b *testing.B) {
   429  				m := make(map[int]int, size)
   430  				for i := 0; i < b.N; i++ {
   431  					m[0] = size // Add one element so len(m) != 0 avoiding fast paths.
   432  					for k := range m {
   433  						delete(m, k)
   434  					}
   435  				}
   436  			})
   437  		}
   438  	})
   439  	b.Run("NonReflexive", func(b *testing.B) {
   440  		for size := 1; size < 100000; size *= 10 {
   441  			b.Run(strconv.Itoa(size), func(b *testing.B) {
   442  				m := make(map[float64]int, size)
   443  				for i := 0; i < b.N; i++ {
   444  					m[1.0] = size // Add one element so len(m) != 0 avoiding fast paths.
   445  					for k := range m {
   446  						delete(m, k)
   447  					}
   448  				}
   449  			})
   450  		}
   451  	})
   452  }
   453  
   454  func BenchmarkMapStringConversion(b *testing.B) {
   455  	for _, length := range []int{32, 64} {
   456  		b.Run(strconv.Itoa(length), func(b *testing.B) {
   457  			bytes := make([]byte, length)
   458  			b.Run("simple", func(b *testing.B) {
   459  				b.ReportAllocs()
   460  				m := make(map[string]int)
   461  				m[string(bytes)] = 0
   462  				for i := 0; i < b.N; i++ {
   463  					_ = m[string(bytes)]
   464  				}
   465  			})
   466  			b.Run("struct", func(b *testing.B) {
   467  				b.ReportAllocs()
   468  				type stringstruct struct{ s string }
   469  				m := make(map[stringstruct]int)
   470  				m[stringstruct{string(bytes)}] = 0
   471  				for i := 0; i < b.N; i++ {
   472  					_ = m[stringstruct{string(bytes)}]
   473  				}
   474  			})
   475  			b.Run("array", func(b *testing.B) {
   476  				b.ReportAllocs()
   477  				type stringarray [1]string
   478  				m := make(map[stringarray]int)
   479  				m[stringarray{string(bytes)}] = 0
   480  				for i := 0; i < b.N; i++ {
   481  					_ = m[stringarray{string(bytes)}]
   482  				}
   483  			})
   484  		})
   485  	}
   486  }
   487  
   488  var BoolSink bool
   489  
   490  func BenchmarkMapInterfaceString(b *testing.B) {
   491  	m := map[any]bool{}
   492  
   493  	for i := 0; i < 100; i++ {
   494  		m[fmt.Sprintf("%d", i)] = true
   495  	}
   496  
   497  	key := (any)("A")
   498  	b.ResetTimer()
   499  	for i := 0; i < b.N; i++ {
   500  		BoolSink = m[key]
   501  	}
   502  }
   503  func BenchmarkMapInterfacePtr(b *testing.B) {
   504  	m := map[any]bool{}
   505  
   506  	for i := 0; i < 100; i++ {
   507  		i := i
   508  		m[&i] = true
   509  	}
   510  
   511  	key := new(int)
   512  	b.ResetTimer()
   513  	for i := 0; i < b.N; i++ {
   514  		BoolSink = m[key]
   515  	}
   516  }
   517  
   518  var (
   519  	hintLessThan8    = 7
   520  	hintGreaterThan8 = 32
   521  )
   522  
   523  func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
   524  	b.ReportAllocs()
   525  	for i := 0; i < b.N; i++ {
   526  		_ = make(map[int]int, hintLessThan8)
   527  	}
   528  }
   529  
   530  func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
   531  	b.ReportAllocs()
   532  	for i := 0; i < b.N; i++ {
   533  		_ = make(map[int]int, hintGreaterThan8)
   534  	}
   535  }
   536  

View as plain text