Skip to content

Commit cd055c9

Browse files
grantnelson-wfgrantnelson-wf
committed
Update hash/maphash
1 parent ff493e4 commit cd055c9

File tree

1 file changed

+66
-30
lines changed

1 file changed

+66
-30
lines changed

‎compiler/natives/src/hash/maphash/maphash.go

Lines changed: 66 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -3,31 +3,58 @@
33

44
package maphash
55

6-
// used in hash{32,64}.go to seed the hash function
7-
var hashkey [4]uint32
6+
import (
7+
_ "unsafe" // for linkname
8+
)
9+
10+
// hashkey is similar how it is defined in runtime/alg.go for Go 1.19
11+
// to be used in hash{32,64}.go to seed the hash function as part of
12+
// runtime_memhash. We're using locally defined memhash so it got moved here.
13+
var hashkey [3]uint32
814

915
func init() {
1016
for i := range hashkey {
11-
hashkey[i] = uint32(runtime_fastrand64())
17+
hashkey[i] = runtime_fastrand() | 1
18+
// The `| 1` is to make sure these numbers are odd
1219
}
13-
hashkey[0] |= 1 // make sure these numbers are odd
14-
hashkey[1] |= 1
15-
hashkey[2] |= 1
16-
hashkey[3] |= 1
1720
}
1821

19-
func _rthash(b []byte, seed uint64) uint64 {
22+
//go:linkname runtime_fastrand runtime.fastrand
23+
func runtime_fastrand() uint32
24+
25+
// Bytes uses less efficient equivalent to avoid using unsafe.
26+
func Bytes(seed Seed, b []byte) uint64 {
27+
var h Hash
28+
h.SetSeed(seed)
29+
_, _ = h.Write(b)
30+
return h.Sum64()
31+
}
32+
33+
// String uses less efficient equivalent to avoid using unsafe.
34+
func String(seed Seed, s string) uint64 {
35+
var h Hash
36+
h.SetSeed(seed)
37+
_, _ = h.WriteString(s)
38+
return h.Sum64()
39+
}
40+
41+
// rthash is similar to the Go 1.19.13 version
42+
// with the call to memhash changed to not use unsafe pointers.
43+
func rthash(b []byte, seed uint64) uint64 {
2044
if len(b) == 0 {
2145
return seed
2246
}
2347
// The runtime hasher only works on uintptr. Since GopherJS implements a
2448
// 32-bit environment, we use two parallel hashers on the lower and upper 32
2549
// bits.
26-
lo := memhash(b, uint32(seed), uint32(len(b)))
27-
hi := memhash(b, uint32(seed>>32), uint32(len(b)))
50+
lo := memhash(b, uint32(seed))
51+
hi := memhash(b, uint32(seed>>32))
2852
return uint64(hi)<<32 | uint64(lo)
2953
}
3054

55+
//gopherjs:purge to remove link using unsafe pointers, use memhash instead.
56+
func runtime_memhash()
57+
3158
// The implementation below is adapted from the upstream runtime/hash32.go
3259
// and avoids use of unsafe, which GopherJS doesn't support well and leads to
3360
// worse performance.
@@ -38,8 +65,9 @@ func _rthash(b []byte, seed uint64) uint64 {
3865
//
3966
// Hashing algorithm inspired by wyhash:
4067
// https://github.com/wangyi-fudan/wyhash/blob/ceb019b530e2c1c14d70b79bfa2bc49de7d95bc1/Modern%20Non-Cryptographic%20Hash%20Function%20and%20Pseudorandom%20Number%20Generator.pdf
41-
func memhash(p []byte, seed uint32, s uint32) uintptr {
42-
a, b := mix32(uint32(seed), uint32(s^hashkey[0]))
68+
func memhash(p []byte, seed uint32) uintptr {
69+
s := len(p)
70+
a, b := mix32(uint32(seed), uint32(s)^hashkey[0])
4371
if s == 0 {
4472
return uintptr(a ^ b)
4573
}
@@ -63,7 +91,7 @@ func memhash(p []byte, seed uint32, s uint32) uintptr {
6391
return uintptr(a ^ b)
6492
}
6593

66-
func add(p []byte, x uint32) []byte {
94+
func add(p []byte, x int) []byte {
6795
return p[x:]
6896
}
6997

@@ -80,51 +108,59 @@ func mix32(a, b uint32) (uint32, uint32) {
80108
/*
81109
The following functions were modified in Go 1.17 to improve performance,
82110
but at the expense of being unsafe, and thus incompatible with GopherJS.
83-
To compensate, we have reverted these to the unoptimized Go 1.16 versions
84-
for now.
111+
See https://cs.opensource.google/go/go/+/refs/tags/go1.19.13:src/hash/maphash/maphash.go;
112+
To compensate, we use a simplified version of each method from Go 1.19.13,
113+
similar to Go 1.16's versions, with the call to rthash changed to not use unsafe pointers.
85114
86115
See upstream issue https://github.com/golang/go/issues/47342 to implement
87116
a purego version of this package, which should render this hack (and
88117
likely this entire file) obsolete.
89118
*/
90119

91-
// Write is borrowed from Go 1.16.
120+
// Write is a simplification from Go 1.19 changed to not use unsafe.
92121
func (h *Hash) Write(b []byte) (int, error) {
93122
size := len(b)
94-
for h.n+len(b) > len(h.buf) {
95-
k := copy(h.buf[h.n:], b)
96-
h.n = len(h.buf)
97-
b = b[k:]
98-
h.flush()
123+
if h.n+len(b) > bufSize {
124+
h.initSeed()
125+
for h.n+len(b) > bufSize {
126+
k := copy(h.buf[h.n:], b)
127+
h.state.s = rthash(h.buf[:], h.state.s)
128+
b = b[k:]
129+
h.n = 0
130+
}
99131
}
100132
h.n += copy(h.buf[h.n:], b)
101133
return size, nil
102134
}
103135

104-
// WriteString is borrowed from Go 1.16.
136+
// WriteString is a simplification from Go 1.19 changed to not use unsafe.
105137
func (h *Hash) WriteString(s string) (int, error) {
106138
size := len(s)
107-
for h.n+len(s) > len(h.buf) {
108-
k := copy(h.buf[h.n:], s)
109-
h.n = len(h.buf)
110-
s = s[k:]
111-
h.flush()
139+
if h.n+len(s) > bufSize {
140+
h.initSeed()
141+
for h.n+len(s) > bufSize {
142+
k := copy(h.buf[h.n:], s)
143+
h.state.s = rthash(h.buf[:], h.state.s)
144+
s = s[k:]
145+
h.n = 0
146+
}
112147
}
113148
h.n += copy(h.buf[h.n:], s)
114149
return size, nil
115150
}
116151

152+
// flush is the Go 1.19 version changed to not use unsafe.
117153
func (h *Hash) flush() {
118154
if h.n != len(h.buf) {
119155
panic("maphash: flush of partially full buffer")
120156
}
121157
h.initSeed()
122-
h.state.s = _rthash(h.buf[:], h.state.s)
158+
h.state.s = rthash(h.buf[:], h.state.s)
123159
h.n = 0
124160
}
125161

126-
// Sum64 is borrowed from Go 1.16.
162+
// Sum64 is the Go 1.19 version changed to not use unsafe.
127163
func (h *Hash) Sum64() uint64 {
128164
h.initSeed()
129-
return _rthash(h.buf[:h.n], h.state.s)
165+
return rthash(h.buf[:h.n], h.state.s)
130166
}

0 commit comments

Comments
 (0)