From 4b05c01f9ce4740e801937af9062ee0a9a96b772 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Mon, 15 Oct 2018 15:14:48 -0700 Subject: [PATCH] runtime: exit early when scanning map buckets MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Divide the "empty" slot state into two, "emptyOne" and "emptyRest". emptyOne means just that slot is empty. emptyRest means all subsequent slots in that bucket are empty and the overflow pointer is nil. When scanning a bucket, we can often stop at emptyRest, reducing the total work we have to do. (This is similar to how tombstones work in open addressing.) Ideally on delete we have to figure out whether to zero the slot with an emptyOne or emptyRest marker. For now, we choose the safe but non-optimal choice. (Fix in subsequent CL?) This is a simpler CL than some others we've tried, including my CL sequence 11835[5-8] and Ilya's CL 115616. Update #19495 name old time/op new time/op delta MegMap 8.96ns ± 2% 8.74ns ± 6% -2.44% (p=0.020 n=10+10) MegOneMap 8.91ns ± 2% 5.53ns ± 2% -37.99% (p=0.000 n=10+10) MegEqMap 46.0µs ± 1% 45.8µs ± 3% ~ (p=0.315 n=9+10) MegEmptyMap 2.50ns ± 0% 2.50ns ± 2% ~ (p=0.957 n=8+10) SmallStrMap 8.54ns ± 1% 8.71ns ± 2% +2.01% (p=0.000 n=10+10) MapStringKeysEight_16 8.61ns ± 3% 8.71ns ± 3% +1.20% (p=0.026 n=9+9) MapStringKeysEight_32 8.54ns ± 2% 8.97ns ± 1% +5.05% (p=0.000 n=10+9) MapStringKeysEight_64 8.66ns ± 2% 8.99ns ± 2% +3.87% (p=0.000 n=10+10) MapStringKeysEight_1M 8.57ns ± 2% 8.95ns ± 2% +4.51% (p=0.000 n=10+9) IntMap 6.69ns ± 1% 7.46ns ± 1% +11.60% (p=0.000 n=9+9) MapFirst/1 3.69ns ± 1% 3.63ns ± 3% -1.52% (p=0.040 n=10+10) MapFirst/2 3.70ns ± 2% 3.63ns ± 2% -1.95% (p=0.001 n=9+9) MapFirst/3 3.74ns ± 2% 3.66ns ± 2% -2.12% (p=0.000 n=8+10) MapFirst/4 3.71ns ± 2% 3.66ns ± 4% ~ (p=0.073 n=9+10) MapFirst/5 3.69ns ± 1% 3.62ns ± 2% -1.88% (p=0.000 n=9+10) MapFirst/6 3.68ns ± 2% 3.62ns ± 1% -1.83% (p=0.001 n=10+9) MapFirst/7 3.67ns ± 1% 3.60ns ± 1% -1.98% (p=0.000 n=10+8) MapFirst/8 3.68ns ± 2% 3.61ns ± 2% -1.87% (p=0.000 n=10+10) MapFirst/9 8.03ns ± 4% 7.89ns ± 2% -1.76% (p=0.007 n=10+10) MapFirst/10 7.99ns ± 2% 7.86ns ± 3% -1.64% (p=0.009 n=9+10) MapFirst/11 7.96ns ± 1% 7.80ns ± 2% -2.01% (p=0.000 n=10+10) MapFirst/12 7.96ns ± 1% 7.82ns ± 1% -1.67% (p=0.000 n=10+10) MapFirst/13 8.06ns ± 3% 7.92ns ± 3% ~ (p=0.055 n=10+10) MapFirst/14 7.95ns ± 1% 7.80ns ± 1% -1.88% (p=0.000 n=10+9) MapFirst/15 8.01ns ± 2% 7.80ns ± 2% -2.57% (p=0.000 n=10+10) MapFirst/16 8.05ns ± 2% 7.90ns ± 2% -1.84% (p=0.005 n=9+10) MapMid/1 4.00ns ± 1% 3.94ns ± 2% -1.30% (p=0.021 n=8+9) MapMid/2 4.39ns ± 2% 4.32ns ± 4% ~ (p=0.128 n=10+10) MapMid/3 4.40ns ± 2% 4.27ns ± 2% -2.93% (p=0.000 n=10+9) MapMid/4 4.76ns ± 2% 4.65ns ± 1% -2.26% (p=0.000 n=10+9) MapMid/5 4.76ns ± 1% 4.65ns ± 1% -2.27% (p=0.000 n=10+10) MapMid/6 5.11ns ± 2% 4.98ns ± 2% -2.55% (p=0.000 n=10+10) MapMid/7 5.12ns ± 1% 5.01ns ± 3% -2.02% (p=0.003 n=9+9) MapMid/8 5.71ns ± 3% 5.97ns ± 1% +4.51% (p=0.000 n=10+9) MapMid/9 8.72ns ±10% 8.89ns ±10% ~ (p=0.458 n=9+10) MapMid/10 10.1ns ±15% 9.6ns ± 7% ~ (p=0.080 n=9+10) MapMid/11 9.88ns ±10% 9.44ns ±11% ~ (p=0.065 n=10+10) MapMid/12 9.90ns ±13% 10.04ns ± 9% ~ (p=1.000 n=10+8) MapMid/13 9.67ns ±14% 10.23ns ±10% ~ (p=0.209 n=10+9) MapMid/14 9.12ns ±14% 9.14ns ±13% ~ (p=0.927 n=10+10) MapMid/15 9.16ns ±12% 9.15ns ±16% ~ (p=0.955 n=10+10) MapMid/16 9.37ns ±11% 9.60ns ±23% ~ (p=0.825 n=9+10) MapLast/1 4.08ns ± 1% 3.92ns ± 0% -3.91% (p=0.000 n=10+9) MapLast/2 4.37ns ± 1% 4.28ns ± 1% -1.95% (p=0.000 n=10+10) MapLast/3 4.94ns ± 2% 4.65ns ± 1% -5.79% (p=0.000 n=9+8) MapLast/4 5.40ns ± 3% 5.02ns ± 2% -7.13% (p=0.000 n=9+9) MapLast/5 5.88ns ± 2% 5.67ns ± 2% -3.57% (p=0.000 n=10+10) MapLast/6 6.48ns ± 3% 5.90ns ± 2% -8.89% (p=0.000 n=10+10) MapLast/7 7.01ns ± 2% 6.27ns ± 5% -10.56% (p=0.000 n=10+10) MapLast/8 7.60ns ± 2% 6.62ns ± 2% -12.93% (p=0.000 n=9+10) MapLast/9 10.6ns ± 9% 10.9ns ±15% ~ (p=0.344 n=9+10) MapLast/10 11.0ns ±12% 10.9ns ±14% ~ (p=0.985 n=10+10) MapLast/11 11.4ns ±12% 11.8ns ±22% ~ (p=0.671 n=10+10) MapLast/12 11.6ns ±10% 12.1ns ±19% ~ (p=0.617 n=10+10) MapLast/13 12.5ns ±23% 11.8ns ±13% ~ (p=0.827 n=10+9) MapLast/14 10.5ns ±22% 10.4ns ± 5% ~ (p=0.797 n=10+9) MapLast/15 10.0ns ±15% 10.3ns ±16% ~ (p=0.565 n=10+10) MapLast/16 10.4ns ±12% 10.5ns ±13% ~ (p=0.889 n=10+9) MapCycle 22.3ns ± 1% 22.0ns ± 2% -1.43% (p=0.002 n=9+10) RepeatedLookupStrMapKey32 16.4ns ± 1% 16.6ns ± 1% +1.24% (p=0.000 n=10+9) RepeatedLookupStrMapKey1M 35.6µs ± 0% 35.4µs ± 1% -0.62% (p=0.002 n=10+10) NewEmptyMap 5.36ns ± 1% 9.05ns ± 1% +69.02% (p=0.000 n=10+8) NewSmallMap 51.2ns ± 2% 33.7ns ± 1% -34.22% (p=0.000 n=10+9) MapIter 83.8ns ± 1% 88.4ns ± 1% +5.55% (p=0.000 n=10+10) MapIterEmpty 4.32ns ± 3% 5.54ns ± 3% +28.12% (p=0.000 n=10+10) SameLengthMap 4.31ns ± 1% 4.59ns ± 2% +6.41% (p=0.000 n=9+10) BigKeyMap 24.2ns ± 2% 24.3ns ± 1% ~ (p=0.432 n=10+10) BigValMap 24.3ns ± 1% 24.4ns ± 2% ~ (p=0.200 n=10+9) SmallKeyMap 17.5ns ± 1% 18.5ns ± 2% +5.81% (p=0.000 n=9+10) MapPopulate/1 29.0ns ± 4% 18.8ns ± 1% -35.27% (p=0.000 n=10+9) MapPopulate/10 736ns ± 5% 693ns ± 4% -5.92% (p=0.000 n=10+10) MapPopulate/100 11.3µs ± 2% 10.8µs ± 3% -4.38% (p=0.000 n=10+10) MapPopulate/1000 139µs ± 8% 132µs ± 4% -5.10% (p=0.002 n=10+10) MapPopulate/10000 1.21ms ± 5% 1.16ms ± 5% -4.56% (p=0.002 n=10+10) MapPopulate/100000 12.2ms ± 3% 11.8ms ± 5% ~ (p=0.052 n=10+10) ComplexAlgMap 73.9ns ± 1% 74.4ns ± 2% ~ (p=0.161 n=9+10) GoMapClear/Reflexive/1 36.0ns ± 1% 26.9ns ± 2% -25.31% (p=0.000 n=10+10) GoMapClear/Reflexive/10 35.2ns ± 1% 24.4ns ± 1% -30.62% (p=0.000 n=10+10) GoMapClear/Reflexive/100 69.6ns ± 2% 59.2ns ± 1% -14.92% (p=0.000 n=10+10) GoMapClear/Reflexive/1000 1.06µs ± 2% 1.05µs ± 1% -1.16% (p=0.013 n=10+9) GoMapClear/Reflexive/10000 11.7µs ± 1% 11.7µs ± 1% ~ (p=0.542 n=10+10) GoMapClear/NonReflexive/1 96.3ns ± 1% 90.0ns ± 1% -6.52% (p=0.000 n=10+10) GoMapClear/NonReflexive/10 110ns ± 2% 101ns ± 0% -8.10% (p=0.000 n=10+7) GoMapClear/NonReflexive/100 270ns ± 2% 235ns ± 2% -12.94% (p=0.000 n=10+10) GoMapClear/NonReflexive/1000 3.02µs ± 2% 2.48µs ± 1% -17.92% (p=0.000 n=10+10) GoMapClear/NonReflexive/10000 23.7µs ± 1% 19.6µs ± 1% -17.30% (p=0.000 n=10+9) MapPop100 9.65µs ± 6% 9.18µs ± 8% -4.82% (p=0.008 n=9+10) MapPop1000 162µs ± 6% 148µs ± 4% -8.67% (p=0.000 n=9+9) MapPop10000 3.05ms ± 8% 2.82ms ±15% -7.66% (p=0.023 n=10+10) MapAssign/Int32/256 15.7ns ± 4% 14.6ns ± 2% -7.08% (p=0.000 n=10+10) MapAssign/Int32/65536 29.8ns ± 1% 30.4ns ± 0% +2.04% (p=0.000 n=10+8) MapAssign/Int64/256 14.9ns ± 5% 14.8ns ± 4% ~ (p=0.611 n=10+10) MapAssign/Int64/65536 30.3ns ± 2% 30.4ns ± 1% +0.54% (p=0.046 n=10+9) MapAssign/Str/256 17.8ns ± 3% 19.8ns ± 4% +11.08% (p=0.000 n=10+10) MapAssign/Str/65536 35.7ns ± 1% 36.4ns ± 1% +1.82% (p=0.000 n=10+10) MapOperatorAssign/Int32/256 18.8ns ± 5% 14.6ns ± 3% -22.57% (p=0.000 n=10+10) MapOperatorAssign/Int32/65536 29.8ns ± 1% 30.5ns ± 1% +2.39% (p=0.000 n=10+10) MapOperatorAssign/Int64/256 16.6ns ± 4% 15.0ns ± 6% -9.34% (p=0.000 n=10+10) MapOperatorAssign/Int64/65536 30.1ns ± 1% 31.7ns ± 2% +5.21% (p=0.000 n=10+10) MapOperatorAssign/Str/256 1.70µs ± 1% 1.61µs ± 2% -5.55% (p=0.000 n=10+8) MapOperatorAssign/Str/65536 289ns ± 7% 294ns ± 4% ~ (p=0.425 n=10+10) MapAppendAssign/Int32/256 34.3ns ± 2% 31.0ns ± 3% -9.59% (p=0.000 n=9+9) MapAppendAssign/Int32/65536 51.8ns ± 3% 47.1ns ±13% -9.17% (p=0.002 n=9+10) MapAppendAssign/Int64/256 32.5ns ± 8% 31.2ns ± 6% ~ (p=0.065 n=10+10) MapAppendAssign/Int64/65536 51.4ns ± 4% 47.2ns ±10% -8.07% (p=0.005 n=9+10) MapAppendAssign/Str/256 105ns ±12% 109ns ± 4% ~ (p=0.138 n=10+8) MapAppendAssign/Str/65536 101ns ±14% 81ns ± 8% -19.82% (p=0.000 n=10+9) MapDelete/Int32/100 32.0ns ± 1% 35.0ns ± 2% +9.59% (p=0.000 n=9+10) MapDelete/Int32/1000 27.0ns ± 3% 30.3ns ± 1% +12.10% (p=0.000 n=10+9) MapDelete/Int32/10000 29.2ns ± 1% 32.9ns ± 2% +12.80% (p=0.000 n=10+10) MapDelete/Int64/100 31.5ns ± 1% 35.7ns ± 2% +13.16% (p=0.000 n=10+10) MapDelete/Int64/1000 27.0ns ± 2% 30.6ns ± 1% +13.21% (p=0.000 n=10+10) MapDelete/Int64/10000 30.3ns ± 1% 34.4ns ± 3% +13.47% (p=0.000 n=10+10) MapDelete/Str/100 23.4ns ± 8% 26.7ns ± 6% +14.10% (p=0.000 n=10+9) MapDelete/Str/1000 31.0ns ± 2% 35.1ns ± 3% +13.19% (p=0.000 n=10+9) MapDelete/Str/10000 38.8ns ± 1% 43.4ns ± 2% +12.02% (p=0.000 n=9+10) Change-Id: I564ce0f40936589f0f9b837f7f2bbcca4c4a1070 Reviewed-on: https://go-review.googlesource.com/c/142437 Reviewed-by: Giovanni Bajo Reviewed-by: Martin Möhrmann Run-TryBot: Martin Möhrmann TryBot-Result: Gobot Gobot --- src/runtime/map.go | 46 ++++++++++++++++++----- src/runtime/map_benchmark_test.go | 62 +++++++++++++++++++++++++++++++ src/runtime/map_fast32.go | 23 ++++++++---- src/runtime/map_fast64.go | 23 ++++++++---- src/runtime/map_faststr.go | 31 ++++++++++++---- 5 files changed, 155 insertions(+), 30 deletions(-) diff --git a/src/runtime/map.go b/src/runtime/map.go index 3e368f929f..617e88faa4 100644 --- a/src/runtime/map.go +++ b/src/runtime/map.go @@ -89,11 +89,12 @@ const ( // Each bucket (including its overflow buckets, if any) will have either all or none of its // entries in the evacuated* states (except during the evacuate() method, which only happens // during map writes and thus no one else can observe the map during that time). - empty = 0 // cell is empty - evacuatedEmpty = 1 // cell is empty, bucket is evacuated. + emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. + emptyOne = 1 // this cell is empty evacuatedX = 2 // key/value is valid. Entry has been evacuated to first half of larger table. evacuatedY = 3 // same as above, but evacuated to second half of larger table. - minTopHash = 4 // minimum tophash for a normal filled cell. + evacuatedEmpty = 4 // cell is empty, bucket is evacuated. + minTopHash = 5 // minimum tophash for a normal filled cell. // flags iterator = 1 // there may be an iterator using buckets @@ -105,6 +106,11 @@ const ( noCheck = 1<<(8*sys.PtrSize) - 1 ) +// isEmpty reports whether the given tophash array entry represents an empty bucket entry. +func isEmpty(x uint8) bool { + return x <= emptyOne +} + // A header for a Go map. type hmap struct { // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go. @@ -197,7 +203,7 @@ func tophash(hash uintptr) uint8 { func evacuated(b *bmap) bool { h := b.tophash[0] - return h > empty && h < minTopHash + return h > emptyOne && h < minTopHash } func (b *bmap) overflow(t *maptype) *bmap { @@ -418,9 +424,13 @@ 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 < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -470,9 +480,13 @@ 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 < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -511,9 +525,13 @@ 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 < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -587,14 +605,18 @@ again: var inserti *uint8 var insertk unsafe.Pointer var val unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { - if b.tophash[i] == empty && inserti == nil { + if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -694,6 +716,9 @@ search: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { + if b.tophash[i] == emptyRest { + break search + } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) @@ -718,7 +743,8 @@ search: } else { memclrNoHeapPointers(v, t.elem.size) } - b.tophash[i] = empty + b.tophash[i] = emptyOne + // TODO: set up emptyRest here. h.count-- break search } @@ -833,7 +859,9 @@ next: } for ; i < bucketCnt; i++ { offi := (i + it.offset) & (bucketCnt - 1) - if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty { + 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. continue } k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) @@ -1092,7 +1120,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { v := add(k, bucketCnt*uintptr(t.keysize)) for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) { top := b.tophash[i] - if top == empty { + if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } @@ -1129,7 +1157,7 @@ func evacuate(t *maptype, h *hmap, oldbucket uintptr) { } } - if evacuatedX+1 != evacuatedY { + if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { throw("bad evacuatedN") } diff --git a/src/runtime/map_benchmark_test.go b/src/runtime/map_benchmark_test.go index 5681d5eeb8..d37dadcb56 100644 --- a/src/runtime/map_benchmark_test.go +++ b/src/runtime/map_benchmark_test.go @@ -5,6 +5,7 @@ package runtime_test import ( "fmt" + "math/rand" "strconv" "strings" "testing" @@ -206,6 +207,67 @@ func BenchmarkIntMap(b *testing.B) { } } +func BenchmarkMapFirst(b *testing.B) { + for n := 1; n <= 16; n++ { + b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { + m := make(map[int]bool) + for i := 0; i < n; i++ { + m[i] = true + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + _ = m[0] + } + }) + } +} +func BenchmarkMapMid(b *testing.B) { + for n := 1; n <= 16; n++ { + b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { + m := make(map[int]bool) + for i := 0; i < n; i++ { + m[i] = true + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + _ = m[n>>1] + } + }) + } +} +func BenchmarkMapLast(b *testing.B) { + for n := 1; n <= 16; n++ { + b.Run(fmt.Sprintf("%d", n), func(b *testing.B) { + m := make(map[int]bool) + for i := 0; i < n; i++ { + m[i] = true + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + _ = m[n-1] + } + }) + } +} + +func BenchmarkMapCycle(b *testing.B) { + // Arrange map entries to be a permuation, so that + // we hit all entries, and one lookup is data dependent + // on the previous lookup. + const N = 3127 + p := rand.New(rand.NewSource(1)).Perm(N) + m := map[int]int{} + for i := 0; i < N; i++ { + m[i] = p[i] + } + b.ResetTimer() + j := 0 + for i := 0; i < b.N; i++ { + j = m[j] + } + sink = uint64(j) +} + // Accessing the same keys in a row. func benchmarkRepeatedLookup(b *testing.B, lookupKeySize int) { m := make(map[string]bool) diff --git a/src/runtime/map_fast32.go b/src/runtime/map_fast32.go index 671558545a..063a5cbe3a 100644 --- a/src/runtime/map_fast32.go +++ b/src/runtime/map_fast32.go @@ -41,7 +41,7 @@ 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 < bucketCnt; i, k = i+1, add(k, 4) { - if *(*uint32)(k) == key && b.tophash[i] != empty { + if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)) } } @@ -81,7 +81,7 @@ 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 < bucketCnt; i, k = i+1, add(k, 4) { - if *(*uint32)(k) == key && b.tophash[i] != empty { + if *(*uint32)(k) == key && !isEmpty(b.tophash[i]) { return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)), true } } @@ -120,13 +120,17 @@ again: var inserti uintptr var insertk unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { + if isEmpty(b.tophash[i]) { if insertb == nil { inserti = i insertb = b } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := *((*uint32)(add(unsafe.Pointer(b), dataOffset+i*4))) @@ -206,13 +210,17 @@ again: var inserti uintptr var insertk unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { + if isEmpty(b.tophash[i]) { if insertb == nil { inserti = i insertb = b } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*4))) @@ -286,7 +294,7 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) { search: for ; b != nil; b = b.overflow(t) { for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 4) { - if key != *(*uint32)(k) || b.tophash[i] == empty { + if key != *(*uint32)(k) || isEmpty(b.tophash[i]) { continue } // Only clear key if there are pointers in it. @@ -299,7 +307,8 @@ search: } else { memclrNoHeapPointers(v, t.elem.size) } - b.tophash[i] = empty + b.tophash[i] = emptyOne + // TODO: emptyRest? h.count-- break search } @@ -350,7 +359,7 @@ func evacuate_fast32(t *maptype, h *hmap, oldbucket uintptr) { v := add(k, bucketCnt*4) for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 4), add(v, uintptr(t.valuesize)) { top := b.tophash[i] - if top == empty { + if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } diff --git a/src/runtime/map_fast64.go b/src/runtime/map_fast64.go index 164a4dd1ce..8270cf7b7d 100644 --- a/src/runtime/map_fast64.go +++ b/src/runtime/map_fast64.go @@ -41,7 +41,7 @@ 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 < bucketCnt; i, k = i+1, add(k, 8) { - if *(*uint64)(k) == key && b.tophash[i] != empty { + if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)) } } @@ -81,7 +81,7 @@ 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 < bucketCnt; i, k = i+1, add(k, 8) { - if *(*uint64)(k) == key && b.tophash[i] != empty { + if *(*uint64)(k) == key && !isEmpty(b.tophash[i]) { return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)), true } } @@ -120,13 +120,17 @@ again: var inserti uintptr var insertk unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { + if isEmpty(b.tophash[i]) { if insertb == nil { insertb = b inserti = i } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := *((*uint64)(add(unsafe.Pointer(b), dataOffset+i*8))) @@ -206,13 +210,17 @@ again: var inserti uintptr var insertk unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { - if b.tophash[i] == empty { + if isEmpty(b.tophash[i]) { if insertb == nil { insertb = b inserti = i } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := *((*unsafe.Pointer)(add(unsafe.Pointer(b), dataOffset+i*8))) @@ -286,7 +294,7 @@ func mapdelete_fast64(t *maptype, h *hmap, key uint64) { search: for ; b != nil; b = b.overflow(t) { for i, k := uintptr(0), b.keys(); i < bucketCnt; i, k = i+1, add(k, 8) { - if key != *(*uint64)(k) || b.tophash[i] == empty { + if key != *(*uint64)(k) || isEmpty(b.tophash[i]) { continue } // Only clear key if there are pointers in it. @@ -299,7 +307,8 @@ search: } else { memclrNoHeapPointers(v, t.elem.size) } - b.tophash[i] = empty + b.tophash[i] = emptyOne + //TODO: emptyRest h.count-- break search } @@ -350,7 +359,7 @@ func evacuate_fast64(t *maptype, h *hmap, oldbucket uintptr) { v := add(k, bucketCnt*8) for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 8), add(v, uintptr(t.valuesize)) { top := b.tophash[i] - if top == empty { + if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } diff --git a/src/runtime/map_faststr.go b/src/runtime/map_faststr.go index bee62dfb03..8f505f90a6 100644 --- a/src/runtime/map_faststr.go +++ b/src/runtime/map_faststr.go @@ -28,7 +28,10 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { // short key, doing lots of comparisons is ok for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { + if k.len != key.len || isEmpty(b.tophash[i]) { + if b.tophash[i] == emptyRest { + break + } continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { @@ -41,7 +44,10 @@ func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { keymaybe := uintptr(bucketCnt) for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { + if k.len != key.len || isEmpty(b.tophash[i]) { + if b.tophash[i] == emptyRest { + break + } continue } if k.str == key.str { @@ -117,7 +123,10 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { // short key, doing lots of comparisons is ok for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { + if k.len != key.len || isEmpty(b.tophash[i]) { + if b.tophash[i] == emptyRest { + break + } continue } if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) { @@ -130,7 +139,10 @@ func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { keymaybe := uintptr(bucketCnt) for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) { k := (*stringStruct)(kptr) - if k.len != key.len || b.tophash[i] == empty { + if k.len != key.len || isEmpty(b.tophash[i]) { + if b.tophash[i] == emptyRest { + break + } continue } if k.str == key.str { @@ -220,13 +232,17 @@ again: var inserti uintptr var insertk unsafe.Pointer +bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { - if b.tophash[i] == empty && insertb == nil { + if isEmpty(b.tophash[i]) && insertb == nil { insertb = b inserti = i } + if b.tophash[i] == emptyRest { + break bucketloop + } continue } k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize)) @@ -320,7 +336,8 @@ search: } else { memclrNoHeapPointers(v, t.elem.size) } - b.tophash[i] = empty + b.tophash[i] = emptyOne + // TODO: emptyRest h.count-- break search } @@ -371,7 +388,7 @@ func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) { v := add(k, bucketCnt*2*sys.PtrSize) for i := 0; i < bucketCnt; i, k, v = i+1, add(k, 2*sys.PtrSize), add(v, uintptr(t.valuesize)) { top := b.tophash[i] - if top == empty { + if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } -- 2.50.0