lib/lz4: add software-pipelined prefetch to decode fast loop
PATCH 1/1 lib/lz4: add software-pipelined prefetch to decode fast loop
From: "S. Biplab Raut" <[email protected]>
LZ4 decompression of cold 4 KiB pages (the zswap/zram hot path) stalls on cache misses because the input stream (compressed) and output buffer (uncompressed page) are not resident in L1/L2. Insert read-ahead and write-intent prefetch hints at the top of the decode loop in LZ4_decompress_generic() to overlap memory latency with decode work.
The prefetch distances (96 B read, 128 B write) are tuned for the page-at-a-time workload where both buffers fit in L1d. Prefetch is architecturally a no-op hint on all Linux-supported architectures; it never faults, never changes correctness, and compiles to nothing on targets without hardware prefetch.
Measured on AMD EPYC 9755 (Turin, 2S×128C), Ubuntu 24.04, kernel 6.8.0-90-generic, real zswap path (cgroup-constrained MADV_PAGEOUT + full scan-back), Silesia corpus, 15 paired rounds:
Kernel LZ4 median scan: 1.0994 s Patched median scan: 1.0472 s Median paired speedup: 5.09% (range 4.19%–6.99%)
Patched was faster in all 15 rounds.
--- lib/lz4/lz4_decompress.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+)
lib/lz4/lz4_decompress.c +21 -0
@@ -37,6 +37,7 @@#include <linux/init.h> #include <linux/module.h> #include <linux/kernel.h> +#include <linux/prefetch.h> #include <linux/unaligned.h> /*-*****************************
@@ -122,6 +123,26 @@ static FORCE_INLINE int LZ4_decompress_generic(const BYTE *match;size_t offset; +/* +* Software-pipelined prefetch hints. On the zswap/zram +* hot path, both the compressed input and the output page +* are cold (just faulted in or freshly allocated). Prime +* the L1d for the next loop iteration so that the actual +* loads/stores hit warm cache lines. +* +* Distances are tuned for 4 KiB page-at-a-time workloads: +* 96 B read-ahead on ip ~ 6 tokens ahead +* 128 B write-intent on op ~ 2 long-literal copies ahead +* 192 B deeper read-ahead ~ covers the match-copy tail +* +* prefetch() / prefetchw() are architecture-portable hints +* that compile to NOP on targets without HW prefetch. They +* never fault, even past buffer boundaries. +*/ +prefetch (ip +96 ); +prefetchw (op +128 ); +prefetch (ip +192 ); +/* get literal length */ unsigned int const token = *ip++; length = token>>ML_BITS ;
Signature · 1 line
2.43.0
Andrew Morton
maintainerQuoted 14 lines · On Tue, 13 Oct 2026 03:20:10 +0000 Biplab Raut <[email protected]> wrote:
From: "S. Biplab Raut" <[email protected]>
LZ4 decompression of cold 4 KiB pages (the zswap/zram hot path) stalls on cache misses because the input stream (compressed) and output buffer (uncompressed page) are not resident in L1/L2. Insert read-ahead and write-intent prefetch hints at the top of the decode loop in
LZ4_decompress_generic()to overlap memory latency with decode work.The prefetch distances (96 B read, 128 B write) are tuned for the page-at-a-time workload where both buffers fit in L1d. Prefetch is architecturally a no-op hint on all Linux-supported architectures; it never faults, never changes correctness, and compiles to nothing on targets without hardware prefetch.
Quoted 8 lines
Measured on AMD EPYC 9755 (Turin, 2S×128C), Ubuntu 24.04, kernel 6.8.0-90-generic, real zswap path (cgroup-constrained
MADV_PAGEOUT+ full scan-back), Silesia corpus, 15 paired rounds:Kernel LZ4 median scan: 1.0994 s Patched median scan: 1.0472 s Median paired speedup: 5.09% (range 4.19%–6.99%)Patched was faster in all 15 rounds.
Well that's nice. I can't actually recall a case where prefetch made a measurable difference, although I'm sure there are such cases.
We used to use prefetches often (10+ years ago) but it seems to fallen out of favor. This code is a prime candidate. mm/ barely uses prefetch. Maybe it should,
Quoted 7 lines · Andrew Morton
Quoted 5 lines · On Tue, 13 Oct 2026 03:20:10 +0000 Biplab Raut <[email protected]> wrote:
Kernel LZ4 median scan: 1.0994 s Patched median scan: 1.0472 s Median paired speedup: 5.09% (range 4.19%–6.99%)Patched was faster in all 15 rounds.
Quoted 6 lines
Well that's nice. I can't actually recall a case where prefetch made a measurable difference, although I'm sure there are such cases.
We used to use prefetches often (10+ years ago) but it seems to fallen out of favor. This code is a prime candidate.
mm/barely uses prefetch. Maybe it should,
Unfortunately the patch causes a build regression on x86 when using lz4
compressed bzImage files:
x86_64-linux-ld: error: unplaced orphan section .altinstructions' from arch/x86/boot/compressed/misc.o'
x86_64-linux-ld: error: unplaced orphan section .altinstr_replacement' from arch/x86/boot/compressed/misc.o'
I see that the zero-day bot has also reported this[1].
The problem is that the prefetch() helpers use SMP alternatives that are not available in the decompressor. This has been a problem in other patches before [2].
Not sure if there is an easy way to stop the decompressor from using the alternatives here, for 7.4 I assume the only option is to drop the patch and try again once that is resolved.
Arnd
[1] https://lore.kernel.org/all/[email protected]/
[2] https://lore.kernel.org/all/CAHk-=whrc-ruKs4Kt90EGzKd+pYhZFKs6bgBVCV=55BK+p1nzg@mail.gmail.com/