PFC: Zero-Copy Data Compression Through
Prefix-Free Codecs and Generic Programming

This work makes the following contributions:

1. 1.

   Zero-copy invariant architecture: A design where in-memory bytes equal wire bytes, eliminating marshaling overhead entirely.

2. 2.

   Complete algebraic type system: Full support for product types (tuples), sum types (variants), optional values, and recursive structures, all maintained in compressed form.

3. 3.

   Generic programming methodology: A concepts-based architecture following Stepanov’s principles of regular types, value semantics, and algorithmic abstraction.

4. 4.

   STL integration: Proxy iterators and type-erased containers that work seamlessly with standard algorithms while maintaining zero-copy semantics.

5. 5.

   Comprehensive codec library: Universal codes (Elias Gamma/Delta/Omega, Fibonacci, Rice), numeric types (configurable floating point, rationals, complex numbers), and composite encodings.

PFC follows Alex Stepanov’s generic programming principles from Elements of Programming [1]:

• •

  Regular types: All types are copyable, assignable, and comparable with expected semantics.

• •

  Value semantics: Objects behave like mathematical values, not references or pointers.

• •

  Algebraic structure: Types form algebras with well-defined composition operations.

• •

  Algorithmic abstraction: Algorithms are independent of data structures through concepts.

• •

  Zero-cost abstractions: Template metaprogramming provides abstraction without runtime overhead.

The zero-copy invariant emerges naturally from these principles. If compression is a property of types rather than an external operation, and if all operations preserve value semantics, then the compressed representation is the value.

Universal codes [2, 3] provide asymptotically optimal encoding for integers without prior knowledge of the distribution. The library implements several fundamental schemes:

Elias Gamma: For positive integer $n$, write $n$ in binary as $1b_{k-1}\mathrm{\dots }{b}_0$ where $k=\lfloor {\log }_{2}n\rfloor +1$. The encoding is $(k-1)$ zeros followed by the binary representation. This requires $2\lfloor {\log }_{2}n\rfloor +1$ bits.

Elias Delta: Improves on Gamma by encoding the length in Gamma code. For $n=1b_{k-1}\mathrm{\dots }{b}_0$, encode $k-1$ in Gamma, then write $b_{k-2}\mathrm{\dots }{b}_0$. This achieves ${\log }_{2}n+2{\log }_2{\log }_{2}n+O(1)$ bits.

Fibonacci: Based on Zeckendorf’s theorem that every positive integer has a unique representation as a sum of non-consecutive Fibonacci numbers. The encoding uses the corresponding bit pattern terminated by two consecutive ones.

Rice/Golomb: Parametric codes optimal for geometric distributions with parameter $p=2^{-k}$. For parameter $k$, encode $n=qk+r$ as unary $q$ followed by binary $r$ in $k$ bits.

The critical property enabling our architecture is that prefix-free codes compose: the concatenation of two prefix-free encodings is itself prefix-free. This allows arbitrary nesting without delimiters:

This compositional property extends to arbitrary type structures, enabling product types, sum types, and recursive definitions while maintaining the zero-copy invariant.

Unlike byte-oriented serialization, prefix-free codes require bit-level operations. The library provides BitWriter and BitSink abstractions:

The corresponding BitReader maintains symmetry for decoding. Both are zero-overhead abstractions: the compiler typically inlines all operations, producing code equivalent to hand-written bit manipulation.

Codecs define the transformation between values and bit sequences. The library uses C++20 concepts to specify requirements:

Each codec is a stateless type providing static encode and decode methods. This design enables compile-time composition and eliminates virtual dispatch overhead.

The Packed<T, Codec> template wraps a value with its encoding scheme:

This design separates the value from its encoding strategy, enabling runtime selection of codecs while maintaining type safety.

Product types combine multiple values. The PackedPair implementation demonstrates the approach:

The encoding is simply the concatenation of element encodings. For example, a pair of Elias Gamma encoded integers $(5,3)$ requires only $3+2=5$ bits, not aligned to byte boundaries.

Sum types (discriminated unions) encode a choice among alternatives. The PackedVariant uses minimal bits for the discriminator:

For $n$ alternatives, the discriminator requires $\lceil {\log }_{2}n\rceil$ bits. A variant of four packed integers uses only 2 bits for discrimination plus the value encoding.

Optional types (Maybe/Option) are special cases of sum types:

The encoding uses a single bit for the presence flag. The Unit type encodes nothing, serving as the identity element for products.

The prefix-free property enables recursive type definitions. A linked list:

Each cons cell encodes as a discriminator (1 bit), the element, and recursively the tail. The nil case uses just the discriminator. This achieves near-optimal encoding for lists: 1 bit overhead per element.

Similarly, binary trees:

The shared pointer codec encodes a boolean flag for null, then recursively the pointed-to value. This prevents infinite recursion during encoding while maintaining structural sharing in memory.

The PackedContainer stores elements sequentially and maintains byte offsets:

The offset vector enables $O(1)$ random access. For $n$ elements, we store $n+1$ offsets (the final offset marks the end). Memory overhead is $n\times sizeof(size\mathrm{\_}t)$ bytes, independent of element size.

Direct element access would violate the zero-copy invariant by creating unpacked copies. Instead, we use proxy objects that decode on access:

The proxy provides value semantics while deferring actual decoding until needed. Comparison operators convert through the value type, enabling natural usage:

