]> git.ipfire.org Git - thirdparty/zstd.git/commit
[huf] Improve fast huffman decoding speed in linux kernel v1.5.5-kernel-cherrypicks v1.5.5-kernel
authorNick Terrell <terrelln@meta.com>
Sat, 18 Nov 2023 02:20:19 +0000 (18:20 -0800)
committerNick Terrell <terrelln@meta.com>
Mon, 20 Nov 2023 20:30:47 +0000 (12:30 -0800)
commit3ff79dbe942dcaaac464bcd57ffbd3123e585248
tree9e48549a97a18362a1948880c26143814773486d
parent58b3ef79eb9f1e6613684ea6e5b89720660ee8b6
[huf] Improve fast huffman decoding speed in linux kernel

gcc in the linux kernel was not unrolling the inner loops of the Huffman
decoder, which was destroying decoding performance. The compiler was
generating crazy code with all sorts of branches. I suspect because of
Spectre mitigations, but I'm not certain. Once the loops were manually
unrolled, performance was restored.

Additionally, when gcc couldn't prove that the variable left shift in
the 4X2 decode loop wasn't greater than 63, it inserted checks to verify
it. To fix this, mask `entry.nbBits & 0x3F`, which allows gcc to eliete
this check. This is a no op, because `entry.nbBits` is guaranteed to be
less than 64.

Lastly, introduce the `HUF_DISABLE_FAST_DECODE` macro to disable the
fast C loops for Issue #3762. So if even after this change, there is a
performance regression, users can opt-out at compile time.
lib/README.md
lib/decompress/huf_decompress.c