blob: c29fb933ee49be2961bfea73a10758b7facce8bb [file] [log] [blame]
// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package runtime_test
import (
"fmt"
"internal/abi"
"internal/goarch"
"internal/testenv"
"math"
"os"
"reflect"
"runtime"
"sort"
"strconv"
"strings"
"sync"
"testing"
"unsafe"
)
func TestHmapSize(t *testing.T) {
// The structure of hmap is defined in runtime/map.go
// and in cmd/compile/internal/gc/reflect.go and must be in sync.
// The size of hmap should be 48 bytes on 64 bit and 28 bytes on 32 bit platforms.
var hmapSize = uintptr(8 + 5*goarch.PtrSize)
if runtime.RuntimeHmapSize != hmapSize {
t.Errorf("sizeof(runtime.hmap{})==%d, want %d", runtime.RuntimeHmapSize, hmapSize)
}
}
// negative zero is a good test because:
// 1. 0 and -0 are equal, yet have distinct representations.
// 2. 0 is represented as all zeros, -0 isn't.
//
// I'm not sure the language spec actually requires this behavior,
// but it's what the current map implementation does.
func TestNegativeZero(t *testing.T) {
m := make(map[float64]bool, 0)
m[+0.0] = true
m[math.Copysign(0.0, -1.0)] = true // should overwrite +0 entry
if len(m) != 1 {
t.Error("length wrong")
}
for k := range m {
if math.Copysign(1.0, k) > 0 {
t.Error("wrong sign")
}
}
m = make(map[float64]bool, 0)
m[math.Copysign(0.0, -1.0)] = true
m[+0.0] = true // should overwrite -0.0 entry
if len(m) != 1 {
t.Error("length wrong")
}
for k := range m {
if math.Copysign(1.0, k) < 0 {
t.Error("wrong sign")
}
}
}
func testMapNan(t *testing.T, m map[float64]int) {
if len(m) != 3 {
t.Error("length wrong")
}
s := 0
for k, v := range m {
if k == k {
t.Error("nan disappeared")
}
if (v & (v - 1)) != 0 {
t.Error("value wrong")
}
s |= v
}
if s != 7 {
t.Error("values wrong")
}
}
// nan is a good test because nan != nan, and nan has
// a randomized hash value.
func TestMapAssignmentNan(t *testing.T) {
m := make(map[float64]int, 0)
nan := math.NaN()
// Test assignment.
m[nan] = 1
m[nan] = 2
m[nan] = 4
testMapNan(t, m)
}
// nan is a good test because nan != nan, and nan has
// a randomized hash value.
func TestMapOperatorAssignmentNan(t *testing.T) {
m := make(map[float64]int, 0)
nan := math.NaN()
// Test assignment operations.
m[nan] += 1
m[nan] += 2
m[nan] += 4
testMapNan(t, m)
}
func TestMapOperatorAssignment(t *testing.T) {
m := make(map[int]int, 0)
// "m[k] op= x" is rewritten into "m[k] = m[k] op x"
// differently when op is / or % than when it isn't.
// Simple test to make sure they all work as expected.
m[0] = 12345
m[0] += 67890
m[0] /= 123
m[0] %= 456
const want = (12345 + 67890) / 123 % 456
if got := m[0]; got != want {
t.Errorf("got %d, want %d", got, want)
}
}
var sinkAppend bool
func TestMapAppendAssignment(t *testing.T) {
m := make(map[int][]int, 0)
m[0] = nil
m[0] = append(m[0], 12345)
m[0] = append(m[0], 67890)
sinkAppend, m[0] = !sinkAppend, append(m[0], 123, 456)
a := []int{7, 8, 9, 0}
m[0] = append(m[0], a...)
want := []int{12345, 67890, 123, 456, 7, 8, 9, 0}
if got := m[0]; !reflect.DeepEqual(got, want) {
t.Errorf("got %v, want %v", got, want)
}
}
// Maps aren't actually copied on assignment.
func TestAlias(t *testing.T) {
m := make(map[int]int, 0)
m[0] = 5
n := m
n[0] = 6
if m[0] != 6 {
t.Error("alias didn't work")
}
}
func TestGrowWithNaN(t *testing.T) {
m := make(map[float64]int, 4)
nan := math.NaN()
// Use both assignment and assignment operations as they may
// behave differently.
m[nan] = 1
m[nan] = 2
m[nan] += 4
cnt := 0
s := 0
growflag := true
for k, v := range m {
if growflag {
// force a hashtable resize
for i := 0; i < 50; i++ {
m[float64(i)] = i
}
for i := 50; i < 100; i++ {
m[float64(i)] += i
}
growflag = false
}
if k != k {
cnt++
s |= v
}
}
if cnt != 3 {
t.Error("NaN keys lost during grow")
}
if s != 7 {
t.Error("NaN values lost during grow")
}
}
type FloatInt struct {
x float64
y int
}
func TestGrowWithNegativeZero(t *testing.T) {
negzero := math.Copysign(0.0, -1.0)
m := make(map[FloatInt]int, 4)
m[FloatInt{0.0, 0}] = 1
m[FloatInt{0.0, 1}] += 2
m[FloatInt{0.0, 2}] += 4
m[FloatInt{0.0, 3}] = 8
growflag := true
s := 0
cnt := 0
negcnt := 0
// The first iteration should return the +0 key.
// The subsequent iterations should return the -0 key.
// I'm not really sure this is required by the spec,
// but it makes sense.
// TODO: are we allowed to get the first entry returned again???
for k, v := range m {
if v == 0 {
continue
} // ignore entries added to grow table
cnt++
if math.Copysign(1.0, k.x) < 0 {
if v&16 == 0 {
t.Error("key/value not updated together 1")
}
negcnt++
s |= v & 15
} else {
if v&16 == 16 {
t.Error("key/value not updated together 2", k, v)
}
s |= v
}
if growflag {
// force a hashtable resize
for i := 0; i < 100; i++ {
m[FloatInt{3.0, i}] = 0
}
// then change all the entries
// to negative zero
m[FloatInt{negzero, 0}] = 1 | 16
m[FloatInt{negzero, 1}] = 2 | 16
m[FloatInt{negzero, 2}] = 4 | 16
m[FloatInt{negzero, 3}] = 8 | 16
growflag = false
}
}
if s != 15 {
t.Error("entry missing", s)
}
if cnt != 4 {
t.Error("wrong number of entries returned by iterator", cnt)
}
if negcnt != 3 {
t.Error("update to negzero missed by iteration", negcnt)
}
}
func TestIterGrowAndDelete(t *testing.T) {
m := make(map[int]int, 4)
for i := 0; i < 100; i++ {
m[i] = i
}
growflag := true
for k := range m {
if growflag {
// grow the table
for i := 100; i < 1000; i++ {
m[i] = i
}
// delete all odd keys
for i := 1; i < 1000; i += 2 {
delete(m, i)
}
growflag = false
} else {
if k&1 == 1 {
t.Error("odd value returned")
}
}
}
}
// make sure old bucket arrays don't get GCd while
// an iterator is still using them.
func TestIterGrowWithGC(t *testing.T) {
m := make(map[int]int, 4)
for i := 0; i < 8; i++ {
m[i] = i
}
for i := 8; i < 16; i++ {
m[i] += i
}
growflag := true
bitmask := 0
for k := range m {
if k < 16 {
bitmask |= 1 << uint(k)
}
if growflag {
// grow the table
for i := 100; i < 1000; i++ {
m[i] = i
}
// trigger a gc
runtime.GC()
growflag = false
}
}
if bitmask != 1<<16-1 {
t.Error("missing key", bitmask)
}
}
func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
t.Parallel()
if runtime.GOMAXPROCS(-1) == 1 {
defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
}
numLoop := 10
numGrowStep := 250
numReader := 16
if testing.Short() {
numLoop, numGrowStep = 2, 100
}
for i := 0; i < numLoop; i++ {
m := make(map[int]int, 0)
for gs := 0; gs < numGrowStep; gs++ {
m[gs] = gs
var wg sync.WaitGroup
wg.Add(numReader * 2)
for nr := 0; nr < numReader; nr++ {
go func() {
defer wg.Done()
for range m {
}
}()
go func() {
defer wg.Done()
for key := 0; key < gs; key++ {
_ = m[key]
}
}()
if useReflect {
wg.Add(1)
go func() {
defer wg.Done()
mv := reflect.ValueOf(m)
keys := mv.MapKeys()
for _, k := range keys {
mv.MapIndex(k)
}
}()
}
}
wg.Wait()
}
}
}
func TestConcurrentReadsAfterGrowth(t *testing.T) {
testConcurrentReadsAfterGrowth(t, false)
}
func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
testConcurrentReadsAfterGrowth(t, true)
}
func TestBigItems(t *testing.T) {
var key [256]string
for i := 0; i < 256; i++ {
key[i] = "foo"
}
m := make(map[[256]string][256]string, 4)
for i := 0; i < 100; i++ {
key[37] = fmt.Sprintf("string%02d", i)
m[key] = key
}
var keys [100]string
var values [100]string
i := 0
for k, v := range m {
keys[i] = k[37]
values[i] = v[37]
i++
}
sort.Strings(keys[:])
sort.Strings(values[:])
for i := 0; i < 100; i++ {
if keys[i] != fmt.Sprintf("string%02d", i) {
t.Errorf("#%d: missing key: %v", i, keys[i])
}
if values[i] != fmt.Sprintf("string%02d", i) {
t.Errorf("#%d: missing value: %v", i, values[i])
}
}
}
func TestMapHugeZero(t *testing.T) {
type T [4000]byte
m := map[int]T{}
x := m[0]
if x != (T{}) {
t.Errorf("map value not zero")
}
y, ok := m[0]
if ok {
t.Errorf("map value should be missing")
}
if y != (T{}) {
t.Errorf("map value not zero")
}
}
type empty struct {
}
func TestEmptyKeyAndValue(t *testing.T) {
a := make(map[int]empty, 4)
b := make(map[empty]int, 4)
c := make(map[empty]empty, 4)
a[0] = empty{}
b[empty{}] = 0
b[empty{}] = 1
c[empty{}] = empty{}
if len(a) != 1 {
t.Errorf("empty value insert problem")
}
if b[empty{}] != 1 {
t.Errorf("empty key returned wrong value")
}
}
// Tests a map with a single bucket, with same-lengthed short keys
// ("quick keys") as well as long keys.
func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
testMapLookups(t, map[string]string{
"x": "x1val",
"xx": "x2val",
"foo": "fooval",
"bar": "barval", // same key length as "foo"
"xxxx": "x4val",
strings.Repeat("x", 128): "longval1",
strings.Repeat("y", 128): "longval2",
})
}
// Tests a map with a single bucket, with all keys having different lengths.
func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
testMapLookups(t, map[string]string{
"x": "x1val",
"xx": "x2val",
"foo": "fooval",
"xxxx": "x4val",
"xxxxx": "x5val",
"xxxxxx": "x6val",
strings.Repeat("x", 128): "longval",
})
}
func testMapLookups(t *testing.T, m map[string]string) {
for k, v := range m {
if m[k] != v {
t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
}
}
}
// Tests whether the iterator returns the right elements when
// started in the middle of a grow, when the keys are NaNs.
func TestMapNanGrowIterator(t *testing.T) {
m := make(map[float64]int)
nan := math.NaN()
const nBuckets = 16
// To fill nBuckets buckets takes LOAD * nBuckets keys.
nKeys := int(nBuckets * runtime.HashLoad)
// Get map to full point with nan keys.
for i := 0; i < nKeys; i++ {
m[nan] = i
}
// Trigger grow
m[1.0] = 1
delete(m, 1.0)
// Run iterator
found := make(map[int]struct{})
for _, v := range m {
if v != -1 {
if _, repeat := found[v]; repeat {
t.Fatalf("repeat of value %d", v)
}
found[v] = struct{}{}
}
if len(found) == nKeys/2 {
// Halfway through iteration, finish grow.
for i := 0; i < nBuckets; i++ {
delete(m, 1.0)
}
}
}
if len(found) != nKeys {
t.Fatalf("missing value")
}
}
func TestMapIterOrder(t *testing.T) {
sizes := []int{3, 7, 9, 15}
if abi.MapBucketCountBits >= 5 {
// it gets flaky (often only one iteration order) at size 3 when abi.MapBucketCountBits >=5.
t.Fatalf("This test becomes flaky if abi.MapBucketCountBits(=%d) is 5 or larger", abi.MapBucketCountBits)
}
for _, n := range sizes {
for i := 0; i < 1000; i++ {
// Make m be {0: true, 1: true, ..., n-1: true}.
m := make(map[int]bool)
for i := 0; i < n; i++ {
m[i] = true
}
// Check that iterating over the map produces at least two different orderings.
ord := func() []int {
var s []int
for key := range m {
s = append(s, key)
}
return s
}
first := ord()
ok := false
for try := 0; try < 100; try++ {
if !reflect.DeepEqual(first, ord()) {
ok = true
break
}
}
if !ok {
t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
break
}
}
}
}
// Issue 8410
func TestMapSparseIterOrder(t *testing.T) {
// Run several rounds to increase the probability
// of failure. One is not enough.
NextRound:
for round := 0; round < 10; round++ {
m := make(map[int]bool)
// Add 1000 items, remove 980.
for i := 0; i < 1000; i++ {
m[i] = true
}
for i := 20; i < 1000; i++ {
delete(m, i)
}
var first []int
for i := range m {
first = append(first, i)
}
// 800 chances to get a different iteration order.
// See bug 8736 for why we need so many tries.
for n := 0; n < 800; n++ {
idx := 0
for i := range m {
if i != first[idx] {
// iteration order changed.
continue NextRound
}
idx++
}
}
t.Fatalf("constant iteration order on round %d: %v", round, first)
}
}
func TestMapStringBytesLookup(t *testing.T) {
// Use large string keys to avoid small-allocation coalescing,
// which can cause AllocsPerRun to report lower counts than it should.
m := map[string]int{
"1000000000000000000000000000000000000000000000000": 1,
"2000000000000000000000000000000000000000000000000": 2,
}
buf := []byte("1000000000000000000000000000000000000000000000000")
if x := m[string(buf)]; x != 1 {
t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
}
buf[0] = '2'
if x := m[string(buf)]; x != 2 {
t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
}
var x int
n := testing.AllocsPerRun(100, func() {
x += m[string(buf)]
})
if n != 0 {
t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
}
x = 0
n = testing.AllocsPerRun(100, func() {
y, ok := m[string(buf)]
if !ok {
panic("!ok")
}
x += y
})
if n != 0 {
t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
}
}
func TestMapLargeKeyNoPointer(t *testing.T) {
const (
I = 1000
N = 64
)
type T [N]int
m := make(map[T]int)
for i := 0; i < I; i++ {
var v T
for j := 0; j < N; j++ {
v[j] = i + j
}
m[v] = i
}
runtime.GC()
for i := 0; i < I; i++ {
var v T
for j := 0; j < N; j++ {
v[j] = i + j
}
if m[v] != i {
t.Fatalf("corrupted map: want %+v, got %+v", i, m[v])
}
}
}
func TestMapLargeValNoPointer(t *testing.T) {
const (
I = 1000
N = 64
)
type T [N]int
m := make(map[int]T)
for i := 0; i < I; i++ {
var v T
for j := 0; j < N; j++ {
v[j] = i + j
}
m[i] = v
}
runtime.GC()
for i := 0; i < I; i++ {
var v T
for j := 0; j < N; j++ {
v[j] = i + j
}
v1 := m[i]
for j := 0; j < N; j++ {
if v1[j] != v[j] {
t.Fatalf("corrupted map: want %+v, got %+v", v, v1)
}
}
}
}
// Test that making a map with a large or invalid hint
// doesn't panic. (Issue 19926).
func TestIgnoreBogusMapHint(t *testing.T) {
for _, hint := range []int64{-1, 1 << 62} {
_ = make(map[int]int, hint)
}
}
const bs = abi.MapBucketCount
// belowOverflow should be a pretty-full pair of buckets;
// atOverflow is 1/8 bs larger = 13/8 buckets or two buckets
// that are 13/16 full each, which is the overflow boundary.
// Adding one to that should ensure overflow to the next higher size.
const (
belowOverflow = bs * 3 / 2 // 1.5 bs = 2 buckets @ 75%
atOverflow = belowOverflow + bs/8 // 2 buckets at 13/16 fill.
)
var mapBucketTests = [...]struct {
n int // n is the number of map elements
noescape int // number of expected buckets for non-escaping map
escape int // number of expected buckets for escaping map
}{
{-(1 << 30), 1, 1},
{-1, 1, 1},
{0, 1, 1},
{1, 1, 1},
{bs, 1, 1},
{bs + 1, 2, 2},
{belowOverflow, 2, 2}, // 1.5 bs = 2 buckets @ 75%
{atOverflow + 1, 4, 4}, // 13/8 bs + 1 == overflow to 4
{2 * belowOverflow, 4, 4}, // 3 bs = 4 buckets @75%
{2*atOverflow + 1, 8, 8}, // 13/4 bs + 1 = overflow to 8
{4 * belowOverflow, 8, 8}, // 6 bs = 8 buckets @ 75%
{4*atOverflow + 1, 16, 16}, // 13/2 bs + 1 = overflow to 16
}
func TestMapBuckets(t *testing.T) {
// Test that maps of different sizes have the right number of buckets.
// Non-escaping maps with small buckets (like map[int]int) never
// have a nil bucket pointer due to starting with preallocated buckets
// on the stack. Escaping maps start with a non-nil bucket pointer if
// hint size is above bucketCnt and thereby have more than one bucket.
// These tests depend on bucketCnt and loadFactor* in map.go.
t.Run("mapliteral", func(t *testing.T) {
for _, tt := range mapBucketTests {
localMap := map[int]int{}
if runtime.MapBucketsPointerIsNil(localMap) {
t.Errorf("no escape: buckets pointer is nil for non-escaping map")
}
for i := 0; i < tt.n; i++ {
localMap[i] = i
}
if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
}
escapingMap := runtime.Escape(map[int]int{})
if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
}
for i := 0; i < tt.n; i++ {
escapingMap[i] = i
}
if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got)
}
}
})
t.Run("nohint", func(t *testing.T) {
for _, tt := range mapBucketTests {
localMap := make(map[int]int)
if runtime.MapBucketsPointerIsNil(localMap) {
t.Errorf("no escape: buckets pointer is nil for non-escaping map")
}
for i := 0; i < tt.n; i++ {
localMap[i] = i
}
if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
}
escapingMap := runtime.Escape(make(map[int]int))
if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
}
for i := 0; i < tt.n; i++ {
escapingMap[i] = i
}
if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
}
}
})
t.Run("makemap", func(t *testing.T) {
for _, tt := range mapBucketTests {
localMap := make(map[int]int, tt.n)
if runtime.MapBucketsPointerIsNil(localMap) {
t.Errorf("no escape: buckets pointer is nil for non-escaping map")
}
for i := 0; i < tt.n; i++ {
localMap[i] = i
}
if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
}
escapingMap := runtime.Escape(make(map[int]int, tt.n))
if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
}
for i := 0; i < tt.n; i++ {
escapingMap[i] = i
}
if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
}
}
})
t.Run("makemap64", func(t *testing.T) {
for _, tt := range mapBucketTests {
localMap := make(map[int]int, int64(tt.n))
if runtime.MapBucketsPointerIsNil(localMap) {
t.Errorf("no escape: buckets pointer is nil for non-escaping map")
}
for i := 0; i < tt.n; i++ {
localMap[i] = i
}
if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
}
escapingMap := runtime.Escape(make(map[int]int, tt.n))
if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
}
for i := 0; i < tt.n; i++ {
escapingMap[i] = i
}
if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
}
}
})
}
func benchmarkMapPop(b *testing.B, n int) {
m := map[int]int{}
for i := 0; i < b.N; i++ {
for j := 0; j < n; j++ {
m[j] = j
}
for j := 0; j < n; j++ {
// Use iterator to pop an element.
// We want this to be fast, see issue 8412.
for k := range m {
delete(m, k)
break
}
}
}
}
func BenchmarkMapPop100(b *testing.B) { benchmarkMapPop(b, 100) }
func BenchmarkMapPop1000(b *testing.B) { benchmarkMapPop(b, 1000) }
func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) }
var testNonEscapingMapVariable int = 8
func TestNonEscapingMap(t *testing.T) {
n := testing.AllocsPerRun(1000, func() {
m := map[int]int{}
m[0] = 0
})
if n != 0 {
t.Fatalf("mapliteral: want 0 allocs, got %v", n)
}
n = testing.AllocsPerRun(1000, func() {
m := make(map[int]int)
m[0] = 0
})
if n != 0 {
t.Fatalf("no hint: want 0 allocs, got %v", n)
}
n = testing.AllocsPerRun(1000, func() {
m := make(map[int]int, 8)
m[0] = 0
})
if n != 0 {
t.Fatalf("with small hint: want 0 allocs, got %v", n)
}
n = testing.AllocsPerRun(1000, func() {
m := make(map[int]int, testNonEscapingMapVariable)
m[0] = 0
})
if n != 0 {
t.Fatalf("with variable hint: want 0 allocs, got %v", n)
}
}
func benchmarkMapAssignInt32(b *testing.B, n int) {
a := make(map[int32]int)
for i := 0; i < b.N; i++ {
a[int32(i&(n-1))] = i
}
}
func benchmarkMapOperatorAssignInt32(b *testing.B, n int) {
a := make(map[int32]int)
for i := 0; i < b.N; i++ {
a[int32(i&(n-1))] += i
}
}
func benchmarkMapAppendAssignInt32(b *testing.B, n int) {
a := make(map[int32][]int)
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
key := int32(i & (n - 1))
a[key] = append(a[key], i)
}
}
func benchmarkMapDeleteInt32(b *testing.B, n int) {
a := make(map[int32]int, n)
b.ResetTimer()
for i := 0; i < b.N; i++ {
if len(a) == 0 {
b.StopTimer()
for j := i; j < i+n; j++ {
a[int32(j)] = j
}
b.StartTimer()
}
delete(a, int32(i))
}
}
func benchmarkMapAssignInt64(b *testing.B, n int) {
a := make(map[int64]int)
for i := 0; i < b.N; i++ {
a[int64(i&(n-1))] = i
}
}
func benchmarkMapOperatorAssignInt64(b *testing.B, n int) {
a := make(map[int64]int)
for i := 0; i < b.N; i++ {
a[int64(i&(n-1))] += i
}
}
func benchmarkMapAppendAssignInt64(b *testing.B, n int) {
a := make(map[int64][]int)
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
key := int64(i & (n - 1))
a[key] = append(a[key], i)
}
}
func benchmarkMapDeleteInt64(b *testing.B, n int) {
a := make(map[int64]int, n)
b.ResetTimer()
for i := 0; i < b.N; i++ {
if len(a) == 0 {
b.StopTimer()
for j := i; j < i+n; j++ {
a[int64(j)] = j
}
b.StartTimer()
}
delete(a, int64(i))
}
}
func benchmarkMapAssignStr(b *testing.B, n int) {
k := make([]string, n)
for i := 0; i < len(k); i++ {
k[i] = strconv.Itoa(i)
}
b.ResetTimer()
a := make(map[string]int)
for i := 0; i < b.N; i++ {
a[k[i&(n-1)]] = i
}
}
func benchmarkMapOperatorAssignStr(b *testing.B, n int) {
k := make([]string, n)
for i := 0; i < len(k); i++ {
k[i] = strconv.Itoa(i)
}
b.ResetTimer()
a := make(map[string]string)
for i := 0; i < b.N; i++ {
key := k[i&(n-1)]
a[key] += key
}
}
func benchmarkMapAppendAssignStr(b *testing.B, n int) {
k := make([]string, n)
for i := 0; i < len(k); i++ {
k[i] = strconv.Itoa(i)
}
a := make(map[string][]string)
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
key := k[i&(n-1)]
a[key] = append(a[key], key)
}
}
func benchmarkMapDeleteStr(b *testing.B, n int) {
i2s := make([]string, n)
for i := 0; i < n; i++ {
i2s[i] = strconv.Itoa(i)
}
a := make(map[string]int, n)
b.ResetTimer()
k := 0
for i := 0; i < b.N; i++ {
if len(a) == 0 {
b.StopTimer()
for j := 0; j < n; j++ {
a[i2s[j]] = j
}
k = i
b.StartTimer()
}
delete(a, i2s[i-k])
}
}
func benchmarkMapDeletePointer(b *testing.B, n int) {
i2p := make([]*int, n)
for i := 0; i < n; i++ {
i2p[i] = new(int)
}
a := make(map[*int]int, n)
b.ResetTimer()
k := 0
for i := 0; i < b.N; i++ {
if len(a) == 0 {
b.StopTimer()
for j := 0; j < n; j++ {
a[i2p[j]] = j
}
k = i
b.StartTimer()
}
delete(a, i2p[i-k])
}
}
func runWith(f func(*testing.B, int), v ...int) func(*testing.B) {
return func(b *testing.B) {
for _, n := range v {
b.Run(strconv.Itoa(n), func(b *testing.B) { f(b, n) })
}
}
}
func BenchmarkMapAssign(b *testing.B) {
b.Run("Int32", runWith(benchmarkMapAssignInt32, 1<<8, 1<<16))
b.Run("Int64", runWith(benchmarkMapAssignInt64, 1<<8, 1<<16))
b.Run("Str", runWith(benchmarkMapAssignStr, 1<<8, 1<<16))
}
func BenchmarkMapOperatorAssign(b *testing.B) {
b.Run("Int32", runWith(benchmarkMapOperatorAssignInt32, 1<<8, 1<<16))
b.Run("Int64", runWith(benchmarkMapOperatorAssignInt64, 1<<8, 1<<16))
b.Run("Str", runWith(benchmarkMapOperatorAssignStr, 1<<8, 1<<16))
}
func BenchmarkMapAppendAssign(b *testing.B) {
b.Run("Int32", runWith(benchmarkMapAppendAssignInt32, 1<<8, 1<<16))
b.Run("Int64", runWith(benchmarkMapAppendAssignInt64, 1<<8, 1<<16))
b.Run("Str", runWith(benchmarkMapAppendAssignStr, 1<<8, 1<<16))
}
func BenchmarkMapDelete(b *testing.B) {
b.Run("Int32", runWith(benchmarkMapDeleteInt32, 100, 1000, 10000))
b.Run("Int64", runWith(benchmarkMapDeleteInt64, 100, 1000, 10000))
b.Run("Str", runWith(benchmarkMapDeleteStr, 100, 1000, 10000))
b.Run("Pointer", runWith(benchmarkMapDeletePointer, 100, 1000, 10000))
}
func TestDeferDeleteSlow(t *testing.T) {
ks := []complex128{0, 1, 2, 3}
m := make(map[any]int)
for i, k := range ks {
m[k] = i
}
if len(m) != len(ks) {
t.Errorf("want %d elements, got %d", len(ks), len(m))
}
func() {
for _, k := range ks {
defer delete(m, k)
}
}()
if len(m) != 0 {
t.Errorf("want 0 elements, got %d", len(m))
}
}
// TestIncrementAfterDeleteValueInt and other test Issue 25936.
// Value types int, int32, int64 are affected. Value type string
// works as expected.
func TestIncrementAfterDeleteValueInt(t *testing.T) {
const key1 = 12
const key2 = 13
m := make(map[int]int)
m[key1] = 99
delete(m, key1)
m[key2]++
if n2 := m[key2]; n2 != 1 {
t.Errorf("incremented 0 to %d", n2)
}
}
func TestIncrementAfterDeleteValueInt32(t *testing.T) {
const key1 = 12
const key2 = 13
m := make(map[int]int32)
m[key1] = 99
delete(m, key1)
m[key2]++
if n2 := m[key2]; n2 != 1 {
t.Errorf("incremented 0 to %d", n2)
}
}
func TestIncrementAfterDeleteValueInt64(t *testing.T) {
const key1 = 12
const key2 = 13
m := make(map[int]int64)
m[key1] = 99
delete(m, key1)
m[key2]++
if n2 := m[key2]; n2 != 1 {
t.Errorf("incremented 0 to %d", n2)
}
}
func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) {
const key1 = ""
const key2 = "x"
m := make(map[string]int)
m[key1] = 99
delete(m, key1)
m[key2] += 1
if n2 := m[key2]; n2 != 1 {
t.Errorf("incremented 0 to %d", n2)
}
}
func TestIncrementAfterDeleteKeyValueString(t *testing.T) {
const key1 = ""
const key2 = "x"
m := make(map[string]string)
m[key1] = "99"
delete(m, key1)
m[key2] += "1"
if n2 := m[key2]; n2 != "1" {
t.Errorf("appended '1' to empty (nil) string, got %s", n2)
}
}
// TestIncrementAfterBulkClearKeyStringValueInt tests that map bulk
// deletion (mapclear) still works as expected. Note that it was not
// affected by Issue 25936.
func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) {
const key1 = ""
const key2 = "x"
m := make(map[string]int)
m[key1] = 99
for k := range m {
delete(m, k)
}
m[key2]++
if n2 := m[key2]; n2 != 1 {
t.Errorf("incremented 0 to %d", n2)
}
}
func TestMapTombstones(t *testing.T) {
m := map[int]int{}
const N = 10000
// Fill a map.
for i := 0; i < N; i++ {
m[i] = i
}
runtime.MapTombstoneCheck(m)
// Delete half of the entries.
for i := 0; i < N; i += 2 {
delete(m, i)
}
runtime.MapTombstoneCheck(m)
// Add new entries to fill in holes.
for i := N; i < 3*N/2; i++ {
m[i] = i
}
runtime.MapTombstoneCheck(m)
// Delete everything.
for i := 0; i < 3*N/2; i++ {
delete(m, i)
}
runtime.MapTombstoneCheck(m)
}
type canString int
func (c canString) String() string {
return fmt.Sprintf("%d", int(c))
}
func TestMapInterfaceKey(t *testing.T) {
// Test all the special cases in runtime.typehash.
type GrabBag struct {
f32 float32
f64 float64
c64 complex64
c128 complex128
s string
i0 any
i1 interface {
String() string
}
a [4]string
}
m := map[any]bool{}
// Put a bunch of data in m, so that a bad hash is likely to
// lead to a bad bucket, which will lead to a missed lookup.
for i := 0; i < 1000; i++ {
m[i] = true
}
m[GrabBag{f32: 1.0}] = true
if !m[GrabBag{f32: 1.0}] {
panic("f32 not found")
}
m[GrabBag{f64: 1.0}] = true
if !m[GrabBag{f64: 1.0}] {
panic("f64 not found")
}
m[GrabBag{c64: 1.0i}] = true
if !m[GrabBag{c64: 1.0i}] {
panic("c64 not found")
}
m[GrabBag{c128: 1.0i}] = true
if !m[GrabBag{c128: 1.0i}] {
panic("c128 not found")
}
m[GrabBag{s: "foo"}] = true
if !m[GrabBag{s: "foo"}] {
panic("string not found")
}
m[GrabBag{i0: "foo"}] = true
if !m[GrabBag{i0: "foo"}] {
panic("interface{} not found")
}
m[GrabBag{i1: canString(5)}] = true
if !m[GrabBag{i1: canString(5)}] {
panic("interface{String() string} not found")
}
m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true
if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] {
panic("array not found")
}
}
type panicStructKey struct {
sli []int
}
func (p panicStructKey) String() string {
return "panic"
}
type structKey struct {
}
func (structKey) String() string {
return "structKey"
}
func TestEmptyMapWithInterfaceKey(t *testing.T) {
var (
b bool
i int
i8 int8
i16 int16
i32 int32
i64 int64
ui uint
ui8 uint8
ui16 uint16
ui32 uint32
ui64 uint64
uipt uintptr
f32 float32
f64 float64
c64 complex64
c128 complex128
a [4]string
s string
p *int
up unsafe.Pointer
ch chan int
i0 any
i1 interface {
String() string
}
structKey structKey
i0Panic any = []int{}
i1Panic interface {
String() string
} = panicStructKey{}
panicStructKey = panicStructKey{}
sli []int
me = map[any]struct{}{}
mi = map[interface {
String() string
}]struct{}{}
)
mustNotPanic := func(f func()) {
f()
}
mustPanic := func(f func()) {
defer func() {
r := recover()
if r == nil {
t.Errorf("didn't panic")
}
}()
f()
}
mustNotPanic(func() {
_ = me[b]
})
mustNotPanic(func() {
_ = me[i]
})
mustNotPanic(func() {
_ = me[i8]
})
mustNotPanic(func() {
_ = me[i16]
})
mustNotPanic(func() {
_ = me[i32]
})
mustNotPanic(func() {
_ = me[i64]
})
mustNotPanic(func() {
_ = me[ui]
})
mustNotPanic(func() {
_ = me[ui8]
})
mustNotPanic(func() {
_ = me[ui16]
})
mustNotPanic(func() {
_ = me[ui32]
})
mustNotPanic(func() {
_ = me[ui64]
})
mustNotPanic(func() {
_ = me[uipt]
})
mustNotPanic(func() {
_ = me[f32]
})
mustNotPanic(func() {
_ = me[f64]
})
mustNotPanic(func() {
_ = me[c64]
})
mustNotPanic(func() {
_ = me[c128]
})
mustNotPanic(func() {
_ = me[a]
})
mustNotPanic(func() {
_ = me[s]
})
mustNotPanic(func() {
_ = me[p]
})
mustNotPanic(func() {
_ = me[up]
})
mustNotPanic(func() {
_ = me[ch]
})
mustNotPanic(func() {
_ = me[i0]
})
mustNotPanic(func() {
_ = me[i1]
})
mustNotPanic(func() {
_ = me[structKey]
})
mustPanic(func() {
_ = me[i0Panic]
})
mustPanic(func() {
_ = me[i1Panic]
})
mustPanic(func() {
_ = me[panicStructKey]
})
mustPanic(func() {
_ = me[sli]
})
mustPanic(func() {
_ = me[me]
})
mustNotPanic(func() {
_ = mi[structKey]
})
mustPanic(func() {
_ = mi[panicStructKey]
})
}
func TestLoadFactor(t *testing.T) {
for b := uint8(0); b < 20; b++ {
count := 13 * (1 << b) / 2 // 6.5
if b == 0 {
count = 8
}
if runtime.OverLoadFactor(count, b) {
t.Errorf("OverLoadFactor(%d,%d)=true, want false", count, b)
}
if !runtime.OverLoadFactor(count+1, b) {
t.Errorf("OverLoadFactor(%d,%d)=false, want true", count+1, b)
}
}
}
func TestMapKeys(t *testing.T) {
type key struct {
s string
pad [128]byte // sizeof(key) > abi.MapMaxKeyBytes
}
m := map[key]int{{s: "a"}: 1, {s: "b"}: 2}
keys := make([]key, 0, len(m))
runtime.MapKeys(m, unsafe.Pointer(&keys))
for _, k := range keys {
if len(k.s) != 1 {
t.Errorf("len(k.s) == %d, want 1", len(k.s))
}
}
}
func TestMapValues(t *testing.T) {
type val struct {
s string
pad [128]byte // sizeof(val) > abi.MapMaxElemBytes
}
m := map[int]val{1: {s: "a"}, 2: {s: "b"}}
vals := make([]val, 0, len(m))
runtime.MapValues(m, unsafe.Pointer(&vals))
for _, v := range vals {
if len(v.s) != 1 {
t.Errorf("len(v.s) == %d, want 1", len(v.s))
}
}
}
func computeHash() uintptr {
var v struct{}
return runtime.MemHash(unsafe.Pointer(&v), 0, unsafe.Sizeof(v))
}
func subprocessHash(t *testing.T, env string) uintptr {
t.Helper()
cmd := testenv.CleanCmdEnv(testenv.Command(t, os.Args[0], "-test.run=^TestMemHashGlobalSeed$"))
cmd.Env = append(cmd.Env, "GO_TEST_SUBPROCESS_HASH=1")
if env != "" {
cmd.Env = append(cmd.Env, env)
}
out, err := cmd.Output()
if err != nil {
t.Fatalf("cmd.Output got err %v want nil", err)
}
s := strings.TrimSpace(string(out))
h, err := strconv.ParseUint(s, 10, 64)
if err != nil {
t.Fatalf("Parse output %q got err %v want nil", s, err)
}
return uintptr(h)
}
// memhash has unique per-process seeds, so hashes should differ across
// processes.
//
// Regression test for https://go.dev/issue/66885.
func TestMemHashGlobalSeed(t *testing.T) {
if os.Getenv("GO_TEST_SUBPROCESS_HASH") != "" {
fmt.Println(computeHash())
os.Exit(0)
return
}
testenv.MustHaveExec(t)
// aeshash and memhashFallback use separate per-process seeds, so test
// both.
t.Run("aes", func(t *testing.T) {
if !*runtime.UseAeshash {
t.Skip("No AES")
}
h1 := subprocessHash(t, "")
t.Logf("%d", h1)
h2 := subprocessHash(t, "")
t.Logf("%d", h2)
h3 := subprocessHash(t, "")
t.Logf("%d", h3)
if h1 == h2 && h2 == h3 {
t.Errorf("got duplicate hash %d want unique", h1)
}
})
t.Run("noaes", func(t *testing.T) {
env := ""
if *runtime.UseAeshash {
env = "GODEBUG=cpu.aes=off"
}
h1 := subprocessHash(t, env)
t.Logf("%d", h1)
h2 := subprocessHash(t, env)
t.Logf("%d", h2)
h3 := subprocessHash(t, env)
t.Logf("%d", h3)
if h1 == h2 && h2 == h3 {
t.Errorf("got duplicate hash %d want unique", h1)
}
})
}