CS Paper Radar

pigzpp: Fast, Parallel, Portable Compression for the Whole Stack

Thamme Gowda

cs.DC ·submitted 2026-08-25 07:16 UTC · v1

Abstract

pigz is a widely deployed parallel gzip utility, but its process-global mutable state means that it was not designed as a reentrant, directly embeddable library. pigzpp is a from-scratch C++23 rewrite that turns the design into a thread-safe library with one accelerated DEFLATE core exposed to C++, Python, WebAssembly, Go, and Rust. As application-level conveniences built on that same core, it also provides multi-entry ZIP archives and a fast PNG codec. Its portable zlib-ng backend preserves gzip/zlib's ratio; its Intel ISA-L backend is an x86-64-only fast path that produces about 10% larger output at level 6 on our text corpus. In that configuration, zlib-ng reaches 2.1 times the CLI throughput of pigz and 16 times that of Python's in-memory gzip; ISA-L reaches 8.5 times and 50 times, respectively. Outputs remain standards-compliant and cross-decode with gzip, pigz, and unzip. The result is a self-contained, multi-platform compression stack and a case study in AI-assisted modernization under automated compatibility tests.

Closest papers

Nearest neighbours by meaning across the whole index.

WZIP and WLZ4: LZ77 Codecs with Match-Length-Dependent Sliding Windows

cs.IT ·2026-10-08 ·Yingquan "Cody" Wu
code/data similarity 0.59
Abstract · 10 pages, 5 tables, 2 figures. Submitted to the 2027 Data Compression Conference (DCC). Source code: https://github.com/icodywu/WZIP (releas…

An LZ77 codec bounds every match by one sliding window, trading cheap offsets for short matches against reach for long ones. Match-length-dependent windows refine this trade-off: each match length has its own window, and the decoder infers the offset range from the decoded length. We present two such codecs: WLZ4, a byte-aligned LZ4-class format with one-byte and flagged offsets, and WZIP, an entropy-coded Zstandard-class format. Each block begins with its decoded length, from which WZIP derives its widest window and a decoder sizes its output. LZ4 blocks may expand incompressible input by 0.4%; WLZ4 adds at most 15 bytes, WZIP 2. We describe the formats, threaded match finders, decoders and parser. On Silesia, WLZ4 reaches a ratio up to 16% above LZ4HC's, decoding more slowly, and WZIP exceeds Zstandard 22's ratio while its trusted decoder runs at 91% of Zstandard's speed (87% checked; on enwik9, about as fast).

0.58

mold: A Massively Parallel Linker

cs.OS ·2026-08-24 ·Rui Ueyama
top venue similarity 0.57
Abstract · 15 pages, 3 figures, 10 tables. Accepted to ASPLOS 2027

Linking is a critical step in the software build process that combines compiled object files into a single executable or shared library. Despite decades of engineering effort, link times remain a significant bottleneck in the edit-compile-debug cycle, particularly for large C++ programs. Existing linkers exploit limited parallelism, leaving most CPU cores idle during linking. We present mold, a Unix/Linux linker that applies data parallelism systematically across the entire linking pipeline. We first analyze the architectural constraints that prevent existing linkers from scaling, including entangled symbol resolution and archive processing, and then show how a clean-slate design that decouples them overcomes these limitations. On large real-world programs, mold links multi-gigabyte debug binaries in at most a few seconds, and often in under a second. It is 2.4-16.1x faster than the state-of-the-art lld linker, and up to 112x faster than the traditional GNU ld. An ablation study shows that no single optimization dominates; the speedup comes from the cumulative effect of parallelizing all passes.

0.47

The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats

