compress/flate: speed up the writeBlockHuff literal loop
Use the same flushing strategy as writeTokens: flush whole bytes from
the accumulator unconditionally after every group of three literals
instead of testing the pending bit count before every group. With at
most 7 bits pending at the top of an iteration, three 15-bit codes
always fit in the 64-bit accumulator.
This only affects Huffman-only encoding and blocks without matches.
goos: darwin
goarch: arm64
pkg: compress/flate
cpu: Apple M1 Max
│ old.txt │ new.txt │
│ sec/op │ sec/op vs base │
Encode/Digits/Huffman/1e5-10 113.6µ ± 1% 106.3µ ± 1% -6.47% (p=0.002 n=6)
Encode/Digits/Huffman/1e6-10 1.122m ± 1% 1.050m ± 2% -6.42% (p=0.002 n=6)
Encode/Digits/Speed/1e5-10 487.6µ ± 0% 478.5µ ± 2% -1.87% (p=0.002 n=6)
Encode/Digits/Speed/1e6-10 6.137m ± 1% 6.130m ± 1% ~ (p=0.240 n=6)
Encode/Digits/Default/1e5-10 1.116m ± 1% 1.113m ± 2% ~ (p=0.818 n=6)
Encode/Digits/Default/1e6-10 11.44m ± 1% 11.43m ± 1% ~ (p=1.000 n=6)
Encode/Digits/Compression/1e5-10 4.104m ± 1% 4.101m ± 2% ~ (p=0.818 n=6)
Encode/Digits/Compression/1e6-10 45.93m ± 1% 45.71m ± 3% ~ (p=0.310 n=6)
Encode/Newton/Huffman/1e5-10 133.4µ ± 2% 125.4µ ± 1% -6.02% (p=0.002 n=6)
Encode/Newton/Huffman/1e6-10 1.522m ± 1% 1.436m ± 1% -5.62% (p=0.002 n=6)
Encode/Newton/Speed/1e5-10 410.5µ ± 1% 410.5µ ± 2% ~ (p=0.937 n=6)
Encode/Newton/Speed/1e6-10 4.589m ± 1% 4.581m ± 1% ~ (p=0.310 n=6)
Encode/Newton/Default/1e5-10 755.2µ ± 2% 753.6µ ± 2% ~ (p=0.310 n=6)
Encode/Newton/Default/1e6-10 7.984m ± 2% 7.970m ± 2% ~ (p=0.310 n=6)
Encode/Newton/Compression/1e5-10 4.737m ± 1% 4.733m ± 3% ~ (p=0.937 n=6)
Encode/Newton/Compression/1e6-10 51.63m ± 2% 51.71m ± 1% ~ (p=0.818 n=6)
geomean 2.276m 2.235m -1.78%
│ old.txt │ new.txt │
│ B/s │ B/s vs base │
Encode/Digits/Huffman/1e5-10 839.2Mi ± 1% 897.3Mi ± 1% +6.92% (p=0.002 n=6)
Encode/Digits/Huffman/1e6-10 850.2Mi ± 1% 908.5Mi ± 2% +6.86% (p=0.002 n=6)
Encode/Digits/Speed/1e5-10 195.6Mi ± 0% 199.3Mi ± 2% +1.90% (p=0.002 n=6)
Encode/Digits/Speed/1e6-10 155.4Mi ± 1% 155.6Mi ± 1% ~ (p=0.258 n=6)
Encode/Digits/Default/1e5-10 85.45Mi ± 1% 85.65Mi ± 2% ~ (p=0.784 n=6)
Encode/Digits/Default/1e6-10 83.33Mi ± 1% 83.40Mi ± 1% ~ (p=1.000 n=6)
Encode/Digits/Compression/1e5-10 23.24Mi ± 1% 23.25Mi ± 2% ~ (p=0.846 n=6)
Encode/Digits/Compression/1e6-10 20.76Mi ± 1% 20.86Mi ± 3% ~ (p=0.357 n=6)
Encode/Newton/Huffman/1e5-10 715.0Mi ± 2% 760.8Mi ± 1% +6.41% (p=0.002 n=6)
Encode/Newton/Huffman/1e6-10 626.8Mi ± 1% 664.1Mi ± 1% +5.95% (p=0.002 n=6)
Encode/Newton/Speed/1e5-10 232.3Mi ± 1% 232.3Mi ± 2% ~ (p=0.937 n=6)
Encode/Newton/Speed/1e6-10 207.8Mi ± 1% 208.2Mi ± 1% ~ (p=0.310 n=6)
Encode/Newton/Default/1e5-10 126.3Mi ± 2% 126.6Mi ± 2% ~ (p=0.310 n=6)
Encode/Newton/Default/1e6-10 119.4Mi ± 2% 119.7Mi ± 2% ~ (p=0.260 n=6)
Encode/Newton/Compression/1e5-10 20.13Mi ± 1% 20.15Mi ± 3% ~ (p=0.970 n=6)
Encode/Newton/Compression/1e6-10 18.47Mi ± 2% 18.44Mi ± 1% ~ (p=0.723 n=6)
geomean 132.5Mi 134.9Mi +1.80%
Updates #81398
diff --git a/src/compress/flate/huffman_bit_writer.go b/src/compress/flate/huffman_bit_writer.go
index ecd3899..9f59111 100644
--- a/src/compress/flate/huffman_bit_writer.go
+++ b/src/compress/flate/huffman_bit_writer.go
@@ -995,20 +995,39 @@
}
encoding := w.literalEncoding.codes[:256]
- // Go 1.16 LOVES having these on stack. At least 1.5x the speed.
+ // Keeping these on the stack instead of in w is significantly faster.
bits, nbits, nbytes := w.bits, w.nbits, w.nbytes
- // Unroll, write 3 codes/loop.
- // Fastest number of unrolls.
- for len(input) > 3 {
- // We must have at least 48 bits free.
- if nbits >= 8 {
- n := nbits >> 3
- storeLE64(w.bytes[nbytes:], bits)
- bits >>= (n * 8) & 63
- nbits -= n * 8
- nbytes += n
+ // Flush whole bytes, so that nbits <= 7 when entering the loop below.
+ storeLE64(w.bytes[nbytes:], bits)
+ nbytes += nbits >> 3
+ bits >>= nbits & 56
+ nbits &= 7
+ if nbytes >= bufferFlushSize {
+ _, w.err = w.writer.Write(w.bytes[:nbytes])
+ nbytes = 0
+ if w.err != nil {
+ return
}
+ }
+
+ // Write 3 codes per iteration. Each code is at most 15 bits,
+ // so with at most 7 bits pending the accumulator cannot overflow.
+ // See writeTokens for a description of the flushing strategy.
+ for len(input) >= 3 {
+ a, b, c := encoding[input[0]], encoding[input[1]], encoding[input[2]]
+ bits |= a.code64() << (nbits & 63)
+ nbits += a.len()
+ bits |= b.code64() << (nbits & 63)
+ nbits += b.len()
+ bits |= c.code64() << (nbits & 63)
+ nbits += c.len()
+ input = input[3:]
+
+ storeLE64(w.bytes[nbytes:], bits)
+ nbytes += nbits >> 3
+ bits >>= nbits & 56
+ nbits &= 7
if nbytes >= bufferFlushSize {
if w.err != nil {
nbytes = 0
@@ -1017,38 +1036,15 @@
_, w.err = w.writer.Write(w.bytes[:nbytes])
nbytes = 0
}
- a, b := encoding[input[0]], encoding[input[1]]
- bits |= a.code64() << (nbits & 63)
- bits |= b.code64() << ((nbits + a.len()) & 63)
- c := encoding[input[2]]
- nbits += b.len() + a.len()
- bits |= c.code64() << (nbits & 63)
- nbits += c.len()
- input = input[3:]
}
// Remaining...
for _, t := range input {
- if nbits >= 48 {
- storeLE64(w.bytes[nbytes:], bits)
- bits >>= 48
- nbits -= 48
- nbytes += 6
- if nbytes >= bufferFlushSize {
- if w.err != nil {
- nbytes = 0
- return
- }
- _, w.err = w.writer.Write(w.bytes[:nbytes])
- nbytes = 0
- }
- }
- // Bitwriting inlined, ~30% speedup
c := encoding[t]
bits |= c.code64() << (nbits & 63)
-
nbits += c.len()
}
+ // At most 7+2*15 bits are pending here.
// Restore...
w.bits, w.nbits, w.nbytes = bits, nbits, nbytes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
| Code-Review | +1 |
Confirmed the speedup an amd64 as well. LGTM.
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
| Auto-Submit | +1 |
| Code-Review | +2 |
| Commit-Queue | +1 |
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
| Commit-Queue | +1 |
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
| Code-Review | +1 |
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
| Code-Review | +1 |
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
compress/flate: combine codes in the writeBlockHuff literal loop
Throughput of the literal loop is bounded by the serial dependency
through the pending bit count: every code is shifted by the current
count and then the count is updated. Assemble the three codes of an
iteration into a separate word first, which only depends on the codes
themselves, and merge that word into the accumulator with a single
shift and or. The flushing structure of the loop is unchanged.
An earlier version of this change also replaced the conditional flush
with an unconditional 8-byte store after every group of three codes.
That was a further 6% faster on an Apple M1 Max, but 12% slower than
the original loop on an Intel Xeon E5-2696 v4, so it is not used.
This only affects Huffman-only encoding and blocks without matches.
goos: darwin
goarch: arm64
pkg: compress/flate
cpu: Apple M1 Max
│ old.txt │ new.txt │
│ sec/op │ sec/op vs base │
Encode/Digits/Huffman/1e5-10 116.5µ ± 1% 105.1µ ± 1% -9.84% (p=0.002 n=6)
Encode/Digits/Huffman/1e6-10 1.148m ± 3% 1.034m ± 5% -9.91% (p=0.002 n=6)
Encode/Digits/Speed/1e5-10 497.3µ ± 2% 496.4µ ± 3% ~ (p=0.818 n=6)
Encode/Digits/Speed/1e6-10 6.268m ± 1% 6.316m ± 1% ~ (p=0.132 n=6)
Encode/Digits/Default/1e5-10 1.145m ± 1% 1.156m ± 4% ~ (p=0.132 n=6)
Encode/Digits/Default/1e6-10 11.74m ± 2% 11.78m ± 1% ~ (p=0.818 n=6)
Encode/Digits/Compression/1e5-10 4.266m ± 2% 4.265m ± 4% ~ (p=1.000 n=6)
Encode/Digits/Compression/1e6-10 47.70m ± 2% 48.09m ± 5% ~ (p=0.818 n=6)
Encode/Newton/Huffman/1e5-10 137.0µ ± 2% 126.0µ ± 2% -8.03% (p=0.002 n=6)
Encode/Newton/Huffman/1e6-10 1.554m ± 0% 1.451m ± 1% -6.63% (p=0.002 n=6)
Encode/Newton/Speed/1e5-10 420.4µ ± 2% 421.9µ ± 2% ~ (p=0.310 n=6)
Encode/Newton/Speed/1e6-10 4.686m ± 1% 4.686m ± 10% ~ (p=0.937 n=6)
Encode/Newton/Default/1e5-10 777.3µ ± 2% 775.6µ ± 3% ~ (p=0.818 n=6)
Encode/Newton/Default/1e6-10 8.235m ± 2% 8.261m ± 4% ~ (p=1.000 n=6)
Encode/Newton/Compression/1e5-10 4.894m ± 4% 4.890m ± 3% ~ (p=0.699 n=6)
Encode/Newton/Compression/1e6-10 54.26m ± 6% 53.85m ± 3% ~ (p=0.589 n=6)
geomean 2.341m 2.292m -2.09%
│ old.txt │ new.txt │
│ B/s │ B/s vs base │
Encode/Digits/Huffman/1e5-10 818.4Mi ± 1% 907.7Mi ± 1% +10.91% (p=0.002 n=6)
Encode/Digits/Huffman/1e6-10 830.6Mi ± 2% 922.0Mi ± 5% +11.00% (p=0.002 n=6)
Encode/Digits/Speed/1e5-10 191.8Mi ± 2% 192.1Mi ± 3% ~ (p=0.818 n=6)
Encode/Digits/Speed/1e6-10 152.1Mi ± 1% 151.0Mi ± 1% ~ (p=0.132 n=6)
Encode/Digits/Default/1e5-10 83.27Mi ± 1% 82.54Mi ± 4% ~ (p=0.132 n=6)
Encode/Digits/Default/1e6-10 81.25Mi ± 2% 80.93Mi ± 1% ~ (p=0.818 n=6)
Encode/Digits/Compression/1e5-10 22.35Mi ± 2% 22.36Mi ± 4% ~ (p=1.000 n=6)
Encode/Digits/Compression/1e6-10 19.99Mi ± 2% 19.83Mi ± 5% ~ (p=0.799 n=6)
Encode/Newton/Huffman/1e5-10 696.0Mi ± 2% 756.8Mi ± 2% +8.74% (p=0.002 n=6)
Encode/Newton/Huffman/1e6-10 613.8Mi ± 0% 657.4Mi ± 1% +7.10% (p=0.002 n=6)
Encode/Newton/Speed/1e5-10 226.8Mi ± 2% 226.0Mi ± 2% ~ (p=0.310 n=6)
Encode/Newton/Speed/1e6-10 203.5Mi ± 1% 203.5Mi ± 9% ~ (p=0.937 n=6)
Encode/Newton/Default/1e5-10 122.7Mi ± 2% 123.0Mi ± 3% ~ (p=0.818 n=6)
Encode/Newton/Default/1e6-10 115.8Mi ± 2% 115.5Mi ± 4% ~ (p=1.000 n=6)
Encode/Newton/Compression/1e5-10 19.48Mi ± 3% 19.50Mi ± 3% ~ (p=0.699 n=6)
Encode/Newton/Compression/1e6-10 17.58Mi ± 6% 17.71Mi ± 3% ~ (p=0.589 n=6)
geomean 128.8Mi 131.6Mi +2.13%
goos: linux
goarch: amd64
pkg: compress/flate
cpu: Intel(R) Xeon(R) CPU E5-2696 v4 @ 2.20GHz
│ old.txt │ new.txt │
│ sec/op │ sec/op vs base │
Encode/Digits/Huffman/1e5-22 181.3µ ± 2% 179.2µ ± 6% ~ (p=0.180 n=6)
Encode/Digits/Huffman/1e6-22 1.817m ± 1% 1.796m ± 2% ~ (p=0.132 n=6)
Encode/Digits/Speed/1e5-22 763.8µ ± 2% 769.1µ ± 8% ~ (p=0.485 n=6)
Encode/Digits/Speed/1e6-22 9.134m ± 2% 9.219m ± 4% ~ (p=0.818 n=6)
Encode/Digits/Default/1e5-22 1.955m ± 10% 1.975m ± 3% ~ (p=0.699 n=6)
Encode/Digits/Default/1e6-22 20.24m ± 4% 20.45m ± 3% ~ (p=0.589 n=6)
Encode/Digits/Compression/1e5-22 7.243m ± 6% 7.304m ± 2% ~ (p=0.485 n=6)
Encode/Digits/Compression/1e6-22 83.60m ± 2% 82.71m ± 5% ~ (p=0.937 n=6)
Encode/Newton/Huffman/1e5-22 226.9µ ± 2% 225.3µ ± 1% -0.69% (p=0.026 n=6)
Encode/Newton/Huffman/1e6-22 2.368m ± 2% 2.336m ± 6% ~ (p=0.180 n=6)
Encode/Newton/Speed/1e5-22 625.0µ ± 2% 624.7µ ± 2% ~ (p=0.589 n=6)
Encode/Newton/Speed/1e6-22 6.602m ± 2% 6.566m ± 6% ~ (p=0.589 n=6)
Encode/Newton/Default/1e5-22 1.356m ± 2% 1.341m ± 2% ~ (p=0.180 n=6)
Encode/Newton/Default/1e6-22 13.54m ± 4% 13.80m ± 2% ~ (p=0.310 n=6)
Encode/Newton/Compression/1e5-22 6.926m ± 2% 6.935m ± 7% ~ (p=0.394 n=6)
Encode/Newton/Compression/1e6-22 74.99m ± 6% 75.60m ± 4% ~ (p=1.000 n=6)
geomean 3.686m 3.687m +0.02%
│ old.txt │ new.txt │
│ B/s │ B/s vs base │
Encode/Digits/Huffman/1e5-22 526.1Mi ± 2% 532.1Mi ± 6% ~ (p=0.180 n=6)
Encode/Digits/Huffman/1e6-22 524.8Mi ± 1% 531.1Mi ± 2% ~ (p=0.132 n=6)
Encode/Digits/Speed/1e5-22 124.9Mi ± 2% 124.0Mi ± 7% ~ (p=0.485 n=6)
Encode/Digits/Speed/1e6-22 104.4Mi ± 2% 103.4Mi ± 4% ~ (p=0.818 n=6)
Encode/Digits/Default/1e5-22 48.79Mi ± 9% 48.29Mi ± 3% ~ (p=0.699 n=6)
Encode/Digits/Default/1e6-22 47.13Mi ± 3% 46.63Mi ± 3% ~ (p=0.563 n=6)
Encode/Digits/Compression/1e5-22 13.17Mi ± 6% 13.06Mi ± 2% ~ (p=0.509 n=6)
Encode/Digits/Compression/1e6-22 11.41Mi ± 2% 11.53Mi ± 5% ~ (p=0.937 n=6)
Encode/Newton/Huffman/1e5-22 420.3Mi ± 2% 423.2Mi ± 1% +0.69% (p=0.026 n=6)
Encode/Newton/Huffman/1e6-22 402.8Mi ± 2% 408.2Mi ± 6% ~ (p=0.180 n=6)
Encode/Newton/Speed/1e5-22 152.6Mi ± 2% 152.7Mi ± 2% ~ (p=0.589 n=6)
Encode/Newton/Speed/1e6-22 144.5Mi ± 3% 145.2Mi ± 6% ~ (p=0.589 n=6)
Encode/Newton/Default/1e5-22 70.37Mi ± 2% 71.13Mi ± 2% ~ (p=0.180 n=6)
Encode/Newton/Default/1e6-22 70.44Mi ± 4% 69.11Mi ± 2% ~ (p=0.329 n=6)
Encode/Newton/Compression/1e5-22 13.77Mi ± 2% 13.75Mi ± 7% ~ (p=0.420 n=6)
Encode/Newton/Compression/1e6-22 12.72Mi ± 6% 12.61Mi ± 5% ~ (p=1.000 n=6)
geomean 81.81Mi 81.79Mi -0.02%
Updates #81398
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |