runtime: use 32-bit hash for maps on Wasm

Currently we use 64-bit hash calculations on Wasm. The 64-bit hash
calculation make intensive uses of 64x64->128 bit multiplications,
which on many 64-bit platforms are compiler intrinsics and can be
compiled to one or two instructions. This is not the case on Wasm,
so it is not very performant.

This CL makes it use 32-bit hashes on Wasm, just like other 32-bit
architectures. The 32-bit hash calculation only uses 32x32->64 bit
multiplications, which can be compiled efficiently on Wasm.

Using 32-bit hashes may increase the chance of collisions. But it
is the same as 32-bit architectures like 386. And our Wasm port
supports only 32-bit address space (like 386), so this is not too
bad.

Runtime Hash benchmark results
goos: js
goarch: wasm
pkg: runtime
                     │   0h.txt    │               1h.txt                │
                     │   sec/op    │   sec/op     vs base                │
Hash5                  20.45n ± 9%   14.06n ± 2%  -31.21% (p=0.000 n=10)
Hash16                 22.34n ± 7%   17.52n ± 1%  -21.62% (p=0.000 n=10)
Hash64                 47.47n ± 3%   28.68n ± 1%  -39.59% (p=0.000 n=10)
Hash1024               475.4n ± 1%   271.4n ± 0%  -42.92% (p=0.000 n=10)
Hash65536              28.42µ ± 1%   16.66µ ± 0%  -41.40% (p=0.000 n=10)
HashStringSpeed        40.07n ± 7%   29.23n ± 1%  -27.05% (p=0.000 n=10)
HashBytesSpeed         62.01n ± 3%   46.11n ± 4%  -25.64% (p=0.000 n=10)
HashInt32Speed         24.31n ± 2%   20.39n ± 1%  -16.13% (p=0.000 n=10)
HashInt64Speed         25.48n ± 7%   20.81n ± 7%  -18.29% (p=0.000 n=10)
HashStringArraySpeed   87.69n ± 4%   76.65n ± 2%  -12.58% (p=0.000 n=10)
FastrandHashiter       87.65n ± 1%   87.65n ± 1%        ~ (p=0.896 n=10)
geomean                90.82n        67.03n       -26.19%

Map benchmarks are too many to post here. The speedups are around
0-40%.

Change-Id: I2f7a68cfc446ab5a547fdb6a40aea07854516d51
Reviewed-on: https://go-review.googlesource.com/c/go/+/714600
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Michael Pratt <mpratt@google.com>

3 files changed, 25 insertions, 12 deletions

diff --git a/src/runtime/alg.go b/src/runtime/alg.go
index b956f9d05a..c5951dc20b 100644
--- a/src/runtime/alg.go
+++ b/src/runtime/alg.go
@@ -14,10 +14,23 @@ import (
 )
 
 const (
-	c0 = uintptr((8-goarch.PtrSize)/4*2860486313 + (goarch.PtrSize-4)/4*33054211828000289)
-	c1 = uintptr((8-goarch.PtrSize)/4*3267000013 + (goarch.PtrSize-4)/4*23344194077549503)
+	// We use 32-bit hash on Wasm, see hash32.go.
+	hashSize = (1-goarch.IsWasm)*goarch.PtrSize + goarch.IsWasm*4
+	c0       = uintptr((8-hashSize)/4*2860486313 + (hashSize-4)/4*33054211828000289)
+	c1       = uintptr((8-hashSize)/4*3267000013 + (hashSize-4)/4*23344194077549503)
 )
 
+func trimHash(h uintptr) uintptr {
+	if goarch.IsWasm != 0 {
+		// On Wasm, we use 32-bit hash, despite that uintptr is 64-bit.
+		// memhash* always returns a uintptr with high 32-bit being 0
+		// (see hash32.go). We trim the hash in other places where we
+		// compute the hash manually, e.g. in interhash.
+		return uintptr(uint32(h))
+	}
+	return h
+}
+
 func memhash0(p unsafe.Pointer, h uintptr) uintptr {
 	return h
 }
@@ -100,9 +113,9 @@ func f32hash(p unsafe.Pointer, h uintptr) uintptr {
 	f := *(*float32)(p)
 	switch {
 	case f == 0:
-		return c1 * (c0 ^ h) // +0, -0
+		return trimHash(c1 * (c0 ^ h)) // +0, -0
 	case f != f:
-		return c1 * (c0 ^ h ^ uintptr(rand())) // any kind of NaN
+		return trimHash(c1 * (c0 ^ h ^ uintptr(rand()))) // any kind of NaN
 	default:
 		return memhash(p, h, 4)
 	}
@@ -112,9 +125,9 @@ func f64hash(p unsafe.Pointer, h uintptr) uintptr {
 	f := *(*float64)(p)
 	switch {
 	case f == 0:
-		return c1 * (c0 ^ h) // +0, -0
+		return trimHash(c1 * (c0 ^ h)) // +0, -0
 	case f != f:
-		return c1 * (c0 ^ h ^ uintptr(rand())) // any kind of NaN
+		return trimHash(c1 * (c0 ^ h ^ uintptr(rand()))) // any kind of NaN
 	default:
 		return memhash(p, h, 8)
 	}
@@ -145,9 +158,9 @@ func interhash(p unsafe.Pointer, h uintptr) uintptr {
 		panic(errorString("hash of unhashable type " + toRType(t).string()))
 	}
 	if t.IsDirectIface() {
-		return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0)
+		return trimHash(c1 * typehash(t, unsafe.Pointer(&a.data), h^c0))
 	} else {
-		return c1 * typehash(t, a.data, h^c0)
+		return trimHash(c1 * typehash(t, a.data, h^c0))
 	}
 }
 
@@ -172,9 +185,9 @@ func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
 		panic(errorString("hash of unhashable type " + toRType(t).string()))
 	}
 	if t.IsDirectIface() {
-		return c1 * typehash(t, unsafe.Pointer(&a.data), h^c0)
+		return trimHash(c1 * typehash(t, unsafe.Pointer(&a.data), h^c0))
 	} else {
-		return c1 * typehash(t, a.data, h^c0)
+		return trimHash(c1 * typehash(t, a.data, h^c0))
 	}
 }
 
diff --git a/src/runtime/hash32.go b/src/runtime/hash32.go
index 0616c7dd05..8589893127 100644
--- a/src/runtime/hash32.go
+++ b/src/runtime/hash32.go
@@ -5,7 +5,7 @@
 // Hashing algorithm inspired by
 // wyhash: https://github.com/wangyi-fudan/wyhash/blob/ceb019b530e2c1c14d70b79bfa2bc49de7d95bc1/Modern%20Non-Cryptographic%20Hash%20Function%20and%20Pseudorandom%20Number%20Generator.pdf
 
-//go:build 386 || arm || mips || mipsle
+//go:build 386 || arm || mips || mipsle || wasm
 
 package runtime
 
diff --git a/src/runtime/hash64.go b/src/runtime/hash64.go
index 124bb7d77a..ac26e660c6 100644
--- a/src/runtime/hash64.go
+++ b/src/runtime/hash64.go
@@ -5,7 +5,7 @@
 // Hashing algorithm inspired by
 // wyhash: https://github.com/wangyi-fudan/wyhash
 
-//go:build amd64 || arm64 || loong64 || mips64 || mips64le || ppc64 || ppc64le || riscv64 || s390x || wasm
+//go:build amd64 || arm64 || loong64 || mips64 || mips64le || ppc64 || ppc64le || riscv64 || s390x
 
 package runtime