...
Run Format

Source file src/runtime/mapspeed_test.go

Documentation: runtime

     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  package runtime_test
     5  
     6  import (
     7  	"fmt"
     8  	"strconv"
     9  	"strings"
    10  	"testing"
    11  )
    12  
    13  const size = 10
    14  
    15  func BenchmarkHashStringSpeed(b *testing.B) {
    16  	strings := make([]string, size)
    17  	for i := 0; i < size; i++ {
    18  		strings[i] = fmt.Sprintf("string#%d", i)
    19  	}
    20  	sum := 0
    21  	m := make(map[string]int, size)
    22  	for i := 0; i < size; i++ {
    23  		m[strings[i]] = 0
    24  	}
    25  	idx := 0
    26  	b.ResetTimer()
    27  	for i := 0; i < b.N; i++ {
    28  		sum += m[strings[idx]]
    29  		idx++
    30  		if idx == size {
    31  			idx = 0
    32  		}
    33  	}
    34  }
    35  
    36  type chunk [17]byte
    37  
    38  func BenchmarkHashBytesSpeed(b *testing.B) {
    39  	// a bunch of chunks, each with a different alignment mod 16
    40  	var chunks [size]chunk
    41  	// initialize each to a different value
    42  	for i := 0; i < size; i++ {
    43  		chunks[i][0] = byte(i)
    44  	}
    45  	// put into a map
    46  	m := make(map[chunk]int, size)
    47  	for i, c := range chunks {
    48  		m[c] = i
    49  	}
    50  	idx := 0
    51  	b.ResetTimer()
    52  	for i := 0; i < b.N; i++ {
    53  		if m[chunks[idx]] != idx {
    54  			b.Error("bad map entry for chunk")
    55  		}
    56  		idx++
    57  		if idx == size {
    58  			idx = 0
    59  		}
    60  	}
    61  }
    62  
    63  func BenchmarkHashInt32Speed(b *testing.B) {
    64  	ints := make([]int32, size)
    65  	for i := 0; i < size; i++ {
    66  		ints[i] = int32(i)
    67  	}
    68  	sum := 0
    69  	m := make(map[int32]int, size)
    70  	for i := 0; i < size; i++ {
    71  		m[ints[i]] = 0
    72  	}
    73  	idx := 0
    74  	b.ResetTimer()
    75  	for i := 0; i < b.N; i++ {
    76  		sum += m[ints[idx]]
    77  		idx++
    78  		if idx == size {
    79  			idx = 0
    80  		}
    81  	}
    82  }
    83  
    84  func BenchmarkHashInt64Speed(b *testing.B) {
    85  	ints := make([]int64, size)
    86  	for i := 0; i < size; i++ {
    87  		ints[i] = int64(i)
    88  	}
    89  	sum := 0
    90  	m := make(map[int64]int, size)
    91  	for i := 0; i < size; i++ {
    92  		m[ints[i]] = 0
    93  	}
    94  	idx := 0
    95  	b.ResetTimer()
    96  	for i := 0; i < b.N; i++ {
    97  		sum += m[ints[idx]]
    98  		idx++
    99  		if idx == size {
   100  			idx = 0
   101  		}
   102  	}
   103  }
   104  func BenchmarkHashStringArraySpeed(b *testing.B) {
   105  	stringpairs := make([][2]string, size)
   106  	for i := 0; i < size; i++ {
   107  		for j := 0; j < 2; j++ {
   108  			stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j)
   109  		}
   110  	}
   111  	sum := 0
   112  	m := make(map[[2]string]int, size)
   113  	for i := 0; i < size; i++ {
   114  		m[stringpairs[i]] = 0
   115  	}
   116  	idx := 0
   117  	b.ResetTimer()
   118  	for i := 0; i < b.N; i++ {
   119  		sum += m[stringpairs[idx]]
   120  		idx++
   121  		if idx == size {
   122  			idx = 0
   123  		}
   124  	}
   125  }
   126  
   127  func BenchmarkMegMap(b *testing.B) {
   128  	m := make(map[string]bool)
   129  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   130  		m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true
   131  	}
   132  	key := strings.Repeat("X", 1<<20-1) + "k"
   133  	b.ResetTimer()
   134  	for i := 0; i < b.N; i++ {
   135  		_, _ = m[key]
   136  	}
   137  }
   138  
   139  func BenchmarkMegOneMap(b *testing.B) {
   140  	m := make(map[string]bool)
   141  	m[strings.Repeat("X", 1<<20)] = true
   142  	key := strings.Repeat("Y", 1<<20)
   143  	b.ResetTimer()
   144  	for i := 0; i < b.N; i++ {
   145  		_, _ = m[key]
   146  	}
   147  }
   148  
   149  func BenchmarkMegEqMap(b *testing.B) {
   150  	m := make(map[string]bool)
   151  	key1 := strings.Repeat("X", 1<<20)
   152  	key2 := strings.Repeat("X", 1<<20) // equal but different instance
   153  	m[key1] = true
   154  	b.ResetTimer()
   155  	for i := 0; i < b.N; i++ {
   156  		_, _ = m[key2]
   157  	}
   158  }
   159  
   160  func BenchmarkMegEmptyMap(b *testing.B) {
   161  	m := make(map[string]bool)
   162  	key := strings.Repeat("X", 1<<20)
   163  	b.ResetTimer()
   164  	for i := 0; i < b.N; i++ {
   165  		_, _ = m[key]
   166  	}
   167  }
   168  
   169  func BenchmarkSmallStrMap(b *testing.B) {
   170  	m := make(map[string]bool)
   171  	for suffix := 'A'; suffix <= 'G'; suffix++ {
   172  		m[fmt.Sprint(suffix)] = true
   173  	}
   174  	key := "k"
   175  	b.ResetTimer()
   176  	for i := 0; i < b.N; i++ {
   177  		_, _ = m[key]
   178  	}
   179  }
   180  
   181  func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
   182  func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
   183  func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
   184  func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
   185  
   186  func benchmarkMapStringKeysEight(b *testing.B, keySize int) {
   187  	m := make(map[string]bool)
   188  	for i := 0; i < 8; i++ {
   189  		m[strings.Repeat("K", i+1)] = true
   190  	}
   191  	key := strings.Repeat("K", keySize)
   192  	b.ResetTimer()
   193  	for i := 0; i < b.N; i++ {
   194  		_ = m[key]
   195  	}
   196  }
   197  
   198  func BenchmarkIntMap(b *testing.B) {
   199  	m := make(map[int]bool)
   200  	for i := 0; i < 8; i++ {
   201  		m[i] = true
   202  	}
   203  	b.ResetTimer()
   204  	for i := 0; i < b.N; i++ {
   205  		_, _ = m[7]
   206  	}
   207  }
   208  
   209  // Accessing the same keys in a row.
   210  func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
   211  	m := make(map[string]bool)
   212  	// At least bigger than a single bucket:
   213  	for i := 0; i < 64; i++ {
   214  		m[fmt.Sprintf("some key %d", i)] = true
   215  	}
   216  	base := strings.Repeat("x", lookupKeySize-1)
   217  	key1 := base + "1"
   218  	key2 := base + "2"
   219  	b.ResetTimer()
   220  	for i := 0; i < b.N/4; i++ {
   221  		_ = m[key1]
   222  		_ = m[key1]
   223  		_ = m[key2]
   224  		_ = m[key2]
   225  	}
   226  }
   227  
   228  func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
   229  func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
   230  
   231  func BenchmarkNewEmptyMap(b *testing.B) {
   232  	b.ReportAllocs()
   233  	for i := 0; i < b.N; i++ {
   234  		_ = make(map[int]int)
   235  	}
   236  }
   237  
   238  func BenchmarkNewSmallMap(b *testing.B) {
   239  	b.ReportAllocs()
   240  	for i := 0; i < b.N; i++ {
   241  		m := make(map[int]int)
   242  		m[0] = 0
   243  		m[1] = 1
   244  	}
   245  }
   246  
   247  func BenchmarkMapIter(b *testing.B) {
   248  	m := make(map[int]bool)
   249  	for i := 0; i < 8; i++ {
   250  		m[i] = true
   251  	}
   252  	b.ResetTimer()
   253  	for i := 0; i < b.N; i++ {
   254  		for range m {
   255  		}
   256  	}
   257  }
   258  
   259  func BenchmarkMapIterEmpty(b *testing.B) {
   260  	m := make(map[int]bool)
   261  	b.ResetTimer()
   262  	for i := 0; i < b.N; i++ {
   263  		for range m {
   264  		}
   265  	}
   266  }
   267  
   268  func BenchmarkSameLengthMap(b *testing.B) {
   269  	// long strings, same length, differ in first few
   270  	// and last few bytes.
   271  	m := make(map[string]bool)
   272  	s1 := "foo" + strings.Repeat("-", 100) + "bar"
   273  	s2 := "goo" + strings.Repeat("-", 100) + "ber"
   274  	m[s1] = true
   275  	m[s2] = true
   276  	b.ResetTimer()
   277  	for i := 0; i < b.N; i++ {
   278  		_ = m[s1]
   279  	}
   280  }
   281  
   282  type BigKey [3]int64
   283  
   284  func BenchmarkBigKeyMap(b *testing.B) {
   285  	m := make(map[BigKey]bool)
   286  	k := BigKey{3, 4, 5}
   287  	m[k] = true
   288  	for i := 0; i < b.N; i++ {
   289  		_ = m[k]
   290  	}
   291  }
   292  
   293  type BigVal [3]int64
   294  
   295  func BenchmarkBigValMap(b *testing.B) {
   296  	m := make(map[BigKey]BigVal)
   297  	k := BigKey{3, 4, 5}
   298  	m[k] = BigVal{6, 7, 8}
   299  	for i := 0; i < b.N; i++ {
   300  		_ = m[k]
   301  	}
   302  }
   303  
   304  func BenchmarkSmallKeyMap(b *testing.B) {
   305  	m := make(map[int16]bool)
   306  	m[5] = true
   307  	for i := 0; i < b.N; i++ {
   308  		_ = m[5]
   309  	}
   310  }
   311  
   312  func BenchmarkMapPopulate(b *testing.B) {
   313  	for size := 1; size < 1000000; size *= 10 {
   314  		b.Run(strconv.Itoa(size), func(b *testing.B) {
   315  			b.ReportAllocs()
   316  			for i := 0; i < b.N; i++ {
   317  				m := make(map[int]bool)
   318  				for j := 0; j < size; j++ {
   319  					m[j] = true
   320  				}
   321  			}
   322  		})
   323  	}
   324  }
   325  
   326  type ComplexAlgKey struct {
   327  	a, b, c int64
   328  	_       int
   329  	d       int32
   330  	_       int
   331  	e       string
   332  	_       int
   333  	f, g, h int64
   334  }
   335  
   336  func BenchmarkComplexAlgMap(b *testing.B) {
   337  	m := make(map[ComplexAlgKey]bool)
   338  	var k ComplexAlgKey
   339  	m[k] = true
   340  	for i := 0; i < b.N; i++ {
   341  		_ = m[k]
   342  	}
   343  }
   344  

View as plain text