diff options
author | Keith Randall <khr@golang.org> | 2014-12-10 17:02:58 -0800 |
---|---|---|
committer | Keith Randall <khr@golang.org> | 2014-12-22 22:41:01 +0000 |
commit | cda0ea1c0e06d1309f66423a8fd72e272d089b6c (patch) | |
tree | 5720fe98083a2945524142f33a9c6720eea19221 /src/runtime/hash64.go | |
parent | fbc56cf05015899aba236d5a68096a770de3ad0a (diff) | |
download | go-cda0ea1c0e06d1309f66423a8fd72e272d089b6c.tar.gz go-cda0ea1c0e06d1309f66423a8fd72e272d089b6c.zip |
runtime: a better fallback hash
For arm and powerpc, as well as x86 without aes instructions.
Contains a mixture of ideas from cityhash and xxhash.
Compared to our old fallback on ARM, it's ~no slower on
small objects and up to ~50% faster on large objects. More
importantly, it is a much better hash function and thus has
less chance of bad behavior.
Fixes #8737
benchmark old ns/op new ns/op delta
BenchmarkHash5 173 181 +4.62%
BenchmarkHash16 252 212 -15.87%
BenchmarkHash64 575 419 -27.13%
BenchmarkHash1024 7173 3995 -44.31%
BenchmarkHash65536 516940 313173 -39.42%
BenchmarkHashStringSpeed 300 279 -7.00%
BenchmarkHashBytesSpeed 478 424 -11.30%
BenchmarkHashInt32Speed 217 207 -4.61%
BenchmarkHashInt64Speed 262 231 -11.83%
BenchmarkHashStringArraySpeed 609 631 +3.61%
Change-Id: I0a9335028f32b10ad484966e3019987973afd3eb
Reviewed-on: https://go-review.googlesource.com/1360
Reviewed-by: Russ Cox <rsc@golang.org>
Diffstat (limited to 'src/runtime/hash64.go')
-rw-r--r-- | src/runtime/hash64.go | 96 |
1 files changed, 96 insertions, 0 deletions
diff --git a/src/runtime/hash64.go b/src/runtime/hash64.go new file mode 100644 index 0000000000..fc7eef45a4 --- /dev/null +++ b/src/runtime/hash64.go @@ -0,0 +1,96 @@ +// Copyright 2014 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. + +// Hashing algorithm inspired by +// xxhash: https://code.google.com/p/xxhash/ +// cityhash: https://code.google.com/p/cityhash/ + +// +build amd64 amd64p32 ppc64 ppc64le + +package runtime + +import "unsafe" + +const ( + // Constants for multiplication: four random odd 64-bit numbers. + m1 = 16877499708836156737 + m2 = 2820277070424839065 + m3 = 9497967016996688599 + m4 = 15839092249703872147 +) + +func memhash(p unsafe.Pointer, s, seed uintptr) uintptr { + if GOARCH == "amd64" && GOOS != "nacl" && useAeshash { + return aeshash(p, s, seed) + } + h := uint64(seed + s) +tail: + switch { + case s == 0: + case s < 4: + w := uint64(*(*byte)(p)) + w += uint64(*(*byte)(add(p, s>>1))) << 8 + w += uint64(*(*byte)(add(p, s-1))) << 16 + h ^= w * m1 + case s <= 8: + w := uint64(readUnaligned32(p)) + w += uint64(readUnaligned32(add(p, s-4))) << 32 + h ^= w * m1 + case s <= 16: + h ^= readUnaligned64(p) * m1 + h = rotl_31(h) * m2 + h = rotl_27(h) + h ^= readUnaligned64(add(p, s-8)) * m1 + case s <= 32: + h ^= readUnaligned64(p) * m1 + h = rotl_31(h) * m2 + h = rotl_27(h) + h ^= readUnaligned64(add(p, 8)) * m1 + h = rotl_31(h) * m2 + h = rotl_27(h) + h ^= readUnaligned64(add(p, s-16)) * m1 + h = rotl_31(h) * m2 + h = rotl_27(h) + h ^= readUnaligned64(add(p, s-8)) * m1 + default: + v1 := h + v2 := h + m1 + v3 := h + m2 + v4 := h + m3 + for s >= 32 { + v1 ^= readUnaligned64(p) * m1 + v1 = rotl_31(v1) * m2 + p = add(p, 8) + v2 ^= readUnaligned64(p) * m1 + v2 = rotl_31(v2) * m2 + p = add(p, 8) + v3 ^= readUnaligned64(p) * m1 + v3 = rotl_31(v3) * m2 + p = add(p, 8) + v4 ^= readUnaligned64(p) * m1 + v4 = rotl_31(v4) * m2 + p = add(p, 8) + s -= 32 + } + h = rotl_27(v1)*m1 + rotl_27(v2)*m2 + rotl_27(v3)*m3 + rotl_27(v4)*m4 + goto tail + } + + h ^= h >> 33 + h *= m2 + h ^= h >> 29 + h *= m3 + h ^= h >> 32 + return uintptr(h) +} + +// Note: in order to get the compiler to issue rotl instructions, we +// need to constant fold the shift amount by hand. +// TODO: convince the compiler to issue rotl instructions after inlining. +func rotl_31(x uint64) uint64 { + return (x << 31) | (x >> (64 - 31)) +} +func rotl_27(x uint64) uint64 { + return (x << 27) | (x >> (64 - 27)) +} |