runtime: improve performance of empty map with interface key type

name                            old time/op    new time/op    delta
MegEmptyMapWithInterfaceKey-10    15.5µs ± 0%     0.0µs ± 0%  -99.97%  (p=0.000 n=20+16)

name                            old alloc/op   new alloc/op   delta
MegEmptyMapWithInterfaceKey-10     0.00B          0.00B          ~     (all equal)

name                            old allocs/op  new allocs/op  delta
MegEmptyMapWithInterfaceKey-10      0.00           0.00          ~     (all equal)

Change-Id: I46248223100e98b7877464da640075d272c14802
Reviewed-on: https://go-review.googlesource.com/c/go/+/502075
Reviewed-by: Keith Randall <khr@google.com>
Run-TryBot: xie cui <523516579@qq.com>
Reviewed-by: Heschi Kreinick <heschi@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 68 insertions, 0 deletions

diff --git a/src/runtime/alg.go b/src/runtime/alg.go
index a1f683f68a..336058d159 100644
--- a/src/runtime/alg.go
+++ b/src/runtime/alg.go
@@ -193,6 +193,74 @@ func typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {
 	}
 }
 
+func mapKeyError(t *maptype, p unsafe.Pointer) error {
+	if !t.HashMightPanic() {
+		return nil
+	}
+	return mapKeyError2(t.Key, p)
+}
+
+func mapKeyError2(t *_type, p unsafe.Pointer) error {
+	if t.TFlag&abi.TFlagRegularMemory != 0 {
+		return nil
+	}
+	switch t.Kind_ & kindMask {
+	case kindFloat32, kindFloat64, kindComplex64, kindComplex128, kindString:
+		return nil
+	case kindInterface:
+		i := (*interfacetype)(unsafe.Pointer(t))
+		var t *_type
+		var pdata *unsafe.Pointer
+		if len(i.Methods) == 0 {
+			a := (*eface)(p)
+			t = a._type
+			if t == nil {
+				return nil
+			}
+			pdata = &a.data
+		} else {
+			a := (*iface)(p)
+			if a.tab == nil {
+				return nil
+			}
+			t = a.tab._type
+			pdata = &a.data
+		}
+
+		if t.Equal == nil {
+			return errorString("hash of unhashable type " + toRType(t).string())
+		}
+
+		if isDirectIface(t) {
+			return mapKeyError2(t, unsafe.Pointer(pdata))
+		} else {
+			return mapKeyError2(t, *pdata)
+		}
+	case kindArray:
+		a := (*arraytype)(unsafe.Pointer(t))
+		for i := uintptr(0); i < a.Len; i++ {
+			if err := mapKeyError2(a.Elem, add(p, i*a.Elem.Size_)); err != nil {
+				return err
+			}
+		}
+		return nil
+	case kindStruct:
+		s := (*structtype)(unsafe.Pointer(t))
+		for _, f := range s.Fields {
+			if f.Name.IsBlank() {
+				continue
+			}
+			if err := mapKeyError2(f.Typ, add(p, f.Offset)); err != nil {
+				return err
+			}
+		}
+		return nil
+	default:
+		// Should never happen, keep this case for robustness.
+		return errorString("hash of unhashable type " + toRType(t).string())
+	}
+}
+
 //go:linkname reflect_typehash reflect.typehash
 func reflect_typehash(t *_type, p unsafe.Pointer, h uintptr) uintptr {
 	return typehash(t, p, h)