Skip to content

Commit a754796

Browse files
twmbtwmb
committed
murmur3: branchless tail from the input's last block; Sum64 inlines
A switch on the tail length compiles to a jump table, and on varying key lengths that indirect branch mispredicts nearly every time: perf counted 0.94 mispredicts per hash against the assembly's 0.30 on a mixed length stream, and the Go code was 34 percent slower there. Once an input has had a full block its last 16 bytes are always in bounds, so the tail is read out of them with two overlapping loads and shifts chosen by the length, before the block loop so only two words stay live across it. Inputs shorter than a block keep the switch. Random lengths in [0, 64) now cost 89 cycles a hash against the assembly's 110 and the previous code's 98, and every fixed length is equal or better. Sum64 and friends call sum128 directly: going through the Sum128 wrapper put them at inline cost 86 against a budget of 80, one extra call per hash, and entering the loop through that call was 6 percent slower at 8 KiB.
1 parent 9ec5a0e commit a754796

5 files changed

Lines changed: 221 additions & 128 deletions

File tree

‎README.md‎

Lines changed: 57 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -39,8 +39,10 @@ Assembly
3939
Earlier versions shipped hand rolled amd64 assembly for the 64 and 128 bit
4040
sums. That assembly was removed once the compiler's output caught up: as of
4141
Go 1.27, the pure Go code is faster than the old assembly for every input
42-
under 32 bytes and within 3 to 8 percent above that. The 32 bit assembly was
43-
removed for the same reason back in Go 1.11. See the benchmarks below.
42+
under 64 bytes, for keys of varying length, and for every 32 bit sum, and 3
43+
to 9 percent slower on fixed inputs of 256 bytes and more. The 32 bit
44+
assembly was removed for the same reason back in Go 1.11. See the benchmarks
45+
below.
4446

4547
Testing
4648
=======
@@ -64,24 +66,29 @@ frequency and thermal throttling drop out. `asm` is the hand rolled amd64
6466
assembly this library used to ship, `old Go` is the pure Go path every other
6567
architecture ran before, and `new Go` is the current code. The `Sizes` rows
6668
hash the block loop; the `Branches` rows hash 0 to 16 bytes and exercise the
67-
tail. Each row includes a few cycles of benchmark harness.
69+
tail; the `RandomLengths` rows draw a fresh xorshift length in [0, 64) on
70+
every call, which is what a real key stream looks like to the branch
71+
predictor. Each row includes a few cycles of benchmark harness.
6872

6973
```
70-
benchmark asm old Go new Go new/asm new/old
71-
128Sizes/8192 4212 4477 4354 +3.4% -2.7%
72-
128Sizes/1024 534 574 558 +4.6% -2.7%
73-
128Sizes/256 140 156 151 +7.9% -3.6%
74-
128Sizes/64 48 52 50 +4.4% -4.3%
75-
128Sizes/32 35 36 35 -0.8% -2.8%
76-
128Branches/16 26 23 26 -1.3% +10.8%
77-
128Branches/13 25 34 22 -12.6% -35.6%
78-
128Branches/7 26 26 22 -14.4% -15.9%
79-
128Branches/3 25 22 21 -16.5% -2.9%
80-
64Sizes/8192 4217 4532 4357 +3.3% -3.9%
81-
32Sizes/8192 10076 10048 9765 -3.1% -2.8%
82-
32Sizes/64 89 89 80 -10.1% -10.1%
83-
32Sizes/32 50 50 44 -10.9% -10.8%
84-
32Branches/3 15 15 17 +12.3% +12.4%
74+
benchmark asm old Go new Go new/asm new/old
75+
128Sizes/8192 4213 4479 4387 +4.1% -2.1%
76+
128Sizes/1024 534 574 569 +6.6% -0.9%
77+
128Sizes/256 140 156 152 +8.6% -2.9%
78+
128Sizes/64 48 52 49 +1.4% -7.1%
79+
128Sizes/32 35 36 34 -2.6% -4.2%
80+
128Branches/16 26 23 25 -5.1% +6.6%
81+
128Branches/13 25 34 21 -14.4% -37.0%
82+
128Branches/7 26 26 21 -18.2% -19.7%
83+
128Branches/3 25 22 21 -16.5% -3.0%
84+
64Sizes/8192 4215 4530 4332 +2.8% -4.4%
85+
64Sizes/32 35 38 34 -3.1% -10.2%
86+
32Sizes/8192 10074 10045 9897 -1.8% -1.5%
87+
32Sizes/64 88 88 78 -11.5% -11.5%
88+
32Sizes/32 50 50 42 -14.6% -14.5%
89+
32Branches/3 15 15 16 +5.6% +5.7%
90+
RandomLengths128 110 96 89 -19.0% -6.8%
91+
RandomLengths32 95 96 87 -8.8% -9.3%
8592
```
8693

