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