cs.DC cs.DS ·2026-09-15 ·Yakiv Shavidze
similarity 0.57
Abstract · 7 pages, 5 figures, 6 tables. Sixth paper in the ACEAPEX series (see arXiv:2606.04268, 2606.18900, 2606.24531, 2607.18541, 2608.10188). Code…

Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (-0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification - that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound - and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records.

0.50

zip2zip++: Towards Inference-Time Token Compression with Minimal Quality Loss

cs.CL ·2026-10-09 ·Saibo Geng, Andrea Gentilini, Xinxian Ma, Nathan Ranchin, Yunzhen Yao +1 more
code/data similarity 0.55
Abstract · 27 pages, 12 figures, 13 tables. Code: https://github.com/epfl-dlab/zip2zip-plus-plus

Dynamic vocabularies built on-the-fly via Lempel-Ziv-Welch (LZW) compression let a language model represent the same text in fewer tokens, but prior work shows that this efficiency comes at a cost to reasoning and perplexity. We show that this quality gap is not a fundamental price of compression but can be substantially closed through targeted improvements to the compression layer and LZW codec, without modifying the underlying pretrained language model. Our analysis reveals four key issues: (1) LZW's compression algorithm creates an implicit conflict between the input embedding and the output embedding, a tension that a single shared embedding cannot resolve; (2) naively applying RoPE to LZW-compressed sequences ignores that merged tokens can span multiple tokens; (3) merging certain tokens (notably digits) disproportionately hurts downstream accuracy; and (4) dynamic vocabularies introduce an inherent segmentation ambiguity that confounds standard evaluation. We address these through decoupled input/output dynamic embedding layer, size-aware RoPE positioning, and a modified LZW codec supporting selective merges and multi-view segmentations. Across four models, our recipe improves perplexity on every corpus we evaluated as well as mathematical reasoning accuracy, closing roughly half the quality gap between zip2zip and the uncompressed baseline at a similar compression ratio on general text. This represents a significant step toward lossless adaptive-vocabulary compression for language models.

0.39

Beyond Compression Ratio: High-Throughput KV Compression for Disaggregated LLM Serving

cs.DC ·2026-11-03 ·Junhong Wu, Zedong Liu, Xinyang Ma, Yuhan Chen, Guangming Tan +1 more
published similarity 0.54
Abstract · Accepted by The 22nd Annual IFIP International Conference on Network and Parallel Computing (NPC 2026)

KV cache compression reduces the communication volume of disaggregated large language model serving, but its practical benefit depends not only on compression ratio and model quality, but also on how efficiently the compression pipeline executes. This requirement becomes increasingly important as modern serving systems adopt high-bandwidth interconnects, where inefficient compression can offset a substantial portion of the saved communication time. This paper presents FastKVComp, a high-throughput KV cache compression data path built on top of KVServe. FastKVComp improves compression execution in two complementary ways. First, it fuses the distribution transformation and low-bit quantization stages into a KVaware TileLang kernel, eliminating intermediate tensor materialization and redundant memory accesses. Second, it replaces the original lossless compression backend with an open, extensible, and searchable backend based on LC, enabling high-performance compression operator pipelines. The fused kernel achieves up to 5.9x speedup, while the new lossless backend increases compression throughput from below 90 GB/s to over 500 GB/s. Across the evaluated workloads, FastKVComp reduces job completion time by up to 2.04x. End-to-end evaluation shows that these optimizations allow KV compression to retain meaningful communication benefits under modern high-bandwidth network.

0.27

Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing

cs.DS ·2026-10-24 ·Florian Kurpicz, Maximilian Paris
similarity 0.54
Abstract

The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about $20$ bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts but 2.0 to 3.2 times slower on five of six non-repetitive ones, i.e., it provides a trade-off between required device memory and throughput.

0.20

Massively Parallel Algorithms for Huffman Coding

cs.DS ·2026-10-06 ·Masoud Seddighin, Saeed Seddighin
similarity 0.53
Abstract

Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $\TextLength$ over a general alphabet, the goal is to assign a binary codeword to each character so that no codeword is a prefix of another and the total encoded length of the string is minimized. Huffman coding is widely used in practical compression systems, including file compression. As modern datasets continue to grow, it is natural to study whether a Huffman code can be constructed efficiently in the massively parallel computation (\MPC) model. The celebrated Huffman coding algorithm admits two straightforward \MPC implementations: for any constant $ε\in(0,1)$, one uses $O(\TextLength^ε)$ memory per machine but requires $Θ(\log \TextLength)$ rounds, while the other runs in $O(1)$ rounds but requires $Θ(\sqrt{\TextLength})$ memory per machine. We give the first nontrivial \MPC algorithm for Huffman coding that bypasses both limitations. For every constant $ε>0$, our algorithm uses $O_ε(\log\log \TextLength)$ rounds and $\softO(\TextLength^ε)$ memory per machine, while its total memory and total computation are $\softO(\TextLength)$. {\color{black}Although our framework is tailored to the \MPC model, we show that it has applications in the \PRAM setting as well. Specifically, we show that the same algorithm can be implemented in the \PRAM model with total work close to linear. In particular, whenever the text length is at most $2^{O\left(\left(\frac{\log \AlphabetSize}{\log\log \AlphabetSize}\right)^2\right)}$ (slightly superpolynomial), where $\AlphabetSize$ is the alphabet size, our parallel running time is asymptotically better than that of all previously known \PRAM algorithms and is essentially optimal.}

0.26

FastPair: GPU-Optimized String Decoding

cs.DB cs.ARcs.DC ·2026-09-14 ·Joseph Isaacs, Francesco Gargiulo, Peter Boncz, Robert Kruszewski, Nicholas Gates +3 more
similarity 0.53
Abstract

Modern data systems compress data at rest and decompress it only when needed to preserve interconnect bandwidth. This design is often inefficient on GPU-based compute platforms because many conventional compression techniques exhibit serial data dependencies that limit GPU parallelism, leaving resources idle. Recent NVIDIA GPUs address this decoding deficiency through the Decompression Engine (DE), an on-die, fixed-function decompression accelerator for general-purpose compression formats such as Deflate, LZ4, and Snappy. Recent work has proposed string codecs that replace frequent substrings with fixed-width codes from a small, trained dictionary, making each code's lookup independent. While these lookups can run in parallel, the resulting scattered reads and short output writes still do not align well with GPU hardware, which handles contiguous memory accesses more efficiently. We present FastPair, a GPU decoder that optimizes the existing dictionary decoding process by reorganizing lookups and assembling decoded substrings for contiguous output writes. On a B300, FastPair decodes ten real-world columns 2.4 to 4.2x faster than the DE, reaching up to 1.6 TB/s.

0.20