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 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 // 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 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 // 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 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 // 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 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 BenchmarkRange(b *testing.B) { 148 const mapSize = 1 << 10 149 150 benchMap(b, bench{ 151 setup: func(_ *testing.B, m mapInterface) { 152 for i := 0; i < mapSize; i++ { 153 m.Store(i, i) 154 } 155 }, 156 157 perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) { 158 for ; pb.Next(); i++ { 159 m.Range(func(_, _ interface{}) bool { return true }) 160 } 161 }, 162 }) 163 } 164 165 // BenchmarkAdversarialAlloc tests performance when we store a new value 166 // immediately whenever the map is promoted to clean and otherwise load a 167 // unique, missing key. 168 // 169 // This forces the Load calls to always acquire the map's mutex. 170 func BenchmarkAdversarialAlloc(b *testing.B) { 171 benchMap(b, bench{ 172 perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) { 173 var stores, loadsSinceStore int64 174 for ; pb.Next(); i++ { 175 m.Load(i) 176 if loadsSinceStore++; loadsSinceStore > stores { 177 m.LoadOrStore(i, stores) 178 loadsSinceStore = 0 179 stores++ 180 } 181 } 182 }, 183 }) 184 } 185 186 // BenchmarkAdversarialDelete tests performance when we periodically delete 187 // one key and add a different one in a large map. 188 // 189 // This forces the Load calls to always acquire the map's mutex and periodically 190 // makes a full copy of the map despite changing only one entry. 191 func BenchmarkAdversarialDelete(b *testing.B) { 192 const mapSize = 1 << 10 193 194 benchMap(b, bench{ 195 setup: func(_ *testing.B, m mapInterface) { 196 for i := 0; i < mapSize; i++ { 197 m.Store(i, i) 198 } 199 }, 200 201 perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) { 202 for ; pb.Next(); i++ { 203 m.Load(i) 204 205 if i%mapSize == 0 { 206 m.Range(func(k, _ interface{}) bool { 207 m.Delete(k) 208 return false 209 }) 210 m.Store(i, i) 211 } 212 } 213 }, 214 }) 215 } 216
