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