From 0b0cc4154e1defed07e73ca1304b9a68c7134577 Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Wed, 23 Aug 2017 07:49:25 -0700 Subject: [PATCH] runtime: refactor walking of bucket overflows MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This eliminates a nil check of b while evaluating b.tophash, which is in the inner loop of many hot map functions. It also makes the code a bit clearer. Also remove some gotos in favor of labeled breaks. On non-x86 architectures, this change introduces a pointless reg-reg move, although the cause is well-understood (#21572). Change-Id: Ib7ee58b59ea5463b92e1590c8b8f5c0ef87d410a Reviewed-on: https://go-review.googlesource.com/58372 Run-TryBot: Josh Bleecher Snyder TryBot-Result: Gobot Gobot Reviewed-by: Martin Möhrmann Reviewed-by: Keith Randall --- src/runtime/hashmap.go | 31 +++++----------- src/runtime/hashmap_fast.go | 72 +++++++++++-------------------------- 2 files changed, 30 insertions(+), 73 deletions(-) diff --git a/src/runtime/hashmap.go b/src/runtime/hashmap.go index df4df053d1..422ccfd41a 100644 --- a/src/runtime/hashmap.go +++ b/src/runtime/hashmap.go @@ -400,7 +400,7 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { } } top := tophash(hash) - for { + for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { continue @@ -417,11 +417,8 @@ func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { return v } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]) - } } + return unsafe.Pointer(&zeroVal[0]) } func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { @@ -455,7 +452,7 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) } } top := tophash(hash) - for { + for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { continue @@ -472,11 +469,8 @@ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) return v, true } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]), false - } } + return unsafe.Pointer(&zeroVal[0]), false } // returns both key and value. Used by map iterator @@ -499,7 +493,7 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe } } top := tophash(hash) - for { + for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { continue @@ -516,11 +510,8 @@ func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe return k, v } } - b = b.overflow(t) - if b == nil { - return nil, nil - } } + return nil, nil } func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer { @@ -681,7 +672,8 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) top := tophash(hash) - for { +search: + for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { continue @@ -711,15 +703,10 @@ func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { } b.tophash[i] = empty h.count-- - goto done - } - b = b.overflow(t) - if b == nil { - goto done + break search } } -done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } diff --git a/src/runtime/hashmap_fast.go b/src/runtime/hashmap_fast.go index f43d005a5b..befc4794fb 100644 --- a/src/runtime/hashmap_fast.go +++ b/src/runtime/hashmap_fast.go @@ -39,17 +39,14 @@ func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { } } } - for { + 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 { return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)) } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]) - } } + return unsafe.Pointer(&zeroVal[0]) } func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { @@ -82,17 +79,14 @@ func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) { } } } - for { + 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 { return add(unsafe.Pointer(b), dataOffset+bucketCnt*4+i*uintptr(t.valuesize)), true } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]), false - } } + return unsafe.Pointer(&zeroVal[0]), false } func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { @@ -125,17 +119,14 @@ func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer { } } } - for { + 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 { return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)) } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]) - } } + return unsafe.Pointer(&zeroVal[0]) } func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { @@ -168,17 +159,14 @@ func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) { } } } - for { + 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 { return add(unsafe.Pointer(b), dataOffset+bucketCnt*8+i*uintptr(t.valuesize)), true } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]), false - } } + return unsafe.Pointer(&zeroVal[0]), false } func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer { @@ -256,7 +244,7 @@ dohash: } } top := tophash(hash) - for { + for ; b != nil; b = b.overflow(t) { 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] != top { @@ -266,11 +254,8 @@ dohash: return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)) } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]) - } } + return unsafe.Pointer(&zeroVal[0]) } func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) { @@ -348,7 +333,7 @@ dohash: } } top := tophash(hash) - for { + for ; b != nil; b = b.overflow(t) { 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] != top { @@ -358,11 +343,8 @@ dohash: return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true } } - b = b.overflow(t) - if b == nil { - return unsafe.Pointer(&zeroVal[0]), false - } } + return unsafe.Pointer(&zeroVal[0]), false } func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer { @@ -647,7 +629,8 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) { growWork(t, h, bucket) } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) - for { +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 { continue @@ -663,15 +646,10 @@ func mapdelete_fast32(t *maptype, h *hmap, key uint32) { } b.tophash[i] = empty h.count-- - goto done - } - b = b.overflow(t) - if b == nil { - goto done + break search } } -done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } @@ -700,7 +678,8 @@ func mapdelete_fast64(t *maptype, h *hmap, key uint64) { growWork(t, h, bucket) } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) - for { +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 { continue @@ -716,15 +695,10 @@ func mapdelete_fast64(t *maptype, h *hmap, key uint64) { } b.tophash[i] = empty h.count-- - goto done - } - b = b.overflow(t) - if b == nil { - goto done + break search } } -done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } @@ -755,7 +729,8 @@ func mapdelete_faststr(t *maptype, h *hmap, ky string) { } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) top := tophash(hash) - for { +search: + for ; b != nil; b = b.overflow(t) { 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] != top { @@ -772,15 +747,10 @@ func mapdelete_faststr(t *maptype, h *hmap, ky string) { } b.tophash[i] = empty h.count-- - goto done - } - b = b.overflow(t) - if b == nil { - goto done + break search } } -done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } -- 2.48.1