STL algorithms require iterators satisfying specific concepts. The PackedIterator provides random access semantics:

This design enables standard algorithms:

The compiler optimizes through the proxy layer, producing code nearly as efficient as hand-written decoding loops.

The FloatingPoint<MantissaBits, ExponentBits> codec enables precision-space tradeoffs:

This approach supports half-precision (16-bit), single-precision (32-bit), and custom formats. For machine learning applications, BFloat16 (7 mantissa bits, 8 exponent bits) provides a favorable accuracy-size tradeoff.

Exact rational arithmetic uses continued fraction approximation:

For ratios with small numerators and denominators, this achieves excellent compression. The fraction $22/7$ (pi approximation) encodes in fewer bits than a 32-bit float.

Both rectangular and polar representations are supported:

Applications can choose the representation matching their data characteristics.

A transform that produces new packed containers:

Each element is decoded exactly once, transformed, then re-encoded. The result container uses the same codec, maintaining compression.

Support for C++17 execution policies:

Decoding parallelizes naturally since elements are independent. Re-encoding could be parallelized by pre-computing offsets, at the cost of additional complexity.

Some algorithms exploit encoding properties. For sorted data with unsigned integers and monotonic codecs (like Elias codes), lexicographic byte order equals numeric order. This enables sorting the compressed representation directly:

This optimization is significant: sorting compressed data without decompression.

Codecs compose through templates:

The compiler inlines through multiple codec layers, producing optimal code with zero overhead.

C++20 concepts provide clear error messages and enable SFINAE-like behavior:

This documents requirements explicitly and prevents invalid compositions at compile time.

The offset vector enables $O(1)$ random access but adds space overhead. For $n$ elements with average size $b$ bits, total storage is:

The overhead becomes negligible when $b\gg 8\times sizeof(size\mathrm{\_}t)$, typically when average element size exceeds 64 bits (for 64-bit systems). For smaller elements, the compression ratio must exceed $8\times sizeof(size\mathrm{\_}t)/b$ to benefit.

Alternative designs trade access time for space. A container without offsets requires linear scan for access but eliminates overhead entirely, suitable for sequential-only workloads.

For geometric distributions with parameter $p$, Elias Gamma achieves expected length:

For $p=0.1$ (mean value 10), this gives approximately 3.3 bits per value, compared to 32 bits for standard representation—a 9.7× compression ratio.

Rice codes with optimal parameter $k=\lceil -{\log }_{2}p\rceil$ achieve:

For geometric distributions, this approaches optimality.

The zero-copy invariant trades CPU for memory. Decoding costs dominate access patterns. For Elias Gamma, decoding requires:

• •

  Count leading zeros: $O(1)$ with hardware support (__builtin_clz)

• •

  Read bits: $O(\log n)$ for value $n$

Modern processors perform these operations in nanoseconds. For data accessed infrequently or streamed sequentially, the compression benefit outweighs decode cost.

Preliminary benchmarks on an x86-64 system with 1M element containers:

Access time includes decode overhead. For applications with large datasets fitting in compressed form but not uncompressed (e.g., exceeding cache or RAM capacity), the effective performance gain is substantial.

Elias [2] introduced the fundamental gamma and delta codes. Rissanen and Langdon [4] developed arithmetic coding for optimal compression. Our contribution is not new codes but rather their integration into a type-safe, zero-copy programming model.

Traditional libraries like zlib and LZ4 operate on byte streams, requiring explicit compress/decompress steps. Protocol Buffers [5] and FlatBuffers [6] provide zero-copy deserialization but require schema compilation and do not support arbitrary composition.

The most similar work is Cap’n Proto [7], which achieves zero-copy through fixed-width encoding. Our approach extends this to variable-length encodings, achieving better compression at the cost of random access overhead.

Stepanov and McJones [1] established the foundations of generic programming in Elements of Programming. Alexandrescu [8] demonstrated advanced template techniques in Modern C++ Design. We apply these principles to compression, showing that generic programming naturally extends to bit-level data representations.

The C++ Ranges library [9] provides composable views over sequences. Our packed containers and iterators follow similar compositional principles but operate at the bit level rather than element level.

Recent work explores type systems for compression. Zhang et al. [10] present a Haskell library for typed binary formats. Our work differs in maintaining the zero-copy invariant: we do not separate encoded and decoded representations.

1. 1.

   Random access overhead: The offset vector adds memory overhead proportional to element count. For very small elements or huge containers, this may dominate.

2. 2.

   Update performance: Modifying an element requires re-encoding subsequent elements. A sophisticated implementation could use gap buffers or piece tables to amortize this cost.

3. 3.

   Parallel encoding: While decoding parallelizes naturally, encoding requires sequential offset computation. Parallel prefix sum algorithms could address this.

4. 4.

   Cache efficiency: Variable-length encoding may reduce spatial locality compared to fixed-width representations.

Several extensions would enhance the library:

Adaptive coding: Huffman coding with precomputed or learned tables for specific data distributions.

Arithmetic coding: For optimal compression when probability distributions are known.

Dictionary methods: LZ77/LZ78 variants for repetitive data, challenging due to the zero-copy constraint.

SIMD optimization: Vector instructions could accelerate encoding/decoding of fixed-width codes.

Persistent data structures: Copy-on-write semantics could improve update performance for large containers.

Compile-time format verification: Dependent types or constexpr evaluation to verify codec compatibility at compile time.