Source file src/sync/map_bench_test.go

     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  				if _, loaded := m.LoadAndDelete(0); loaded {
   202  					m.Store(0, 0)
   203  				}
   204  			}
   205  		},
   206  	})
   207  }
   208  
   209  func BenchmarkRange(b *testing.B) {
   210  	const mapSize = 1 << 10
   211  
   212  	benchMap(b, bench{
   213  		setup: func(_ *testing.B, m mapInterface) {
   214  			for i := 0; i < mapSize; i++ {
   215  				m.Store(i, i)
   216  			}
   217  		},
   218  
   219  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   220  			for ; pb.Next(); i++ {
   221  				m.Range(func(_, _ any) bool { return true })
   222  			}
   223  		},
   224  	})
   225  }
   226  
   227  // BenchmarkAdversarialAlloc tests performance when we store a new value
   228  // immediately whenever the map is promoted to clean and otherwise load a
   229  // unique, missing key.
   230  //
   231  // This forces the Load calls to always acquire the map's mutex.
   232  func BenchmarkAdversarialAlloc(b *testing.B) {
   233  	benchMap(b, bench{
   234  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   235  			var stores, loadsSinceStore int64
   236  			for ; pb.Next(); i++ {
   237  				m.Load(i)
   238  				if loadsSinceStore++; loadsSinceStore > stores {
   239  					m.LoadOrStore(i, stores)
   240  					loadsSinceStore = 0
   241  					stores++
   242  				}
   243  			}
   244  		},
   245  	})
   246  }
   247  
   248  // BenchmarkAdversarialDelete tests performance when we periodically delete
   249  // one key and add a different one in a large map.
   250  //
   251  // This forces the Load calls to always acquire the map's mutex and periodically
   252  // makes a full copy of the map despite changing only one entry.
   253  func BenchmarkAdversarialDelete(b *testing.B) {
   254  	const mapSize = 1 << 10
   255  
   256  	benchMap(b, bench{
   257  		setup: func(_ *testing.B, m mapInterface) {
   258  			for i := 0; i < mapSize; i++ {
   259  				m.Store(i, i)
   260  			}
   261  		},
   262  
   263  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   264  			for ; pb.Next(); i++ {
   265  				m.Load(i)
   266  
   267  				if i%mapSize == 0 {
   268  					m.Range(func(k, _ any) bool {
   269  						m.Delete(k)
   270  						return false
   271  					})
   272  					m.Store(i, i)
   273  				}
   274  			}
   275  		},
   276  	})
   277  }
   278  
   279  func BenchmarkDeleteCollision(b *testing.B) {
   280  	benchMap(b, bench{
   281  		setup: func(_ *testing.B, m mapInterface) {
   282  			m.LoadOrStore(0, 0)
   283  		},
   284  
   285  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   286  			for ; pb.Next(); i++ {
   287  				m.Delete(0)
   288  			}
   289  		},
   290  	})
   291  }
   292  
   293  func BenchmarkSwapCollision(b *testing.B) {
   294  	benchMap(b, bench{
   295  		setup: func(_ *testing.B, m mapInterface) {
   296  			m.LoadOrStore(0, 0)
   297  		},
   298  
   299  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   300  			for ; pb.Next(); i++ {
   301  				m.Swap(0, 0)
   302  			}
   303  		},
   304  	})
   305  }
   306  
   307  func BenchmarkSwapMostlyHits(b *testing.B) {
   308  	const hits, misses = 1023, 1
   309  
   310  	benchMap(b, bench{
   311  		setup: func(_ *testing.B, m mapInterface) {
   312  			for i := 0; i < hits; i++ {
   313  				m.LoadOrStore(i, i)
   314  			}
   315  			// Prime the map to get it into a steady state.
   316  			for i := 0; i < hits*2; i++ {
   317  				m.Load(i % hits)
   318  			}
   319  		},
   320  
   321  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   322  			for ; pb.Next(); i++ {
   323  				if i%(hits+misses) < hits {
   324  					v := i % (hits + misses)
   325  					m.Swap(v, v)
   326  				} else {
   327  					m.Swap(i, i)
   328  					m.Delete(i)
   329  				}
   330  			}
   331  		},
   332  	})
   333  }
   334  
   335  func BenchmarkSwapMostlyMisses(b *testing.B) {
   336  	const hits, misses = 1, 1023
   337  
   338  	benchMap(b, bench{
   339  		setup: func(_ *testing.B, m mapInterface) {
   340  			for i := 0; i < hits; i++ {
   341  				m.LoadOrStore(i, i)
   342  			}
   343  			// Prime the map to get it into a steady state.
   344  			for i := 0; i < hits*2; i++ {
   345  				m.Load(i % hits)
   346  			}
   347  		},
   348  
   349  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   350  			for ; pb.Next(); i++ {
   351  				if i%(hits+misses) < hits {
   352  					v := i % (hits + misses)
   353  					m.Swap(v, v)
   354  				} else {
   355  					m.Swap(i, i)
   356  					m.Delete(i)
   357  				}
   358  			}
   359  		},
   360  	})
   361  }
   362  
   363  func BenchmarkCompareAndSwapCollision(b *testing.B) {
   364  	benchMap(b, bench{
   365  		setup: func(_ *testing.B, m mapInterface) {
   366  			m.LoadOrStore(0, 0)
   367  		},
   368  
   369  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   370  			for pb.Next() {
   371  				if m.CompareAndSwap(0, 0, 42) {
   372  					m.CompareAndSwap(0, 42, 0)
   373  				}
   374  			}
   375  		},
   376  	})
   377  }
   378  
   379  func BenchmarkCompareAndSwapNoExistingKey(b *testing.B) {
   380  	benchMap(b, bench{
   381  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   382  			for ; pb.Next(); i++ {
   383  				if m.CompareAndSwap(i, 0, 0) {
   384  					m.Delete(i)
   385  				}
   386  			}
   387  		},
   388  	})
   389  }
   390  
   391  func BenchmarkCompareAndSwapValueNotEqual(b *testing.B) {
   392  	benchMap(b, bench{
   393  		setup: func(_ *testing.B, m mapInterface) {
   394  			m.Store(0, 0)
   395  		},
   396  
   397  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   398  			for ; pb.Next(); i++ {
   399  				m.CompareAndSwap(0, 1, 2)
   400  			}
   401  		},
   402  	})
   403  }
   404  
   405  func BenchmarkCompareAndSwapMostlyHits(b *testing.B) {
   406  	const hits, misses = 1023, 1
   407  
   408  	benchMap(b, bench{
   409  		setup: func(b *testing.B, m mapInterface) {
   410  			if _, ok := m.(*DeepCopyMap); ok {
   411  				b.Skip("DeepCopyMap has quadratic running time.")
   412  			}
   413  
   414  			for i := 0; i < hits; i++ {
   415  				m.LoadOrStore(i, i)
   416  			}
   417  			// Prime the map to get it into a steady state.
   418  			for i := 0; i < hits*2; i++ {
   419  				m.Load(i % hits)
   420  			}
   421  		},
   422  
   423  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   424  			for ; pb.Next(); i++ {
   425  				v := i
   426  				if i%(hits+misses) < hits {
   427  					v = i % (hits + misses)
   428  				}
   429  				m.CompareAndSwap(v, v, v)
   430  			}
   431  		},
   432  	})
   433  }
   434  
   435  func BenchmarkCompareAndSwapMostlyMisses(b *testing.B) {
   436  	const hits, misses = 1, 1023
   437  
   438  	benchMap(b, bench{
   439  		setup: func(_ *testing.B, m mapInterface) {
   440  			for i := 0; i < hits; i++ {
   441  				m.LoadOrStore(i, i)
   442  			}
   443  			// Prime the map to get it into a steady state.
   444  			for i := 0; i < hits*2; i++ {
   445  				m.Load(i % hits)
   446  			}
   447  		},
   448  
   449  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   450  			for ; pb.Next(); i++ {
   451  				v := i
   452  				if i%(hits+misses) < hits {
   453  					v = i % (hits + misses)
   454  				}
   455  				m.CompareAndSwap(v, v, v)
   456  			}
   457  		},
   458  	})
   459  }
   460  
   461  func BenchmarkCompareAndDeleteCollision(b *testing.B) {
   462  	benchMap(b, bench{
   463  		setup: func(_ *testing.B, m mapInterface) {
   464  			m.LoadOrStore(0, 0)
   465  		},
   466  
   467  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   468  			for ; pb.Next(); i++ {
   469  				if m.CompareAndDelete(0, 0) {
   470  					m.Store(0, 0)
   471  				}
   472  			}
   473  		},
   474  	})
   475  }
   476  
   477  func BenchmarkCompareAndDeleteMostlyHits(b *testing.B) {
   478  	const hits, misses = 1023, 1
   479  
   480  	benchMap(b, bench{
   481  		setup: func(b *testing.B, m mapInterface) {
   482  			if _, ok := m.(*DeepCopyMap); ok {
   483  				b.Skip("DeepCopyMap has quadratic running time.")
   484  			}
   485  
   486  			for i := 0; i < hits; i++ {
   487  				m.LoadOrStore(i, i)
   488  			}
   489  			// Prime the map to get it into a steady state.
   490  			for i := 0; i < hits*2; i++ {
   491  				m.Load(i % hits)
   492  			}
   493  		},
   494  
   495  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   496  			for ; pb.Next(); i++ {
   497  				v := i
   498  				if i%(hits+misses) < hits {
   499  					v = i % (hits + misses)
   500  				}
   501  				if m.CompareAndDelete(v, v) {
   502  					m.Store(v, v)
   503  				}
   504  			}
   505  		},
   506  	})
   507  }
   508  
   509  func BenchmarkCompareAndDeleteMostlyMisses(b *testing.B) {
   510  	const hits, misses = 1, 1023
   511  
   512  	benchMap(b, bench{
   513  		setup: func(_ *testing.B, m mapInterface) {
   514  			for i := 0; i < hits; i++ {
   515  				m.LoadOrStore(i, i)
   516  			}
   517  			// Prime the map to get it into a steady state.
   518  			for i := 0; i < hits*2; i++ {
   519  				m.Load(i % hits)
   520  			}
   521  		},
   522  
   523  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   524  			for ; pb.Next(); i++ {
   525  				v := i
   526  				if i%(hits+misses) < hits {
   527  					v = i % (hits + misses)
   528  				}
   529  				if m.CompareAndDelete(v, v) {
   530  					m.Store(v, v)
   531  				}
   532  			}
   533  		},
   534  	})
   535  }
   536  

View as plain text