runtime: using wyhash for memhashFallback on 64bit platform

wyhash is a general hash function that:

1. About 8-70% faster that internal maphash
2. Passed Smhasher, BigCrush and PractRand tests

name                  old time/op    new time/op    delta
Hash5                   28.9ns ± 0%    30.0ns ± 0%   +3.77%  (p=0.000 n=9+10)
Hash16                  32.4ns ± 0%    30.2ns ± 0%   -6.74%  (p=0.000 n=10+8)
Hash64                  52.4ns ± 0%    43.4ns ± 0%  -17.20%  (p=0.000 n=9+10)
Hash1024                 415ns ± 0%     258ns ± 2%  -37.89%  (p=0.000 n=10+10)
Hash65536               24.9µs ± 0%    14.6µs ± 0%  -41.22%  (p=0.000 n=9+9)
HashStringSpeed         50.2ns ± 4%    47.8ns ± 4%   -4.88%  (p=0.000 n=10+10)
HashBytesSpeed          90.1ns ± 7%    78.3ns ± 4%  -13.06%  (p=0.000 n=10+10)
HashInt32Speed          33.3ns ± 6%    33.6ns ± 4%     ~     (p=0.071 n=10+10)
HashInt64Speed          32.7ns ± 3%    34.0ns ± 3%   +4.05%  (p=0.000 n=9+10)
HashStringArraySpeed     131ns ± 2%     117ns ± 5%  -10.32%  (p=0.000 n=9+10)
FastrandHashiter        72.2ns ± 1%    75.7ns ±10%   +4.87%  (p=0.019 n=8+10)

name                  old speed      new speed      delta
Hash5                  173MB/s ± 0%   167MB/s ± 0%   -3.63%  (p=0.000 n=9+10)
Hash16                 494MB/s ± 0%   530MB/s ± 0%   +7.23%  (p=0.000 n=10+8)
Hash64                1.22GB/s ± 0%  1.48GB/s ± 0%  +20.77%  (p=0.000 n=9+10)
Hash1024              2.47GB/s ± 0%  3.97GB/s ± 2%  +61.01%  (p=0.000 n=8+10)
Hash65536             2.64GB/s ± 0%  4.48GB/s ± 0%  +70.13%  (p=0.000 n=9+9)

Change-Id: I76af4e2bc1995a18149d11983ea8a149c132865e
Reviewed-on: https://go-review.googlesource.com/c/go/+/279612
Trust: Meng Zhuo <mzh@golangcn.org>
Run-TryBot: Meng Zhuo <mzh@golangcn.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

1 files changed, 21 insertions, 0 deletions

diff --git a/src/runtime/internal/math/math.go b/src/runtime/internal/math/math.go
index 5385f5dd86..b6bd12d3e8 100644
--- a/src/runtime/internal/math/math.go
+++ b/src/runtime/internal/math/math.go
@@ -17,3 +17,24 @@ func MulUintptr(a, b uintptr) (uintptr, bool) {
 	overflow := b > MaxUintptr/a
 	return a * b, overflow
 }
+
+// Mul64 returns the 128-bit product of x and y: (hi, lo) = x * y
+// with the product bits' upper half returned in hi and the lower
+// half returned in lo.
+// This is a copy from math/bits.Mul64
+// On supported platforms this is an intrinsic lowered by the compiler.
+func Mul64(x, y uint64) (hi, lo uint64) {
+	const mask32 = 1<<32 - 1
+	x0 := x & mask32
+	x1 := x >> 32
+	y0 := y & mask32
+	y1 := y >> 32
+	w0 := x0 * y0
+	t := x1*y0 + w0>>32
+	w1 := t & mask32
+	w2 := t >> 32
+	w1 += x0 * y1
+	hi = x1*y1 + w2 + w1>>32
+	lo = x * y
+	return
+}