diff options
| author | Michael Pratt <mpratt@google.com> | 2024-08-21 16:17:16 -0400 |
|---|---|---|
| committer | Gopher Robot <gobot@golang.org> | 2024-10-28 21:25:50 +0000 |
| commit | cd54b9bae94b36f67869ef174cbb432bc4012183 (patch) | |
| tree | 95771c1b1e79fb4650dc144d3dae56bdf803ea31 /src/internal/runtime/maps | |
| parent | 775837f51f03245bcba333094b4b3742f8fbfca3 (diff) | |
| download | go-cd54b9bae94b36f67869ef174cbb432bc4012183.tar.xz | |
internal/runtime/maps: shift optimizations
Masking the shift lets the compiler elide a few instructions for
handling a shift of > 63 bits.
For #54766.
Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I669fe01caa1de1b8521f1f56b6906f3e9066a39b
Reviewed-on: https://go-review.googlesource.com/c/go/+/611190
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Diffstat (limited to 'src/internal/runtime/maps')
| -rw-r--r-- | src/internal/runtime/maps/map.go | 20 |
1 files changed, 14 insertions, 6 deletions
diff --git a/src/internal/runtime/maps/map.go b/src/internal/runtime/maps/map.go index a4fa07635a..67e4bd6811 100644 --- a/src/internal/runtime/maps/map.go +++ b/src/internal/runtime/maps/map.go @@ -233,11 +233,22 @@ type Map struct { // The number of bits to use in table directory lookups. globalDepth uint8 + // The number of bits to shift out of the hash for directory lookups. + // On 64-bit systems, this is 64 - globalDepth. + globalShift uint8 + // clearSeq is a sequence counter of calls to Clear. It is used to // detect map clears during iteration. clearSeq uint64 } +func depthToShift(depth uint8) uint8 { + if goarch.PtrSize == 4 { + return 32 - depth + } + return 64 - depth +} + func NewMap(mt *abi.SwissMapType, capacity uint64) *Map { if capacity < abi.SwissMapGroupSlots { // TODO: temporary to simplify initial implementation. @@ -259,6 +270,7 @@ func NewMap(mt *abi.SwissMapType, capacity uint64) *Map { //directory: make([]*table, dirSize), globalDepth: globalDepth, + globalShift: depthToShift(globalDepth), } if capacity > abi.SwissMapGroupSlots { @@ -294,12 +306,7 @@ func (m *Map) directoryIndex(hash uintptr) uintptr { if m.dirLen == 1 { return 0 } - // TODO(prattmic): Store the shift as globalShift, as we need that more - // often than globalDepth. - if goarch.PtrSize == 4 { - return hash >> (32 - m.globalDepth) - } - return hash >> (64 - m.globalDepth) + return hash >> (m.globalShift & 63) } func (m *Map) directoryAt(i uintptr) *table { @@ -338,6 +345,7 @@ func (m *Map) installTableSplit(old, left, right *table) { } } m.globalDepth++ + m.globalShift-- //m.directory = newDir m.dirPtr = unsafe.Pointer(&newDir[0]) m.dirLen = len(newDir) |