Skip to contentSkip to conversation

lib/lz4: add software-pipelined prefetch to decode fast loop

PATCH In review Biplab Raut 3 participants 3 messages Oct 13 – Oct 14 Memory management

lore
Share & tools
lore
#0 lore raw

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
index 3a2cd9acada4..efbbde7ae58d 100644
@@ -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
maintainer
#1 lore raw
Quoted 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,

#2 lore raw
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/