...
Run Format

Source file src/sync/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 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  

View as plain text