Source file src/runtime/map_test.go

Documentation: runtime

		 1  // Copyright 2013 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  package runtime_test
		 6  
		 7  import (
		 8  	"fmt"
		 9  	"math"
		10  	"reflect"
		11  	"runtime"
		12  	"runtime/internal/sys"
		13  	"sort"
		14  	"strconv"
		15  	"strings"
		16  	"sync"
		17  	"testing"
		18  )
		19  
		20  func TestHmapSize(t *testing.T) {
		21  	// The structure of hmap is defined in runtime/map.go
		22  	// and in cmd/compile/internal/gc/reflect.go and must be in sync.
		23  	// The size of hmap should be 48 bytes on 64 bit and 28 bytes on 32 bit platforms.
		24  	var hmapSize = uintptr(8 + 5*sys.PtrSize)
		25  	if runtime.RuntimeHmapSize != hmapSize {
		26  		t.Errorf("sizeof(runtime.hmap{})==%d, want %d", runtime.RuntimeHmapSize, hmapSize)
		27  	}
		28  
		29  }
		30  
		31  // negative zero is a good test because:
		32  //	1) 0 and -0 are equal, yet have distinct representations.
		33  //	2) 0 is represented as all zeros, -0 isn't.
		34  // I'm not sure the language spec actually requires this behavior,
		35  // but it's what the current map implementation does.
		36  func TestNegativeZero(t *testing.T) {
		37  	m := make(map[float64]bool, 0)
		38  
		39  	m[+0.0] = true
		40  	m[math.Copysign(0.0, -1.0)] = true // should overwrite +0 entry
		41  
		42  	if len(m) != 1 {
		43  		t.Error("length wrong")
		44  	}
		45  
		46  	for k := range m {
		47  		if math.Copysign(1.0, k) > 0 {
		48  			t.Error("wrong sign")
		49  		}
		50  	}
		51  
		52  	m = make(map[float64]bool, 0)
		53  	m[math.Copysign(0.0, -1.0)] = true
		54  	m[+0.0] = true // should overwrite -0.0 entry
		55  
		56  	if len(m) != 1 {
		57  		t.Error("length wrong")
		58  	}
		59  
		60  	for k := range m {
		61  		if math.Copysign(1.0, k) < 0 {
		62  			t.Error("wrong sign")
		63  		}
		64  	}
		65  }
		66  
		67  func testMapNan(t *testing.T, m map[float64]int) {
		68  	if len(m) != 3 {
		69  		t.Error("length wrong")
		70  	}
		71  	s := 0
		72  	for k, v := range m {
		73  		if k == k {
		74  			t.Error("nan disappeared")
		75  		}
		76  		if (v & (v - 1)) != 0 {
		77  			t.Error("value wrong")
		78  		}
		79  		s |= v
		80  	}
		81  	if s != 7 {
		82  		t.Error("values wrong")
		83  	}
		84  }
		85  
		86  // nan is a good test because nan != nan, and nan has
		87  // a randomized hash value.
		88  func TestMapAssignmentNan(t *testing.T) {
		89  	m := make(map[float64]int, 0)
		90  	nan := math.NaN()
		91  
		92  	// Test assignment.
		93  	m[nan] = 1
		94  	m[nan] = 2
		95  	m[nan] = 4
		96  	testMapNan(t, m)
		97  }
		98  
		99  // nan is a good test because nan != nan, and nan has
	 100  // a randomized hash value.
	 101  func TestMapOperatorAssignmentNan(t *testing.T) {
	 102  	m := make(map[float64]int, 0)
	 103  	nan := math.NaN()
	 104  
	 105  	// Test assignment operations.
	 106  	m[nan] += 1
	 107  	m[nan] += 2
	 108  	m[nan] += 4
	 109  	testMapNan(t, m)
	 110  }
	 111  
	 112  func TestMapOperatorAssignment(t *testing.T) {
	 113  	m := make(map[int]int, 0)
	 114  
	 115  	// "m[k] op= x" is rewritten into "m[k] = m[k] op x"
	 116  	// differently when op is / or % than when it isn't.
	 117  	// Simple test to make sure they all work as expected.
	 118  	m[0] = 12345
	 119  	m[0] += 67890
	 120  	m[0] /= 123
	 121  	m[0] %= 456
	 122  
	 123  	const want = (12345 + 67890) / 123 % 456
	 124  	if got := m[0]; got != want {
	 125  		t.Errorf("got %d, want %d", got, want)
	 126  	}
	 127  }
	 128  
	 129  var sinkAppend bool
	 130  
	 131  func TestMapAppendAssignment(t *testing.T) {
	 132  	m := make(map[int][]int, 0)
	 133  
	 134  	m[0] = nil
	 135  	m[0] = append(m[0], 12345)
	 136  	m[0] = append(m[0], 67890)
	 137  	sinkAppend, m[0] = !sinkAppend, append(m[0], 123, 456)
	 138  	a := []int{7, 8, 9, 0}
	 139  	m[0] = append(m[0], a...)
	 140  
	 141  	want := []int{12345, 67890, 123, 456, 7, 8, 9, 0}
	 142  	if got := m[0]; !reflect.DeepEqual(got, want) {
	 143  		t.Errorf("got %v, want %v", got, want)
	 144  	}
	 145  }
	 146  
	 147  // Maps aren't actually copied on assignment.
	 148  func TestAlias(t *testing.T) {
	 149  	m := make(map[int]int, 0)
	 150  	m[0] = 5
	 151  	n := m
	 152  	n[0] = 6
	 153  	if m[0] != 6 {
	 154  		t.Error("alias didn't work")
	 155  	}
	 156  }
	 157  
	 158  func TestGrowWithNaN(t *testing.T) {
	 159  	m := make(map[float64]int, 4)
	 160  	nan := math.NaN()
	 161  
	 162  	// Use both assignment and assignment operations as they may
	 163  	// behave differently.
	 164  	m[nan] = 1
	 165  	m[nan] = 2
	 166  	m[nan] += 4
	 167  
	 168  	cnt := 0
	 169  	s := 0
	 170  	growflag := true
	 171  	for k, v := range m {
	 172  		if growflag {
	 173  			// force a hashtable resize
	 174  			for i := 0; i < 50; i++ {
	 175  				m[float64(i)] = i
	 176  			}
	 177  			for i := 50; i < 100; i++ {
	 178  				m[float64(i)] += i
	 179  			}
	 180  			growflag = false
	 181  		}
	 182  		if k != k {
	 183  			cnt++
	 184  			s |= v
	 185  		}
	 186  	}
	 187  	if cnt != 3 {
	 188  		t.Error("NaN keys lost during grow")
	 189  	}
	 190  	if s != 7 {
	 191  		t.Error("NaN values lost during grow")
	 192  	}
	 193  }
	 194  
	 195  type FloatInt struct {
	 196  	x float64
	 197  	y int
	 198  }
	 199  
	 200  func TestGrowWithNegativeZero(t *testing.T) {
	 201  	negzero := math.Copysign(0.0, -1.0)
	 202  	m := make(map[FloatInt]int, 4)
	 203  	m[FloatInt{0.0, 0}] = 1
	 204  	m[FloatInt{0.0, 1}] += 2
	 205  	m[FloatInt{0.0, 2}] += 4
	 206  	m[FloatInt{0.0, 3}] = 8
	 207  	growflag := true
	 208  	s := 0
	 209  	cnt := 0
	 210  	negcnt := 0
	 211  	// The first iteration should return the +0 key.
	 212  	// The subsequent iterations should return the -0 key.
	 213  	// I'm not really sure this is required by the spec,
	 214  	// but it makes sense.
	 215  	// TODO: are we allowed to get the first entry returned again???
	 216  	for k, v := range m {
	 217  		if v == 0 {
	 218  			continue
	 219  		} // ignore entries added to grow table
	 220  		cnt++
	 221  		if math.Copysign(1.0, k.x) < 0 {
	 222  			if v&16 == 0 {
	 223  				t.Error("key/value not updated together 1")
	 224  			}
	 225  			negcnt++
	 226  			s |= v & 15
	 227  		} else {
	 228  			if v&16 == 16 {
	 229  				t.Error("key/value not updated together 2", k, v)
	 230  			}
	 231  			s |= v
	 232  		}
	 233  		if growflag {
	 234  			// force a hashtable resize
	 235  			for i := 0; i < 100; i++ {
	 236  				m[FloatInt{3.0, i}] = 0
	 237  			}
	 238  			// then change all the entries
	 239  			// to negative zero
	 240  			m[FloatInt{negzero, 0}] = 1 | 16
	 241  			m[FloatInt{negzero, 1}] = 2 | 16
	 242  			m[FloatInt{negzero, 2}] = 4 | 16
	 243  			m[FloatInt{negzero, 3}] = 8 | 16
	 244  			growflag = false
	 245  		}
	 246  	}
	 247  	if s != 15 {
	 248  		t.Error("entry missing", s)
	 249  	}
	 250  	if cnt != 4 {
	 251  		t.Error("wrong number of entries returned by iterator", cnt)
	 252  	}
	 253  	if negcnt != 3 {
	 254  		t.Error("update to negzero missed by iteration", negcnt)
	 255  	}
	 256  }
	 257  
	 258  func TestIterGrowAndDelete(t *testing.T) {
	 259  	m := make(map[int]int, 4)
	 260  	for i := 0; i < 100; i++ {
	 261  		m[i] = i
	 262  	}
	 263  	growflag := true
	 264  	for k := range m {
	 265  		if growflag {
	 266  			// grow the table
	 267  			for i := 100; i < 1000; i++ {
	 268  				m[i] = i
	 269  			}
	 270  			// delete all odd keys
	 271  			for i := 1; i < 1000; i += 2 {
	 272  				delete(m, i)
	 273  			}
	 274  			growflag = false
	 275  		} else {
	 276  			if k&1 == 1 {
	 277  				t.Error("odd value returned")
	 278  			}
	 279  		}
	 280  	}
	 281  }
	 282  
	 283  // make sure old bucket arrays don't get GCd while
	 284  // an iterator is still using them.
	 285  func TestIterGrowWithGC(t *testing.T) {
	 286  	m := make(map[int]int, 4)
	 287  	for i := 0; i < 8; i++ {
	 288  		m[i] = i
	 289  	}
	 290  	for i := 8; i < 16; i++ {
	 291  		m[i] += i
	 292  	}
	 293  	growflag := true
	 294  	bitmask := 0
	 295  	for k := range m {
	 296  		if k < 16 {
	 297  			bitmask |= 1 << uint(k)
	 298  		}
	 299  		if growflag {
	 300  			// grow the table
	 301  			for i := 100; i < 1000; i++ {
	 302  				m[i] = i
	 303  			}
	 304  			// trigger a gc
	 305  			runtime.GC()
	 306  			growflag = false
	 307  		}
	 308  	}
	 309  	if bitmask != 1<<16-1 {
	 310  		t.Error("missing key", bitmask)
	 311  	}
	 312  }
	 313  
	 314  func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
	 315  	t.Parallel()
	 316  	if runtime.GOMAXPROCS(-1) == 1 {
	 317  		defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
	 318  	}
	 319  	numLoop := 10
	 320  	numGrowStep := 250
	 321  	numReader := 16
	 322  	if testing.Short() {
	 323  		numLoop, numGrowStep = 2, 100
	 324  	}
	 325  	for i := 0; i < numLoop; i++ {
	 326  		m := make(map[int]int, 0)
	 327  		for gs := 0; gs < numGrowStep; gs++ {
	 328  			m[gs] = gs
	 329  			var wg sync.WaitGroup
	 330  			wg.Add(numReader * 2)
	 331  			for nr := 0; nr < numReader; nr++ {
	 332  				go func() {
	 333  					defer wg.Done()
	 334  					for range m {
	 335  					}
	 336  				}()
	 337  				go func() {
	 338  					defer wg.Done()
	 339  					for key := 0; key < gs; key++ {
	 340  						_ = m[key]
	 341  					}
	 342  				}()
	 343  				if useReflect {
	 344  					wg.Add(1)
	 345  					go func() {
	 346  						defer wg.Done()
	 347  						mv := reflect.ValueOf(m)
	 348  						keys := mv.MapKeys()
	 349  						for _, k := range keys {
	 350  							mv.MapIndex(k)
	 351  						}
	 352  					}()
	 353  				}
	 354  			}
	 355  			wg.Wait()
	 356  		}
	 357  	}
	 358  }
	 359  
	 360  func TestConcurrentReadsAfterGrowth(t *testing.T) {
	 361  	testConcurrentReadsAfterGrowth(t, false)
	 362  }
	 363  
	 364  func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
	 365  	testConcurrentReadsAfterGrowth(t, true)
	 366  }
	 367  
	 368  func TestBigItems(t *testing.T) {
	 369  	var key [256]string
	 370  	for i := 0; i < 256; i++ {
	 371  		key[i] = "foo"
	 372  	}
	 373  	m := make(map[[256]string][256]string, 4)
	 374  	for i := 0; i < 100; i++ {
	 375  		key[37] = fmt.Sprintf("string%02d", i)
	 376  		m[key] = key
	 377  	}
	 378  	var keys [100]string
	 379  	var values [100]string
	 380  	i := 0
	 381  	for k, v := range m {
	 382  		keys[i] = k[37]
	 383  		values[i] = v[37]
	 384  		i++
	 385  	}
	 386  	sort.Strings(keys[:])
	 387  	sort.Strings(values[:])
	 388  	for i := 0; i < 100; i++ {
	 389  		if keys[i] != fmt.Sprintf("string%02d", i) {
	 390  			t.Errorf("#%d: missing key: %v", i, keys[i])
	 391  		}
	 392  		if values[i] != fmt.Sprintf("string%02d", i) {
	 393  			t.Errorf("#%d: missing value: %v", i, values[i])
	 394  		}
	 395  	}
	 396  }
	 397  
	 398  func TestMapHugeZero(t *testing.T) {
	 399  	type T [4000]byte
	 400  	m := map[int]T{}
	 401  	x := m[0]
	 402  	if x != (T{}) {
	 403  		t.Errorf("map value not zero")
	 404  	}
	 405  	y, ok := m[0]
	 406  	if ok {
	 407  		t.Errorf("map value should be missing")
	 408  	}
	 409  	if y != (T{}) {
	 410  		t.Errorf("map value not zero")
	 411  	}
	 412  }
	 413  
	 414  type empty struct {
	 415  }
	 416  
	 417  func TestEmptyKeyAndValue(t *testing.T) {
	 418  	a := make(map[int]empty, 4)
	 419  	b := make(map[empty]int, 4)
	 420  	c := make(map[empty]empty, 4)
	 421  	a[0] = empty{}
	 422  	b[empty{}] = 0
	 423  	b[empty{}] = 1
	 424  	c[empty{}] = empty{}
	 425  
	 426  	if len(a) != 1 {
	 427  		t.Errorf("empty value insert problem")
	 428  	}
	 429  	if b[empty{}] != 1 {
	 430  		t.Errorf("empty key returned wrong value")
	 431  	}
	 432  }
	 433  
	 434  // Tests a map with a single bucket, with same-lengthed short keys
	 435  // ("quick keys") as well as long keys.
	 436  func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
	 437  	testMapLookups(t, map[string]string{
	 438  		"x":											"x1val",
	 439  		"xx":										 "x2val",
	 440  		"foo":										"fooval",
	 441  		"bar":										"barval", // same key length as "foo"
	 442  		"xxxx":									 "x4val",
	 443  		strings.Repeat("x", 128): "longval1",
	 444  		strings.Repeat("y", 128): "longval2",
	 445  	})
	 446  }
	 447  
	 448  // Tests a map with a single bucket, with all keys having different lengths.
	 449  func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
	 450  	testMapLookups(t, map[string]string{
	 451  		"x":											"x1val",
	 452  		"xx":										 "x2val",
	 453  		"foo":										"fooval",
	 454  		"xxxx":									 "x4val",
	 455  		"xxxxx":									"x5val",
	 456  		"xxxxxx":								 "x6val",
	 457  		strings.Repeat("x", 128): "longval",
	 458  	})
	 459  }
	 460  
	 461  func testMapLookups(t *testing.T, m map[string]string) {
	 462  	for k, v := range m {
	 463  		if m[k] != v {
	 464  			t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
	 465  		}
	 466  	}
	 467  }
	 468  
	 469  // Tests whether the iterator returns the right elements when
	 470  // started in the middle of a grow, when the keys are NaNs.
	 471  func TestMapNanGrowIterator(t *testing.T) {
	 472  	m := make(map[float64]int)
	 473  	nan := math.NaN()
	 474  	const nBuckets = 16
	 475  	// To fill nBuckets buckets takes LOAD * nBuckets keys.
	 476  	nKeys := int(nBuckets * *runtime.HashLoad)
	 477  
	 478  	// Get map to full point with nan keys.
	 479  	for i := 0; i < nKeys; i++ {
	 480  		m[nan] = i
	 481  	}
	 482  	// Trigger grow
	 483  	m[1.0] = 1
	 484  	delete(m, 1.0)
	 485  
	 486  	// Run iterator
	 487  	found := make(map[int]struct{})
	 488  	for _, v := range m {
	 489  		if v != -1 {
	 490  			if _, repeat := found[v]; repeat {
	 491  				t.Fatalf("repeat of value %d", v)
	 492  			}
	 493  			found[v] = struct{}{}
	 494  		}
	 495  		if len(found) == nKeys/2 {
	 496  			// Halfway through iteration, finish grow.
	 497  			for i := 0; i < nBuckets; i++ {
	 498  				delete(m, 1.0)
	 499  			}
	 500  		}
	 501  	}
	 502  	if len(found) != nKeys {
	 503  		t.Fatalf("missing value")
	 504  	}
	 505  }
	 506  
	 507  func TestMapIterOrder(t *testing.T) {
	 508  	for _, n := range [...]int{3, 7, 9, 15} {
	 509  		for i := 0; i < 1000; i++ {
	 510  			// Make m be {0: true, 1: true, ..., n-1: true}.
	 511  			m := make(map[int]bool)
	 512  			for i := 0; i < n; i++ {
	 513  				m[i] = true
	 514  			}
	 515  			// Check that iterating over the map produces at least two different orderings.
	 516  			ord := func() []int {
	 517  				var s []int
	 518  				for key := range m {
	 519  					s = append(s, key)
	 520  				}
	 521  				return s
	 522  			}
	 523  			first := ord()
	 524  			ok := false
	 525  			for try := 0; try < 100; try++ {
	 526  				if !reflect.DeepEqual(first, ord()) {
	 527  					ok = true
	 528  					break
	 529  				}
	 530  			}
	 531  			if !ok {
	 532  				t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
	 533  				break
	 534  			}
	 535  		}
	 536  	}
	 537  }
	 538  
	 539  // Issue 8410
	 540  func TestMapSparseIterOrder(t *testing.T) {
	 541  	// Run several rounds to increase the probability
	 542  	// of failure. One is not enough.
	 543  NextRound:
	 544  	for round := 0; round < 10; round++ {
	 545  		m := make(map[int]bool)
	 546  		// Add 1000 items, remove 980.
	 547  		for i := 0; i < 1000; i++ {
	 548  			m[i] = true
	 549  		}
	 550  		for i := 20; i < 1000; i++ {
	 551  			delete(m, i)
	 552  		}
	 553  
	 554  		var first []int
	 555  		for i := range m {
	 556  			first = append(first, i)
	 557  		}
	 558  
	 559  		// 800 chances to get a different iteration order.
	 560  		// See bug 8736 for why we need so many tries.
	 561  		for n := 0; n < 800; n++ {
	 562  			idx := 0
	 563  			for i := range m {
	 564  				if i != first[idx] {
	 565  					// iteration order changed.
	 566  					continue NextRound
	 567  				}
	 568  				idx++
	 569  			}
	 570  		}
	 571  		t.Fatalf("constant iteration order on round %d: %v", round, first)
	 572  	}
	 573  }
	 574  
	 575  func TestMapStringBytesLookup(t *testing.T) {
	 576  	// Use large string keys to avoid small-allocation coalescing,
	 577  	// which can cause AllocsPerRun to report lower counts than it should.
	 578  	m := map[string]int{
	 579  		"1000000000000000000000000000000000000000000000000": 1,
	 580  		"2000000000000000000000000000000000000000000000000": 2,
	 581  	}
	 582  	buf := []byte("1000000000000000000000000000000000000000000000000")
	 583  	if x := m[string(buf)]; x != 1 {
	 584  		t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
	 585  	}
	 586  	buf[0] = '2'
	 587  	if x := m[string(buf)]; x != 2 {
	 588  		t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
	 589  	}
	 590  
	 591  	var x int
	 592  	n := testing.AllocsPerRun(100, func() {
	 593  		x += m[string(buf)]
	 594  	})
	 595  	if n != 0 {
	 596  		t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
	 597  	}
	 598  
	 599  	x = 0
	 600  	n = testing.AllocsPerRun(100, func() {
	 601  		y, ok := m[string(buf)]
	 602  		if !ok {
	 603  			panic("!ok")
	 604  		}
	 605  		x += y
	 606  	})
	 607  	if n != 0 {
	 608  		t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
	 609  	}
	 610  }
	 611  
	 612  func TestMapLargeKeyNoPointer(t *testing.T) {
	 613  	const (
	 614  		I = 1000
	 615  		N = 64
	 616  	)
	 617  	type T [N]int
	 618  	m := make(map[T]int)
	 619  	for i := 0; i < I; i++ {
	 620  		var v T
	 621  		for j := 0; j < N; j++ {
	 622  			v[j] = i + j
	 623  		}
	 624  		m[v] = i
	 625  	}
	 626  	runtime.GC()
	 627  	for i := 0; i < I; i++ {
	 628  		var v T
	 629  		for j := 0; j < N; j++ {
	 630  			v[j] = i + j
	 631  		}
	 632  		if m[v] != i {
	 633  			t.Fatalf("corrupted map: want %+v, got %+v", i, m[v])
	 634  		}
	 635  	}
	 636  }
	 637  
	 638  func TestMapLargeValNoPointer(t *testing.T) {
	 639  	const (
	 640  		I = 1000
	 641  		N = 64
	 642  	)
	 643  	type T [N]int
	 644  	m := make(map[int]T)
	 645  	for i := 0; i < I; i++ {
	 646  		var v T
	 647  		for j := 0; j < N; j++ {
	 648  			v[j] = i + j
	 649  		}
	 650  		m[i] = v
	 651  	}
	 652  	runtime.GC()
	 653  	for i := 0; i < I; i++ {
	 654  		var v T
	 655  		for j := 0; j < N; j++ {
	 656  			v[j] = i + j
	 657  		}
	 658  		v1 := m[i]
	 659  		for j := 0; j < N; j++ {
	 660  			if v1[j] != v[j] {
	 661  				t.Fatalf("corrupted map: want %+v, got %+v", v, v1)
	 662  			}
	 663  		}
	 664  	}
	 665  }
	 666  
	 667  // Test that making a map with a large or invalid hint
	 668  // doesn't panic. (Issue 19926).
	 669  func TestIgnoreBogusMapHint(t *testing.T) {
	 670  	for _, hint := range []int64{-1, 1 << 62} {
	 671  		_ = make(map[int]int, hint)
	 672  	}
	 673  }
	 674  
	 675  var mapSink map[int]int
	 676  
	 677  var mapBucketTests = [...]struct {
	 678  	n				int // n is the number of map elements
	 679  	noescape int // number of expected buckets for non-escaping map
	 680  	escape	 int // number of expected buckets for escaping map
	 681  }{
	 682  	{-(1 << 30), 1, 1},
	 683  	{-1, 1, 1},
	 684  	{0, 1, 1},
	 685  	{1, 1, 1},
	 686  	{8, 1, 1},
	 687  	{9, 2, 2},
	 688  	{13, 2, 2},
	 689  	{14, 4, 4},
	 690  	{26, 4, 4},
	 691  }
	 692  
	 693  func TestMapBuckets(t *testing.T) {
	 694  	// Test that maps of different sizes have the right number of buckets.
	 695  	// Non-escaping maps with small buckets (like map[int]int) never
	 696  	// have a nil bucket pointer due to starting with preallocated buckets
	 697  	// on the stack. Escaping maps start with a non-nil bucket pointer if
	 698  	// hint size is above bucketCnt and thereby have more than one bucket.
	 699  	// These tests depend on bucketCnt and loadFactor* in map.go.
	 700  	t.Run("mapliteral", func(t *testing.T) {
	 701  		for _, tt := range mapBucketTests {
	 702  			localMap := map[int]int{}
	 703  			if runtime.MapBucketsPointerIsNil(localMap) {
	 704  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
	 705  			}
	 706  			for i := 0; i < tt.n; i++ {
	 707  				localMap[i] = i
	 708  			}
	 709  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
	 710  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
	 711  			}
	 712  			escapingMap := map[int]int{}
	 713  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
	 714  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
	 715  			}
	 716  			for i := 0; i < tt.n; i++ {
	 717  				escapingMap[i] = i
	 718  			}
	 719  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
	 720  				t.Errorf("escape n=%d want %d buckets, got %d", tt.n, tt.escape, got)
	 721  			}
	 722  			mapSink = escapingMap
	 723  		}
	 724  	})
	 725  	t.Run("nohint", func(t *testing.T) {
	 726  		for _, tt := range mapBucketTests {
	 727  			localMap := make(map[int]int)
	 728  			if runtime.MapBucketsPointerIsNil(localMap) {
	 729  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
	 730  			}
	 731  			for i := 0; i < tt.n; i++ {
	 732  				localMap[i] = i
	 733  			}
	 734  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
	 735  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
	 736  			}
	 737  			escapingMap := make(map[int]int)
	 738  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
	 739  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
	 740  			}
	 741  			for i := 0; i < tt.n; i++ {
	 742  				escapingMap[i] = i
	 743  			}
	 744  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
	 745  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
	 746  			}
	 747  			mapSink = escapingMap
	 748  		}
	 749  	})
	 750  	t.Run("makemap", func(t *testing.T) {
	 751  		for _, tt := range mapBucketTests {
	 752  			localMap := make(map[int]int, tt.n)
	 753  			if runtime.MapBucketsPointerIsNil(localMap) {
	 754  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
	 755  			}
	 756  			for i := 0; i < tt.n; i++ {
	 757  				localMap[i] = i
	 758  			}
	 759  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
	 760  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
	 761  			}
	 762  			escapingMap := make(map[int]int, tt.n)
	 763  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
	 764  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
	 765  			}
	 766  			for i := 0; i < tt.n; i++ {
	 767  				escapingMap[i] = i
	 768  			}
	 769  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
	 770  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
	 771  			}
	 772  			mapSink = escapingMap
	 773  		}
	 774  	})
	 775  	t.Run("makemap64", func(t *testing.T) {
	 776  		for _, tt := range mapBucketTests {
	 777  			localMap := make(map[int]int, int64(tt.n))
	 778  			if runtime.MapBucketsPointerIsNil(localMap) {
	 779  				t.Errorf("no escape: buckets pointer is nil for non-escaping map")
	 780  			}
	 781  			for i := 0; i < tt.n; i++ {
	 782  				localMap[i] = i
	 783  			}
	 784  			if got := runtime.MapBucketsCount(localMap); got != tt.noescape {
	 785  				t.Errorf("no escape: n=%d want %d buckets, got %d", tt.n, tt.noescape, got)
	 786  			}
	 787  			escapingMap := make(map[int]int, tt.n)
	 788  			if count := runtime.MapBucketsCount(escapingMap); count > 1 && runtime.MapBucketsPointerIsNil(escapingMap) {
	 789  				t.Errorf("escape: buckets pointer is nil for n=%d buckets", count)
	 790  			}
	 791  			for i := 0; i < tt.n; i++ {
	 792  				escapingMap[i] = i
	 793  			}
	 794  			if got := runtime.MapBucketsCount(escapingMap); got != tt.escape {
	 795  				t.Errorf("escape: n=%d want %d buckets, got %d", tt.n, tt.escape, got)
	 796  			}
	 797  			mapSink = escapingMap
	 798  		}
	 799  	})
	 800  
	 801  }
	 802  
	 803  func benchmarkMapPop(b *testing.B, n int) {
	 804  	m := map[int]int{}
	 805  	for i := 0; i < b.N; i++ {
	 806  		for j := 0; j < n; j++ {
	 807  			m[j] = j
	 808  		}
	 809  		for j := 0; j < n; j++ {
	 810  			// Use iterator to pop an element.
	 811  			// We want this to be fast, see issue 8412.
	 812  			for k := range m {
	 813  				delete(m, k)
	 814  				break
	 815  			}
	 816  		}
	 817  	}
	 818  }
	 819  
	 820  func BenchmarkMapPop100(b *testing.B)	 { benchmarkMapPop(b, 100) }
	 821  func BenchmarkMapPop1000(b *testing.B)	{ benchmarkMapPop(b, 1000) }
	 822  func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) }
	 823  
	 824  var testNonEscapingMapVariable int = 8
	 825  
	 826  func TestNonEscapingMap(t *testing.T) {
	 827  	n := testing.AllocsPerRun(1000, func() {
	 828  		m := map[int]int{}
	 829  		m[0] = 0
	 830  	})
	 831  	if n != 0 {
	 832  		t.Fatalf("mapliteral: want 0 allocs, got %v", n)
	 833  	}
	 834  	n = testing.AllocsPerRun(1000, func() {
	 835  		m := make(map[int]int)
	 836  		m[0] = 0
	 837  	})
	 838  	if n != 0 {
	 839  		t.Fatalf("no hint: want 0 allocs, got %v", n)
	 840  	}
	 841  	n = testing.AllocsPerRun(1000, func() {
	 842  		m := make(map[int]int, 8)
	 843  		m[0] = 0
	 844  	})
	 845  	if n != 0 {
	 846  		t.Fatalf("with small hint: want 0 allocs, got %v", n)
	 847  	}
	 848  	n = testing.AllocsPerRun(1000, func() {
	 849  		m := make(map[int]int, testNonEscapingMapVariable)
	 850  		m[0] = 0
	 851  	})
	 852  	if n != 0 {
	 853  		t.Fatalf("with variable hint: want 0 allocs, got %v", n)
	 854  	}
	 855  
	 856  }
	 857  
	 858  func benchmarkMapAssignInt32(b *testing.B, n int) {
	 859  	a := make(map[int32]int)
	 860  	for i := 0; i < b.N; i++ {
	 861  		a[int32(i&(n-1))] = i
	 862  	}
	 863  }
	 864  
	 865  func benchmarkMapOperatorAssignInt32(b *testing.B, n int) {
	 866  	a := make(map[int32]int)
	 867  	for i := 0; i < b.N; i++ {
	 868  		a[int32(i&(n-1))] += i
	 869  	}
	 870  }
	 871  
	 872  func benchmarkMapAppendAssignInt32(b *testing.B, n int) {
	 873  	a := make(map[int32][]int)
	 874  	b.ReportAllocs()
	 875  	b.ResetTimer()
	 876  	for i := 0; i < b.N; i++ {
	 877  		key := int32(i & (n - 1))
	 878  		a[key] = append(a[key], i)
	 879  	}
	 880  }
	 881  
	 882  func benchmarkMapDeleteInt32(b *testing.B, n int) {
	 883  	a := make(map[int32]int, n)
	 884  	b.ResetTimer()
	 885  	for i := 0; i < b.N; i++ {
	 886  		if len(a) == 0 {
	 887  			b.StopTimer()
	 888  			for j := i; j < i+n; j++ {
	 889  				a[int32(j)] = j
	 890  			}
	 891  			b.StartTimer()
	 892  		}
	 893  		delete(a, int32(i))
	 894  	}
	 895  }
	 896  
	 897  func benchmarkMapAssignInt64(b *testing.B, n int) {
	 898  	a := make(map[int64]int)
	 899  	for i := 0; i < b.N; i++ {
	 900  		a[int64(i&(n-1))] = i
	 901  	}
	 902  }
	 903  
	 904  func benchmarkMapOperatorAssignInt64(b *testing.B, n int) {
	 905  	a := make(map[int64]int)
	 906  	for i := 0; i < b.N; i++ {
	 907  		a[int64(i&(n-1))] += i
	 908  	}
	 909  }
	 910  
	 911  func benchmarkMapAppendAssignInt64(b *testing.B, n int) {
	 912  	a := make(map[int64][]int)
	 913  	b.ReportAllocs()
	 914  	b.ResetTimer()
	 915  	for i := 0; i < b.N; i++ {
	 916  		key := int64(i & (n - 1))
	 917  		a[key] = append(a[key], i)
	 918  	}
	 919  }
	 920  
	 921  func benchmarkMapDeleteInt64(b *testing.B, n int) {
	 922  	a := make(map[int64]int, n)
	 923  	b.ResetTimer()
	 924  	for i := 0; i < b.N; i++ {
	 925  		if len(a) == 0 {
	 926  			b.StopTimer()
	 927  			for j := i; j < i+n; j++ {
	 928  				a[int64(j)] = j
	 929  			}
	 930  			b.StartTimer()
	 931  		}
	 932  		delete(a, int64(i))
	 933  	}
	 934  }
	 935  
	 936  func benchmarkMapAssignStr(b *testing.B, n int) {
	 937  	k := make([]string, n)
	 938  	for i := 0; i < len(k); i++ {
	 939  		k[i] = strconv.Itoa(i)
	 940  	}
	 941  	b.ResetTimer()
	 942  	a := make(map[string]int)
	 943  	for i := 0; i < b.N; i++ {
	 944  		a[k[i&(n-1)]] = i
	 945  	}
	 946  }
	 947  
	 948  func benchmarkMapOperatorAssignStr(b *testing.B, n int) {
	 949  	k := make([]string, n)
	 950  	for i := 0; i < len(k); i++ {
	 951  		k[i] = strconv.Itoa(i)
	 952  	}
	 953  	b.ResetTimer()
	 954  	a := make(map[string]string)
	 955  	for i := 0; i < b.N; i++ {
	 956  		key := k[i&(n-1)]
	 957  		a[key] += key
	 958  	}
	 959  }
	 960  
	 961  func benchmarkMapAppendAssignStr(b *testing.B, n int) {
	 962  	k := make([]string, n)
	 963  	for i := 0; i < len(k); i++ {
	 964  		k[i] = strconv.Itoa(i)
	 965  	}
	 966  	a := make(map[string][]string)
	 967  	b.ReportAllocs()
	 968  	b.ResetTimer()
	 969  	for i := 0; i < b.N; i++ {
	 970  		key := k[i&(n-1)]
	 971  		a[key] = append(a[key], key)
	 972  	}
	 973  }
	 974  
	 975  func benchmarkMapDeleteStr(b *testing.B, n int) {
	 976  	i2s := make([]string, n)
	 977  	for i := 0; i < n; i++ {
	 978  		i2s[i] = strconv.Itoa(i)
	 979  	}
	 980  	a := make(map[string]int, n)
	 981  	b.ResetTimer()
	 982  	k := 0
	 983  	for i := 0; i < b.N; i++ {
	 984  		if len(a) == 0 {
	 985  			b.StopTimer()
	 986  			for j := 0; j < n; j++ {
	 987  				a[i2s[j]] = j
	 988  			}
	 989  			k = i
	 990  			b.StartTimer()
	 991  		}
	 992  		delete(a, i2s[i-k])
	 993  	}
	 994  }
	 995  
	 996  func benchmarkMapDeletePointer(b *testing.B, n int) {
	 997  	i2p := make([]*int, n)
	 998  	for i := 0; i < n; i++ {
	 999  		i2p[i] = new(int)
	1000  	}
	1001  	a := make(map[*int]int, n)
	1002  	b.ResetTimer()
	1003  	k := 0
	1004  	for i := 0; i < b.N; i++ {
	1005  		if len(a) == 0 {
	1006  			b.StopTimer()
	1007  			for j := 0; j < n; j++ {
	1008  				a[i2p[j]] = j
	1009  			}
	1010  			k = i
	1011  			b.StartTimer()
	1012  		}
	1013  		delete(a, i2p[i-k])
	1014  	}
	1015  }
	1016  
	1017  func runWith(f func(*testing.B, int), v ...int) func(*testing.B) {
	1018  	return func(b *testing.B) {
	1019  		for _, n := range v {
	1020  			b.Run(strconv.Itoa(n), func(b *testing.B) { f(b, n) })
	1021  		}
	1022  	}
	1023  }
	1024  
	1025  func BenchmarkMapAssign(b *testing.B) {
	1026  	b.Run("Int32", runWith(benchmarkMapAssignInt32, 1<<8, 1<<16))
	1027  	b.Run("Int64", runWith(benchmarkMapAssignInt64, 1<<8, 1<<16))
	1028  	b.Run("Str", runWith(benchmarkMapAssignStr, 1<<8, 1<<16))
	1029  }
	1030  
	1031  func BenchmarkMapOperatorAssign(b *testing.B) {
	1032  	b.Run("Int32", runWith(benchmarkMapOperatorAssignInt32, 1<<8, 1<<16))
	1033  	b.Run("Int64", runWith(benchmarkMapOperatorAssignInt64, 1<<8, 1<<16))
	1034  	b.Run("Str", runWith(benchmarkMapOperatorAssignStr, 1<<8, 1<<16))
	1035  }
	1036  
	1037  func BenchmarkMapAppendAssign(b *testing.B) {
	1038  	b.Run("Int32", runWith(benchmarkMapAppendAssignInt32, 1<<8, 1<<16))
	1039  	b.Run("Int64", runWith(benchmarkMapAppendAssignInt64, 1<<8, 1<<16))
	1040  	b.Run("Str", runWith(benchmarkMapAppendAssignStr, 1<<8, 1<<16))
	1041  }
	1042  
	1043  func BenchmarkMapDelete(b *testing.B) {
	1044  	b.Run("Int32", runWith(benchmarkMapDeleteInt32, 100, 1000, 10000))
	1045  	b.Run("Int64", runWith(benchmarkMapDeleteInt64, 100, 1000, 10000))
	1046  	b.Run("Str", runWith(benchmarkMapDeleteStr, 100, 1000, 10000))
	1047  	b.Run("Pointer", runWith(benchmarkMapDeletePointer, 100, 1000, 10000))
	1048  }
	1049  
	1050  func TestDeferDeleteSlow(t *testing.T) {
	1051  	ks := []complex128{0, 1, 2, 3}
	1052  
	1053  	m := make(map[interface{}]int)
	1054  	for i, k := range ks {
	1055  		m[k] = i
	1056  	}
	1057  	if len(m) != len(ks) {
	1058  		t.Errorf("want %d elements, got %d", len(ks), len(m))
	1059  	}
	1060  
	1061  	func() {
	1062  		for _, k := range ks {
	1063  			defer delete(m, k)
	1064  		}
	1065  	}()
	1066  	if len(m) != 0 {
	1067  		t.Errorf("want 0 elements, got %d", len(m))
	1068  	}
	1069  }
	1070  
	1071  // TestIncrementAfterDeleteValueInt and other test Issue 25936.
	1072  // Value types int, int32, int64 are affected. Value type string
	1073  // works as expected.
	1074  func TestIncrementAfterDeleteValueInt(t *testing.T) {
	1075  	const key1 = 12
	1076  	const key2 = 13
	1077  
	1078  	m := make(map[int]int)
	1079  	m[key1] = 99
	1080  	delete(m, key1)
	1081  	m[key2]++
	1082  	if n2 := m[key2]; n2 != 1 {
	1083  		t.Errorf("incremented 0 to %d", n2)
	1084  	}
	1085  }
	1086  
	1087  func TestIncrementAfterDeleteValueInt32(t *testing.T) {
	1088  	const key1 = 12
	1089  	const key2 = 13
	1090  
	1091  	m := make(map[int]int32)
	1092  	m[key1] = 99
	1093  	delete(m, key1)
	1094  	m[key2]++
	1095  	if n2 := m[key2]; n2 != 1 {
	1096  		t.Errorf("incremented 0 to %d", n2)
	1097  	}
	1098  }
	1099  
	1100  func TestIncrementAfterDeleteValueInt64(t *testing.T) {
	1101  	const key1 = 12
	1102  	const key2 = 13
	1103  
	1104  	m := make(map[int]int64)
	1105  	m[key1] = 99
	1106  	delete(m, key1)
	1107  	m[key2]++
	1108  	if n2 := m[key2]; n2 != 1 {
	1109  		t.Errorf("incremented 0 to %d", n2)
	1110  	}
	1111  }
	1112  
	1113  func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) {
	1114  	const key1 = ""
	1115  	const key2 = "x"
	1116  
	1117  	m := make(map[string]int)
	1118  	m[key1] = 99
	1119  	delete(m, key1)
	1120  	m[key2] += 1
	1121  	if n2 := m[key2]; n2 != 1 {
	1122  		t.Errorf("incremented 0 to %d", n2)
	1123  	}
	1124  }
	1125  
	1126  func TestIncrementAfterDeleteKeyValueString(t *testing.T) {
	1127  	const key1 = ""
	1128  	const key2 = "x"
	1129  
	1130  	m := make(map[string]string)
	1131  	m[key1] = "99"
	1132  	delete(m, key1)
	1133  	m[key2] += "1"
	1134  	if n2 := m[key2]; n2 != "1" {
	1135  		t.Errorf("appended '1' to empty (nil) string, got %s", n2)
	1136  	}
	1137  }
	1138  
	1139  // TestIncrementAfterBulkClearKeyStringValueInt tests that map bulk
	1140  // deletion (mapclear) still works as expected. Note that it was not
	1141  // affected by Issue 25936.
	1142  func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) {
	1143  	const key1 = ""
	1144  	const key2 = "x"
	1145  
	1146  	m := make(map[string]int)
	1147  	m[key1] = 99
	1148  	for k := range m {
	1149  		delete(m, k)
	1150  	}
	1151  	m[key2]++
	1152  	if n2 := m[key2]; n2 != 1 {
	1153  		t.Errorf("incremented 0 to %d", n2)
	1154  	}
	1155  }
	1156  
	1157  func TestMapTombstones(t *testing.T) {
	1158  	m := map[int]int{}
	1159  	const N = 10000
	1160  	// Fill a map.
	1161  	for i := 0; i < N; i++ {
	1162  		m[i] = i
	1163  	}
	1164  	runtime.MapTombstoneCheck(m)
	1165  	// Delete half of the entries.
	1166  	for i := 0; i < N; i += 2 {
	1167  		delete(m, i)
	1168  	}
	1169  	runtime.MapTombstoneCheck(m)
	1170  	// Add new entries to fill in holes.
	1171  	for i := N; i < 3*N/2; i++ {
	1172  		m[i] = i
	1173  	}
	1174  	runtime.MapTombstoneCheck(m)
	1175  	// Delete everything.
	1176  	for i := 0; i < 3*N/2; i++ {
	1177  		delete(m, i)
	1178  	}
	1179  	runtime.MapTombstoneCheck(m)
	1180  }
	1181  
	1182  type canString int
	1183  
	1184  func (c canString) String() string {
	1185  	return fmt.Sprintf("%d", int(c))
	1186  }
	1187  
	1188  func TestMapInterfaceKey(t *testing.T) {
	1189  	// Test all the special cases in runtime.typehash.
	1190  	type GrabBag struct {
	1191  		f32	float32
	1192  		f64	float64
	1193  		c64	complex64
	1194  		c128 complex128
	1195  		s		string
	1196  		i0	 interface{}
	1197  		i1	 interface {
	1198  			String() string
	1199  		}
	1200  		a [4]string
	1201  	}
	1202  
	1203  	m := map[interface{}]bool{}
	1204  	// Put a bunch of data in m, so that a bad hash is likely to
	1205  	// lead to a bad bucket, which will lead to a missed lookup.
	1206  	for i := 0; i < 1000; i++ {
	1207  		m[i] = true
	1208  	}
	1209  	m[GrabBag{f32: 1.0}] = true
	1210  	if !m[GrabBag{f32: 1.0}] {
	1211  		panic("f32 not found")
	1212  	}
	1213  	m[GrabBag{f64: 1.0}] = true
	1214  	if !m[GrabBag{f64: 1.0}] {
	1215  		panic("f64 not found")
	1216  	}
	1217  	m[GrabBag{c64: 1.0i}] = true
	1218  	if !m[GrabBag{c64: 1.0i}] {
	1219  		panic("c64 not found")
	1220  	}
	1221  	m[GrabBag{c128: 1.0i}] = true
	1222  	if !m[GrabBag{c128: 1.0i}] {
	1223  		panic("c128 not found")
	1224  	}
	1225  	m[GrabBag{s: "foo"}] = true
	1226  	if !m[GrabBag{s: "foo"}] {
	1227  		panic("string not found")
	1228  	}
	1229  	m[GrabBag{i0: "foo"}] = true
	1230  	if !m[GrabBag{i0: "foo"}] {
	1231  		panic("interface{} not found")
	1232  	}
	1233  	m[GrabBag{i1: canString(5)}] = true
	1234  	if !m[GrabBag{i1: canString(5)}] {
	1235  		panic("interface{String() string} not found")
	1236  	}
	1237  	m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true
	1238  	if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] {
	1239  		panic("array not found")
	1240  	}
	1241  }
	1242  

View as plain text