1// Copyright 2016 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 sync_test
6
7import (
8	"fmt"
9	"reflect"
10	"sync"
11	"sync/atomic"
12	"testing"
13)
14
15type bench struct {
16	setup func(*testing.B, mapInterface)
17	perG  func(b *testing.B, pb *testing.PB, i int, m mapInterface)
18}
19
20func benchMap(b *testing.B, bench bench) {
21	for _, m := range [...]mapInterface{&DeepCopyMap{}, &RWMutexMap{}, &sync.Map{}} {
22		b.Run(fmt.Sprintf("%T", m), func(b *testing.B) {
23			m = reflect.New(reflect.TypeOf(m).Elem()).Interface().(mapInterface)
24			if bench.setup != nil {
25				bench.setup(b, m)
26			}
27
28			b.ResetTimer()
29
30			var i int64
31			b.RunParallel(func(pb *testing.PB) {
32				id := int(atomic.AddInt64(&i, 1) - 1)
33				bench.perG(b, pb, id*b.N, m)
34			})
35		})
36	}
37}
38
39func BenchmarkLoadMostlyHits(b *testing.B) {
40	const hits, misses = 1023, 1
41
42	benchMap(b, bench{
43		setup: func(_ *testing.B, m mapInterface) {
44			for i := 0; i < hits; i++ {
45				m.LoadOrStore(i, i)
46			}
47			// Prime the map to get it into a steady state.
48			for i := 0; i < hits*2; i++ {
49				m.Load(i % hits)
50			}
51		},
52
53		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
54			for ; pb.Next(); i++ {
55				m.Load(i % (hits + misses))
56			}
57		},
58	})
59}
60
61func BenchmarkLoadMostlyMisses(b *testing.B) {
62	const hits, misses = 1, 1023
63
64	benchMap(b, bench{
65		setup: func(_ *testing.B, m mapInterface) {
66			for i := 0; i < hits; i++ {
67				m.LoadOrStore(i, i)
68			}
69			// Prime the map to get it into a steady state.
70			for i := 0; i < hits*2; i++ {
71				m.Load(i % hits)
72			}
73		},
74
75		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
76			for ; pb.Next(); i++ {
77				m.Load(i % (hits + misses))
78			}
79		},
80	})
81}
82
83func BenchmarkLoadOrStoreBalanced(b *testing.B) {
84	const hits, misses = 128, 128
85
86	benchMap(b, bench{
87		setup: func(b *testing.B, m mapInterface) {
88			if _, ok := m.(*DeepCopyMap); ok {
89				b.Skip("DeepCopyMap has quadratic running time.")
90			}
91			for i := 0; i < hits; i++ {
92				m.LoadOrStore(i, i)
93			}
94			// Prime the map to get it into a steady state.
95			for i := 0; i < hits*2; i++ {
96				m.Load(i % hits)
97			}
98		},
99
100		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
101			for ; pb.Next(); i++ {
102				j := i % (hits + misses)
103				if j < hits {
104					if _, ok := m.LoadOrStore(j, i); !ok {
105						b.Fatalf("unexpected miss for %v", j)
106					}
107				} else {
108					if v, loaded := m.LoadOrStore(i, i); loaded {
109						b.Fatalf("failed to store %v: existing value %v", i, v)
110					}
111				}
112			}
113		},
114	})
115}
116
117func BenchmarkLoadOrStoreUnique(b *testing.B) {
118	benchMap(b, bench{
119		setup: func(b *testing.B, m mapInterface) {
120			if _, ok := m.(*DeepCopyMap); ok {
121				b.Skip("DeepCopyMap has quadratic running time.")
122			}
123		},
124
125		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
126			for ; pb.Next(); i++ {
127				m.LoadOrStore(i, i)
128			}
129		},
130	})
131}
132
133func BenchmarkLoadOrStoreCollision(b *testing.B) {
134	benchMap(b, bench{
135		setup: func(_ *testing.B, m mapInterface) {
136			m.LoadOrStore(0, 0)
137		},
138
139		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
140			for ; pb.Next(); i++ {
141				m.LoadOrStore(0, 0)
142			}
143		},
144	})
145}
146
147func BenchmarkLoadAndDeleteBalanced(b *testing.B) {
148	const hits, misses = 128, 128
149
150	benchMap(b, bench{
151		setup: func(b *testing.B, m mapInterface) {
152			if _, ok := m.(*DeepCopyMap); ok {
153				b.Skip("DeepCopyMap has quadratic running time.")
154			}
155			for i := 0; i < hits; i++ {
156				m.LoadOrStore(i, i)
157			}
158			// Prime the map to get it into a steady state.
159			for i := 0; i < hits*2; i++ {
160				m.Load(i % hits)
161			}
162		},
163
164		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
165			for ; pb.Next(); i++ {
166				j := i % (hits + misses)
167				if j < hits {
168					m.LoadAndDelete(j)
169				} else {
170					m.LoadAndDelete(i)
171				}
172			}
173		},
174	})
175}
176
177func BenchmarkLoadAndDeleteUnique(b *testing.B) {
178	benchMap(b, bench{
179		setup: func(b *testing.B, m mapInterface) {
180			if _, ok := m.(*DeepCopyMap); ok {
181				b.Skip("DeepCopyMap has quadratic running time.")
182			}
183		},
184
185		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
186			for ; pb.Next(); i++ {
187				m.LoadAndDelete(i)
188			}
189		},
190	})
191}
192
193func BenchmarkLoadAndDeleteCollision(b *testing.B) {
194	benchMap(b, bench{
195		setup: func(_ *testing.B, m mapInterface) {
196			m.LoadOrStore(0, 0)
197		},
198
199		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
200			for ; pb.Next(); i++ {
201				if _, loaded := m.LoadAndDelete(0); loaded {
202					m.Store(0, 0)
203				}
204			}
205		},
206	})
207}
208
209func BenchmarkRange(b *testing.B) {
210	const mapSize = 1 << 10
211
212	benchMap(b, bench{
213		setup: func(_ *testing.B, m mapInterface) {
214			for i := 0; i < mapSize; i++ {
215				m.Store(i, i)
216			}
217		},
218
219		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
220			for ; pb.Next(); i++ {
221				m.Range(func(_, _ any) bool { return true })
222			}
223		},
224	})
225}
226
227// BenchmarkAdversarialAlloc tests performance when we store a new value
228// immediately whenever the map is promoted to clean and otherwise load a
229// unique, missing key.
230//
231// This forces the Load calls to always acquire the map's mutex.
232func BenchmarkAdversarialAlloc(b *testing.B) {
233	benchMap(b, bench{
234		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
235			var stores, loadsSinceStore int64
236			for ; pb.Next(); i++ {
237				m.Load(i)
238				if loadsSinceStore++; loadsSinceStore > stores {
239					m.LoadOrStore(i, stores)
240					loadsSinceStore = 0
241					stores++
242				}
243			}
244		},
245	})
246}
247
248// BenchmarkAdversarialDelete tests performance when we periodically delete
249// one key and add a different one in a large map.
250//
251// This forces the Load calls to always acquire the map's mutex and periodically
252// makes a full copy of the map despite changing only one entry.
253func BenchmarkAdversarialDelete(b *testing.B) {
254	const mapSize = 1 << 10
255
256	benchMap(b, bench{
257		setup: func(_ *testing.B, m mapInterface) {
258			for i := 0; i < mapSize; i++ {
259				m.Store(i, i)
260			}
261		},
262
263		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
264			for ; pb.Next(); i++ {
265				m.Load(i)
266
267				if i%mapSize == 0 {
268					m.Range(func(k, _ any) bool {
269						m.Delete(k)
270						return false
271					})
272					m.Store(i, i)
273				}
274			}
275		},
276	})
277}
278
279func BenchmarkDeleteCollision(b *testing.B) {
280	benchMap(b, bench{
281		setup: func(_ *testing.B, m mapInterface) {
282			m.LoadOrStore(0, 0)
283		},
284
285		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
286			for ; pb.Next(); i++ {
287				m.Delete(0)
288			}
289		},
290	})
291}
292
293func BenchmarkSwapCollision(b *testing.B) {
294	benchMap(b, bench{
295		setup: func(_ *testing.B, m mapInterface) {
296			m.LoadOrStore(0, 0)
297		},
298
299		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
300			for ; pb.Next(); i++ {
301				m.Swap(0, 0)
302			}
303		},
304	})
305}
306
307func BenchmarkSwapMostlyHits(b *testing.B) {
308	const hits, misses = 1023, 1
309
310	benchMap(b, bench{
311		setup: func(_ *testing.B, m mapInterface) {
312			for i := 0; i < hits; i++ {
313				m.LoadOrStore(i, i)
314			}
315			// Prime the map to get it into a steady state.
316			for i := 0; i < hits*2; i++ {
317				m.Load(i % hits)
318			}
319		},
320
321		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
322			for ; pb.Next(); i++ {
323				if i%(hits+misses) < hits {
324					v := i % (hits + misses)
325					m.Swap(v, v)
326				} else {
327					m.Swap(i, i)
328					m.Delete(i)
329				}
330			}
331		},
332	})
333}
334
335func BenchmarkSwapMostlyMisses(b *testing.B) {
336	const hits, misses = 1, 1023
337
338	benchMap(b, bench{
339		setup: func(_ *testing.B, m mapInterface) {
340			for i := 0; i < hits; i++ {
341				m.LoadOrStore(i, i)
342			}
343			// Prime the map to get it into a steady state.
344			for i := 0; i < hits*2; i++ {
345				m.Load(i % hits)
346			}
347		},
348
349		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
350			for ; pb.Next(); i++ {
351				if i%(hits+misses) < hits {
352					v := i % (hits + misses)
353					m.Swap(v, v)
354				} else {
355					m.Swap(i, i)
356					m.Delete(i)
357				}
358			}
359		},
360	})
361}
362
363func BenchmarkCompareAndSwapCollision(b *testing.B) {
364	benchMap(b, bench{
365		setup: func(_ *testing.B, m mapInterface) {
366			m.LoadOrStore(0, 0)
367		},
368
369		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
370			for pb.Next() {
371				if m.CompareAndSwap(0, 0, 42) {
372					m.CompareAndSwap(0, 42, 0)
373				}
374			}
375		},
376	})
377}
378
379func BenchmarkCompareAndSwapNoExistingKey(b *testing.B) {
380	benchMap(b, bench{
381		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
382			for ; pb.Next(); i++ {
383				if m.CompareAndSwap(i, 0, 0) {
384					m.Delete(i)
385				}
386			}
387		},
388	})
389}
390
391func BenchmarkCompareAndSwapValueNotEqual(b *testing.B) {
392	benchMap(b, bench{
393		setup: func(_ *testing.B, m mapInterface) {
394			m.Store(0, 0)
395		},
396
397		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
398			for ; pb.Next(); i++ {
399				m.CompareAndSwap(0, 1, 2)
400			}
401		},
402	})
403}
404
405func BenchmarkCompareAndSwapMostlyHits(b *testing.B) {
406	const hits, misses = 1023, 1
407
408	benchMap(b, bench{
409		setup: func(b *testing.B, m mapInterface) {
410			if _, ok := m.(*DeepCopyMap); ok {
411				b.Skip("DeepCopyMap has quadratic running time.")
412			}
413
414			for i := 0; i < hits; i++ {
415				m.LoadOrStore(i, i)
416			}
417			// Prime the map to get it into a steady state.
418			for i := 0; i < hits*2; i++ {
419				m.Load(i % hits)
420			}
421		},
422
423		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
424			for ; pb.Next(); i++ {
425				v := i
426				if i%(hits+misses) < hits {
427					v = i % (hits + misses)
428				}
429				m.CompareAndSwap(v, v, v)
430			}
431		},
432	})
433}
434
435func BenchmarkCompareAndSwapMostlyMisses(b *testing.B) {
436	const hits, misses = 1, 1023
437
438	benchMap(b, bench{
439		setup: func(_ *testing.B, m mapInterface) {
440			for i := 0; i < hits; i++ {
441				m.LoadOrStore(i, i)
442			}
443			// Prime the map to get it into a steady state.
444			for i := 0; i < hits*2; i++ {
445				m.Load(i % hits)
446			}
447		},
448
449		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
450			for ; pb.Next(); i++ {
451				v := i
452				if i%(hits+misses) < hits {
453					v = i % (hits + misses)
454				}
455				m.CompareAndSwap(v, v, v)
456			}
457		},
458	})
459}
460
461func BenchmarkCompareAndDeleteCollision(b *testing.B) {
462	benchMap(b, bench{
463		setup: func(_ *testing.B, m mapInterface) {
464			m.LoadOrStore(0, 0)
465		},
466
467		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
468			for ; pb.Next(); i++ {
469				if m.CompareAndDelete(0, 0) {
470					m.Store(0, 0)
471				}
472			}
473		},
474	})
475}
476
477func BenchmarkCompareAndDeleteMostlyHits(b *testing.B) {
478	const hits, misses = 1023, 1
479
480	benchMap(b, bench{
481		setup: func(b *testing.B, m mapInterface) {
482			if _, ok := m.(*DeepCopyMap); ok {
483				b.Skip("DeepCopyMap has quadratic running time.")
484			}
485
486			for i := 0; i < hits; i++ {
487				m.LoadOrStore(i, i)
488			}
489			// Prime the map to get it into a steady state.
490			for i := 0; i < hits*2; i++ {
491				m.Load(i % hits)
492			}
493		},
494
495		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
496			for ; pb.Next(); i++ {
497				v := i
498				if i%(hits+misses) < hits {
499					v = i % (hits + misses)
500				}
501				if m.CompareAndDelete(v, v) {
502					m.Store(v, v)
503				}
504			}
505		},
506	})
507}
508
509func BenchmarkCompareAndDeleteMostlyMisses(b *testing.B) {
510	const hits, misses = 1, 1023
511
512	benchMap(b, bench{
513		setup: func(_ *testing.B, m mapInterface) {
514			for i := 0; i < hits; i++ {
515				m.LoadOrStore(i, i)
516			}
517			// Prime the map to get it into a steady state.
518			for i := 0; i < hits*2; i++ {
519				m.Load(i % hits)
520			}
521		},
522
523		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
524			for ; pb.Next(); i++ {
525				v := i
526				if i%(hits+misses) < hits {
527					v = i % (hits + misses)
528				}
529				if m.CompareAndDelete(v, v) {
530					m.Store(v, v)
531				}
532			}
533		},
534	})
535}
536
537func BenchmarkClear(b *testing.B) {
538	benchMap(b, bench{
539		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
540			for ; pb.Next(); i++ {
541				k, v := i%256, i%256
542				m.Clear()
543				m.Store(k, v)
544			}
545		},
546	})
547}
548