From 8a85a2e70a97773ac96e899df7411eda4f5da2cb Mon Sep 17 00:00:00 2001 From: Mateusz Poliwczak Date: Mon, 7 Apr 2025 15:21:16 +0200 Subject: runtime, internal/runtime/maps: speed-up empty/zero map lookups MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This lets the inliner do a better job optimizing the mapKeyError call. goos: linux goarch: amd64 pkg: runtime cpu: AMD Ryzen 5 4600G with Radeon Graphics │ /tmp/before2 │ /tmp/after3 │ │ sec/op │ sec/op vs base │ MapAccessZero/Key=int64-12 1.875n ± 0% 1.875n ± 0% ~ (p=0.506 n=25) MapAccessZero/Key=int32-12 1.875n ± 0% 1.875n ± 0% ~ (p=0.082 n=25) MapAccessZero/Key=string-12 1.902n ± 1% 1.902n ± 1% ~ (p=0.256 n=25) MapAccessZero/Key=mediumType-12 2.816n ± 0% 1.958n ± 0% -30.47% (p=0.000 n=25) MapAccessZero/Key=bigType-12 2.815n ± 0% 1.935n ± 0% -31.26% (p=0.000 n=25) MapAccessEmpty/Key=int64-12 1.942n ± 0% 2.109n ± 0% +8.60% (p=0.000 n=25) MapAccessEmpty/Key=int32-12 2.110n ± 0% 1.940n ± 0% -8.06% (p=0.000 n=25) MapAccessEmpty/Key=string-12 2.024n ± 0% 2.109n ± 0% +4.20% (p=0.000 n=25) MapAccessEmpty/Key=mediumType-12 3.157n ± 0% 2.344n ± 0% -25.75% (p=0.000 n=25) MapAccessEmpty/Key=bigType-12 3.054n ± 0% 2.115n ± 0% -30.75% (p=0.000 n=25) geomean 2.305n 2.011n -12.75% Change-Id: Iee83930884dc4c8a791a711aa189a1c93b68d536 Reviewed-on: https://go-review.googlesource.com/c/go/+/663495 Reviewed-by: Dmitri Shuralyov LUCI-TryBot-Result: Go LUCI Reviewed-by: Michael Pratt --- src/internal/runtime/maps/map.go | 86 ++++++++++++++++++++++++++++ src/internal/runtime/maps/runtime_noswiss.go | 17 ------ src/internal/runtime/maps/runtime_swiss.go | 3 - 3 files changed, 86 insertions(+), 20 deletions(-) delete mode 100644 src/internal/runtime/maps/runtime_noswiss.go (limited to 'src/internal/runtime') diff --git a/src/internal/runtime/maps/map.go b/src/internal/runtime/maps/map.go index 94000a942d..c5bd01490d 100644 --- a/src/internal/runtime/maps/map.go +++ b/src/internal/runtime/maps/map.go @@ -806,3 +806,89 @@ func (m *Map) Clone(typ *abi.SwissMapType) *Map { return m } + +func OldMapKeyError(t *abi.OldMapType, p unsafe.Pointer) error { + if !t.HashMightPanic() { + return nil + } + return mapKeyError2(t.Key, p) +} + +func mapKeyError(t *abi.SwissMapType, p unsafe.Pointer) error { + if !t.HashMightPanic() { + return nil + } + return mapKeyError2(t.Key, p) +} + +func mapKeyError2(t *abi.Type, p unsafe.Pointer) error { + if t.TFlag&abi.TFlagRegularMemory != 0 { + return nil + } + switch t.Kind() { + case abi.Float32, abi.Float64, abi.Complex64, abi.Complex128, abi.String: + return nil + case abi.Interface: + i := (*abi.InterfaceType)(unsafe.Pointer(t)) + var t *abi.Type + var pdata *unsafe.Pointer + if len(i.Methods) == 0 { + a := (*abi.EmptyInterface)(p) + t = a.Type + if t == nil { + return nil + } + pdata = &a.Data + } else { + a := (*abi.NonEmptyInterface)(p) + if a.ITab == nil { + return nil + } + t = a.ITab.Type + pdata = &a.Data + } + + if t.Equal == nil { + return unhashableTypeError{t} + } + + if t.Kind_&abi.KindDirectIface != 0 { + return mapKeyError2(t, unsafe.Pointer(pdata)) + } else { + return mapKeyError2(t, *pdata) + } + case abi.Array: + a := (*abi.ArrayType)(unsafe.Pointer(t)) + for i := uintptr(0); i < a.Len; i++ { + if err := mapKeyError2(a.Elem, unsafe.Pointer(uintptr(p)+i*a.Elem.Size_)); err != nil { + return err + } + } + return nil + case abi.Struct: + s := (*abi.StructType)(unsafe.Pointer(t)) + for _, f := range s.Fields { + if f.Name.IsBlank() { + continue + } + if err := mapKeyError2(f.Typ, unsafe.Pointer(uintptr(p)+f.Offset)); err != nil { + return err + } + } + return nil + default: + // Should never happen, keep this case for robustness. + return unhashableTypeError{t} + } +} + +type unhashableTypeError struct{ typ *abi.Type } + +func (unhashableTypeError) RuntimeError() {} + +func (e unhashableTypeError) Error() string { return "hash of unhashable type: " + typeString(e.typ) } + +// Pushed from runtime +// +//go:linkname typeString +func typeString(typ *abi.Type) string diff --git a/src/internal/runtime/maps/runtime_noswiss.go b/src/internal/runtime/maps/runtime_noswiss.go deleted file mode 100644 index c9342e08dd..0000000000 --- a/src/internal/runtime/maps/runtime_noswiss.go +++ /dev/null @@ -1,17 +0,0 @@ -// Copyright 2024 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -//go:build !goexperiment.swissmap - -package maps - -import ( - "internal/abi" - "unsafe" -) - -// For testing, we don't ever need key errors. -func mapKeyError(typ *abi.SwissMapType, p unsafe.Pointer) error { - return nil -} diff --git a/src/internal/runtime/maps/runtime_swiss.go b/src/internal/runtime/maps/runtime_swiss.go index 3f4f970fb7..3ea018185b 100644 --- a/src/internal/runtime/maps/runtime_swiss.go +++ b/src/internal/runtime/maps/runtime_swiss.go @@ -17,9 +17,6 @@ import ( // Functions below pushed from runtime. -//go:linkname mapKeyError -func mapKeyError(typ *abi.SwissMapType, p unsafe.Pointer) error - // Pushed from runtime in order to use runtime.plainError // //go:linkname errNilAssign -- cgit v1.3