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
5package runtime_test
6
7import (
8	"fmt"
9	"math/rand"
10	"strconv"
11	"strings"
12	"testing"
13)
14
15const size = 10
16
17func 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
38type chunk [17]byte
39
40func 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
65func 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
86func 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}
106func 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
129func 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
141func 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
151func 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
162func 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
171func 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
180func 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
192func BenchmarkMapStringKeysEight_16(b *testing.B) { benchmarkMapStringKeysEight(b, 16) }
193func BenchmarkMapStringKeysEight_32(b *testing.B) { benchmarkMapStringKeysEight(b, 32) }
194func BenchmarkMapStringKeysEight_64(b *testing.B) { benchmarkMapStringKeysEight(b, 64) }
195func BenchmarkMapStringKeysEight_1M(b *testing.B) { benchmarkMapStringKeysEight(b, 1<<20) }
196
197func 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
209func 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
220func 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}
234func 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}
248func 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
263func 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.
282func 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
300func BenchmarkRepeatedLookupStrMapKey32(b *testing.B) { benchmarkRepeatedLookup(b, 32) }
301func BenchmarkRepeatedLookupStrMapKey1M(b *testing.B) { benchmarkRepeatedLookup(b, 1<<20) }
302
303func 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
320func BenchmarkNewEmptyMap(b *testing.B) {
321	b.ReportAllocs()
322	for i := 0; i < b.N; i++ {
323		_ = make(map[int]int)
324	}
325}
326
327func 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
336func 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
348func 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
357func 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
371type BigKey [3]int64
372
373func 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
382type BigVal [3]int64
383
384func 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
393func 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
401func 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
415type 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
425func 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
434func 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
459func 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
493var BoolSink bool
494
495func 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}
508func 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
523var (
524	hintLessThan8    = 7
525	hintGreaterThan8 = 32
526)
527
528func BenchmarkNewEmptyMapHintLessThan8(b *testing.B) {
529	b.ReportAllocs()
530	for i := 0; i < b.N; i++ {
531		_ = make(map[int]int, hintLessThan8)
532	}
533}
534
535func BenchmarkNewEmptyMapHintGreaterThan8(b *testing.B) {
536	b.ReportAllocs()
537	for i := 0; i < b.N; i++ {
538		_ = make(map[int]int, hintGreaterThan8)
539	}
540}
541