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 "sort" 13 "strings" 14 "sync" 15 "testing" 16 ) 17 18 // negative zero is a good test because: 19 // 1) 0 and -0 are equal, yet have distinct representations. 20 // 2) 0 is represented as all zeros, -0 isn't. 21 // I'm not sure the language spec actually requires this behavior, 22 // but it's what the current map implementation does. 23 func TestNegativeZero(t *testing.T) { 24 m := make(map[float64]bool, 0) 25 26 m[+0.0] = true 27 m[math.Copysign(0.0, -1.0)] = true // should overwrite +0 entry 28 29 if len(m) != 1 { 30 t.Error("length wrong") 31 } 32 33 for k := range m { 34 if math.Copysign(1.0, k) > 0 { 35 t.Error("wrong sign") 36 } 37 } 38 39 m = make(map[float64]bool, 0) 40 m[math.Copysign(0.0, -1.0)] = true 41 m[+0.0] = true // should overwrite -0.0 entry 42 43 if len(m) != 1 { 44 t.Error("length wrong") 45 } 46 47 for k := range m { 48 if math.Copysign(1.0, k) < 0 { 49 t.Error("wrong sign") 50 } 51 } 52 } 53 54 // nan is a good test because nan != nan, and nan has 55 // a randomized hash value. 56 func TestNan(t *testing.T) { 57 m := make(map[float64]int, 0) 58 nan := math.NaN() 59 m[nan] = 1 60 m[nan] = 2 61 m[nan] = 4 62 if len(m) != 3 { 63 t.Error("length wrong") 64 } 65 s := 0 66 for k, v := range m { 67 if k == k { 68 t.Error("nan disappeared") 69 } 70 if (v & (v - 1)) != 0 { 71 t.Error("value wrong") 72 } 73 s |= v 74 } 75 if s != 7 { 76 t.Error("values wrong") 77 } 78 } 79 80 // Maps aren't actually copied on assignment. 81 func TestAlias(t *testing.T) { 82 m := make(map[int]int, 0) 83 m[0] = 5 84 n := m 85 n[0] = 6 86 if m[0] != 6 { 87 t.Error("alias didn't work") 88 } 89 } 90 91 func TestGrowWithNaN(t *testing.T) { 92 m := make(map[float64]int, 4) 93 nan := math.NaN() 94 m[nan] = 1 95 m[nan] = 2 96 m[nan] = 4 97 cnt := 0 98 s := 0 99 growflag := true 100 for k, v := range m { 101 if growflag { 102 // force a hashtable resize 103 for i := 0; i < 100; i++ { 104 m[float64(i)] = i 105 } 106 growflag = false 107 } 108 if k != k { 109 cnt++ 110 s |= v 111 } 112 } 113 if cnt != 3 { 114 t.Error("NaN keys lost during grow") 115 } 116 if s != 7 { 117 t.Error("NaN values lost during grow") 118 } 119 } 120 121 type FloatInt struct { 122 x float64 123 y int 124 } 125 126 func TestGrowWithNegativeZero(t *testing.T) { 127 negzero := math.Copysign(0.0, -1.0) 128 m := make(map[FloatInt]int, 4) 129 m[FloatInt{0.0, 0}] = 1 130 m[FloatInt{0.0, 1}] = 2 131 m[FloatInt{0.0, 2}] = 4 132 m[FloatInt{0.0, 3}] = 8 133 growflag := true 134 s := 0 135 cnt := 0 136 negcnt := 0 137 // The first iteration should return the +0 key. 138 // The subsequent iterations should return the -0 key. 139 // I'm not really sure this is required by the spec, 140 // but it makes sense. 141 // TODO: are we allowed to get the first entry returned again??? 142 for k, v := range m { 143 if v == 0 { 144 continue 145 } // ignore entries added to grow table 146 cnt++ 147 if math.Copysign(1.0, k.x) < 0 { 148 if v&16 == 0 { 149 t.Error("key/value not updated together 1") 150 } 151 negcnt++ 152 s |= v & 15 153 } else { 154 if v&16 == 16 { 155 t.Error("key/value not updated together 2", k, v) 156 } 157 s |= v 158 } 159 if growflag { 160 // force a hashtable resize 161 for i := 0; i < 100; i++ { 162 m[FloatInt{3.0, i}] = 0 163 } 164 // then change all the entries 165 // to negative zero 166 m[FloatInt{negzero, 0}] = 1 | 16 167 m[FloatInt{negzero, 1}] = 2 | 16 168 m[FloatInt{negzero, 2}] = 4 | 16 169 m[FloatInt{negzero, 3}] = 8 | 16 170 growflag = false 171 } 172 } 173 if s != 15 { 174 t.Error("entry missing", s) 175 } 176 if cnt != 4 { 177 t.Error("wrong number of entries returned by iterator", cnt) 178 } 179 if negcnt != 3 { 180 t.Error("update to negzero missed by iteration", negcnt) 181 } 182 } 183 184 func TestIterGrowAndDelete(t *testing.T) { 185 m := make(map[int]int, 4) 186 for i := 0; i < 100; i++ { 187 m[i] = i 188 } 189 growflag := true 190 for k := range m { 191 if growflag { 192 // grow the table 193 for i := 100; i < 1000; i++ { 194 m[i] = i 195 } 196 // delete all odd keys 197 for i := 1; i < 1000; i += 2 { 198 delete(m, i) 199 } 200 growflag = false 201 } else { 202 if k&1 == 1 { 203 t.Error("odd value returned") 204 } 205 } 206 } 207 } 208 209 // make sure old bucket arrays don't get GCd while 210 // an iterator is still using them. 211 func TestIterGrowWithGC(t *testing.T) { 212 m := make(map[int]int, 4) 213 for i := 0; i < 16; i++ { 214 m[i] = i 215 } 216 growflag := true 217 bitmask := 0 218 for k := range m { 219 if k < 16 { 220 bitmask |= 1 << uint(k) 221 } 222 if growflag { 223 // grow the table 224 for i := 100; i < 1000; i++ { 225 m[i] = i 226 } 227 // trigger a gc 228 runtime.GC() 229 growflag = false 230 } 231 } 232 if bitmask != 1<<16-1 { 233 t.Error("missing key", bitmask) 234 } 235 } 236 237 func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) { 238 t.Parallel() 239 if runtime.GOMAXPROCS(-1) == 1 { 240 defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16)) 241 } 242 numLoop := 10 243 numGrowStep := 250 244 numReader := 16 245 if testing.Short() { 246 numLoop, numGrowStep = 2, 500 247 } 248 for i := 0; i < numLoop; i++ { 249 m := make(map[int]int, 0) 250 for gs := 0; gs < numGrowStep; gs++ { 251 m[gs] = gs 252 var wg sync.WaitGroup 253 wg.Add(numReader * 2) 254 for nr := 0; nr < numReader; nr++ { 255 go func() { 256 defer wg.Done() 257 for range m { 258 } 259 }() 260 go func() { 261 defer wg.Done() 262 for key := 0; key < gs; key++ { 263 _ = m[key] 264 } 265 }() 266 if useReflect { 267 wg.Add(1) 268 go func() { 269 defer wg.Done() 270 mv := reflect.ValueOf(m) 271 keys := mv.MapKeys() 272 for _, k := range keys { 273 mv.MapIndex(k) 274 } 275 }() 276 } 277 } 278 wg.Wait() 279 } 280 } 281 } 282 283 func TestConcurrentReadsAfterGrowth(t *testing.T) { 284 testConcurrentReadsAfterGrowth(t, false) 285 } 286 287 func TestConcurrentReadsAfterGrowthReflect(t *testing.T) { 288 testConcurrentReadsAfterGrowth(t, true) 289 } 290 291 func TestBigItems(t *testing.T) { 292 var key [256]string 293 for i := 0; i < 256; i++ { 294 key[i] = "foo" 295 } 296 m := make(map[[256]string][256]string, 4) 297 for i := 0; i < 100; i++ { 298 key[37] = fmt.Sprintf("string%02d", i) 299 m[key] = key 300 } 301 var keys [100]string 302 var values [100]string 303 i := 0 304 for k, v := range m { 305 keys[i] = k[37] 306 values[i] = v[37] 307 i++ 308 } 309 sort.Strings(keys[:]) 310 sort.Strings(values[:]) 311 for i := 0; i < 100; i++ { 312 if keys[i] != fmt.Sprintf("string%02d", i) { 313 t.Errorf("#%d: missing key: %v", i, keys[i]) 314 } 315 if values[i] != fmt.Sprintf("string%02d", i) { 316 t.Errorf("#%d: missing value: %v", i, values[i]) 317 } 318 } 319 } 320 321 func TestMapHugeZero(t *testing.T) { 322 type T [4000]byte 323 m := map[int]T{} 324 x := m[0] 325 if x != (T{}) { 326 t.Errorf("map value not zero") 327 } 328 y, ok := m[0] 329 if ok { 330 t.Errorf("map value should be missing") 331 } 332 if y != (T{}) { 333 t.Errorf("map value not zero") 334 } 335 } 336 337 type empty struct { 338 } 339 340 func TestEmptyKeyAndValue(t *testing.T) { 341 a := make(map[int]empty, 4) 342 b := make(map[empty]int, 4) 343 c := make(map[empty]empty, 4) 344 a[0] = empty{} 345 b[empty{}] = 0 346 b[empty{}] = 1 347 c[empty{}] = empty{} 348 349 if len(a) != 1 { 350 t.Errorf("empty value insert problem") 351 } 352 if b[empty{}] != 1 { 353 t.Errorf("empty key returned wrong value") 354 } 355 } 356 357 // Tests a map with a single bucket, with same-lengthed short keys 358 // ("quick keys") as well as long keys. 359 func TestSingleBucketMapStringKeys_DupLen(t *testing.T) { 360 testMapLookups(t, map[string]string{ 361 "x": "x1val", 362 "xx": "x2val", 363 "foo": "fooval", 364 "bar": "barval", // same key length as "foo" 365 "xxxx": "x4val", 366 strings.Repeat("x", 128): "longval1", 367 strings.Repeat("y", 128): "longval2", 368 }) 369 } 370 371 // Tests a map with a single bucket, with all keys having different lengths. 372 func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) { 373 testMapLookups(t, map[string]string{ 374 "x": "x1val", 375 "xx": "x2val", 376 "foo": "fooval", 377 "xxxx": "x4val", 378 "xxxxx": "x5val", 379 "xxxxxx": "x6val", 380 strings.Repeat("x", 128): "longval", 381 }) 382 } 383 384 func testMapLookups(t *testing.T, m map[string]string) { 385 for k, v := range m { 386 if m[k] != v { 387 t.Fatalf("m[%q] = %q; want %q", k, m[k], v) 388 } 389 } 390 } 391 392 // Tests whether the iterator returns the right elements when 393 // started in the middle of a grow, when the keys are NaNs. 394 func TestMapNanGrowIterator(t *testing.T) { 395 m := make(map[float64]int) 396 nan := math.NaN() 397 const nBuckets = 16 398 // To fill nBuckets buckets takes LOAD * nBuckets keys. 399 nKeys := int(nBuckets * *runtime.HashLoad) 400 401 // Get map to full point with nan keys. 402 for i := 0; i < nKeys; i++ { 403 m[nan] = i 404 } 405 // Trigger grow 406 m[1.0] = 1 407 delete(m, 1.0) 408 409 // Run iterator 410 found := make(map[int]struct{}) 411 for _, v := range m { 412 if v != -1 { 413 if _, repeat := found[v]; repeat { 414 t.Fatalf("repeat of value %d", v) 415 } 416 found[v] = struct{}{} 417 } 418 if len(found) == nKeys/2 { 419 // Halfway through iteration, finish grow. 420 for i := 0; i < nBuckets; i++ { 421 delete(m, 1.0) 422 } 423 } 424 } 425 if len(found) != nKeys { 426 t.Fatalf("missing value") 427 } 428 } 429 430 func TestMapIterOrder(t *testing.T) { 431 for _, n := range [...]int{3, 7, 9, 15} { 432 for i := 0; i < 1000; i++ { 433 // Make m be {0: true, 1: true, ..., n-1: true}. 434 m := make(map[int]bool) 435 for i := 0; i < n; i++ { 436 m[i] = true 437 } 438 // Check that iterating over the map produces at least two different orderings. 439 ord := func() []int { 440 var s []int 441 for key := range m { 442 s = append(s, key) 443 } 444 return s 445 } 446 first := ord() 447 ok := false 448 for try := 0; try < 100; try++ { 449 if !reflect.DeepEqual(first, ord()) { 450 ok = true 451 break 452 } 453 } 454 if !ok { 455 t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first) 456 break 457 } 458 } 459 } 460 } 461 462 // Issue 8410 463 func TestMapSparseIterOrder(t *testing.T) { 464 // Run several rounds to increase the probability 465 // of failure. One is not enough. 466 NextRound: 467 for round := 0; round < 10; round++ { 468 m := make(map[int]bool) 469 // Add 1000 items, remove 980. 470 for i := 0; i < 1000; i++ { 471 m[i] = true 472 } 473 for i := 20; i < 1000; i++ { 474 delete(m, i) 475 } 476 477 var first []int 478 for i := range m { 479 first = append(first, i) 480 } 481 482 // 800 chances to get a different iteration order. 483 // See bug 8736 for why we need so many tries. 484 for n := 0; n < 800; n++ { 485 idx := 0 486 for i := range m { 487 if i != first[idx] { 488 // iteration order changed. 489 continue NextRound 490 } 491 idx++ 492 } 493 } 494 t.Fatalf("constant iteration order on round %d: %v", round, first) 495 } 496 } 497 498 func TestMapStringBytesLookup(t *testing.T) { 499 // Use large string keys to avoid small-allocation coalescing, 500 // which can cause AllocsPerRun to report lower counts than it should. 501 m := map[string]int{ 502 "1000000000000000000000000000000000000000000000000": 1, 503 "2000000000000000000000000000000000000000000000000": 2, 504 } 505 buf := []byte("1000000000000000000000000000000000000000000000000") 506 if x := m[string(buf)]; x != 1 { 507 t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x) 508 } 509 buf[0] = '2' 510 if x := m[string(buf)]; x != 2 { 511 t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x) 512 } 513 514 var x int 515 n := testing.AllocsPerRun(100, func() { 516 x += m[string(buf)] 517 }) 518 if n != 0 { 519 t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n) 520 } 521 522 x = 0 523 n = testing.AllocsPerRun(100, func() { 524 y, ok := m[string(buf)] 525 if !ok { 526 panic("!ok") 527 } 528 x += y 529 }) 530 if n != 0 { 531 t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n) 532 } 533 } 534 535 func TestMapLargeKeyNoPointer(t *testing.T) { 536 const ( 537 I = 1000 538 N = 64 539 ) 540 type T [N]int 541 m := make(map[T]int) 542 for i := 0; i < I; i++ { 543 var v T 544 for j := 0; j < N; j++ { 545 v[j] = i + j 546 } 547 m[v] = i 548 } 549 runtime.GC() 550 for i := 0; i < I; i++ { 551 var v T 552 for j := 0; j < N; j++ { 553 v[j] = i + j 554 } 555 if m[v] != i { 556 t.Fatalf("corrupted map: want %+v, got %+v", i, m[v]) 557 } 558 } 559 } 560 561 func TestMapLargeValNoPointer(t *testing.T) { 562 const ( 563 I = 1000 564 N = 64 565 ) 566 type T [N]int 567 m := make(map[int]T) 568 for i := 0; i < I; i++ { 569 var v T 570 for j := 0; j < N; j++ { 571 v[j] = i + j 572 } 573 m[i] = v 574 } 575 runtime.GC() 576 for i := 0; i < I; i++ { 577 var v T 578 for j := 0; j < N; j++ { 579 v[j] = i + j 580 } 581 v1 := m[i] 582 for j := 0; j < N; j++ { 583 if v1[j] != v[j] { 584 t.Fatalf("corrupted map: want %+v, got %+v", v, v1) 585 } 586 } 587 } 588 } 589 590 func benchmarkMapPop(b *testing.B, n int) { 591 m := map[int]int{} 592 for i := 0; i < b.N; i++ { 593 for j := 0; j < n; j++ { 594 m[j] = j 595 } 596 for j := 0; j < n; j++ { 597 // Use iterator to pop an element. 598 // We want this to be fast, see issue 8412. 599 for k := range m { 600 delete(m, k) 601 break 602 } 603 } 604 } 605 } 606 607 func BenchmarkMapPop100(b *testing.B) { benchmarkMapPop(b, 100) } 608 func BenchmarkMapPop1000(b *testing.B) { benchmarkMapPop(b, 1000) } 609 func BenchmarkMapPop10000(b *testing.B) { benchmarkMapPop(b, 10000) } 610 611 func TestNonEscapingMap(t *testing.T) { 612 n := testing.AllocsPerRun(1000, func() { 613 m := make(map[int]int) 614 m[0] = 0 615 }) 616 if n != 0 { 617 t.Fatalf("want 0 allocs, got %v", n) 618 } 619 } 620