zstd: Replace bytes.Equal with smaller comparisons #695

greatroar · 2022-11-22T19:51:16Z

This replaces some bytes.Equal calls, which compile down to calls to runtime.memequal, with uint32 or string comparisons that become CMPL instructions (or a series of CMPBs, in one case).

The code is several dozen instructions shorter. Benchmarks show no regressions:

name                                                  old speed      new speed      delta
Decoder_DecoderSmall/kppkn.gtb.zst/buffered-8          459MB/s ± 0%   458MB/s ± 0%    ~     (p=0.546 n=9 9)
Decoder_DecoderSmall/kppkn.gtb.zst/unbuffered-8        566MB/s ± 3%   568MB/s ± 2%    ~     (p=0.481 n=10 10)
Decoder_DecoderSmall/geo.protodata.zst/buffered-8     1.19GB/s ± 0%  1.19GB/s ± 0%   0.24%  (p=0.040 n=9 9)
Decoder_DecoderSmall/geo.protodata.zst/unbuffered-8    831MB/s ± 2%   832MB/s ± 2%    ~     (p=0.853 n=10 10)
Decoder_DecoderSmall/plrabn12.txt.zst/buffered-8       349MB/s ± 3%   352MB/s ± 0%    ~     (p=0.075 n=9 10)
Decoder_DecoderSmall/plrabn12.txt.zst/unbuffered-8     529MB/s ± 6%   534MB/s ± 7%    ~     (p=0.796 n=10 10)
Decoder_DecoderSmall/lcet10.txt.zst/buffered-8         421MB/s ± 1%   422MB/s ± 0%   0.32%  (p=0.029 n=9 8)
Decoder_DecoderSmall/lcet10.txt.zst/unbuffered-8       608MB/s ± 2%   606MB/s ± 9%    ~     (p=0.897 n=8 10)
Decoder_DecoderSmall/asyoulik.txt.zst/buffered-8       367MB/s ± 0%   362MB/s ± 5%    ~     (p=0.388 n=10 9)
Decoder_DecoderSmall/asyoulik.txt.zst/unbuffered-8     454MB/s ± 4%   449MB/s ± 3%    ~     (p=0.353 n=10 10)
Decoder_DecoderSmall/alice29.txt.zst/buffered-8        360MB/s ± 0%   361MB/s ± 0%   0.18%  (p=0.001 n=10 8)
Decoder_DecoderSmall/alice29.txt.zst/unbuffered-8      572MB/s ± 4%   569MB/s ± 8%    ~     (p=0.842 n=10 9)
Decoder_DecoderSmall/html_x_4.zst/buffered-8          2.46GB/s ± 0%  2.46GB/s ± 1%    ~     (p=0.497 n=9 10)
Decoder_DecoderSmall/html_x_4.zst/unbuffered-8        1.65GB/s ± 5%  1.67GB/s ± 6%    ~     (p=0.481 n=10 10)
Decoder_DecoderSmall/paper-100k.pdf.zst/buffered-8    3.87GB/s ± 1%  3.87GB/s ± 0%    ~     (p=0.353 n=10 10)
Decoder_DecoderSmall/paper-100k.pdf.zst/unbuffered-8  1.85GB/s ± 4%  1.84GB/s ± 7%    ~     (p=0.529 n=10 10)
Decoder_DecoderSmall/fireworks.jpeg.zst/buffered-8    8.62GB/s ± 1%  8.63GB/s ± 1%    ~     (p=0.529 n=10 10)
Decoder_DecoderSmall/fireworks.jpeg.zst/unbuffered-8  3.34GB/s ± 2%  3.34GB/s ± 3%    ~     (p=0.796 n=10 10)
Decoder_DecoderSmall/urls.10K.zst/buffered-8           587MB/s ± 1%   586MB/s ± 1%    ~     (p=0.589 n=10 9)
Decoder_DecoderSmall/urls.10K.zst/unbuffered-8         875MB/s ± 4%   877MB/s ± 2%    ~     (p=0.661 n=9 10)
Decoder_DecoderSmall/html.zst/buffered-8               962MB/s ± 0%   961MB/s ± 0%    ~     (p=0.368 n=10 9)
Decoder_DecoderSmall/html.zst/unbuffered-8             711MB/s ± 3%   709MB/s ± 1%    ~     (p=0.965 n=10 8)
Decoder_DecoderSmall/comp-data.bin.zst/buffered-8      407MB/s ± 1%   407MB/s ± 0%    ~     (p=0.684 n=10 10)
Decoder_DecoderSmall/comp-data.bin.zst/unbuffered-8    152MB/s ± 4%   152MB/s ± 3%    ~     (p=0.971 n=10 10)

