map_bench_test.go

Documentation: sync

		 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 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  
	 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  				m.LoadAndDelete(0)
	 202  			}
	 203  		},
	 204  	})
	 205  }
	 206  
	 207  func BenchmarkRange(b *testing.B) {
	 208  	const mapSize = 1 << 10
	 209  
	 210  	benchMap(b, bench{
	 211  		setup: func(_ *testing.B, m mapInterface) {
	 212  			for i := 0; i < mapSize; i++ {
	 213  				m.Store(i, i)
	 214  			}
	 215  		},
	 216  
	 217  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
	 218  			for ; pb.Next(); i++ {
	 219  				m.Range(func(_, _ interface{}) bool { return true })
	 220  			}
	 221  		},
	 222  	})
	 223  }
	 224  
	 225  // BenchmarkAdversarialAlloc tests performance when we store a new value
	 226  // immediately whenever the map is promoted to clean and otherwise load a
	 227  // unique, missing key.
	 228  //
	 229  // This forces the Load calls to always acquire the map's mutex.
	 230  func BenchmarkAdversarialAlloc(b *testing.B) {
	 231  	benchMap(b, bench{
	 232  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
	 233  			var stores, loadsSinceStore int64
	 234  			for ; pb.Next(); i++ {
	 235  				m.Load(i)
	 236  				if loadsSinceStore++; loadsSinceStore > stores {
	 237  					m.LoadOrStore(i, stores)
	 238  					loadsSinceStore = 0
	 239  					stores++
	 240  				}
	 241  			}
	 242  		},
	 243  	})
	 244  }
	 245  
	 246  // BenchmarkAdversarialDelete tests performance when we periodically delete
	 247  // one key and add a different one in a large map.
	 248  //
	 249  // This forces the Load calls to always acquire the map's mutex and periodically
	 250  // makes a full copy of the map despite changing only one entry.
	 251  func BenchmarkAdversarialDelete(b *testing.B) {
	 252  	const mapSize = 1 << 10
	 253  
	 254  	benchMap(b, bench{
	 255  		setup: func(_ *testing.B, m mapInterface) {
	 256  			for i := 0; i < mapSize; i++ {
	 257  				m.Store(i, i)
	 258  			}
	 259  		},
	 260  
	 261  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
	 262  			for ; pb.Next(); i++ {
	 263  				m.Load(i)
	 264  
	 265  				if i%mapSize == 0 {
	 266  					m.Range(func(k, _ interface{}) bool {
	 267  						m.Delete(k)
	 268  						return false
	 269  					})
	 270  					m.Store(i, i)
	 271  				}
	 272  			}
	 273  		},
	 274  	})
	 275  }
	 276  
	 277  func BenchmarkDeleteCollision(b *testing.B) {
	 278  	benchMap(b, bench{
	 279  		setup: func(_ *testing.B, m mapInterface) {
	 280  			m.LoadOrStore(0, 0)
	 281  		},
	 282  
	 283  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
	 284  			for ; pb.Next(); i++ {
	 285  				m.Delete(0)
	 286  			}
	 287  		},
	 288  	})
	 289  }
	 290
View as plain text