Source file
src/sync/map_bench_test.go
1
2
3
4
5 package sync_test
6
7 import (
8 "fmt"
9 "reflect"
10 "sync"
11 "sync/atomic"
12 "testing"
13 )
14
15 type bench struct {
16 setup func(*testing.B, mapInterface)
17 perG func(b *testing.B, pb *testing.PB, i int, m mapInterface)
18 }
19
20 func 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
39 func 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
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
61 func 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
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
83 func 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
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
117 func 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
133 func 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
147 func 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
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
177 func 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
193 func 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
209 func 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
228
229
230
231
232 func 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
249
250
251
252
253 func 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
279 func 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
293 func 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
307 func 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
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
335 func 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
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
363 func 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
379 func 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
391 func 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
405 func 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
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
435 func 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
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
461 func 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
477 func 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
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
509 func 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
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
537 func 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
View as plain text