diff options
Diffstat (limited to 'src/runtime')
| -rw-r--r-- | src/runtime/export_map_noswiss_test.go | 58 | ||||
| -rw-r--r-- | src/runtime/export_map_swiss_test.go | 58 | ||||
| -rw-r--r-- | src/runtime/export_test.go | 46 | ||||
| -rw-r--r-- | src/runtime/map_fast32_noswiss.go | 42 | ||||
| -rw-r--r-- | src/runtime/map_fast32_swiss.go | 42 | ||||
| -rw-r--r-- | src/runtime/map_fast64_noswiss.go | 42 | ||||
| -rw-r--r-- | src/runtime/map_fast64_swiss.go | 42 | ||||
| -rw-r--r-- | src/runtime/map_faststr_noswiss.go | 68 | ||||
| -rw-r--r-- | src/runtime/map_faststr_swiss.go | 68 | ||||
| -rw-r--r-- | src/runtime/map_noswiss.go | 104 | ||||
| -rw-r--r-- | src/runtime/map_noswiss_test.go | 188 | ||||
| -rw-r--r-- | src/runtime/map_swiss.go | 104 | ||||
| -rw-r--r-- | src/runtime/map_swiss_test.go | 188 | ||||
| -rw-r--r-- | src/runtime/map_test.go | 176 | ||||
| -rw-r--r-- | src/runtime/runtime-gdb.py | 1 | ||||
| -rw-r--r-- | src/runtime/runtime-gdb_test.go | 4 | ||||
| -rw-r--r-- | src/runtime/type.go | 12 |
17 files changed, 761 insertions, 482 deletions
diff --git a/src/runtime/export_map_noswiss_test.go b/src/runtime/export_map_noswiss_test.go new file mode 100644 index 0000000000..9e6d81a77c --- /dev/null +++ b/src/runtime/export_map_noswiss_test.go @@ -0,0 +1,58 @@ +// Copyright 2024 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. + +//go:build !goexperiment.swissmap + +package runtime + +import ( + "internal/abi" + "unsafe" +) + +func MapBucketsCount(m map[int]int) int { + h := *(**hmap)(unsafe.Pointer(&m)) + return 1 << h.B +} + +func MapBucketsPointerIsNil(m map[int]int) bool { + h := *(**hmap)(unsafe.Pointer(&m)) + return h.buckets == nil +} + +func MapTombstoneCheck(m map[int]int) { + // Make sure emptyOne and emptyRest are distributed correctly. + // We should have a series of filled and emptyOne cells, followed by + // a series of emptyRest cells. + h := *(**hmap)(unsafe.Pointer(&m)) + i := any(m) + t := *(**maptype)(unsafe.Pointer(&i)) + + for x := 0; x < 1<<h.B; x++ { + b0 := (*bmap)(add(h.buckets, uintptr(x)*uintptr(t.BucketSize))) + n := 0 + for b := b0; b != nil; b = b.overflow(t) { + for i := 0; i < abi.OldMapBucketCount; i++ { + if b.tophash[i] != emptyRest { + n++ + } + } + } + k := 0 + for b := b0; b != nil; b = b.overflow(t) { + for i := 0; i < abi.OldMapBucketCount; i++ { + if k < n && b.tophash[i] == emptyRest { + panic("early emptyRest") + } + if k >= n && b.tophash[i] != emptyRest { + panic("late non-emptyRest") + } + if k == n-1 && b.tophash[i] == emptyOne { + panic("last non-emptyRest entry is emptyOne") + } + k++ + } + } + } +} diff --git a/src/runtime/export_map_swiss_test.go b/src/runtime/export_map_swiss_test.go new file mode 100644 index 0000000000..ac0308fce0 --- /dev/null +++ b/src/runtime/export_map_swiss_test.go @@ -0,0 +1,58 @@ +// Copyright 2024 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. + +//go:build goexperiment.swissmap + +package runtime + +import ( + "internal/abi" + "unsafe" +) + +func MapBucketsCount(m map[int]int) int { + h := *(**hmap)(unsafe.Pointer(&m)) + return 1 << h.B +} + +func MapBucketsPointerIsNil(m map[int]int) bool { + h := *(**hmap)(unsafe.Pointer(&m)) + return h.buckets == nil +} + +func MapTombstoneCheck(m map[int]int) { + // Make sure emptyOne and emptyRest are distributed correctly. + // We should have a series of filled and emptyOne cells, followed by + // a series of emptyRest cells. + h := *(**hmap)(unsafe.Pointer(&m)) + i := any(m) + t := *(**maptype)(unsafe.Pointer(&i)) + + for x := 0; x < 1<<h.B; x++ { + b0 := (*bmap)(add(h.buckets, uintptr(x)*uintptr(t.BucketSize))) + n := 0 + for b := b0; b != nil; b = b.overflow(t) { + for i := 0; i < abi.SwissMapBucketCount; i++ { + if b.tophash[i] != emptyRest { + n++ + } + } + } + k := 0 + for b := b0; b != nil; b = b.overflow(t) { + for i := 0; i < abi.SwissMapBucketCount; i++ { + if k < n && b.tophash[i] == emptyRest { + panic("early emptyRest") + } + if k >= n && b.tophash[i] != emptyRest { + panic("late non-emptyRest") + } + if k == n-1 && b.tophash[i] == emptyOne { + panic("last non-emptyRest entry is emptyOne") + } + k++ + } + } + } +} diff --git a/src/runtime/export_test.go b/src/runtime/export_test.go index b18480d0af..c45a4586d4 100644 --- a/src/runtime/export_test.go +++ b/src/runtime/export_test.go @@ -483,16 +483,6 @@ func (rw *RWMutex) Unlock() { const RuntimeHmapSize = unsafe.Sizeof(hmap{}) -func MapBucketsCount(m map[int]int) int { - h := *(**hmap)(unsafe.Pointer(&m)) - return 1 << h.B -} - -func MapBucketsPointerIsNil(m map[int]int) bool { - h := *(**hmap)(unsafe.Pointer(&m)) - return h.buckets == nil -} - func OverLoadFactor(count int, B uint8) bool { return overLoadFactor(count, B) } @@ -614,42 +604,6 @@ func stackOverflow(x *byte) { stackOverflow(&buf[0]) } -func MapTombstoneCheck(m map[int]int) { - // Make sure emptyOne and emptyRest are distributed correctly. - // We should have a series of filled and emptyOne cells, followed by - // a series of emptyRest cells. - h := *(**hmap)(unsafe.Pointer(&m)) - i := any(m) - t := *(**maptype)(unsafe.Pointer(&i)) - - for x := 0; x < 1<<h.B; x++ { - b0 := (*bmap)(add(h.buckets, uintptr(x)*uintptr(t.BucketSize))) - n := 0 - for b := b0; b != nil; b = b.overflow(t) { - for i := 0; i < abi.MapBucketCount; i++ { - if b.tophash[i] != emptyRest { - n++ - } - } - } - k := 0 - for b := b0; b != nil; b = b.overflow(t) { - for i := 0; i < abi.MapBucketCount; i++ { - if k < n && b.tophash[i] == emptyRest { - panic("early emptyRest") - } - if k >= n && b.tophash[i] != emptyRest { - panic("late non-emptyRest") - } - if k == n-1 && b.tophash[i] == emptyOne { - panic("last non-emptyRest entry is emptyOne") - } - k++ - } - } - } -} - func RunGetgThreadSwitchTest() { // Test that getg works correctly with thread switch. // With gccgo, if we generate getg inlined, the backend diff --git a/src/runtime/map_fast32_noswiss.go b/src/runtime/map_fast32_noswiss.go index 58d5a050f5..05e2ee54db 100644 --- a/src/runtime/map_fast32_noswiss.go +++ b/src/runtime/map_fast32_noswiss.go @@ -43,9 +43,9 @@ func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 4) { + for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 4) { if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*4+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*4+i*uintptr(t.ValueSize)) } } } @@ -92,9 +92,9 @@ func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 4) { + for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 4) { if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*4+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*4+i*uintptr(t.ValueSize)), true } } } @@ -145,7 +145,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { inserti = i @@ -185,7 +185,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) // store new key at insert position @@ -194,7 +194,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*4+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*4+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -244,7 +244,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { inserti = i @@ -284,7 +284,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) // store new key at insert position @@ -293,7 +293,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*4+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*4+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -326,7 +326,7 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) { bOrig := b search: for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 4) { + for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 4) { if key != *(*uint32)(k) || isEmpty(b.tophash[i]) { continue } @@ -338,7 +338,7 @@ search: // 32 bits wide and the key is 32 bits wide also. *(*unsafe.Pointer)(k) = nil } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*4+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*4+i*uintptr(t.ValueSize)) if t.Elem.Pointers() { memclrHasPointers(e, t.Elem.Size_) } else { @@ -347,7 +347,7 @@ search: b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, // change those to emptyRest states. - if i == abi.MapBucketCount-1 { + if i == abi.OldMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -366,7 +366,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.OldMapBucketCount - 1 } else { i-- } @@ -414,7 +414,7 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*4) + x.e = add(x.k, abi.OldMapBucketCount*4) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -422,13 +422,13 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*4) + y.e = add(y.k, abi.OldMapBucketCount*4) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*4) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, 4), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.OldMapBucketCount*4) + for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, 4), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -450,13 +450,13 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.OldMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*4) + dst.e = add(dst.k, abi.OldMapBucketCount*4) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check // Copy key. if goarch.PtrSize == 4 && t.Key.Pointers() && writeBarrier.enabled { diff --git a/src/runtime/map_fast32_swiss.go b/src/runtime/map_fast32_swiss.go index a6fb26716b..af75f182ec 100644 --- a/src/runtime/map_fast32_swiss.go +++ b/src/runtime/map_fast32_swiss.go @@ -43,9 +43,9 @@ func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 4) { + for i, k := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, k = i+1, add(k, 4) { if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*4+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*4+i*uintptr(t.ValueSize)) } } } @@ -83,9 +83,9 @@ func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 4) { + for i, k := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, k = i+1, add(k, 4) { if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*4+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*4+i*uintptr(t.ValueSize)), true } } } @@ -125,7 +125,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { inserti = i @@ -165,7 +165,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.SwissMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) // store new key at insert position @@ -174,7 +174,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*4+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.SwissMapBucketCount*4+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -215,7 +215,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { inserti = i @@ -255,7 +255,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.SwissMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*4) // store new key at insert position @@ -264,7 +264,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*4+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.SwissMapBucketCount*4+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -297,7 +297,7 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) { bOrig := b search: for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 4) { + for i, k := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, k = i+1, add(k, 4) { if key != *(*uint32)(k) || isEmpty(b.tophash[i]) { continue } @@ -309,7 +309,7 @@ search: // 32 bits wide and the key is 32 bits wide also. *(*unsafe.Pointer)(k) = nil } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*4+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*4+i*uintptr(t.ValueSize)) if t.Elem.Pointers() { memclrHasPointers(e, t.Elem.Size_) } else { @@ -318,7 +318,7 @@ search: b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, // change those to emptyRest states. - if i == abi.MapBucketCount-1 { + if i == abi.SwissMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -337,7 +337,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.SwissMapBucketCount - 1 } else { i-- } @@ -385,7 +385,7 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*4) + x.e = add(x.k, abi.SwissMapBucketCount*4) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -393,13 +393,13 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*4) + y.e = add(y.k, abi.SwissMapBucketCount*4) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*4) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, 4), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.SwissMapBucketCount*4) + for i := 0; i < abi.SwissMapBucketCount; i, k, e = i+1, add(k, 4), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -421,13 +421,13 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.SwissMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*4) + dst.e = add(dst.k, abi.SwissMapBucketCount*4) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.SwissMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check // Copy key. if goarch.PtrSize == 4 && t.Key.Pointers() && writeBarrier.enabled { diff --git a/src/runtime/map_fast64_noswiss.go b/src/runtime/map_fast64_noswiss.go index bd3c1c34da..1d56e5c029 100644 --- a/src/runtime/map_fast64_noswiss.go +++ b/src/runtime/map_fast64_noswiss.go @@ -43,9 +43,9 @@ func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 8) { + for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 8) { if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*8+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*8+i*uintptr(t.ValueSize)) } } } @@ -92,9 +92,9 @@ func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 8) { + for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 8) { if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*8+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*8+i*uintptr(t.ValueSize)), true } } } @@ -145,7 +145,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { insertb = b @@ -185,7 +185,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) // store new key at insert position @@ -194,7 +194,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*8+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*8+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -246,7 +246,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { insertb = b @@ -286,7 +286,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) // store new key at insert position @@ -295,7 +295,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*8+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*8+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -328,7 +328,7 @@ func mapdelete_fast64(t *maptype, h *hmap, key uint64) { bOrig := b search: for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 8) { + for i, k := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, k = i+1, add(k, 8) { if key != *(*uint64)(k) || isEmpty(b.tophash[i]) { continue } @@ -342,7 +342,7 @@ search: memclrHasPointers(k, 8) } } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*8+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*8+i*uintptr(t.ValueSize)) if t.Elem.Pointers() { memclrHasPointers(e, t.Elem.Size_) } else { @@ -351,7 +351,7 @@ search: b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, // change those to emptyRest states. - if i == abi.MapBucketCount-1 { + if i == abi.OldMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -370,7 +370,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.OldMapBucketCount - 1 } else { i-- } @@ -418,7 +418,7 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*8) + x.e = add(x.k, abi.OldMapBucketCount*8) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -426,13 +426,13 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*8) + y.e = add(y.k, abi.OldMapBucketCount*8) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*8) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, 8), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.OldMapBucketCount*8) + for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, 8), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -454,13 +454,13 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.OldMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*8) + dst.e = add(dst.k, abi.OldMapBucketCount*8) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check // Copy key. if t.Key.Pointers() && writeBarrier.enabled { diff --git a/src/runtime/map_fast64_swiss.go b/src/runtime/map_fast64_swiss.go index 105b2ea517..6548969ab0 100644 --- a/src/runtime/map_fast64_swiss.go +++ b/src/runtime/map_fast64_swiss.go @@ -43,9 +43,9 @@ func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 8) { + for i, k := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, k = i+1, add(k, 8) { if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*8+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*8+i*uintptr(t.ValueSize)) } } } @@ -83,9 +83,9 @@ func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { } } for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 8) { + for i, k := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, k = i+1, add(k, 8) { if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*8+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*8+i*uintptr(t.ValueSize)), true } } } @@ -125,7 +125,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { insertb = b @@ -165,7 +165,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.SwissMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) // store new key at insert position @@ -174,7 +174,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*8+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.SwissMapBucketCount*8+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -215,7 +215,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if isEmpty(b.tophash[i]) { if insertb == nil { insertb = b @@ -255,7 +255,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.SwissMapBucketCount-1)] = tophash(hash) // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*8) // store new key at insert position @@ -264,7 +264,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*8+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.SwissMapBucketCount*8+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -297,7 +297,7 @@ func mapdelete_fast64(t *maptype, h *hmap, key uint64) { bOrig := b search: for ; b != nil; b = b.overflow(t) { - for i, k := uintptr(0), b.keys(); i < abi.MapBucketCount; i, k = i+1, add(k, 8) { + for i, k := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, k = i+1, add(k, 8) { if key != *(*uint64)(k) || isEmpty(b.tophash[i]) { continue } @@ -311,7 +311,7 @@ search: memclrHasPointers(k, 8) } } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*8+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*8+i*uintptr(t.ValueSize)) if t.Elem.Pointers() { memclrHasPointers(e, t.Elem.Size_) } else { @@ -320,7 +320,7 @@ search: b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, // change those to emptyRest states. - if i == abi.MapBucketCount-1 { + if i == abi.SwissMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -339,7 +339,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.SwissMapBucketCount - 1 } else { i-- } @@ -387,7 +387,7 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*8) + x.e = add(x.k, abi.SwissMapBucketCount*8) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -395,13 +395,13 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*8) + y.e = add(y.k, abi.SwissMapBucketCount*8) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*8) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, 8), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.SwissMapBucketCount*8) + for i := 0; i < abi.SwissMapBucketCount; i, k, e = i+1, add(k, 8), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -423,13 +423,13 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.SwissMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*8) + dst.e = add(dst.k, abi.SwissMapBucketCount*8) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.SwissMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check // Copy key. if t.Key.Pointers() && writeBarrier.enabled { diff --git a/src/runtime/map_faststr_noswiss.go b/src/runtime/map_faststr_noswiss.go index 6dfe61ec46..bacc6071e7 100644 --- a/src/runtime/map_faststr_noswiss.go +++ b/src/runtime/map_faststr_noswiss.go @@ -29,7 +29,7 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { b := (*bmap)(h.buckets) if key.len < 32 { // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -38,14 +38,14 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) } } return unsafe.Pointer(&zeroVal[0]) } // long key, try not to do more comparisons than necessary - keymaybe := uintptr(abi.MapBucketCount) - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + keymaybe := uintptr(abi.OldMapBucketCount) + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -54,7 +54,7 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { continue } if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) } // check first 4 bytes if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { @@ -64,16 +64,16 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { continue } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.OldMapBucketCount { // Two keys are potential matches. Use hash to distinguish them. goto dohash } keymaybe = i } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.OldMapBucketCount { k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*goarch.PtrSize)) if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)) } } return unsafe.Pointer(&zeroVal[0]) @@ -94,13 +94,13 @@ dohash: } top := tophash(hash) for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || b.tophash[i] != top { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) } } } @@ -133,7 +133,7 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { b := (*bmap)(h.buckets) if key.len < 32 { // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -142,14 +142,14 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true } } return unsafe.Pointer(&zeroVal[0]), false } // long key, try not to do more comparisons than necessary - keymaybe := uintptr(abi.MapBucketCount) - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + keymaybe := uintptr(abi.OldMapBucketCount) + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -158,7 +158,7 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { continue } if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true } // check first 4 bytes if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { @@ -168,16 +168,16 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { continue } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.OldMapBucketCount { // Two keys are potential matches. Use hash to distinguish them. goto dohash } keymaybe = i } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.OldMapBucketCount { k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*goarch.PtrSize)) if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)), true } } return unsafe.Pointer(&zeroVal[0]), false @@ -198,13 +198,13 @@ dohash: } top := tophash(hash) for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || b.tophash[i] != top { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true } } } @@ -257,7 +257,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && insertb == nil { insertb = b @@ -304,7 +304,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = top // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.OldMapBucketCount-1)] = top // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*goarch.PtrSize) // store new key at insert position @@ -312,7 +312,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -347,7 +347,7 @@ func mapdelete_faststr(t *maptype, h *hmap, ky string) { top := tophash(hash) search: for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.OldMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || b.tophash[i] != top { continue @@ -357,7 +357,7 @@ search: } // Clear key's pointer. k.str = nil - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) if t.Elem.Pointers() { memclrHasPointers(e, t.Elem.Size_) } else { @@ -366,7 +366,7 @@ search: b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, // change those to emptyRest states. - if i == abi.MapBucketCount-1 { + if i == abi.OldMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -385,7 +385,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.OldMapBucketCount - 1 } else { i-- } @@ -433,7 +433,7 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*2*goarch.PtrSize) + x.e = add(x.k, abi.OldMapBucketCount*2*goarch.PtrSize) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -441,13 +441,13 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*2*goarch.PtrSize) + y.e = add(y.k, abi.OldMapBucketCount*2*goarch.PtrSize) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*2*goarch.PtrSize) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, 2*goarch.PtrSize), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.OldMapBucketCount*2*goarch.PtrSize) + for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, 2*goarch.PtrSize), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -469,13 +469,13 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.OldMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*2*goarch.PtrSize) + dst.e = add(dst.k, abi.OldMapBucketCount*2*goarch.PtrSize) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check // Copy key. *(*string)(dst.k) = *(*string)(k) diff --git a/src/runtime/map_faststr_swiss.go b/src/runtime/map_faststr_swiss.go index 9f3e14d869..340e1a3235 100644 --- a/src/runtime/map_faststr_swiss.go +++ b/src/runtime/map_faststr_swiss.go @@ -29,7 +29,7 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { b := (*bmap)(h.buckets) if key.len < 32 { // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -38,14 +38,14 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) } } return unsafe.Pointer(&zeroVal[0]) } // long key, try not to do more comparisons than necessary - keymaybe := uintptr(abi.MapBucketCount) - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + keymaybe := uintptr(abi.SwissMapBucketCount) + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -54,7 +54,7 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { continue } if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) } // check first 4 bytes if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { @@ -64,16 +64,16 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { continue } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.SwissMapBucketCount { // Two keys are potential matches. Use hash to distinguish them. goto dohash } keymaybe = i } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.SwissMapBucketCount { k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*goarch.PtrSize)) if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)) } } return unsafe.Pointer(&zeroVal[0]) @@ -94,13 +94,13 @@ dohash: } top := tophash(hash) for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || b.tophash[i] != top { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) } } } @@ -124,7 +124,7 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { b := (*bmap)(h.buckets) if key.len < 32 { // short key, doing lots of comparisons is ok - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -133,14 +133,14 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true } } return unsafe.Pointer(&zeroVal[0]), false } // long key, try not to do more comparisons than necessary - keymaybe := uintptr(abi.MapBucketCount) - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + keymaybe := uintptr(abi.SwissMapBucketCount) + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || isEmpty(b.tophash[i]) { if b.tophash[i] == emptyRest { @@ -149,7 +149,7 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { continue } if k.str == key.str { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true } // check first 4 bytes if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) { @@ -159,16 +159,16 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) { continue } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.SwissMapBucketCount { // Two keys are potential matches. Use hash to distinguish them. goto dohash } keymaybe = i } - if keymaybe != abi.MapBucketCount { + if keymaybe != abi.SwissMapBucketCount { k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*goarch.PtrSize)) if memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+keymaybe*uintptr(t.ValueSize)), true } } return unsafe.Pointer(&zeroVal[0]), false @@ -189,13 +189,13 @@ dohash: } top := tophash(hash) for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || b.tophash[i] != top { continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { - return add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true + return add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)), true } } } @@ -237,7 +237,7 @@ again: bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && insertb == nil { insertb = b @@ -284,7 +284,7 @@ bucketloop: insertb = h.newoverflow(t, b) inserti = 0 // not necessary, but avoids needlessly spilling inserti } - insertb.tophash[inserti&(abi.MapBucketCount-1)] = top // mask inserti to avoid bounds checks + insertb.tophash[inserti&(abi.SwissMapBucketCount-1)] = top // mask inserti to avoid bounds checks insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*goarch.PtrSize) // store new key at insert position @@ -292,7 +292,7 @@ bucketloop: h.count++ done: - elem := add(unsafe.Pointer(insertb), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+inserti*uintptr(t.ValueSize)) + elem := add(unsafe.Pointer(insertb), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+inserti*uintptr(t.ValueSize)) if h.flags&hashWriting == 0 { fatal("concurrent map writes") } @@ -327,7 +327,7 @@ func mapdelete_faststr(t *maptype, h *hmap, ky string) { top := tophash(hash) search: for ; b != nil; b = b.overflow(t) { - for i, kptr := uintptr(0), b.keys(); i < abi.MapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { + for i, kptr := uintptr(0), b.keys(); i < abi.SwissMapBucketCount; i, kptr = i+1, add(kptr, 2*goarch.PtrSize) { k := (*stringStruct)(kptr) if k.len != key.len || b.tophash[i] != top { continue @@ -337,7 +337,7 @@ search: } // Clear key's pointer. k.str = nil - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*2*goarch.PtrSize+i*uintptr(t.ValueSize)) if t.Elem.Pointers() { memclrHasPointers(e, t.Elem.Size_) } else { @@ -346,7 +346,7 @@ search: b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, // change those to emptyRest states. - if i == abi.MapBucketCount-1 { + if i == abi.SwissMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -365,7 +365,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.SwissMapBucketCount - 1 } else { i-- } @@ -413,7 +413,7 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*2*goarch.PtrSize) + x.e = add(x.k, abi.SwissMapBucketCount*2*goarch.PtrSize) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -421,13 +421,13 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*2*goarch.PtrSize) + y.e = add(y.k, abi.SwissMapBucketCount*2*goarch.PtrSize) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*2*goarch.PtrSize) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, 2*goarch.PtrSize), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.SwissMapBucketCount*2*goarch.PtrSize) + for i := 0; i < abi.SwissMapBucketCount; i, k, e = i+1, add(k, 2*goarch.PtrSize), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -449,13 +449,13 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.SwissMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*2*goarch.PtrSize) + dst.e = add(dst.k, abi.SwissMapBucketCount*2*goarch.PtrSize) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.SwissMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check // Copy key. *(*string)(dst.k) = *(*string)(k) diff --git a/src/runtime/map_noswiss.go b/src/runtime/map_noswiss.go index aff124691f..3a1c774b9d 100644 --- a/src/runtime/map_noswiss.go +++ b/src/runtime/map_noswiss.go @@ -63,15 +63,17 @@ import ( "unsafe" ) +type maptype = abi.OldMapType + const ( // Maximum number of key/elem pairs a bucket can hold. - bucketCntBits = abi.MapBucketCountBits + bucketCntBits = abi.OldMapBucketCountBits // Maximum average load of a bucket that triggers growth is bucketCnt*13/16 (about 80% full) // Because of minimum alignment rules, bucketCnt is known to be at least 8. // Represent as loadFactorNum/loadFactorDen, to allow integer math. loadFactorDen = 2 - loadFactorNum = loadFactorDen * abi.MapBucketCount * 13 / 16 + loadFactorNum = loadFactorDen * abi.OldMapBucketCount * 13 / 16 // data offset should be the size of the bmap struct, but needs to be // aligned correctly. For amd64p32 this means 64-bit alignment @@ -146,7 +148,7 @@ type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. - tophash [abi.MapBucketCount]uint8 + tophash [abi.OldMapBucketCount]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // NOTE: packing all the keys together and then all the elems together makes the // code a bit more complicated than alternating key/elem/key/elem/... but it allows @@ -446,7 +448,7 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { top := tophash(hash) bucketloop: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop @@ -458,7 +460,7 @@ bucketloop: k = *((*unsafe.Pointer)(k)) } if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { e = *((*unsafe.Pointer)(e)) } @@ -516,7 +518,7 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) top := tophash(hash) bucketloop: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop @@ -528,7 +530,7 @@ bucketloop: k = *((*unsafe.Pointer)(k)) } if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { e = *((*unsafe.Pointer)(e)) } @@ -560,7 +562,7 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe top := tophash(hash) bucketloop: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop @@ -572,7 +574,7 @@ bucketloop: k = *((*unsafe.Pointer)(k)) } if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { e = *((*unsafe.Pointer)(e)) } @@ -656,12 +658,12 @@ again: var elem unsafe.Pointer bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + elem = add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) } if b.tophash[i] == emptyRest { break bucketloop @@ -679,7 +681,7 @@ bucketloop: if t.NeedKeyUpdate() { typedmemmove(t.Key, k, key) } - elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + elem = add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) goto done } ovf := b.overflow(t) @@ -703,7 +705,7 @@ bucketloop: newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) - elem = add(insertk, abi.MapBucketCount*uintptr(t.KeySize)) + elem = add(insertk, abi.OldMapBucketCount*uintptr(t.KeySize)) } // store new key/elem at insert position @@ -778,7 +780,7 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { top := tophash(hash) search: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break search @@ -799,7 +801,7 @@ search: } else if t.Key.Pointers() { memclrHasPointers(k, t.Key.Size_) } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { *(*unsafe.Pointer)(e) = nil } else if t.Elem.Pointers() { @@ -812,7 +814,7 @@ search: // change those to emptyRest states. // It would be nice to make this a separate function, but // for loops are not currently inlineable. - if i == abi.MapBucketCount-1 { + if i == abi.OldMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -831,7 +833,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.OldMapBucketCount - 1 } else { i-- } @@ -908,7 +910,7 @@ func mapiterinit(t *maptype, h *hmap, it *hiter) { // decide where to start r := uintptr(rand()) it.startBucket = r & bucketMask(h.B) - it.offset = uint8(r >> h.B & (abi.MapBucketCount - 1)) + it.offset = uint8(r >> h.B & (abi.OldMapBucketCount - 1)) // iterator state it.bucket = it.startBucket @@ -983,8 +985,8 @@ next: } i = 0 } - for ; i < abi.MapBucketCount; i++ { - offi := (i + it.offset) & (abi.MapBucketCount - 1) + for ; i < abi.OldMapBucketCount; i++ { + offi := (i + it.offset) & (abi.OldMapBucketCount - 1) if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { // TODO: emptyRest is hard to use here, as we start iterating // in the middle of a bucket. It's feasible, just tricky. @@ -994,7 +996,7 @@ next: if t.IndirectKey() { k = *((*unsafe.Pointer)(k)) } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize)) if checkBucket != noCheck && !h.sameSizeGrow() { // Special case: iterator was started during a grow to a larger size // and the grow is not done yet. We're working on a bucket whose @@ -1096,7 +1098,7 @@ func mapclear(t *maptype, h *hmap) { for i := uintptr(0); i <= mask; i++ { b := (*bmap)(add(bucket, i*uintptr(t.BucketSize))) for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { b.tophash[i] = emptyRest } } @@ -1183,7 +1185,7 @@ func hashGrow(t *maptype, h *hmap) { // overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor. func overLoadFactor(count int, B uint8) bool { - return count > abi.MapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) + return count > abi.OldMapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } // tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets. @@ -1261,7 +1263,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*uintptr(t.KeySize)) + x.e = add(x.k, abi.OldMapBucketCount*uintptr(t.KeySize)) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -1269,13 +1271,13 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*uintptr(t.KeySize)) + y.e = add(y.k, abi.OldMapBucketCount*uintptr(t.KeySize)) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*uintptr(t.KeySize)) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.OldMapBucketCount*uintptr(t.KeySize)) + for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -1321,13 +1323,13 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.OldMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*uintptr(t.KeySize)) + dst.e = add(dst.k, abi.OldMapBucketCount*uintptr(t.KeySize)) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check if t.IndirectKey() { *(*unsafe.Pointer)(dst.k) = k2 // copy pointer } else { @@ -1408,18 +1410,18 @@ func reflect_makemap(t *maptype, cap int) *hmap { if t.Key.Equal == nil { throw("runtime.reflect_makemap: unsupported map key type") } - if t.Key.Size_ > abi.MapMaxKeyBytes && (!t.IndirectKey() || t.KeySize != uint8(goarch.PtrSize)) || - t.Key.Size_ <= abi.MapMaxKeyBytes && (t.IndirectKey() || t.KeySize != uint8(t.Key.Size_)) { + if t.Key.Size_ > abi.OldMapMaxKeyBytes && (!t.IndirectKey() || t.KeySize != uint8(goarch.PtrSize)) || + t.Key.Size_ <= abi.OldMapMaxKeyBytes && (t.IndirectKey() || t.KeySize != uint8(t.Key.Size_)) { throw("key size wrong") } - if t.Elem.Size_ > abi.MapMaxElemBytes && (!t.IndirectElem() || t.ValueSize != uint8(goarch.PtrSize)) || - t.Elem.Size_ <= abi.MapMaxElemBytes && (t.IndirectElem() || t.ValueSize != uint8(t.Elem.Size_)) { + if t.Elem.Size_ > abi.OldMapMaxElemBytes && (!t.IndirectElem() || t.ValueSize != uint8(goarch.PtrSize)) || + t.Elem.Size_ <= abi.OldMapMaxElemBytes && (t.IndirectElem() || t.ValueSize != uint8(t.Elem.Size_)) { throw("elem size wrong") } - if t.Key.Align_ > abi.MapBucketCount { + if t.Key.Align_ > abi.OldMapBucketCount { throw("key align too big") } - if t.Elem.Align_ > abi.MapBucketCount { + if t.Elem.Align_ > abi.OldMapBucketCount { throw("elem align too big") } if t.Key.Size_%uintptr(t.Key.Align_) != 0 { @@ -1428,7 +1430,7 @@ func reflect_makemap(t *maptype, cap int) *hmap { if t.Elem.Size_%uintptr(t.Elem.Align_) != 0 { throw("elem size not a multiple of elem align") } - if abi.MapBucketCount < 8 { + if abi.OldMapBucketCount < 8 { throw("bucketsize too small for proper alignment") } if dataOffset%uintptr(t.Key.Align_) != 0 { @@ -1619,26 +1621,26 @@ func mapclone(m any) any { // moveToBmap moves a bucket from src to dst. It returns the destination bucket or new destination bucket if it overflows // and the pos that the next key/value will be written, if pos == bucketCnt means needs to written in overflow bucket. func moveToBmap(t *maptype, h *hmap, dst *bmap, pos int, src *bmap) (*bmap, int) { - for i := 0; i < abi.MapBucketCount; i++ { + for i := 0; i < abi.OldMapBucketCount; i++ { if isEmpty(src.tophash[i]) { continue } - for ; pos < abi.MapBucketCount; pos++ { + for ; pos < abi.OldMapBucketCount; pos++ { if isEmpty(dst.tophash[pos]) { break } } - if pos == abi.MapBucketCount { + if pos == abi.OldMapBucketCount { dst = h.newoverflow(t, dst) pos = 0 } srcK := add(unsafe.Pointer(src), dataOffset+uintptr(i)*uintptr(t.KeySize)) - srcEle := add(unsafe.Pointer(src), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(i)*uintptr(t.ValueSize)) + srcEle := add(unsafe.Pointer(src), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+uintptr(i)*uintptr(t.ValueSize)) dstK := add(unsafe.Pointer(dst), dataOffset+uintptr(pos)*uintptr(t.KeySize)) - dstEle := add(unsafe.Pointer(dst), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(pos)*uintptr(t.ValueSize)) + dstEle := add(unsafe.Pointer(dst), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+uintptr(pos)*uintptr(t.ValueSize)) dst.tophash[pos] = src.tophash[i] if t.IndirectKey() { @@ -1742,7 +1744,7 @@ func mapclone2(t *maptype, src *hmap) *hmap { // Process entries one at a time. for srcBmap != nil { // move from oldBlucket to new bucket - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { if isEmpty(srcBmap.tophash[i]) { continue } @@ -1756,7 +1758,7 @@ func mapclone2(t *maptype, src *hmap) *hmap { srcK = *((*unsafe.Pointer)(srcK)) } - srcEle := add(unsafe.Pointer(srcBmap), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + srcEle := add(unsafe.Pointer(srcBmap), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { srcEle = *((*unsafe.Pointer)(srcEle)) } @@ -1782,7 +1784,7 @@ func keys(m any, p unsafe.Pointer) { } s := (*slice)(p) r := int(rand()) - offset := uint8(r >> h.B & (abi.MapBucketCount - 1)) + offset := uint8(r >> h.B & (abi.OldMapBucketCount - 1)) if h.B == 0 { copyKeys(t, h, (*bmap)(h.buckets), s, offset) return @@ -1811,8 +1813,8 @@ func keys(m any, p unsafe.Pointer) { func copyKeys(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { for b != nil { - for i := uintptr(0); i < abi.MapBucketCount; i++ { - offi := (i + uintptr(offset)) & (abi.MapBucketCount - 1) + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { + offi := (i + uintptr(offset)) & (abi.OldMapBucketCount - 1) if isEmpty(b.tophash[offi]) { continue } @@ -1845,7 +1847,7 @@ func values(m any, p unsafe.Pointer) { } s := (*slice)(p) r := int(rand()) - offset := uint8(r >> h.B & (abi.MapBucketCount - 1)) + offset := uint8(r >> h.B & (abi.OldMapBucketCount - 1)) if h.B == 0 { copyValues(t, h, (*bmap)(h.buckets), s, offset) return @@ -1874,8 +1876,8 @@ func values(m any, p unsafe.Pointer) { func copyValues(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { for b != nil { - for i := uintptr(0); i < abi.MapBucketCount; i++ { - offi := (i + uintptr(offset)) & (abi.MapBucketCount - 1) + for i := uintptr(0); i < abi.OldMapBucketCount; i++ { + offi := (i + uintptr(offset)) & (abi.OldMapBucketCount - 1) if isEmpty(b.tophash[offi]) { continue } @@ -1884,7 +1886,7 @@ func copyValues(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { fatal("concurrent map read and map write") } - ele := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+offi*uintptr(t.ValueSize)) + ele := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+offi*uintptr(t.ValueSize)) if t.IndirectElem() { ele = *((*unsafe.Pointer)(ele)) } diff --git a/src/runtime/map_noswiss_test.go b/src/runtime/map_noswiss_test.go new file mode 100644 index 0000000000..72d7e6d362 --- /dev/null +++ b/src/runtime/map_noswiss_test.go @@ -0,0 +1,188 @@ +// Copyright 2024 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. + +//go:build !goexperiment.swissmap + +package runtime_test + +import ( + "internal/abi" + "runtime" + "slices" + "testing" +) + +func TestMapIterOrder(t *testing.T) { + sizes := []int{3, 7, 9, 15} + if abi.OldMapBucketCountBits >= 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.OldMapBucketCountBits) + } + 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 !slices.Equal(first, ord()) { + ok = true + break + } + } + if !ok { + t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first) + break + } + } + } +} + +const bs = abi.OldMapBucketCount + +// 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) + } + } + }) +} diff --git a/src/runtime/map_swiss.go b/src/runtime/map_swiss.go index d6c97e4654..b76878da9a 100644 --- a/src/runtime/map_swiss.go +++ b/src/runtime/map_swiss.go @@ -63,15 +63,17 @@ import ( "unsafe" ) +type maptype = abi.SwissMapType + const ( // Maximum number of key/elem pairs a bucket can hold. - bucketCntBits = abi.MapBucketCountBits + bucketCntBits = abi.SwissMapBucketCountBits // Maximum average load of a bucket that triggers growth is bucketCnt*13/16 (about 80% full) // Because of minimum alignment rules, bucketCnt is known to be at least 8. // Represent as loadFactorNum/loadFactorDen, to allow integer math. loadFactorDen = 2 - loadFactorNum = loadFactorDen * abi.MapBucketCount * 13 / 16 + loadFactorNum = loadFactorDen * abi.SwissMapBucketCount * 13 / 16 // data offset should be the size of the bmap struct, but needs to be // aligned correctly. For amd64p32 this means 64-bit alignment @@ -146,7 +148,7 @@ type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. - tophash [abi.MapBucketCount]uint8 + tophash [abi.SwissMapBucketCount]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // NOTE: packing all the keys together and then all the elems together makes the // code a bit more complicated than alternating key/elem/key/elem/... but it allows @@ -425,7 +427,7 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { top := tophash(hash) bucketloop: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop @@ -437,7 +439,7 @@ bucketloop: k = *((*unsafe.Pointer)(k)) } if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { e = *((*unsafe.Pointer)(e)) } @@ -486,7 +488,7 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) top := tophash(hash) bucketloop: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop @@ -498,7 +500,7 @@ bucketloop: k = *((*unsafe.Pointer)(k)) } if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { e = *((*unsafe.Pointer)(e)) } @@ -530,7 +532,7 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe top := tophash(hash) bucketloop: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop @@ -542,7 +544,7 @@ bucketloop: k = *((*unsafe.Pointer)(k)) } if t.Key.Equal(key, k) { - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { e = *((*unsafe.Pointer)(e)) } @@ -612,12 +614,12 @@ again: var elem unsafe.Pointer bucketloop: for { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize)) - elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + elem = add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) } if b.tophash[i] == emptyRest { break bucketloop @@ -635,7 +637,7 @@ bucketloop: if t.NeedKeyUpdate() { typedmemmove(t.Key, k, key) } - elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + elem = add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) goto done } ovf := b.overflow(t) @@ -659,7 +661,7 @@ bucketloop: newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) - elem = add(insertk, abi.MapBucketCount*uintptr(t.KeySize)) + elem = add(insertk, abi.SwissMapBucketCount*uintptr(t.KeySize)) } // store new key/elem at insert position @@ -725,7 +727,7 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { top := tophash(hash) search: for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break search @@ -746,7 +748,7 @@ search: } else if t.Key.Pointers() { memclrHasPointers(k, t.Key.Size_) } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { *(*unsafe.Pointer)(e) = nil } else if t.Elem.Pointers() { @@ -759,7 +761,7 @@ search: // change those to emptyRest states. // It would be nice to make this a separate function, but // for loops are not currently inlineable. - if i == abi.MapBucketCount-1 { + if i == abi.SwissMapBucketCount-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } @@ -778,7 +780,7 @@ search: c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } - i = abi.MapBucketCount - 1 + i = abi.SwissMapBucketCount - 1 } else { i-- } @@ -839,7 +841,7 @@ func mapiterinit(t *maptype, h *hmap, it *hiter) { // decide where to start r := uintptr(rand()) it.startBucket = r & bucketMask(h.B) - it.offset = uint8(r >> h.B & (abi.MapBucketCount - 1)) + it.offset = uint8(r >> h.B & (abi.SwissMapBucketCount - 1)) // iterator state it.bucket = it.startBucket @@ -900,8 +902,8 @@ next: } i = 0 } - for ; i < abi.MapBucketCount; i++ { - offi := (i + it.offset) & (abi.MapBucketCount - 1) + for ; i < abi.SwissMapBucketCount; i++ { + offi := (i + it.offset) & (abi.SwissMapBucketCount - 1) if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { // TODO: emptyRest is hard to use here, as we start iterating // in the middle of a bucket. It's feasible, just tricky. @@ -911,7 +913,7 @@ next: if t.IndirectKey() { k = *((*unsafe.Pointer)(k)) } - e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize)) + e := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize)) if checkBucket != noCheck && !h.sameSizeGrow() { // Special case: iterator was started during a grow to a larger size // and the grow is not done yet. We're working on a bucket whose @@ -1002,7 +1004,7 @@ func mapclear(t *maptype, h *hmap) { for i := uintptr(0); i <= mask; i++ { b := (*bmap)(add(bucket, i*uintptr(t.BucketSize))) for ; b != nil; b = b.overflow(t) { - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { b.tophash[i] = emptyRest } } @@ -1089,7 +1091,7 @@ func hashGrow(t *maptype, h *hmap) { // overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor. func overLoadFactor(count int, B uint8) bool { - return count > abi.MapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) + return count > abi.SwissMapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } // tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets. @@ -1167,7 +1169,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize))) x.k = add(unsafe.Pointer(x.b), dataOffset) - x.e = add(x.k, abi.MapBucketCount*uintptr(t.KeySize)) + x.e = add(x.k, abi.SwissMapBucketCount*uintptr(t.KeySize)) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. @@ -1175,13 +1177,13 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize))) y.k = add(unsafe.Pointer(y.b), dataOffset) - y.e = add(y.k, abi.MapBucketCount*uintptr(t.KeySize)) + y.e = add(y.k, abi.SwissMapBucketCount*uintptr(t.KeySize)) } for ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) - e := add(k, abi.MapBucketCount*uintptr(t.KeySize)) - for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) { + e := add(k, abi.SwissMapBucketCount*uintptr(t.KeySize)) + for i := 0; i < abi.SwissMapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) { top := b.tophash[i] if isEmpty(top) { b.tophash[i] = evacuatedEmpty @@ -1227,13 +1229,13 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY dst := &xy[useY] // evacuation destination - if dst.i == abi.MapBucketCount { + if dst.i == abi.SwissMapBucketCount { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) - dst.e = add(dst.k, abi.MapBucketCount*uintptr(t.KeySize)) + dst.e = add(dst.k, abi.SwissMapBucketCount*uintptr(t.KeySize)) } - dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check + dst.b.tophash[dst.i&(abi.SwissMapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds check if t.IndirectKey() { *(*unsafe.Pointer)(dst.k) = k2 // copy pointer } else { @@ -1301,18 +1303,18 @@ func reflect_makemap(t *maptype, cap int) *hmap { if t.Key.Equal == nil { throw("runtime.reflect_makemap: unsupported map key type") } - if t.Key.Size_ > abi.MapMaxKeyBytes && (!t.IndirectKey() || t.KeySize != uint8(goarch.PtrSize)) || - t.Key.Size_ <= abi.MapMaxKeyBytes && (t.IndirectKey() || t.KeySize != uint8(t.Key.Size_)) { + if t.Key.Size_ > abi.SwissMapMaxKeyBytes && (!t.IndirectKey() || t.KeySize != uint8(goarch.PtrSize)) || + t.Key.Size_ <= abi.SwissMapMaxKeyBytes && (t.IndirectKey() || t.KeySize != uint8(t.Key.Size_)) { throw("key size wrong") } - if t.Elem.Size_ > abi.MapMaxElemBytes && (!t.IndirectElem() || t.ValueSize != uint8(goarch.PtrSize)) || - t.Elem.Size_ <= abi.MapMaxElemBytes && (t.IndirectElem() || t.ValueSize != uint8(t.Elem.Size_)) { + if t.Elem.Size_ > abi.SwissMapMaxElemBytes && (!t.IndirectElem() || t.ValueSize != uint8(goarch.PtrSize)) || + t.Elem.Size_ <= abi.SwissMapMaxElemBytes && (t.IndirectElem() || t.ValueSize != uint8(t.Elem.Size_)) { throw("elem size wrong") } - if t.Key.Align_ > abi.MapBucketCount { + if t.Key.Align_ > abi.SwissMapBucketCount { throw("key align too big") } - if t.Elem.Align_ > abi.MapBucketCount { + if t.Elem.Align_ > abi.SwissMapBucketCount { throw("elem align too big") } if t.Key.Size_%uintptr(t.Key.Align_) != 0 { @@ -1321,7 +1323,7 @@ func reflect_makemap(t *maptype, cap int) *hmap { if t.Elem.Size_%uintptr(t.Elem.Align_) != 0 { throw("elem size not a multiple of elem align") } - if abi.MapBucketCount < 8 { + if abi.SwissMapBucketCount < 8 { throw("bucketsize too small for proper alignment") } if dataOffset%uintptr(t.Key.Align_) != 0 { @@ -1444,26 +1446,26 @@ func mapclone(m any) any { // moveToBmap moves a bucket from src to dst. It returns the destination bucket or new destination bucket if it overflows // and the pos that the next key/value will be written, if pos == bucketCnt means needs to written in overflow bucket. func moveToBmap(t *maptype, h *hmap, dst *bmap, pos int, src *bmap) (*bmap, int) { - for i := 0; i < abi.MapBucketCount; i++ { + for i := 0; i < abi.SwissMapBucketCount; i++ { if isEmpty(src.tophash[i]) { continue } - for ; pos < abi.MapBucketCount; pos++ { + for ; pos < abi.SwissMapBucketCount; pos++ { if isEmpty(dst.tophash[pos]) { break } } - if pos == abi.MapBucketCount { + if pos == abi.SwissMapBucketCount { dst = h.newoverflow(t, dst) pos = 0 } srcK := add(unsafe.Pointer(src), dataOffset+uintptr(i)*uintptr(t.KeySize)) - srcEle := add(unsafe.Pointer(src), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(i)*uintptr(t.ValueSize)) + srcEle := add(unsafe.Pointer(src), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+uintptr(i)*uintptr(t.ValueSize)) dstK := add(unsafe.Pointer(dst), dataOffset+uintptr(pos)*uintptr(t.KeySize)) - dstEle := add(unsafe.Pointer(dst), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+uintptr(pos)*uintptr(t.ValueSize)) + dstEle := add(unsafe.Pointer(dst), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+uintptr(pos)*uintptr(t.ValueSize)) dst.tophash[pos] = src.tophash[i] if t.IndirectKey() { @@ -1567,7 +1569,7 @@ func mapclone2(t *maptype, src *hmap) *hmap { // Process entries one at a time. for srcBmap != nil { // move from oldBlucket to new bucket - for i := uintptr(0); i < abi.MapBucketCount; i++ { + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { if isEmpty(srcBmap.tophash[i]) { continue } @@ -1581,7 +1583,7 @@ func mapclone2(t *maptype, src *hmap) *hmap { srcK = *((*unsafe.Pointer)(srcK)) } - srcEle := add(unsafe.Pointer(srcBmap), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) + srcEle := add(unsafe.Pointer(srcBmap), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize)) if t.IndirectElem() { srcEle = *((*unsafe.Pointer)(srcEle)) } @@ -1607,7 +1609,7 @@ func keys(m any, p unsafe.Pointer) { } s := (*slice)(p) r := int(rand()) - offset := uint8(r >> h.B & (abi.MapBucketCount - 1)) + offset := uint8(r >> h.B & (abi.SwissMapBucketCount - 1)) if h.B == 0 { copyKeys(t, h, (*bmap)(h.buckets), s, offset) return @@ -1636,8 +1638,8 @@ func keys(m any, p unsafe.Pointer) { func copyKeys(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { for b != nil { - for i := uintptr(0); i < abi.MapBucketCount; i++ { - offi := (i + uintptr(offset)) & (abi.MapBucketCount - 1) + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { + offi := (i + uintptr(offset)) & (abi.SwissMapBucketCount - 1) if isEmpty(b.tophash[offi]) { continue } @@ -1670,7 +1672,7 @@ func values(m any, p unsafe.Pointer) { } s := (*slice)(p) r := int(rand()) - offset := uint8(r >> h.B & (abi.MapBucketCount - 1)) + offset := uint8(r >> h.B & (abi.SwissMapBucketCount - 1)) if h.B == 0 { copyValues(t, h, (*bmap)(h.buckets), s, offset) return @@ -1699,8 +1701,8 @@ func values(m any, p unsafe.Pointer) { func copyValues(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { for b != nil { - for i := uintptr(0); i < abi.MapBucketCount; i++ { - offi := (i + uintptr(offset)) & (abi.MapBucketCount - 1) + for i := uintptr(0); i < abi.SwissMapBucketCount; i++ { + offi := (i + uintptr(offset)) & (abi.SwissMapBucketCount - 1) if isEmpty(b.tophash[offi]) { continue } @@ -1709,7 +1711,7 @@ func copyValues(t *maptype, h *hmap, b *bmap, s *slice, offset uint8) { fatal("concurrent map read and map write") } - ele := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+offi*uintptr(t.ValueSize)) + ele := add(unsafe.Pointer(b), dataOffset+abi.SwissMapBucketCount*uintptr(t.KeySize)+offi*uintptr(t.ValueSize)) if t.IndirectElem() { ele = *((*unsafe.Pointer)(ele)) } diff --git a/src/runtime/map_swiss_test.go b/src/runtime/map_swiss_test.go new file mode 100644 index 0000000000..78db4aa926 --- /dev/null +++ b/src/runtime/map_swiss_test.go @@ -0,0 +1,188 @@ +// Copyright 2024 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. + +//go:build goexperiment.swissmap + +package runtime_test + +import ( + "internal/abi" + "runtime" + "slices" + "testing" +) + +func TestMapIterOrder(t *testing.T) { + sizes := []int{3, 7, 9, 15} + if abi.SwissMapBucketCountBits >= 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.SwissMapBucketCountBits) + } + 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 !slices.Equal(first, ord()) { + ok = true + break + } + } + if !ok { + t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first) + break + } + } + } +} + +const bs = abi.SwissMapBucketCount + +// 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) + } + } + }) +} diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go index ba2ea74649..7d884c4922 100644 --- a/src/runtime/map_test.go +++ b/src/runtime/map_test.go @@ -6,7 +6,6 @@ package runtime_test import ( "fmt" - "internal/abi" "internal/goarch" "internal/testenv" "math" @@ -509,43 +508,6 @@ func TestMapNanGrowIterator(t *testing.T) { } } -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 !slices.Equal(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 @@ -682,144 +644,6 @@ func TestIgnoreBogusMapHint(t *testing.T) { } } -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++ { diff --git a/src/runtime/runtime-gdb.py b/src/runtime/runtime-gdb.py index 46f014fc76..8618ebbc3b 100644 --- a/src/runtime/runtime-gdb.py +++ b/src/runtime/runtime-gdb.py @@ -141,6 +141,7 @@ class SliceTypePrinter: yield ('[{0}]'.format(idx), item) +# TODO(go.dev/issue/54766): Support swisstable maps. class MapTypePrinter: """Pretty print map[K]V types. diff --git a/src/runtime/runtime-gdb_test.go b/src/runtime/runtime-gdb_test.go index 5defe2f615..30703005b3 100644 --- a/src/runtime/runtime-gdb_test.go +++ b/src/runtime/runtime-gdb_test.go @@ -119,8 +119,8 @@ import "fmt" import "runtime" var gslice []string func main() { - mapvar := make(map[string]string, ` + strconv.FormatInt(abi.MapBucketCount+9, 10) + `) - slicemap := make(map[string][]string,` + strconv.FormatInt(abi.MapBucketCount+3, 10) + `) + mapvar := make(map[string]string, ` + strconv.FormatInt(abi.OldMapBucketCount+9, 10) + `) + slicemap := make(map[string][]string,` + strconv.FormatInt(abi.OldMapBucketCount+3, 10) + `) chanint := make(chan int, 10) chanstr := make(chan string, 10) chanint <- 99 diff --git a/src/runtime/type.go b/src/runtime/type.go index 201340752b..5e5c99276c 100644 --- a/src/runtime/type.go +++ b/src/runtime/type.go @@ -8,6 +8,7 @@ package runtime import ( "internal/abi" + "internal/goexperiment" "unsafe" ) @@ -235,8 +236,6 @@ type uncommontype = abi.UncommonType type interfacetype = abi.InterfaceType -type maptype = abi.MapType - type arraytype = abi.ArrayType type chantype = abi.ChanType @@ -439,8 +438,13 @@ func typesEqual(t, v *_type, seen map[_typePair]struct{}) bool { } return true case abi.Map: - mt := (*maptype)(unsafe.Pointer(t)) - mv := (*maptype)(unsafe.Pointer(v)) + if goexperiment.SwissMap { + mt := (*abi.SwissMapType)(unsafe.Pointer(t)) + mv := (*abi.SwissMapType)(unsafe.Pointer(v)) + return typesEqual(mt.Key, mv.Key, seen) && typesEqual(mt.Elem, mv.Elem, seen) + } + mt := (*abi.OldMapType)(unsafe.Pointer(t)) + mv := (*abi.OldMapType)(unsafe.Pointer(v)) return typesEqual(mt.Key, mv.Key, seen) && typesEqual(mt.Elem, mv.Elem, seen) case abi.Pointer: pt := (*ptrtype)(unsafe.Pointer(t)) |