This replaces some bytes.Equal calls, which compile down to calls to runtime.memequal, with uint32 or string comparisons that become CMPL instructions (or a series of CMPBs, in one case).

klauspost

bytes.Equal is doing a string conversion so it is only a semantic change.

But it looks better.

greatroar · 2022-11-23T09:41:36Z

Thanks. I see you've changed the commit message, but I assure you this is not a purely cosmetic change.

The issue isn't really string == vs bytes.Equal, it's var vs const. If you compile the following file...

package comparisons

import "bytes"

const sc = "abcd"

var sv = "abcd"

var bv = []byte("abcd")

func eqSc(p []byte) bool { return string(p[:4]) == sc }
func eqSv(p []byte) bool { return string(p[:4]) == sv }
func eqBv(p []byte) bool { return bytes.Equal(p[:4], bv) }

then you'll find that eqSv and eqBv compile to practically identical code, a bounds check and a call to runtime.memequal. But eqSc compiles to a bounds check and

CMPL    (AX), $1684234849 // AX = p_data, immediate = "abcd" interpreted as little-endian

because the compiler knows the length of both arguments and the value of the latter.

klauspost · 2022-11-23T11:04:54Z

@greatroar

I tried comparing the skippableFrameMagic (in (*Header).Decode) alone just for my curiosity. Both resulted in a runtime.memequal call on go version go1.19.2 windows/amd64. Perhaps because that is 3 and not 4 bytes, so there is no shortcut.

The functions are typically called once per decode (per frame), so I don't expect to see it being anything measurable either way. I do think the code is nicer (except the "\x2a\x4d\x18" - but the rest makes up for it).

zstd: Replace bytes.Equal with smaller comparisons

c09b86f

This replaces some bytes.Equal calls, which compile down to calls to runtime.memequal, with uint32 or string comparisons that become CMPL instructions (or a series of CMPBs, in one case).

greatroar force-pushed the compare branch from d4db81d to c09b86f Compare November 23, 2022 07:41

greatroar changed the title ~~zstd: Replace bytes.Equal with faster comparisons~~ zstd: Replace bytes.Equal with smaller comparisons Nov 23, 2022

klauspost approved these changes Nov 23, 2022

View reviewed changes

klauspost merged commit 4af4108 into klauspost:master Nov 23, 2022

greatroar deleted the compare branch November 23, 2022 09:29

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

zstd: Replace bytes.Equal with smaller comparisons #695

zstd: Replace bytes.Equal with smaller comparisons #695

greatroar commented Nov 22, 2022 •

edited

Loading

klauspost left a comment

greatroar commented Nov 23, 2022 •

edited

Loading

klauspost commented Nov 23, 2022

zstd: Replace bytes.Equal with smaller comparisons #695

zstd: Replace bytes.Equal with smaller comparisons #695

Conversation

greatroar commented Nov 22, 2022 • edited Loading

klauspost left a comment

Choose a reason for hiding this comment

greatroar commented Nov 23, 2022 • edited Loading

klauspost commented Nov 23, 2022

greatroar commented Nov 22, 2022 •

edited

Loading

greatroar commented Nov 23, 2022 •

edited

Loading