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
View as plain text