diff options
author | Keith Randall <khr@google.com> | 2018-10-15 15:14:48 -0700 |
---|---|---|
committer | Keith Randall <khr@golang.org> | 2018-10-31 22:48:13 +0000 |
commit | 4b05c01f9ce4740e801937af9062ee0a9a96b772 (patch) | |
tree | e1850562a4bf5d0fcacb98b608877fc5ef956581 /src/runtime/map_fast32.go | |
parent | d086c5c81f6e19e1dce0a17d901fec071b9394ff (diff) | |
download | go-4b05c01f9ce4740e801937af9062ee0a9a96b772.tar.gz go-4b05c01f9ce4740e801937af9062ee0a9a96b772.zip |
runtime: exit early when scanning map buckets
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 <rasky@develer.com>
Reviewed-by: Martin Möhrmann <martisch@uos.de>
Run-TryBot: Martin Möhrmann <martisch@uos.de>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Diffstat (limited to 'src/runtime/map_fast32.go')
-rw-r--r-- | src/runtime/map_fast32.go | 23 |
1 files changed, 16 insertions, 7 deletions
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 } |