libgo/go/runtime/mapspeed_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 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 }