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. 4package runtime_test 5 6import ( 7 "fmt" 8 "math/rand" 9 "strconv" 10 "strings" 11 "testing" 12) 13 14const size = 10 15 16func BenchmarkHashStringSpeed(b *testing.B) { 17 strings := make([]string, size) 18 for i := 0; i < size; i++ { 19 strings[i] = fmt.Sprintf("string#%d", i) 20 } 21 sum := 0 22 m := make(map[string]int, size) 23 for i := 0; i < size; i++ { 24 m[strings[i]] = 0 25 } 26 idx := 0 27 b.ResetTimer() 28 for i := 0; i < b.N; i++ { 29 sum += m[strings[idx]] 30 idx++ 31 if idx == size { 32 idx = 0 33 } 34 } 35} 36 37type chunk [17]byte 38 39func BenchmarkHashBytesSpeed(b *testing.B) { 40 // a bunch of chunks, each with a different alignment mod 16 41 var chunks [size]chunk 42 // initialize each to a different value 43 for i := 0; i < size; i++ { 44 chunks[i][0] = byte(i) 45 } 46 // put into a map 47 m := make(map[chunk]int, size) 48 for i, c := range chunks { 49 m[c] = i 50 } 51 idx := 0 52 b.ResetTimer() 53 for i := 0; i < b.N; i++ { 54 if m[chunks[idx]] != idx { 55 b.Error("bad map entry for chunk") 56 } 57 idx++ 58 if idx == size { 59 idx = 0 60 } 61 } 62} 63 64func BenchmarkHashInt32Speed(b *testing.B) { 65 ints := make([]int32, size) 66 for i := 0; i < size; i++ { 67 ints[i] = int32(i) 68 } 69 sum := 0 70 m := make(map[int32]int, size) 71 for i := 0; i < size; i++ { 72 m[ints[i]] = 0 73 } 74 idx := 0 75 b.ResetTimer() 76 for i := 0; i < b.N; i++ { 77 sum += m[ints[idx]] 78 idx++ 79 if idx == size { 80 idx = 0 81 } 82 } 83} 84 85func BenchmarkHashInt64Speed(b *testing.B) { 86 ints := make([]int64, size) 87 for i := 0; i < size; i++ { 88 ints[i] = int64(i) 89 } 90 sum := 0 91 m := make(map[int64]int, size) 92 for i := 0; i < size; i++ { 93 m[ints[i]] = 0 94 } 95 idx := 0 96 b.ResetTimer() 97 for i := 0; i < b.N; i++ { 98 sum += m[ints[idx]] 99 idx++ 100 if idx == size { 101 idx = 0 102 } 103 } 104} 105func BenchmarkHashStringArraySpeed(b *testing.B) { 106 stringpairs := make([][2]string, size) 107 for i := 0; i < size; i++ { 108 for j := 0; j < 2; j++ { 109 stringpairs[i][j] = fmt.Sprintf("string#%d/%d", i, j) 110 } 111 } 112 sum := 0 113 m := make(map[[2]string]int, size) 114 for i := 0; i < size; i++ { 115 m[stringpairs[i]] = 0 116 } 117 idx := 0 118 b.ResetTimer() 119 for i := 0; i < b.N; i++ { 120 sum += m[stringpairs[idx]] 121 idx++ 122 if idx == size { 123 idx = 0 124 } 125 } 126} 127 128func BenchmarkMegMap(b *testing.B) { 129 m := make(map[string]bool) 130 for suffix := 'A'; suffix <= 'G'; suffix++ { 131 m[strings.Repeat("X", 1<<20-1)+fmt.Sprint(suffix)] = true 132 } 133 key := strings.Repeat("X", 1<<20-1) + "k" 134 b.ResetTimer() 135 for i := 0; i < b.N; i++ { 136 _, _ = m[key] 137 } 138} 139 140func BenchmarkMegOneMap(b *testing.B) { 141 m := make(map[string]bool) 142 m[strings.Repeat("X", 1<<20)] = true 143 key := strings.Repeat("Y", 1<<20) 144 b.ResetTimer() 145 for i := 0; i < b.N; i++ { 146 _, _ = m[key] 147 } 148} 149 150func BenchmarkMegEqMap(b *testing.B) { 151 m := make(map[string]bool) 152 key1 := strings.Repeat("X", 1<<20) 153 key2 := strings.Repeat("X", 1<<20) // equal but different instance 154 m[key1] = true 155 b.ResetTimer() 156 for i := 0; i < b.N; i++ { 157 _, _ = m[key2] 158 } 159} 160 161func BenchmarkMegEmptyMap(b *testing.B) { 162 m := make(map[string]bool) 163 key := strings.Repeat("X", 1<<20) 164 b.ResetTimer() 165 for i := 0; i < b.N; i++ { 166 _, _ = m[key] 167 } 168} 169 170func BenchmarkSmallStrMap(b *testing.B) { 171 m := make(map[string]bool) 172 for suffix := 'A'; suffix <= 'G'; suffix++ { 173 m[fmt.Sprint(suffix)] = true 174 } 175 key := "k" 176 b.ResetTimer() 177 for i := 0; i < b.N; i++ { 178 _, _ = m[key] 179 } 180} 181 182func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) } 183func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) } 184func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) } 185func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) } 186 187func benchmarkMapStringKeysEight(b *testing.B, keySize int) { 188 m := make(map[string]bool) 189 for i := 0; i < 8; i++ { 190 m[strings.Repeat("K", i+1)] = true 191 } 192 key := strings.Repeat("K", keySize) 193 b.ResetTimer() 194 for i := 0; i < b.N; i++ { 195 _ = m[key] 196 } 197} 198 199func BenchmarkIntMap(b *testing.B) { 200 m := make(map[int]bool) 201 for i := 0; i < 8; i++ { 202 m[i] = true 203 } 204 b.ResetTimer() 205 for i := 0; i < b.N; i++ { 206 _, _ = m[7] 207 } 208} 209 210func BenchmarkMapFirst(b *testing.B) { 211 for n := 1; n <= 16; n++ { 212 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { 213 m := make(map[int]bool) 214 for i := 0; i < n; i++ { 215 m[i] = true 216 } 217 b.ResetTimer() 218 for i := 0; i < b.N; i++ { 219 _ = m[0] 220 } 221 }) 222 } 223} 224func BenchmarkMapMid(b *testing.B) { 225 for n := 1; n <= 16; n++ { 226 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { 227 m := make(map[int]bool) 228 for i := 0; i < n; i++ { 229 m[i] = true 230 } 231 b.ResetTimer() 232 for i := 0; i < b.N; i++ { 233 _ = m[n>>1] 234 } 235 }) 236 } 237} 238func BenchmarkMapLast(b *testing.B) { 239 for n := 1; n <= 16; n++ { 240 b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { 241 m := make(map[int]bool) 242 for i := 0; i < n; i++ { 243 m[i] = true 244 } 245 b.ResetTimer() 246 for i := 0; i < b.N; i++ { 247 _ = m[n-1] 248 } 249 }) 250 } 251} 252 253func BenchmarkMapCycle(b *testing.B) { 254 // Arrange map entries to be a permutation, so that 255 // we hit all entries, and one lookup is data dependent 256 // on the previous lookup. 257 const N = 3127 258 p := rand.New(rand.NewSource(1)).Perm(N) 259 m := map[int]int{} 260 for i := 0; i < N; i++ { 261 m[i] = p[i] 262 } 263 b.ResetTimer() 264 j := 0 265 for i := 0; i < b.N; i++ { 266 j = m[j] 267 } 268 sink = uint64(j) 269} 270 271// Accessing the same keys in a row. 272func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) { 273 m := make(map[string]bool) 274 // At least bigger than a single bucket: 275 for i := 0; i < 64; i++ { 276 m[fmt.Sprintf("some key %d", i)] = true 277 } 278 base := strings.Repeat("x", lookupKeySize-1) 279 key1 := base + "1" 280 key2 := base + "2" 281 b.ResetTimer() 282 for i := 0; i < b.N/4; i++ { 283 _ = m[key1] 284 _ = m[key1] 285 _ = m[key2] 286 _ = m[key2] 287 } 288} 289 290func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) } 291func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) } 292 293func BenchmarkMakeMap(b *testing.B) { 294 b.Run("[Byte]Byte", func(b *testing.B) { 295 var m map[byte]byte 296 for i := 0; i < b.N; i++ { 297 m = make(map[byte]byte, 10) 298 } 299 hugeSink = m 300 }) 301 b.Run("[Int]Int", func(b *testing.B) { 302 var m map[int]int 303 for i := 0; i < b.N; i++ { 304 m = make(map[int]int, 10) 305 } 306 hugeSink = m 307 }) 308} 309 310func BenchmarkNewEmptyMap(b *testing.B) { 311 b.ReportAllocs() 312 for i := 0; i < b.N; i++ { 313 _ = make(map[int]int) 314 } 315} 316 317func BenchmarkNewSmallMap(b *testing.B) { 318 b.ReportAllocs() 319 for i := 0; i < b.N; i++ { 320 m := make(map[int]int) 321 m[0] = 0 322 m[1] = 1 323 } 324} 325 326func BenchmarkMapIter(b *testing.B) { 327 m := make(map[int]bool) 328 for i := 0; i < 8; i++ { 329 m[i] = true 330 } 331 b.ResetTimer() 332 for i := 0; i < b.N; i++ { 333 for range m { 334 } 335 } 336} 337 338func BenchmarkMapIterEmpty(b *testing.B) { 339 m := make(map[int]bool) 340 b.ResetTimer() 341 for i := 0; i < b.N; i++ { 342 for range m { 343 } 344 } 345} 346 347func BenchmarkSameLengthMap(b *testing.B) { 348 // long strings, same length, differ in first few 349 // and last few bytes. 350 m := make(map[string]bool) 351 s1 := "foo" + strings.Repeat("-", 100) + "bar" 352 s2 := "goo" + strings.Repeat("-", 100) + "ber" 353 m[s1] = true 354 m[s2] = true 355 b.ResetTimer() 356 for i := 0; i < b.N; i++ { 357 _ = m[s1] 358 } 359} 360 361type BigKey [3]int64 362 363func BenchmarkBigKeyMap(b *testing.B) { 364 m := make(map[BigKey]bool) 365 k := BigKey{3, 4, 5} 366 m[k] = true 367 for i := 0; i < b.N; i++ { 368 _ = m[k] 369 } 370} 371 372type BigVal [3]int64 373 374func BenchmarkBigValMap(b *testing.B) { 375 m := make(map[BigKey]BigVal) 376 k := BigKey{3, 4, 5} 377 m[k] = BigVal{6, 7, 8} 378 for i := 0; i < b.N; i++ { 379 _ = m[k] 380 } 381} 382 383func BenchmarkSmallKeyMap(b *testing.B) { 384 m := make(map[int16]bool) 385 m[5] = true 386 for i := 0; i < b.N; i++ { 387 _ = m[5] 388 } 389} 390 391func BenchmarkMapPopulate(b *testing.B) { 392 for size := 1; size < 1000000; size *= 10 { 393 b.Run(strconv.Itoa(size), func(b *testing.B) { 394 b.ReportAllocs() 395 for i := 0; i < b.N; i++ { 396 m := make(map[int]bool) 397 for j := 0; j < size; j++ { 398 m[j] = true 399 } 400 } 401 }) 402 } 403} 404 405type ComplexAlgKey struct { 406 a, b, c int64 407 _ int 408 d int32 409 _ int 410 e string 411 _ int 412 f, g, h int64 413} 414 415func BenchmarkComplexAlgMap(b *testing.B) { 416 m := make(map[ComplexAlgKey]bool) 417 var k ComplexAlgKey 418 m[k] = true 419 for i := 0; i < b.N; i++ { 420 _ = m[k] 421 } 422} 423 424func BenchmarkGoMapClear(b *testing.B) { 425 b.Run("Reflexive", func(b *testing.B) { 426 for size := 1; size < 100000; size *= 10 { 427 b.Run(strconv.Itoa(size), func(b *testing.B) { 428 m := make(map[int]int, size) 429 for i := 0; i < b.N; i++ { 430 m[0] = size // Add one element so len(m) != 0 avoiding fast paths. 431 for k := range m { 432 delete(m, k) 433 } 434 } 435 }) 436 } 437 }) 438 b.Run("NonReflexive", func(b *testing.B) { 439 for size := 1; size < 100000; size *= 10 { 440 b.Run(strconv.Itoa(size), func(b *testing.B) { 441 m := make(map[float64]int, size) 442 for i := 0; i < b.N; i++ { 443 m[1.0] = size // Add one element so len(m) != 0 avoiding fast paths. 444 for k := range m { 445 delete(m, k) 446 } 447 } 448 }) 449 } 450 }) 451} 452 453func BenchmarkMapStringConversion(b *testing.B) { 454 for _, length := range []int{32, 64} { 455 b.Run(strconv.Itoa(length), func(b *testing.B) { 456 bytes := make([]byte, length) 457 b.Run("simple", func(b *testing.B) { 458 b.ReportAllocs() 459 m := make(map[string]int) 460 m[string(bytes)] = 0 461 for i := 0; i < b.N; i++ { 462 _ = m[string(bytes)] 463 } 464 }) 465 b.Run("struct", func(b *testing.B) { 466 b.ReportAllocs() 467 type stringstruct struct{ s string } 468 m := make(map[stringstruct]int) 469 m[stringstruct{string(bytes)}] = 0 470 for i := 0; i < b.N; i++ { 471 _ = m[stringstruct{string(bytes)}] 472 } 473 }) 474 b.Run("array", func(b *testing.B) { 475 b.ReportAllocs() 476 type stringarray [1]string 477 m := make(map[stringarray]int) 478 m[stringarray{string(bytes)}] = 0 479 for i := 0; i < b.N; i++ { 480 _ = m[stringarray{string(bytes)}] 481 } 482 }) 483 }) 484 } 485} 486 487var BoolSink bool 488 489func BenchmarkMapInterfaceString(b *testing.B) { 490 m := map[interface{}]bool{} 491 492 for i := 0; i < 100; i++ { 493 m[fmt.Sprintf("%d", i)] = true 494 } 495 496 key := (interface{})("A") 497 b.ResetTimer() 498 for i := 0; i < b.N; i++ { 499 BoolSink = m[key] 500 } 501} 502func BenchmarkMapInterfacePtr(b *testing.B) { 503 m := map[interface{}]bool{} 504 505 for i := 0; i < 100; i++ { 506 i := i 507 m[&i] = true 508 } 509 510 key := new(int) 511 b.ResetTimer() 512 for i := 0; i < b.N; i++ { 513 BoolSink = m[key] 514 } 515} 516