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  		// TODO(go.dev/issue/54766): implement stack allocated maps
    54  	}{
    55  		{
    56  			n: -(1 << 30),
    57  			escape: mapCase{
    58  				initialLit:  mapCount{0, 0},
    59  				initialHint: mapCount{0, 0},
    60  				after:       mapCount{0, 0},
    61  			},
    62  		},
    63  		{
    64  			n: -1,
    65  			escape: mapCase{
    66  				initialLit:  mapCount{0, 0},
    67  				initialHint: mapCount{0, 0},
    68  				after:       mapCount{0, 0},
    69  			},
    70  		},
    71  		{
    72  			n: 0,
    73  			escape: mapCase{
    74  				initialLit:  mapCount{0, 0},
    75  				initialHint: mapCount{0, 0},
    76  				after:       mapCount{0, 0},
    77  			},
    78  		},
    79  		{
    80  			n: 1,
    81  			escape: mapCase{
    82  				initialLit:  mapCount{0, 0},
    83  				initialHint: mapCount{0, 0},
    84  				after:       mapCount{0, 1},
    85  			},
    86  		},
    87  		{
    88  			n: abi.SwissMapGroupSlots,
    89  			escape: mapCase{
    90  				initialLit:  mapCount{0, 0},
    91  				initialHint: mapCount{0, 0},
    92  				after:       mapCount{0, 1},
    93  			},
    94  		},
    95  		{
    96  			n: abi.SwissMapGroupSlots + 1,
    97  			escape: mapCase{
    98  				initialLit:  mapCount{0, 0},
    99  				initialHint: mapCount{1, 2},
   100  				after:       mapCount{1, 2},
   101  			},
   102  		},
   103  		{
   104  			n: belowMax, // 1.5 group max = 2 groups @ 75%
   105  			escape: mapCase{
   106  				initialLit:  mapCount{0, 0},
   107  				initialHint: mapCount{1, 2},
   108  				after:       mapCount{1, 2},
   109  			},
   110  		},
   111  		{
   112  			n: atMax, // 2 groups at max
   113  			escape: mapCase{
   114  				initialLit:  mapCount{0, 0},
   115  				initialHint: mapCount{1, 2},
   116  				after:       mapCount{1, 2},
   117  			},
   118  		},
   119  		{
   120  			n: atMax + 1, // 2 groups at max + 1 -> grow to 4 groups
   121  			escape: mapCase{
   122  				initialLit:  mapCount{0, 0},
   123  				initialHint: mapCount{1, 4},
   124  				after:       mapCount{1, 4},
   125  			},
   126  		},
   127  		{
   128  			n: 2 * belowMax, // 3 * group max = 4 groups @75%
   129  			escape: mapCase{
   130  				initialLit:  mapCount{0, 0},
   131  				initialHint: mapCount{1, 4},
   132  				after:       mapCount{1, 4},
   133  			},
   134  		},
   135  		{
   136  			n: 2*atMax + 1, // 4 groups at max + 1 -> grow to 8 groups
   137  			escape: mapCase{
   138  				initialLit:  mapCount{0, 0},
   139  				initialHint: mapCount{1, 8},
   140  				after:       mapCount{1, 8},
   141  			},
   142  		},
   143  	}
   144  
   145  	testMap := func(t *testing.T, m map[int]int, n int, initial, after mapCount) {
   146  		mm := *(**maps.Map)(unsafe.Pointer(&m))
   147  
   148  		gotTab := mm.TableCount()
   149  		if gotTab != initial.tables {
   150  			t.Errorf("initial TableCount got %d want %d", gotTab, initial.tables)
   151  		}
   152  
   153  		gotGroup := mm.GroupCount()
   154  		if gotGroup != initial.groups {
   155  			t.Errorf("initial GroupCount got %d want %d", gotGroup, initial.groups)
   156  		}
   157  
   158  		for i := 0; i < n; i++ {
   159  			m[i] = i
   160  		}
   161  
   162  		gotTab = mm.TableCount()
   163  		if gotTab != after.tables {
   164  			t.Errorf("after TableCount got %d want %d", gotTab, after.tables)
   165  		}
   166  
   167  		gotGroup = mm.GroupCount()
   168  		if gotGroup != after.groups {
   169  			t.Errorf("after GroupCount got %d want %d", gotGroup, after.groups)
   170  		}
   171  	}
   172  
   173  	t.Run("mapliteral", func(t *testing.T) {
   174  		for _, tc := range testCases {
   175  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   176  				t.Run("escape", func(t *testing.T) {
   177  					m := escape(map[int]int{})
   178  					testMap(t, m, tc.n, tc.escape.initialLit, tc.escape.after)
   179  				})
   180  			})
   181  		}
   182  	})
   183  	t.Run("nohint", func(t *testing.T) {
   184  		for _, tc := range testCases {
   185  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   186  				t.Run("escape", func(t *testing.T) {
   187  					m := escape(make(map[int]int))
   188  					testMap(t, m, tc.n, tc.escape.initialLit, tc.escape.after)
   189  				})
   190  			})
   191  		}
   192  	})
   193  	t.Run("makemap", func(t *testing.T) {
   194  		for _, tc := range testCases {
   195  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   196  				t.Run("escape", func(t *testing.T) {
   197  					m := escape(make(map[int]int, tc.n))
   198  					testMap(t, m, tc.n, tc.escape.initialHint, tc.escape.after)
   199  				})
   200  			})
   201  		}
   202  	})
   203  	t.Run("makemap64", func(t *testing.T) {
   204  		for _, tc := range testCases {
   205  			t.Run(fmt.Sprintf("n=%d", tc.n), func(t *testing.T) {
   206  				t.Run("escape", func(t *testing.T) {
   207  					m := escape(make(map[int]int, int64(tc.n)))
   208  					testMap(t, m, tc.n, tc.escape.initialHint, tc.escape.after)
   209  				})
   210  			})
   211  		}
   212  	})
   213  }
   214
View as plain text