8794
Per 16 byte block that is 8.2 cycles for the assembly and 8.5 for the Go
@@ -91,23 +98,38 @@ floor is 7.3 cycles and ports 0, 1 and 6 each run 75 to 80 percent busy; the
9198
measured 8.5 is scheduling slack on top of that. The assembly has slack on
9299
every port and sits on its dependency chain instead: the four 64 bit
93100
multiplies and the rotates are off that chain, and what is left is h1 to h2
94-
through two three operand LEAs at three cycles each.
95-
96-
The one change that helped was the strictly greater loop bound, which
97-
removes the zero length pointer guard the compiler emits after every reslice,
98-
four micro ops per block, without touching the arithmetic. Everything else
99-
was measured and lost: unrolling two or four blocks per iteration, hoisting
100-
the constants into registers, folding the two adds by hand, and moving the
101-
loop into its own function. Cutting micro ops only wins if the h1 to h2 chain
102-
stays at the five cycles the compiler's own folding of 5*c1 + c2 gives it, and
103-
which registers the allocator hands out decides whether a three address add
104-
is an ADD or an LEA. Byte identical loops landed anywhere from 8.5 to 11
105-
cycles per block on that alone. That also makes the result a property of the
106-
compiler version: Go 1.26 and 1.27 both produce the 8.5 cycle loop from this
107-
source, while Go 1.25 emits four more instructions for it and lands at 9.5,
108-
slower than the two block unroll it replaced. GOAMD64=v3 changes nothing.
101+
through two three operand LEAs at three cycles each. The one loop change that
102+
helped was the strictly greater bound, which removes the zero length pointer
103+
guard the compiler emits after every reslice, four micro ops per block,
104+
without touching the arithmetic. Everything else was measured and lost:
105+
unrolling two or four blocks per iteration, hoisting the constants into
106+
registers, folding the two adds by hand, and moving the loop into its own
107+
function. Cutting micro ops only wins if the h1 to h2 chain stays at the five
108+
cycles the compiler's own folding of 5*c1 + c2 gives it, and which registers
109+
the allocator hands out decides whether a three address add is an ADD or an
110+
LEA. Byte identical loops landed anywhere from 8.5 to 11 cycles per block on
111+
that alone. That also makes the result a property of the compiler version:
112+
Go 1.26 and 1.27 both produce the 8.5 cycle loop from this source, while Go
113+
1.25 emits four more instructions for it and lands at 9.5. GOAMD64=v3
114+
changes nothing.
115+
116+
The tail is where the two differ most, in both directions. On a fixed length
117+
every branch in a tail is perfectly predicted, and the Go code wins by
118+
reading the tail in two or three word sized loads where the assembly walks a
119+
tree of byte loads. On varying lengths a switch on the tail length is a jump
120+
table, an indirect branch that mispredicts nearly every time the length
121+
changes, and each miss is about 20 cycles: on a mixed stream the first
122+
version of this code took 0.94 mispredicts per hash to the assembly's 0.30
123+
and was 34 percent slower. So once an input has had a full block, the tail is
124+
read out of the input's last 16 bytes, which are always in bounds, with two
125+
overlapping loads and shifts that the length selects without a branch, and
126+
this happens before the block loop so that only two words stay live across
127+
it. Only inputs shorter than one block take the switch. That is what the
128+
RandomLengths rows measure: 19 percent under the assembly for 128 bit sums
129+
and 9 percent for 32 bit. Sum64 and its variants call the shared
130+
implementation directly rather than through Sum128, which kept them under
131+
the inliner's budget and saves a call per hash.
109132

