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  	isync "internal/sync"
    10  	"reflect"
    11  	"sync"
    12  	"sync/atomic"
    13  	"testing"
    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{}, &isync.HashTrieMap[any, any]{}, &sync.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.ReportAllocs()
    30  			b.ResetTimer()
    31  
    32  			var i int64
    33  			b.RunParallel(func(pb *testing.PB) {
    34  				id := int(atomic.AddInt64(&i, 1) - 1)
    35  				bench.perG(b, pb, id*b.N, m)
    36  			})
    37  		})
    38  	}
    39  }
    40  
    41  func BenchmarkMapLoadMostlyHits(b *testing.B) {
    42  	const hits, misses = 1023, 1
    43  
    44  	benchMap(b, bench{
    45  		setup: func(_ *testing.B, m mapInterface) {
    46  			for i := 0; i < hits; i++ {
    47  				m.LoadOrStore(i, i)
    48  			}
    49  			// Prime the map to get it into a steady state.
    50  			for i := 0; i < hits*2; i++ {
    51  				m.Load(i % hits)
    52  			}
    53  		},
    54  
    55  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
    56  			for ; pb.Next(); i++ {
    57  				m.Load(i % (hits + misses))
    58  			}
    59  		},
    60  	})
    61  }
    62  
    63  func BenchmarkMapLoadMostlyMisses(b *testing.B) {
    64  	const hits, misses = 1, 1023
    65  
    66  	benchMap(b, bench{
    67  		setup: func(_ *testing.B, m mapInterface) {
    68  			for i := 0; i < hits; i++ {
    69  				m.LoadOrStore(i, i)
    70  			}
    71  			// Prime the map to get it into a steady state.
    72  			for i := 0; i < hits*2; i++ {
    73  				m.Load(i % hits)
    74  			}
    75  		},
    76  
    77  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
    78  			for ; pb.Next(); i++ {
    79  				m.Load(i % (hits + misses))
    80  			}
    81  		},
    82  	})
    83  }
    84  
    85  func BenchmarkMapLoadOrStoreBalanced(b *testing.B) {
    86  	const hits, misses = 128, 128
    87  
    88  	benchMap(b, bench{
    89  		setup: func(b *testing.B, m mapInterface) {
    90  			if _, ok := m.(*DeepCopyMap); ok {
    91  				b.Skip("DeepCopyMap has quadratic running time.")
    92  			}
    93  			for i := 0; i < hits; i++ {
    94  				m.LoadOrStore(i, i)
    95  			}
    96  			// Prime the map to get it into a steady state.
    97  			for i := 0; i < hits*2; i++ {
    98  				m.Load(i % hits)
    99  			}
   100  		},
   101  
   102  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   103  			for ; pb.Next(); i++ {
   104  				j := i % (hits + misses)
   105  				if j < hits {
   106  					if _, ok := m.LoadOrStore(j, i); !ok {
   107  						b.Fatalf("unexpected miss for %v", j)
   108  					}
   109  				} else {
   110  					if v, loaded := m.LoadOrStore(i, i); loaded {
   111  						b.Fatalf("failed to store %v: existing value %v", i, v)
   112  					}
   113  				}
   114  			}
   115  		},
   116  	})
   117  }
   118  
   119  func BenchmarkMapLoadOrStoreUnique(b *testing.B) {
   120  	benchMap(b, bench{
   121  		setup: func(b *testing.B, m mapInterface) {
   122  			if _, ok := m.(*DeepCopyMap); ok {
   123  				b.Skip("DeepCopyMap has quadratic running time.")
   124  			}
   125  		},
   126  
   127  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   128  			for ; pb.Next(); i++ {
   129  				m.LoadOrStore(i, i)
   130  			}
   131  		},
   132  	})
   133  }
   134  
   135  func BenchmarkMapLoadOrStoreCollision(b *testing.B) {
   136  	benchMap(b, bench{
   137  		setup: func(_ *testing.B, m mapInterface) {
   138  			m.LoadOrStore(0, 0)
   139  		},
   140  
   141  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   142  			for ; pb.Next(); i++ {
   143  				m.LoadOrStore(0, 0)
   144  			}
   145  		},
   146  	})
   147  }
   148  
   149  func BenchmarkMapLoadAndDeleteBalanced(b *testing.B) {
   150  	const hits, misses = 128, 128
   151  
   152  	benchMap(b, bench{
   153  		setup: func(b *testing.B, m mapInterface) {
   154  			if _, ok := m.(*DeepCopyMap); ok {
   155  				b.Skip("DeepCopyMap has quadratic running time.")
   156  			}
   157  			for i := 0; i < hits; i++ {
   158  				m.LoadOrStore(i, i)
   159  			}
   160  			// Prime the map to get it into a steady state.
   161  			for i := 0; i < hits*2; i++ {
   162  				m.Load(i % hits)
   163  			}
   164  		},
   165  
   166  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   167  			for ; pb.Next(); i++ {
   168  				j := i % (hits + misses)
   169  				if j < hits {
   170  					m.LoadAndDelete(j)
   171  				} else {
   172  					m.LoadAndDelete(i)
   173  				}
   174  			}
   175  		},
   176  	})
   177  }
   178  
   179  func BenchmarkMapLoadAndDeleteUnique(b *testing.B) {
   180  	benchMap(b, bench{
   181  		setup: func(b *testing.B, m mapInterface) {
   182  			if _, ok := m.(*DeepCopyMap); ok {
   183  				b.Skip("DeepCopyMap has quadratic running time.")
   184  			}
   185  		},
   186  
   187  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   188  			for ; pb.Next(); i++ {
   189  				m.LoadAndDelete(i)
   190  			}
   191  		},
   192  	})
   193  }
   194  
   195  func BenchmarkMapLoadAndDeleteCollision(b *testing.B) {
   196  	benchMap(b, bench{
   197  		setup: func(_ *testing.B, m mapInterface) {
   198  			m.LoadOrStore(0, 0)
   199  		},
   200  
   201  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   202  			for ; pb.Next(); i++ {
   203  				if _, loaded := m.LoadAndDelete(0); loaded {
   204  					m.Store(0, 0)
   205  				}
   206  			}
   207  		},
   208  	})
   209  }
   210  
   211  func BenchmarkMapRange(b *testing.B) {
   212  	const mapSize = 1 << 10
   213  
   214  	benchMap(b, bench{
   215  		setup: func(_ *testing.B, m mapInterface) {
   216  			for i := 0; i < mapSize; i++ {
   217  				m.Store(i, i)
   218  			}
   219  		},
   220  
   221  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   222  			for ; pb.Next(); i++ {
   223  				m.Range(func(_, _ any) bool { return true })
   224  			}
   225  		},
   226  	})
   227  }
   228  
   229  // BenchmarkMapAdversarialAlloc tests performance when we store a new value
   230  // immediately whenever the map is promoted to clean and otherwise load a
   231  // unique, missing key.
   232  //
   233  // This forces the Load calls to always acquire the map's mutex.
   234  func BenchmarkMapAdversarialAlloc(b *testing.B) {
   235  	benchMap(b, bench{
   236  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   237  			var stores, loadsSinceStore int64
   238  			for ; pb.Next(); i++ {
   239  				m.Load(i)
   240  				if loadsSinceStore++; loadsSinceStore > stores {
   241  					m.LoadOrStore(i, stores)
   242  					loadsSinceStore = 0
   243  					stores++
   244  				}
   245  			}
   246  		},
   247  	})
   248  }
   249  
   250  // BenchmarkMapAdversarialDelete tests performance when we periodically delete
   251  // one key and add a different one in a large map.
   252  //
   253  // This forces the Load calls to always acquire the map's mutex and periodically
   254  // makes a full copy of the map despite changing only one entry.
   255  func BenchmarkMapAdversarialDelete(b *testing.B) {
   256  	const mapSize = 1 << 10
   257  
   258  	benchMap(b, bench{
   259  		setup: func(_ *testing.B, m mapInterface) {
   260  			for i := 0; i < mapSize; i++ {
   261  				m.Store(i, i)
   262  			}
   263  		},
   264  
   265  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   266  			for ; pb.Next(); i++ {
   267  				m.Load(i)
   268  
   269  				if i%mapSize == 0 {
   270  					m.Range(func(k, _ any) bool {
   271  						m.Delete(k)
   272  						return false
   273  					})
   274  					m.Store(i, i)
   275  				}
   276  			}
   277  		},
   278  	})
   279  }
   280  
   281  func BenchmarkMapDeleteCollision(b *testing.B) {
   282  	benchMap(b, bench{
   283  		setup: func(_ *testing.B, m mapInterface) {
   284  			m.LoadOrStore(0, 0)
   285  		},
   286  
   287  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   288  			for ; pb.Next(); i++ {
   289  				m.Delete(0)
   290  			}
   291  		},
   292  	})
   293  }
   294  
   295  func BenchmarkMapSwapCollision(b *testing.B) {
   296  	benchMap(b, bench{
   297  		setup: func(_ *testing.B, m mapInterface) {
   298  			m.LoadOrStore(0, 0)
   299  		},
   300  
   301  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   302  			for ; pb.Next(); i++ {
   303  				m.Swap(0, 0)
   304  			}
   305  		},
   306  	})
   307  }
   308  
   309  func BenchmarkMapSwapMostlyHits(b *testing.B) {
   310  	const hits, misses = 1023, 1
   311  
   312  	benchMap(b, bench{
   313  		setup: func(_ *testing.B, m mapInterface) {
   314  			for i := 0; i < hits; i++ {
   315  				m.LoadOrStore(i, i)
   316  			}
   317  			// Prime the map to get it into a steady state.
   318  			for i := 0; i < hits*2; i++ {
   319  				m.Load(i % hits)
   320  			}
   321  		},
   322  
   323  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   324  			for ; pb.Next(); i++ {
   325  				if i%(hits+misses) < hits {
   326  					v := i % (hits + misses)
   327  					m.Swap(v, v)
   328  				} else {
   329  					m.Swap(i, i)
   330  					m.Delete(i)
   331  				}
   332  			}
   333  		},
   334  	})
   335  }
   336  
   337  func BenchmarkMapSwapMostlyMisses(b *testing.B) {
   338  	const hits, misses = 1, 1023
   339  
   340  	benchMap(b, bench{
   341  		setup: func(_ *testing.B, m mapInterface) {
   342  			for i := 0; i < hits; i++ {
   343  				m.LoadOrStore(i, i)
   344  			}
   345  			// Prime the map to get it into a steady state.
   346  			for i := 0; i < hits*2; i++ {
   347  				m.Load(i % hits)
   348  			}
   349  		},
   350  
   351  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   352  			for ; pb.Next(); i++ {
   353  				if i%(hits+misses) < hits {
   354  					v := i % (hits + misses)
   355  					m.Swap(v, v)
   356  				} else {
   357  					m.Swap(i, i)
   358  					m.Delete(i)
   359  				}
   360  			}
   361  		},
   362  	})
   363  }
   364  
   365  func BenchmarkMapCompareAndSwapCollision(b *testing.B) {
   366  	benchMap(b, bench{
   367  		setup: func(_ *testing.B, m mapInterface) {
   368  			m.LoadOrStore(0, 0)
   369  		},
   370  
   371  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   372  			for pb.Next() {
   373  				if m.CompareAndSwap(0, 0, 42) {
   374  					m.CompareAndSwap(0, 42, 0)
   375  				}
   376  			}
   377  		},
   378  	})
   379  }
   380  
   381  func BenchmarkMapCompareAndSwapNoExistingKey(b *testing.B) {
   382  	benchMap(b, bench{
   383  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   384  			for ; pb.Next(); i++ {
   385  				if m.CompareAndSwap(i, 0, 0) {
   386  					m.Delete(i)
   387  				}
   388  			}
   389  		},
   390  	})
   391  }
   392  
   393  func BenchmarkMapCompareAndSwapValueNotEqual(b *testing.B) {
   394  	benchMap(b, bench{
   395  		setup: func(_ *testing.B, m mapInterface) {
   396  			m.Store(0, 0)
   397  		},
   398  
   399  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   400  			for ; pb.Next(); i++ {
   401  				m.CompareAndSwap(0, 1, 2)
   402  			}
   403  		},
   404  	})
   405  }
   406  
   407  func BenchmarkMapCompareAndSwapMostlyHits(b *testing.B) {
   408  	const hits, misses = 1023, 1
   409  
   410  	benchMap(b, bench{
   411  		setup: func(b *testing.B, m mapInterface) {
   412  			if _, ok := m.(*DeepCopyMap); ok {
   413  				b.Skip("DeepCopyMap has quadratic running time.")
   414  			}
   415  
   416  			for i := 0; i < hits; i++ {
   417  				m.LoadOrStore(i, i)
   418  			}
   419  			// Prime the map to get it into a steady state.
   420  			for i := 0; i < hits*2; i++ {
   421  				m.Load(i % hits)
   422  			}
   423  		},
   424  
   425  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   426  			for ; pb.Next(); i++ {
   427  				v := i
   428  				if i%(hits+misses) < hits {
   429  					v = i % (hits + misses)
   430  				}
   431  				m.CompareAndSwap(v, v, v)
   432  			}
   433  		},
   434  	})
   435  }
   436  
   437  func BenchmarkMapCompareAndSwapMostlyMisses(b *testing.B) {
   438  	const hits, misses = 1, 1023
   439  
   440  	benchMap(b, bench{
   441  		setup: func(_ *testing.B, m mapInterface) {
   442  			for i := 0; i < hits; i++ {
   443  				m.LoadOrStore(i, i)
   444  			}
   445  			// Prime the map to get it into a steady state.
   446  			for i := 0; i < hits*2; i++ {
   447  				m.Load(i % hits)
   448  			}
   449  		},
   450  
   451  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   452  			for ; pb.Next(); i++ {
   453  				v := i
   454  				if i%(hits+misses) < hits {
   455  					v = i % (hits + misses)
   456  				}
   457  				m.CompareAndSwap(v, v, v)
   458  			}
   459  		},
   460  	})
   461  }
   462  
   463  func BenchmarkMapCompareAndDeleteCollision(b *testing.B) {
   464  	benchMap(b, bench{
   465  		setup: func(_ *testing.B, m mapInterface) {
   466  			m.LoadOrStore(0, 0)
   467  		},
   468  
   469  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   470  			for ; pb.Next(); i++ {
   471  				if m.CompareAndDelete(0, 0) {
   472  					m.Store(0, 0)
   473  				}
   474  			}
   475  		},
   476  	})
   477  }
   478  
   479  func BenchmarkMapCompareAndDeleteMostlyHits(b *testing.B) {
   480  	const hits, misses = 1023, 1
   481  
   482  	benchMap(b, bench{
   483  		setup: func(b *testing.B, m mapInterface) {
   484  			if _, ok := m.(*DeepCopyMap); ok {
   485  				b.Skip("DeepCopyMap has quadratic running time.")
   486  			}
   487  
   488  			for i := 0; i < hits; i++ {
   489  				m.LoadOrStore(i, i)
   490  			}
   491  			// Prime the map to get it into a steady state.
   492  			for i := 0; i < hits*2; i++ {
   493  				m.Load(i % hits)
   494  			}
   495  		},
   496  
   497  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   498  			for ; pb.Next(); i++ {
   499  				v := i
   500  				if i%(hits+misses) < hits {
   501  					v = i % (hits + misses)
   502  				}
   503  				if m.CompareAndDelete(v, v) {
   504  					m.Store(v, v)
   505  				}
   506  			}
   507  		},
   508  	})
   509  }
   510  
   511  func BenchmarkMapCompareAndDeleteMostlyMisses(b *testing.B) {
   512  	const hits, misses = 1, 1023
   513  
   514  	benchMap(b, bench{
   515  		setup: func(_ *testing.B, m mapInterface) {
   516  			for i := 0; i < hits; i++ {
   517  				m.LoadOrStore(i, i)
   518  			}
   519  			// Prime the map to get it into a steady state.
   520  			for i := 0; i < hits*2; i++ {
   521  				m.Load(i % hits)
   522  			}
   523  		},
   524  
   525  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   526  			for ; pb.Next(); i++ {
   527  				v := i
   528  				if i%(hits+misses) < hits {
   529  					v = i % (hits + misses)
   530  				}
   531  				if m.CompareAndDelete(v, v) {
   532  					m.Store(v, v)
   533  				}
   534  			}
   535  		},
   536  	})
   537  }
   538  
   539  func BenchmarkMapClear(b *testing.B) {
   540  	benchMap(b, bench{
   541  		perG: func(b *testing.B, pb *testing.PB, i int, m mapInterface) {
   542  			for ; pb.Next(); i++ {
   543  				k, v := i%256, i%256
   544  				m.Clear()
   545  				m.Store(k, v)
   546  			}
   547  		},
   548  	})
   549  }
   550
View as plain text