map_noswiss_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  //go:build !goexperiment.swissmap
     6  
     7  package runtime_test
     8  
     9  import (
    10  	"internal/abi"
    11  	"internal/goarch"
    12  	"runtime"
    13  	"slices"
    14  	"testing"
    15  )
    16  
    17  func TestHmapSize(t *testing.T) {
    18  	// The structure of hmap is defined in runtime/map.go
    19  	// and in cmd/compile/internal/reflectdata/map.go and must be in sync.
    20  	// The size of hmap should be 56 bytes on 64 bit and 36 bytes on 32 bit platforms.
    21  	var hmapSize = uintptr(2*8 + 5*goarch.PtrSize)
    22  	if runtime.RuntimeHmapSize != hmapSize {
    23  		t.Errorf("sizeof(runtime.hmap{})==%d, want %d", runtime.RuntimeHmapSize, hmapSize)
    24  	}
    25  }
    26  
    27  func TestLoadFactor(t *testing.T) {
    28  	for b := uint8(0); b < 20; b++ {
    29  		count := 13 * (1 << b) / 2 // 6.5
    30  		if b == 0 {
    31  			count = 8
    32  		}
    33  		if runtime.OverLoadFactor(count, b) {
    34  			t.Errorf("OverLoadFactor(%d,%d)=true, want false", count, b)
    35  		}
    36  		if !runtime.OverLoadFactor(count+1, b) {
    37  			t.Errorf("OverLoadFactor(%d,%d)=false, want true", count+1, b)
    38  		}
    39  	}
    40  }
    41  
    42  func TestMapIterOrder(t *testing.T) {
    43  	sizes := []int{3, 7, 9, 15}
    44  	if abi.OldMapBucketCountBits >= 5 {
    45  		// it gets flaky (often only one iteration order) at size 3 when abi.MapBucketCountBits >=5.
    46  		t.Fatalf("This test becomes flaky if abi.MapBucketCountBits(=%d) is 5 or larger", abi.OldMapBucketCountBits)
    47  	}
    48  	for _, n := range sizes {
    49  		for i := 0; i < 1000; i++ {
    50  			// Make m be {0: true, 1: true, ..., n-1: true}.
    51  			m := make(map[int]bool)
    52  			for i := 0; i < n; i++ {
    53  				m[i] = true
    54  			}
    55  			// Check that iterating over the map produces at least two different orderings.
    56  			ord := func() []int {
    57  				var s []int
    58  				for key := range m {
    59  					s = append(s, key)
    60  				}
    61  				return s
    62  			}
    63  			first := ord()
    64  			ok := false
    65  			for try := 0; try < 100; try++ {
    66  				if !slices.Equal(first, ord()) {
    67  					ok = true
    68  					break
    69  				}
    70  			}
    71  			if !ok {
    72  				t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
    73  				break
    74  			}
    75  		}
    76  	}
    77  }
    78  
    79  const bs = abi.OldMapBucketCount
    80  
    81  // belowOverflow should be a pretty-full pair of buckets;
    82  // atOverflow is 1/8 bs larger = 13/8 buckets or two buckets
    83  // that are 13/16 full each, which is the overflow boundary.
    84  // Adding one to that should ensure overflow to the next higher size.
    85  const (
    86  	belowOverflow = bs * 3 / 2           // 1.5 bs = 2 buckets @ 75%
    87  	atOverflow    = belowOverflow + bs/8 // 2 buckets at 13/16 fill.
    88  )
    89  
    90  var mapBucketTests = [...]struct {
    91  	n        int // n is the number of map elements
    92  	noescape int // number of expected buckets for non-escaping map
    93  	escape   int // number of expected buckets for escaping map
    94  }{
    95  	{-(1 << 30), 1, 1},
    96  	{-1, 1, 1},
    97  	{0, 1, 1},
    98  	{1, 1, 1},
    99  	{bs, 1, 1},
   100  	{bs + 1, 2, 2},
   101  	{belowOverflow, 2, 2},  // 1.5 bs = 2 buckets @ 75%
   102  	{atOverflow + 1, 4, 4}, // 13/8 bs + 1 == overflow to 4
   103  
   104  	{2 * belowOverflow, 4, 4}, // 3 bs = 4 buckets @75%
   105  	{2*atOverflow + 1, 8, 8},  // 13/4 bs + 1 = overflow to 8
   106  
   107  	{4 * belowOverflow, 8, 8},  // 6 bs = 8 buckets @ 75%
   108  	{4*atOverflow + 1, 16, 16}, // 13/2 bs + 1 = overflow to 16
   109  }
   110  
   111  func TestMapBuckets(t *testing.T) {
   112  	// Test that maps of different sizes have the right number of buckets.
   113  	// Non-escaping maps with small buckets (like map[int]int) never
   114  	// have a nil bucket pointer due to starting with preallocated buckets
   115  	// on the stack. Escaping maps start with a non-nil bucket pointer if
   116  	// hint size is above bucketCnt and thereby have more than one bucket.
   117  	// These tests depend on bucketCnt and loadFactor* in map.go.
   118  	t.Run("mapliteral", func(t *testing.T) {
   119  		for _, tt := range mapBucketTests {
   120  			localMap := map[int]int{}
   121  			if runtime.MapBucketsPointerIsNil(localMap) {
   122  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   123  			}
   124  			for i := 0; i < tt.n; i++ {
   125  				localMap[i] = i
   126  			}
   127  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   128  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   129  			}
   130  			escapingMap := runtime.Escape(map[int]int{})
   131  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   132  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   133  			}
   134  			for i := 0; i < tt.n; i++ {
   135  				escapingMap[i] = i
   136  			}
   137  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   138  				t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   139  			}
   140  		}
   141  	})
   142  	t.Run("nohint", func(t *testing.T) {
   143  		for _, tt := range mapBucketTests {
   144  			localMap := make(map[int]int)
   145  			if runtime.MapBucketsPointerIsNil(localMap) {
   146  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   147  			}
   148  			for i := 0; i < tt.n; i++ {
   149  				localMap[i] = i
   150  			}
   151  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   152  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   153  			}
   154  			escapingMap := runtime.Escape(make(map[int]int))
   155  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   156  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   157  			}
   158  			for i := 0; i < tt.n; i++ {
   159  				escapingMap[i] = i
   160  			}
   161  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   162  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   163  			}
   164  		}
   165  	})
   166  	t.Run("makemap", func(t *testing.T) {
   167  		for _, tt := range mapBucketTests {
   168  			localMap := make(map[int]int, tt.n)
   169  			if runtime.MapBucketsPointerIsNil(localMap) {
   170  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   171  			}
   172  			for i := 0; i < tt.n; i++ {
   173  				localMap[i] = i
   174  			}
   175  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   176  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   177  			}
   178  			escapingMap := runtime.Escape(make(map[int]int, tt.n))
   179  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   180  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   181  			}
   182  			for i := 0; i < tt.n; i++ {
   183  				escapingMap[i] = i
   184  			}
   185  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   186  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   187  			}
   188  		}
   189  	})
   190  	t.Run("makemap64", func(t *testing.T) {
   191  		for _, tt := range mapBucketTests {
   192  			localMap := make(map[int]int, int64(tt.n))
   193  			if runtime.MapBucketsPointerIsNil(localMap) {
   194  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
   195  			}
   196  			for i := 0; i < tt.n; i++ {
   197  				localMap[i] = i
   198  			}
   199  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
   200  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
   201  			}
   202  			escapingMap := runtime.Escape(make(map[int]int, tt.n))
   203  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
   204  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
   205  			}
   206  			for i := 0; i < tt.n; i++ {
   207  				escapingMap[i] = i
   208  			}
   209  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
   210  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
   211  			}
   212  		}
   213  	})
   214  }
   215
View as plain text