110133
The 32 bit sum is bound by its own four cycle per block dependency chain and
111134
sits at 4.8 with every port under 80 percent busy; nothing above the
112-
algorithm changes that. The strict bound
113-
is what it gains at 32 to 64 bytes.
135+
algorithm changes that. The strict bound is what it gains at 32 to 64 bytes.

‎murmur128_gen.go‎

Lines changed: 95 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -38,74 +38,103 @@ func SeedStringSum128(seed1, seed2 uint64, data string) (h1 uint64, h2 uint64) {
3838
// with clen, the total number of bytes hashed. The one shot sums pass all
3939
// of their input; the streaming digest passes its leftover tail.
4040
func sum128[T bytestring](h1, h2 uint64, data T, clen int) (uint64, uint64) {
41-
// The bound is strictly greater so the reslice can never leave zero
42-
// bytes, which lets the compiler drop the pointer guard it otherwise
43-
// emits for that case; the block that can be left over is taken below.
44-
// Unrolling does not pay once the guard is gone: the loop is bound by
45-
// the multiply port and the h1 to h2 chain, not by instruction count.
46-
for len(data) > 16 {
47-
h1, h2 = mix128(h1, h2, load64(data), load64(data[8:]))
48-
data = data[16:]
49-
}
5041
if len(data) >= 16 {
51-
h1, h2 = mix128(h1, h2, load64(data), load64(data[8:]))
52-
data = data[16:]
53-
}
42+
// With at least one full block, the last 16 bytes of the input are
43+
// always in bounds, and the tail is whatever of them the block loop
44+
// will not consume. Read it out of them here with two overlapping
45+
// loads instead of branching on its length afterwards: a switch on
46+
// the length is a jump table, and on varying key lengths it
47+
// mispredicts nearly every time. Doing it before the loop also
48+
// leaves only two words live across the loop and hides the loads
49+
// behind it. k1 is the first eight tail bytes, loaded exactly when
50+
// n >= 8 and otherwise shifted down out of the last eight bytes;
51+
// k2 is whatever sits above those. A shift of 64 or more is zero
52+
// in Go, so k2 is zero for a tail of eight bytes or fewer, and
53+
// mixing zero changes nothing, so the mixes need no guard of
54+
// their own.
55+
n := len(data) & 15
56+
var k1, k2 uint64
57+
if n != 0 {
58+
end := data[len(data)-16:]
59+
m := max(n, 8)
60+
k1 = load64(end[16-m:24-m]) >> (8 * uint(8-min(n, 8)))
61+
k2 = load64(end[8:]) >> (8 * uint(16-n))
62+
}
63+
for len(data) > 16 {
64+
h1, h2 = mix128(h1, h2, load64(data), load64(data[8:]))
65+
data = data[16:]
66+
}
67+
if len(data) >= 16 {
68+
h1, h2 = mix128(h1, h2, load64(data), load64(data[8:]))
69+
}
70+
71+
if n != 0 {
72+
k2 *= c2_128
73+
k2 = bits.RotateLeft64(k2, 33)
74+
k2 *= c1_128
75+
h2 ^= k2
76+
k1 *= c1_128
77+
k1 = bits.RotateLeft64(k1, 31)
78+
k1 *= c2_128
79+
h1 ^= k1
80+
}
81+
} else {
82+
// Every case knows its exact length, so the compiler proves all bounds
83+
// and each case is two or three word sized loads. This is faster than
84+
// the canonical byte at a time fallthrough switch.
85+
var k1, k2 uint64
86+
switch len(data) {
87+
case 15:
88+
k2 = uint64(load32(data[8:])) | uint64(load16(data[12:]))<<32 | uint64(data[14])<<48
89+
k1 = load64(data)
90+
case 14:
91+
k2 = uint64(load32(data[8:])) | uint64(load16(data[12:]))<<32
92+
k1 = load64(data)
93+
case 13:
94+
k2 = uint64(load32(data[8:])) | uint64(data[12])<<32
95+
k1 = load64(data)
96+
case 12:
97+
k2 = uint64(load32(data[8:]))
98+
k1 = load64(data)
99+
case 11:
100+
k2 = uint64(load16(data[8:])) | uint64(data[10])<<16
101+
k1 = load64(data)
102+
case 10:
103+
k2 = uint64(load16(data[8:]))
104+
k1 = load64(data)
105+
case 9:
106+
k2 = uint64(data[8])
107+
k1 = load64(data)
108+
case 8:
109+
k1 = load64(data)
110+
case 7:
111+
k1 = uint64(load32(data)) | uint64(load16(data[4:]))<<32 | uint64(data[6])<<48
112+
case 6:
113+
k1 = uint64(load32(data)) | uint64(load16(data[4:]))<<32
114+
case 5:
115+
k1 = uint64(load32(data)) | uint64(data[4])<<32
116+
case 4:
117+
k1 = uint64(load32(data))
118+
case 3:
119+
k1 = uint64(load16(data)) | uint64(data[2])<<16
120+
case 2:
121+
k1 = uint64(load16(data))
122+
case 1:
123+
k1 = uint64(data[0])
124+
}
125+
if len(data) > 8 {
126+
k2 *= c2_128
127+
k2 = bits.RotateLeft64(k2, 33)
128+
k2 *= c1_128
129+
h2 ^= k2
130+
}
131+
if len(data) > 0 {
132+
k1 *= c1_128
133+
k1 = bits.RotateLeft64(k1, 31)
134+
k1 *= c2_128
135+
h1 ^= k1
136+
}
54137

55-
// Every case knows its exact length, so the compiler proves all bounds
56-
// and each case is two or three word sized loads. This is faster than
57-
// the canonical byte at a time fallthrough switch.
58-
var k1, k2 uint64
59-
switch len(data) {
60-
case 15:
61-
k2 = uint64(load32(data[8:])) | uint64(load16(data[12:]))<<32 | uint64(data[14])<<48
62-
k1 = load64(data)
63-
case 14:
64-
k2 = uint64(load32(data[8:])) | uint64(load16(data[12:]))<<32
65-
k1 = load64(data)
66-
case 13:
67-
k2 = uint64(load32(data[8:])) | uint64(data[12])<<32
68-
k1 = load64(data)
69-
case 12:
70-
k2 = uint64(load32(data[8:]))
71-
k1 = load64(data)
72-
case 11:
73-
k2 = uint64(load16(data[8:])) | uint64(data[10])<<16
74-
k1 = load64(data)
75-
case 10:
76-
k2 = uint64(load16(data[8:]))
77-
k1 = load64(data)
78-
case 9:
79-
k2 = uint64(data[8])
80-
k1 = load64(data)
81-
case 8:
82-
k1 = load64(data)
83-
case 7:
84-
k1 = uint64(load32(data)) | uint64(load16(data[4:]))<<32 | uint64(data[6])<<48
85-
case 6:
86-
k1 = uint64(load32(data)) | uint64(load16(data[4:]))<<32
87-
case 5:
88-
k1 = uint64(load32(data)) | uint64(data[4])<<32
89-
case 4:
90-
k1 = uint64(load32(data))
91-
case 3:
92-
k1 = uint64(load16(data)) | uint64(data[2])<<16
93-
case 2:
94-
k1 = uint64(load16(data))
95-
case 1:
96-
k1 = uint64(data[0])
97-
}
98-
if len(data) > 8 {
99-
k2 *= c2_128
100-
k2 = bits.RotateLeft64(k2, 33)
101-
k2 *= c1_128
102-
h2 ^= k2
103-
}
104-
if len(data) > 0 {
105-
k1 *= c1_128
106-
k1 = bits.RotateLeft64(k1, 31)
107-
k1 *= c2_128
108-
h1 ^= k1
109138
}
110139

111140
h1 ^= uint64(clen)

‎murmur32_gen.go‎

Lines changed: 39 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -35,31 +35,47 @@ func SeedStringSum32(seed uint32, data string) (h1 uint32) {
3535
// the total number of bytes hashed. The one shot sums pass all of their
3636
// input; the streaming digest passes its leftover tail.
3737
func sum32[T bytestring](h1 uint32, data T, clen int) uint32 {
38-
// Strictly greater for the same reason as in sum128: it removes the
39-
// compiler's zero length pointer guard from the loop.
40-
for len(data) > 4 {
41-
h1 = mix32(h1, load32(data))
42-
data = data[4:]
43-
}
4438
if len(data) >= 4 {
45-
h1 = mix32(h1, load32(data))
46-
data = data[4:]
47-
}
39+
// See sum128: the last four bytes are in bounds, so shift the tail
40+
// out of them before the loop rather than branch on its length
41+
// after it.
42+
n := len(data) & 3
43+
var k1 uint32
44+
if n != 0 {
45+
end := data[len(data)-4:]
46+
k1 = load32(end[:4]) >> (8 * uint(4-n))
47+
}
48+
for len(data) > 4 {
49+
h1 = mix32(h1, load32(data))
50+
data = data[4:]
51+
}
52+
if len(data) >= 4 {
53+
h1 = mix32(h1, load32(data))
54+
}
55+
56+
if n != 0 {
57+
k1 *= c1_32
58+
k1 = bits.RotateLeft32(k1, 15)
59+
k1 *= c2_32
60+
h1 ^= k1
61+
}
62+
} else {
63+
var k1 uint32
64+
switch len(data) {
65+
case 3:
66+
k1 ^= uint32(data[2]) << 16
67+
fallthrough
68+
case 2:
69+
k1 ^= uint32(data[1]) << 8
70+
fallthrough
71+
case 1:
72+
k1 ^= uint32(data[0])
73+
k1 *= c1_32
74+
k1 = bits.RotateLeft32(k1, 15)
75+
k1 *= c2_32
76+
h1 ^= k1
77+
}
4878

49-
var k1 uint32
50-
switch len(data) {
51-
case 3:
52-
k1 ^= uint32(data[2]) << 16
53-
fallthrough
54-
case 2:
55-
k1 ^= uint32(data[1]) << 8
56-
fallthrough
57-
case 1:
58-
k1 ^= uint32(data[0])
59-
k1 *= c1_32
60-
k1 = bits.RotateLeft32(k1, 15)
61-
k1 *= c2_32
62-
h1 ^= k1
6379
}
6480

6581
h1 ^= uint32(clen)

‎murmur64.go‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ func (d *digest64) Clone() (hash.Cloner, error) {
5353
// hasher.Write(data)
5454
// return hasher.Sum64()
5555
func Sum64(data []byte) uint64 {
56-
h1, _ := Sum128(data)
56+
h1, _ := sum128(0, 0, data, len(data))
5757
return h1
5858
}
5959

@@ -63,18 +63,18 @@ func Sum64(data []byte) uint64 {
6363
// Because the canonical implementation does not support SeedSum64, this uses
6464
// SeedSum128(seed, seed, data).
6565
func SeedSum64(seed uint64, data []byte) uint64 {
66-
h1, _ := SeedSum128(seed, seed, data)
66+
h1, _ := sum128(seed, seed, data, len(data))
6767
return h1
6868
}
6969

7070
// StringSum64 is the string version of Sum64.
7171
func StringSum64(data string) uint64 {
72-
h1, _ := StringSum128(data)
72+
h1, _ := sum128(0, 0, data, len(data))
7373
return h1
7474
}
7575

7676
// SeedStringSum64 is the string version of SeedSum64.
7777
func SeedStringSum64(seed uint64, data string) uint64 {
78-
h1, _ := SeedStringSum128(seed, seed, data)
78+
h1, _ := sum128(seed, seed, data, len(data))
7979
return h1
8080
}

0 commit comments

Comments
 (0)