Pipeline Parallel Decompression - by Blake Pelton

Dangling Pointers

SubscribeSign in

Pipeline Parallel Decompression<br>Bribing God

Blake Pelton<br>May 26, 2026

Share

This isn’t a paper summary, but rather a description of a hobby experiment I’ve been hacking on ("research quality" code).<br>The Potential of Pipeline Parallelism

This quote (attributed to either Anonymous or David Clark) originally referred to networking, but applies to parallel programming as well:<br>There is an old network saying: Bandwidth problems can be cured with money. Latency problems are harder because the speed of light is fixed—you can’t bribe God.

Standard "cured with money" parallelization techniques (e.g., shared-nothing architectures, data parallelism) try to minimize cross-core communication. These hammers are great for hitting nails labeled: "improve throughput by throwing more cores at the problem”.<br>Not everything is a nail. Important problems which cannot be solved with this kind of approach include:<br>Parallel network packet processing in cases where load balancing schemes like RSS do not apply

Parallel transaction processing when there is high contention between transactions

Parallel encryption of a single stream of data

Pipeline parallelism has the potential to provide "bribing God” solutions to some of these problems.<br>A potential additional benefit that pipeline parallelism brings to the table is better usage of CPU caches because of a smaller working set. For example, if 8 cores cooperate to process 1 input file, the working set (input data, output data, intermediate data structures) is potentially 8 times smaller than the case where each core processes a separate input file. This caching advantage also applies to instruction caches, as pipeline parallelism distributes the computational steps of an algorithm across cores.<br>Pipeline parallelism has some major drawbacks:<br>Fine-grain synchronization/communication

Load imbalance

The purpose of this experiment is to put some numbers on the costs and benefits in a real-world application (DEFLATE decompression).<br>Pipeline Design

DEFLATE decompression is hard to parallelize because of two tight feedback loops:<br>The position of encoded token N in the input stream is not known until token N-1 is decoded (because input data is encoded with a variable length code).

The output generated by a match (i.e., length & distance tuple) cannot be computed until some amount of previous output has been generated (because a match references previously generated output)

A Negative Nancy might view these as problems, but a Positive Pipeliner views them as a guide for how to decompose the algorithm into pipeline stages. The general technique is to dedicate a pipeline stage to each of these feedback loops and whittle them down to be as tight as possible.<br>The design I’ve landed on has three pipeline stages: chase, lookup, and output.<br>The chase stage computes the length of each encoded token. It simply reads the next 13 bits from the input stream and uses them as an index into a lookup table. The inner loop looks like this:<br>const size_t lut_key_bits = 13;<br>const uint32_t lut_key_mask = (1 (lut_key_bits);<br>const uint8_t length = length_lut[input_bits & lut_key_mask];<br>bits.consume(length);

Note that in contrast to non-pipelined implementations, the only thing this code (and the lookup table) are concerned with is finding the length of each token, everything else is dealt with in another pipeline stage. Each iteration of this loop runs in about 8 clock cycles, and the lookup table fits in the L1 cache. The CPU cannot run multiple iterations of this loop in parallel due to the tight dependency chain.<br>The input to the lookup stage is the encoded bits associated with each input token (input_bits in the code above). These bits are used to perform another lookup (in a larger lookup table, stored in the L2 cache) which results in much more information about each token. Optimizing this stage is easy, because it doesn’t contain any tight feedback loops. The CPU can process multiple loop iterations in parallel, which enables it to hide the latency of accessing the L2. If necessary, it would be easy to split this pipeline stage into two. The inner loop looks like this:<br>const output_lookup_result olr = lookup_lut[input_bits & lut_key_mask];

const size_t match_length = olr.match_length;

const uint16_t dist_extra_bits_mask = (1ull > olr.offset_to_dist_extra_bits) & dist_extra_bits_mask;<br>const size_t match_dist = olr.base_dist + dist_extra_bits;

The olr structure contains metadata about the input token (literal value and/or information about a match). This data structure does not contain the exact distance associated with the match, the variables named extra_bits deal with that detail from the DEFLATE spec.<br>The output stage writes literals and matches to the output buffer. This code leans on the CPU store-to-load forwarding hardware to deal with match operations which must read data that was recently produced....