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>

1 files changed, 24 insertions, 7 deletions

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
 				}