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 }