]> git.ipfire.org Git - thirdparty/zstd.git/commit
[huf] Improve fast huffman decoding speed in linux kernel
authorNick Terrell <terrelln@meta.com>
Sat, 18 Nov 2023 02:20:19 +0000 (18:20 -0800)
committerNick Terrell <nickrterrell@gmail.com>
Mon, 20 Nov 2023 19:56:46 +0000 (14:56 -0500)
commitc7269add7eaf028ed828d9af41e732cf01993aad
treeb965e9214537180c6fb10d35ff321d7f8f783d76
parente122fcbf58e142e837a2bba382ef7ca4f5eaa13b
[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