Source file
src/runtime/map_benchmark_test.go
Documentation: runtime
1
2
3
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
42 var chunks [size]chunk
43
44 for i := 0; i < size; i++ {
45 chunks[i][0] = byte(i)
46 }
47
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)
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
256
257
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
273 func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) {
274 m := make(map[string]bool)
275
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
350
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
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
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[interface{}]bool{}
492
493 for i := 0; i < 100; i++ {
494 m[fmt.Sprintf("%d", i)] = true
495 }
496
497 key := (interface{})("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[interface{}]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 }
536
View as plain text