map_swiss_test.go

     1  // Copyright 2024 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  // Tests of map internals that need to use the builtin map type, and thus must
     6  // be built with GOEXPERIMENT=swissmap.
     7  
     8  //go:build goexperiment.swissmap
     9  
    10  package maps_test
    11  
    12  import (
    13  	"fmt"
    14  	"internal/abi"
    15  	"internal/runtime/maps"
    16  	"testing"
    17  	"unsafe"
    18  )
    19  
    20  var alwaysFalse bool
    21  var escapeSink any
    22  
    23  func escape[T any](x T) T {
    24  	if alwaysFalse {
    25  		escapeSink = x
    26  	}
    27  	return x
    28  }
    29  
    30  const (
    31  	belowMax = abi.SwissMapGroupSlots * 3 / 2                                               // 1.5 * group max = 2 groups @ 75%
    32  	atMax    = (2 * abi.SwissMapGroupSlots * maps.MaxAvgGroupLoad) / abi.SwissMapGroupSlots // 2 groups at 7/8 full.
    33  )
    34  
    35  func TestTableGroupCount(t *testing.T) {
    36  	// Test that maps of different sizes have the right number of
    37  	// tables/groups.
    38  
    39  	type mapCount struct {
    40  		tables int
    41  		groups uint64
    42  	}
    43  
    44  	type mapCase struct {
    45  		initialLit  mapCount
    46  		initialHint mapCount
    47  		after       mapCount
    48  	}
    49  
    50  	var testCases = []struct {
    51  		n      int     // n is the number of map elements
    52  		escape mapCase // expected values for escaping map
    53  	}{
    54  		{
    55  			n: -(1 << 30),
    56  			escape: mapCase{
    57  				initialLit:  mapCount{0, 0},
    58  				initialHint: mapCount{0, 0},
    59  				after:       mapCount{0, 0},
    60  			},
    61  		},
    62  		{
    63  			n: -1,
    64  			escape: mapCase{
    65  				initialLit:  mapCount{0, 0},
    66  				initialHint: mapCount{0, 0},
    67  				after:       mapCount{0, 0},
    68  			},
    69  		},
    70  		{
    71  			n: 0,
    72  			escape: mapCase{
    73  				initialLit:  mapCount{0, 0},
    74  				initialHint: mapCount{0, 0},
    75  				after:       mapCount{0, 0},
    76  			},
    77  		},
    78  		{
    79  			n: 1,
    80  			escape: mapCase{
    81  				initialLit:  mapCount{0, 0},
    82  				initialHint: mapCount{0, 0},
    83  				after:       mapCount{0, 1},
    84  			},
    85  		},
    86  		{
    87  			n: abi.SwissMapGroupSlots,
    88  			escape: mapCase{
    89  				initialLit:  mapCount{0, 0},
    90  				initialHint: mapCount{0, 0},
    91  				after:       mapCount{0, 1},
    92  			},
    93  		},
    94  		{
    95  			n: abi.SwissMapGroupSlots + 1,
    96  			escape: mapCase{
    97  				initialLit:  mapCount{0, 0},
    98  				initialHint: mapCount{1, 2},
    99  				after:       mapCount{1, 2},
   100  			},
   101  		},
   102  		{
   103  			n: belowMax, // 1.5 group max = 2 groups @ 75%
   104  			escape: mapCase{
   105  				initialLit:  mapCount{0, 0},
   106  				initialHint: mapCount{1, 2},
   107  				after:       mapCount{1, 2},
   108  			},
   109  		},
   110  		{
   111  			n: atMax, // 2 groups at max
   112  			escape: mapCase{
   113  				initialLit:  mapCount{0, 0},
   114  				initialHint: mapCount{1, 2},
   115  				after:       mapCount{1, 2},
   116  			},
   117  		},
   118  		{
   119  			n: atMax + 1, // 2 groups at max + 1 -> grow to 4 groups
   120  			escape: mapCase{
   121  				initialLit:  mapCount{0, 0},
   122  				initialHint: mapCount{1, 4},
   123  				after:       mapCount{1, 4},
   124  			},
   125  		},
   126  		{
   127  			n: 2 * belowMax, // 3 * group max = 4 groups @75%
   128  			escape: mapCase{
   129  				initialLit:  mapCount{0, 0},
   130  				initialHint: mapCount{1, 4},
   131  				after:       mapCount{1, 4},
   132  			},
   133  		},
   134  		{
   135  			n: 2*atMax + 1, // 4 groups at max + 1 -> grow to 8 groups
   136  			escape: mapCase{
   137  				initialLit:  mapCount{0, 0},
   138  				initialHint: mapCount{1, 8},
   139  				after:       mapCount{1, 8},
   140  			},
   141  		},
   142  	}
   143  
   144  	testMap := func(t *testing.T, m map[int]int, n int, initial, after mapCount) {
   145  		mm := *(**maps.Map)(unsafe.Pointer(&m))
   146  
   147  		gotTab := mm.TableCount()
   148  		if gotTab != initial.tables {
   149  			t.Errorf("initial TableCount got %d want %d", gotTab, initial.tables)
   150  		}
   151  
   152  		gotGroup := mm.GroupCount()
   153  		if gotGroup != initial.groups {
   154  			t.Errorf("initial GroupCount got %d want %d", gotGroup, initial.groups)
   155  		}
   156  
   157  		for i := 0; i < n; i++ {
   158  			m[i] = i
   159  		}
   160  
   161  		gotTab = mm.TableCount()
   162  		if gotTab != after.tables {
   163  			t.Errorf("after TableCount got %d want %d", gotTab, after.tables)
   164  		}
   165  
   166  		gotGroup = mm.GroupCount()
   167  		if gotGroup != after.groups {
   168  			t.Errorf("after GroupCount got %d want %d", gotGroup, after.groups)
   169  		}
   170  	}
   171  
   172  	t.Run("mapliteral", func(t *testing.T) {
   173  		for _, tc := range testCases {
   174  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   175  				t.Run("escape", func(t *testing.T) {
   176  					m := escape(map[int]int{})
   177  					testMap(t, m, tc.n, tc.escape.initialLit, tc.escape.after)
   178  				})
   179  			})
   180  		}
   181  	})
   182  	t.Run("nohint", func(t *testing.T) {
   183  		for _, tc := range testCases {
   184  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   185  				t.Run("escape", func(t *testing.T) {
   186  					m := escape(make(map[int]int))
   187  					testMap(t, m, tc.n, tc.escape.initialLit, tc.escape.after)
   188  				})
   189  			})
   190  		}
   191  	})
   192  	t.Run("makemap", func(t *testing.T) {
   193  		for _, tc := range testCases {
   194  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   195  				t.Run("escape", func(t *testing.T) {
   196  					m := escape(make(map[int]int, tc.n))
   197  					testMap(t, m, tc.n, tc.escape.initialHint, tc.escape.after)
   198  				})
   199  			})
   200  		}
   201  	})
   202  	t.Run("makemap64", func(t *testing.T) {
   203  		for _, tc := range testCases {
   204  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   205  				t.Run("escape", func(t *testing.T) {
   206  					m := escape(make(map[int]int, int64(tc.n)))
   207  					testMap(t, m, tc.n, tc.escape.initialHint, tc.escape.after)
   208  				})
   209  			})
   210  		}
   211  	})
   212  }
   213  
   214  func TestTombstoneGrow(t *testing.T) {
   215  	tableSizes := []int{16, 32, 64, 128, 256}
   216  	for _, tableSize := range tableSizes {
   217  		for _, load := range []string{"low", "mid", "high"} {
   218  			capacity := tableSize * 7 / 8
   219  			var initialElems int
   220  			switch load {
   221  			case "low":
   222  				initialElems = capacity / 8
   223  			case "mid":
   224  				initialElems = capacity / 2
   225  			case "high":
   226  				initialElems = capacity
   227  			}
   228  			t.Run(fmt.Sprintf("tableSize=%d/elems=%d/load=%0.3f", tableSize, initialElems, float64(initialElems)/float64(tableSize)), func(t *testing.T) {
   229  				allocs := testing.AllocsPerRun(1, func() {
   230  					// Fill the map with elements.
   231  					m := make(map[int]int, capacity)
   232  					for i := range initialElems {
   233  						m[i] = i
   234  					}
   235  
   236  					// This is the heart of our test.
   237  					// Loop over the map repeatedly, deleting a key then adding a not-yet-seen key
   238  					// while keeping the map at a ~constant number of elements (+/-1).
   239  					nextKey := initialElems
   240  					for range 100000 {
   241  						for k := range m {
   242  							delete(m, k)
   243  							break
   244  						}
   245  						m[nextKey] = nextKey
   246  						nextKey++
   247  						if len(m) != initialElems {
   248  							t.Fatal("len(m) should remain constant")
   249  						}
   250  					}
   251  				})
   252  
   253  				// The make has 4 allocs (map, directory, table, groups).
   254  				// Each growth has 2 allocs (table, groups).
   255  				// We allow two growths if we start full, 1 otherwise.
   256  				// Fail (somewhat arbitrarily) if there are more than that.
   257  				allowed := float64(4 + 1*2)
   258  				if initialElems == capacity {
   259  					allowed += 2
   260  				}
   261  				if allocs > allowed {
   262  					t.Fatalf("got %v allocations, allowed %v", allocs, allowed)
   263  				}
   264  			})
   265  		}
   266  	}
   267  }
   268
View as plain text