map_bench_test.go

Documentation: golang.org/x/sync/syncmap

     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 syncmap_test
     6  
     7  import (
     8  	"fmt"
     9  	"reflect"
    10  	"sync/atomic"
    11  	"testing"
    12  
    13  	"golang.org/x/sync/syncmap"
    14  )
    15  
    16  type bench struct {
    17  	setup func(*testing.B, mapInterface)
    18  	perG  func(b *testing.B, pb *testing.PB, i int, m mapInterface)
    19  }
    20  
    21  func benchMap(b *testing.B, bench bench) {
    22  	for _, m := range [...]mapInterface{&DeepCopyMap{}, &RWMutexMap{}, &syncmap.Map{}} {
    23  		b.Run(fmt.Sprintf("%T", m), func(b *testing.B) {
    24  			m = reflect.New(reflect.TypeOf(m).Elem()).Interface().(mapInterface)
    25  			if bench.setup != nil {
    26  				bench.setup(b, m)
    27  			}
    28  
    29  			b.ResetTimer()
    30  
    31  			var i int64
    32  			b.RunParallel(func(pb *testing.PB) {
    33  				id := int(atomic.AddInt64(&i, 1) - 1)
    34  				bench.perG(b, pb, id*b.N, m)
    35  			})
    36  		})
    37  	}
    38  }
    39  
    40  func BenchmarkLoadMostlyHits(b *testing.B) {
    41  	const hits, misses = 1023, 1
    42  
    43  	benchMap(b, bench{
    44  		setup: func(_ *testing.B, m mapInterface) {
    45  			for i := 0; i < hits; i++ {
    46  				m.LoadOrStore(i, i)
    47  			}
    48  			// Prime the map to get it into a steady state.
    49  			for i := 0; i < hits*2; i++ {
    50  				m.Load(i % hits)
    51  			}
    52  		},
    53  
    54  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
    55  			for ; pb.Next(); i++ {
    56  				m.Load(i % (hits + misses))
    57  			}
    58  		},
    59  	})
    60  }
    61  
    62  func BenchmarkLoadMostlyMisses(b *testing.B) {
    63  	const hits, misses = 1, 1023
    64  
    65  	benchMap(b, bench{
    66  		setup: func(_ *testing.B, m mapInterface) {
    67  			for i := 0; i < hits; i++ {
    68  				m.LoadOrStore(i, i)
    69  			}
    70  			// Prime the map to get it into a steady state.
    71  			for i := 0; i < hits*2; i++ {
    72  				m.Load(i % hits)
    73  			}
    74  		},
    75  
    76  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
    77  			for ; pb.Next(); i++ {
    78  				m.Load(i % (hits + misses))
    79  			}
    80  		},
    81  	})
    82  }
    83  
    84  func BenchmarkLoadOrStoreBalanced(b *testing.B) {
    85  	const hits, misses = 128, 128
    86  
    87  	benchMap(b, bench{
    88  		setup: func(b *testing.B, m mapInterface) {
    89  			if _, ok := m.(*DeepCopyMap); ok {
    90  				b.Skip("DeepCopyMap has quadratic running time.")
    91  			}
    92  			for i := 0; i < hits; i++ {
    93  				m.LoadOrStore(i, i)
    94  			}
    95  			// Prime the map to get it into a steady state.
    96  			for i := 0; i < hits*2; i++ {
    97  				m.Load(i % hits)
    98  			}
    99  		},
   100  
   101  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   102  			for ; pb.Next(); i++ {
   103  				j := i % (hits + misses)
   104  				if j < hits {
   105  					if _, ok := m.LoadOrStore(j, i); !ok {
   106  						b.Fatalf("unexpected miss for %v", j)
   107  					}
   108  				} else {
   109  					if v, loaded := m.LoadOrStore(i, i); loaded {
   110  						b.Fatalf("failed to store %v: existing value %v", i, v)
   111  					}
   112  				}
   113  			}
   114  		},
   115  	})
   116  }
   117  
   118  func BenchmarkLoadOrStoreUnique(b *testing.B) {
   119  	benchMap(b, bench{
   120  		setup: func(b *testing.B, m mapInterface) {
   121  			if _, ok := m.(*DeepCopyMap); ok {
   122  				b.Skip("DeepCopyMap has quadratic running time.")
   123  			}
   124  		},
   125  
   126  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   127  			for ; pb.Next(); i++ {
   128  				m.LoadOrStore(i, i)
   129  			}
   130  		},
   131  	})
   132  }
   133  
   134  func BenchmarkLoadOrStoreCollision(b *testing.B) {
   135  	benchMap(b, bench{
   136  		setup: func(_ *testing.B, m mapInterface) {
   137  			m.LoadOrStore(0, 0)
   138  		},
   139  
   140  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   141  			for ; pb.Next(); i++ {
   142  				m.LoadOrStore(0, 0)
   143  			}
   144  		},
   145  	})
   146  }
   147  
   148  func BenchmarkRange(b *testing.B) {
   149  	const mapSize = 1 << 10
   150  
   151  	benchMap(b, bench{
   152  		setup: func(_ *testing.B, m mapInterface) {
   153  			for i := 0; i < mapSize; i++ {
   154  				m.Store(i, i)
   155  			}
   156  		},
   157  
   158  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   159  			for ; pb.Next(); i++ {
   160  				m.Range(func(_, _ interface{}) bool { return true })
   161  			}
   162  		},
   163  	})
   164  }
   165  
   166  // BenchmarkAdversarialAlloc tests performance when we store a new value
   167  // immediately whenever the map is promoted to clean and otherwise load a
   168  // unique, missing key.
   169  //
   170  // This forces the Load calls to always acquire the map's mutex.
   171  func BenchmarkAdversarialAlloc(b *testing.B) {
   172  	benchMap(b, bench{
   173  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   174  			var stores, loadsSinceStore int64
   175  			for ; pb.Next(); i++ {
   176  				m.Load(i)
   177  				if loadsSinceStore++; loadsSinceStore > stores {
   178  					m.LoadOrStore(i, stores)
   179  					loadsSinceStore = 0
   180  					stores++
   181  				}
   182  			}
   183  		},
   184  	})
   185  }
   186  
   187  // BenchmarkAdversarialDelete tests performance when we periodically delete
   188  // one key and add a different one in a large map.
   189  //
   190  // This forces the Load calls to always acquire the map's mutex and periodically
   191  // makes a full copy of the map despite changing only one entry.
   192  func BenchmarkAdversarialDelete(b *testing.B) {
   193  	const mapSize = 1 << 10
   194  
   195  	benchMap(b, bench{
   196  		setup: func(_ *testing.B, m mapInterface) {
   197  			for i := 0; i < mapSize; i++ {
   198  				m.Store(i, i)
   199  			}
   200  		},
   201  
   202  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   203  			for ; pb.Next(); i++ {
   204  				m.Load(i)
   205  
   206  				if i%mapSize == 0 {
   207  					m.Range(func(k, _ interface{}) bool {
   208  						m.Delete(k)
   209  						return false
   210  					})
   211  					m.Store(i, i)
   212  				}
   213  			}
   214  		},
   215  	})
   216  }
   217
View as plain text