TAKT showcase: bzip2 decompression (Silesia corpus)

One program in two builds: bz2dec decompresses .bz2 files to standard output, like bzip2 -dc. bz2dec-original uses the crate bzip2-rs 0.1.2 (a pure Rust bzip2 decoder) as published on crates.io; bz2dec-takt uses the same crate after TAKT optimization. The driver is the same source file, the build recipe is the same, and the output of both programs is identical to the byte. Here you get both ready programs, the source of the original build, a script that fetches the corpus and the scripts that repeat the measurement and the checks.

What the benchmark does

The twelve files of the Silesia corpus (text, executables, databases, images, XML; 211,938,580 bytes), each compressed with Python's bz2.compress(data, 9) (libbz2 1.0.8, one stream per file, 54,506,769 bytes in total), are decompressed in one process:

bz2dec -c dickens.bz2 mozilla.bz2 mr.bz2 nci.bz2 ooffice.bz2 osdb.bz2 reymont.bz2 \
          samba.bz2 sao.bz2 webster.bz2 xml.bz2 x-ray.bz2 > /dev/null

The system bzip2 -dc (the reference C implementation) runs the same job for comparison.

Measurement (TAKT rig)

AMD Threadripper PRO 5975WX (Zen 3), Linux, one dedicated core (its SMT sibling idle, its CCX reserved for the measurement). perf stat counts user-mode cycles and instructions of the decoding process and its wall time; 9 interleaved rounds (the program order rotates from round to round), median. Exactly these files were measured. All three programs are dynamically linked glibc executables; both bz2dec builds use the same recipe: Rust 1.96.0, LTO, codegen-units 1, target-cpu=x86-64-v3, panic abort, stripped.

The whole set, one process per program:

bz2dec-takt against the C bzip2 -dc: 4.14× by cycles, 4.06× by time. Against bz2dec-original by time: 3.43×. Speedup is the ratio of median cycles; MB/s is decompressed megabytes (10⁶ bytes) per second of wall time.

Every file in its own process (same rounds; time in ms, speedup by cycles):

The speedup depends on the data: from 2.96× to 4.32× against the original and from 3.43× to 4.87× against bzip2 -dc on these files. Wall time also includes process start, reading the input and kernel work, which are the same for every program; that is why the ratios by time are a little lower than the ratios by cycles. Other data and other CPUs will give other numbers. Details and every sample are in measurements.json.

Running

python3 tools/fetch_silesia.py      # downloads silesia.zip (68 MB), checks it, writes data/raw and data/bz2
tools/run_bench.sh 7 2              # checks every output byte, then 7 interleaved rounds on core 2
bin/bz2dec-takt -c data/bz2/dickens.bz2 | cmp - data/raw/dickens      # identical to the byte
sha256sum -c SHA256SUMS

tools/fetch_silesia.py needs only Python 3 and checks the archive (sha256) and every file (size, the MD5 published on the corpus page, sha256); it also tells you whether your .bz2 inputs are the exact bytes we measured. tools/run_bench.sh counts cycles too when perf is available.

Usage: bz2dec -c FILE.bz2 [FILE.bz2 ...] > OUT. Exit codes: 0 success; 1 usage, I/O or CPU error; 2 invalid stream (the decoder's error message is printed to stderr); 3 internal decoder error.

Linux x86-64 (glibc). Both programs are built for x86-64-v3: AVX2, BMI1, BMI2, FMA (Intel Haswell and newer, AMD Zen and newer); they do not run on older CPUs.

Equivalence

• The twelve Silesia files: the output of bz2dec-original, bz2dec-takt and bzip2 -dc equals the raw file byte for byte, file by file and as one twelve-file run.
• 12,900 more streams: 1,200 valid ones (random slices of the corpus files, compression levels 1–9) and 11,700 corrupted ones (900 corrupted copies of the full inputs, the rest corrupted slices: bit flips, truncation, byte substitution, zeroed ranges, inserted and deleted ranges). For every stream stdout, stderr and the exit code of the two programs are identical (exit code 0: 1,360 streams, exit code 2: 11,540); 0 mismatches. Repeat it with python3 tools/compare_corrupted.py bin/bz2dec-original bin/bz2dec-takt data --seed 1 (seeds 1 and 2 were used, see measurements.json).

Building the original

cd source
RUSTFLAGS="-C target-cpu=x86-64-v3 --remap-path-prefix=$(ls -d ~/.cargo/registry/src/index.crates.io-*)=. \
  --remap-path-prefix=$HOME/.rustup=. --remap-path-prefix=$PWD=." cargo +1.96.0 build --release --locked
strip --strip-all target/release/bz2dec

In our check this rebuilt bin/bz2dec-original bit for bit (Rust 1.96.0 from rustup, in another directory). bin/bz2dec-takt is the same source/src/main.rs linked with the TAKT build of the crate, which keeps the crate's public API, error type and messages.

Contents

• bin/: bz2dec-original and bz2dec-takt;
• source/: the driver and the Cargo files from which bz2dec-original is built;
• tools/: fetch_silesia.py (corpus and inputs), run_bench.sh (check and timing), compare_corrupted.py (valid and corrupted streams);
• measurements.json, SHA256SUMS, LICENSE.

The source of the TAKT build of bzip2-rs is not published: we deliver builds.