summaryrefslogtreecommitdiffstats
path: root/src/sync/map_bench_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/sync/map_bench_test.go')
-rw-r--r--src/sync/map_bench_test.go535
1 files changed, 535 insertions, 0 deletions
diff --git a/src/sync/map_bench_test.go b/src/sync/map_bench_test.go
new file mode 100644
index 0000000..eebec3b
--- /dev/null
+++ b/src/sync/map_bench_test.go
@@ -0,0 +1,535 @@
+// Copyright 2016 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package sync_test
+
+import (
+ "fmt"
+ "reflect"
+ "sync"
+ "sync/atomic"
+ "testing"
+)
+
+type bench struct {
+ setup func(*testing.B, mapInterface)
+ perG func(b *testing.B, pb *testing.PB, i int, m mapInterface)
+}
+
+func benchMap(b *testing.B, bench bench) {
+ for _, m := range [...]mapInterface{&DeepCopyMap{}, &RWMutexMap{}, &sync.Map{}} {
+ b.Run(fmt.Sprintf("%T", m), func(b *testing.B) {
+ m = reflect.New(reflect.TypeOf(m).Elem()).Interface().(mapInterface)
+ if bench.setup != nil {
+ bench.setup(b, m)
+ }
+
+ b.ResetTimer()
+
+ var i int64
+ b.RunParallel(func(pb *testing.PB) {
+ id := int(atomic.AddInt64(&i, 1) - 1)
+ bench.perG(b, pb, id*b.N, m)
+ })
+ })
+ }
+}
+
+func BenchmarkLoadMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Load(i % (hits + misses))
+ }
+ },
+ })
+}
+
+func BenchmarkLoadMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Load(i % (hits + misses))
+ }
+ },
+ })
+}
+
+func BenchmarkLoadOrStoreBalanced(b *testing.B) {
+ const hits, misses = 128, 128
+
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ j := i % (hits + misses)
+ if j < hits {
+ if _, ok := m.LoadOrStore(j, i); !ok {
+ b.Fatalf("unexpected miss for %v", j)
+ }
+ } else {
+ if v, loaded := m.LoadOrStore(i, i); loaded {
+ b.Fatalf("failed to store %v: existing value %v", i, v)
+ }
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkLoadOrStoreUnique(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.LoadOrStore(i, i)
+ }
+ },
+ })
+}
+
+func BenchmarkLoadOrStoreCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.LoadOrStore(0, 0)
+ }
+ },
+ })
+}
+
+func BenchmarkLoadAndDeleteBalanced(b *testing.B) {
+ const hits, misses = 128, 128
+
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ j := i % (hits + misses)
+ if j < hits {
+ m.LoadAndDelete(j)
+ } else {
+ m.LoadAndDelete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkLoadAndDeleteUnique(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.LoadAndDelete(i)
+ }
+ },
+ })
+}
+
+func BenchmarkLoadAndDeleteCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ if _, loaded := m.LoadAndDelete(0); loaded {
+ m.Store(0, 0)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkRange(b *testing.B) {
+ const mapSize = 1 << 10
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < mapSize; i++ {
+ m.Store(i, i)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Range(func(_, _ any) bool { return true })
+ }
+ },
+ })
+}
+
+// BenchmarkAdversarialAlloc tests performance when we store a new value
+// immediately whenever the map is promoted to clean and otherwise load a
+// unique, missing key.
+//
+// This forces the Load calls to always acquire the map's mutex.
+func BenchmarkAdversarialAlloc(b *testing.B) {
+ benchMap(b, bench{
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ var stores, loadsSinceStore int64
+ for ; pb.Next(); i++ {
+ m.Load(i)
+ if loadsSinceStore++; loadsSinceStore > stores {
+ m.LoadOrStore(i, stores)
+ loadsSinceStore = 0
+ stores++
+ }
+ }
+ },
+ })
+}
+
+// BenchmarkAdversarialDelete tests performance when we periodically delete
+// one key and add a different one in a large map.
+//
+// This forces the Load calls to always acquire the map's mutex and periodically
+// makes a full copy of the map despite changing only one entry.
+func BenchmarkAdversarialDelete(b *testing.B) {
+ const mapSize = 1 << 10
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < mapSize; i++ {
+ m.Store(i, i)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Load(i)
+
+ if i%mapSize == 0 {
+ m.Range(func(k, _ any) bool {
+ m.Delete(k)
+ return false
+ })
+ m.Store(i, i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkDeleteCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Delete(0)
+ }
+ },
+ })
+}
+
+func BenchmarkSwapCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.Swap(0, 0)
+ }
+ },
+ })
+}
+
+func BenchmarkSwapMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ if i%(hits+misses) < hits {
+ v := i % (hits + misses)
+ m.Swap(v, v)
+ } else {
+ m.Swap(i, i)
+ m.Delete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkSwapMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ if i%(hits+misses) < hits {
+ v := i % (hits + misses)
+ m.Swap(v, v)
+ } else {
+ m.Swap(i, i)
+ m.Delete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for pb.Next() {
+ if m.CompareAndSwap(0, 0, 42) {
+ m.CompareAndSwap(0, 42, 0)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapNoExistingKey(b *testing.B) {
+ benchMap(b, bench{
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ if m.CompareAndSwap(i, 0, 0) {
+ m.Delete(i)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapValueNotEqual(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.Store(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ m.CompareAndSwap(0, 1, 2)
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ m.CompareAndSwap(v, v, v)
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndSwapMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ m.CompareAndSwap(v, v, v)
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndDeleteCollision(b *testing.B) {
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ m.LoadOrStore(0, 0)
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ if m.CompareAndDelete(0, 0) {
+ m.Store(0, 0)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndDeleteMostlyHits(b *testing.B) {
+ const hits, misses = 1023, 1
+
+ benchMap(b, bench{
+ setup: func(b *testing.B, m mapInterface) {
+ if _, ok := m.(*DeepCopyMap); ok {
+ b.Skip("DeepCopyMap has quadratic running time.")
+ }
+
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ if m.CompareAndDelete(v, v) {
+ m.Store(v, v)
+ }
+ }
+ },
+ })
+}
+
+func BenchmarkCompareAndDeleteMostlyMisses(b *testing.B) {
+ const hits, misses = 1, 1023
+
+ benchMap(b, bench{
+ setup: func(_ *testing.B, m mapInterface) {
+ for i := 0; i < hits; i++ {
+ m.LoadOrStore(i, i)
+ }
+ // Prime the map to get it into a steady state.
+ for i := 0; i < hits*2; i++ {
+ m.Load(i % hits)
+ }
+ },
+
+ perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
+ for ; pb.Next(); i++ {
+ v := i
+ if i%(hits+misses) < hits {
+ v = i % (hits + misses)
+ }
+ if m.CompareAndDelete(v, v) {
+ m.Store(v, v)
+ }
+ }
+ },
+ })
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-27 23:28:10 +0000