misa77 0.2.0: High-Throughput LZ-Based Decompression Codec

misa77 0.2.0: High-Throughput LZ-Based Decompression Codec

misa77 0.2.0 is an LZ-based codec optimized for the "write-once, read-many" niche, prioritizing extreme single-threaded decompression throughput over compression speed. By shifting the computational burden to the compression phase, misa77 achieves decompression speeds 1.5-3x faster than LZ4 on x86 and ARM architectures while maintaining competitive compression ratios.

Decompression Performance and Benchmarks

misa77 consistently outperforms LZ4 and other fast-decode codecs in decompression throughput, particularly on highly compressible data.

In benchmarks using the Silesia Corpus and enwik8 on an Intel Core i7-14650HX, misa77 (level 0) achieved decompression speeds significantly higher than its competitors:

  • Silesia Corpus: misa77 0.2.0 (-0) reached 5219 MB/s, compared to LZ4 1.10.0's 2505 MB/s.
  • enwik8: misa77 0.2.0 (-0) reached 4802 MB/s, compared to LZ4 1.10.0's 2355 MB/s.

Performance characteristics include:

  • Pareto Frontier: misa77 typically sits on the Pareto frontier for decompression throughput versus compression ratio for most data shapes.
  • Compressibility Synergy: The codec decompresses highly compressed files faster. Spending more effort during compression to achieve a better ratio often results in higher decompression throughput.
  • Edge Cases: Performance may dip on highly incompressible files. For example, on the x-ray file in the Silesia corpus, LZ4 may be faster because it effectively devolves into a memcpy operation.

Technical Design and Trade-offs

misa77 trades slow compression speed for near-instantaneous decompression and constant memory overhead.

To achieve its throughput goals, the codec implements the following constraints:

  • Memory Usage: Memory use remains constant regardless of input size, requiring $\le 5$ MB across all compression modes and 0 MB for decompression.
  • Compression Effort: Compression is intentionally slow. This is the primary trade-off required to produce a stream that is optimized for the microarchitectures of modern CPUs.
  • Architecture Support: The codec is designed for little-endian 64-bit systems. On x86-64, it utilizes AVX2/SSE2 at runtime. Other architectures use a portable path that is designed to be easily auto-vectorized by compilers (e.g., Apple ARM).

Compression Levels and Modes

misa77 provides multiple effort levels and experimental modes to tune the balance between ratio and decode speed.

As of version 0.2.0, the codec offers two primary levels:

  • Level 0: Optimized for the highest decode throughput with a slightly worse compression ratio.
  • Level 1 (Default): Optimized for a better compression ratio with slightly lower decode throughput.

Experimental modes available via the CLI include:

  • --adaptive: Autotunes the compressor based on input data for maximum decode speed.
  • --yolo: A high-effort mode designed specifically for decode optimization.
  • --params: Allows compression using a parameter vector generated by the misa suggest command.

Implementation and Status

misa77 is currently an experimental project in the v0.x.y stage and is not yet hardened for production use.

Users should be aware of the following current limitations:

  • Format Stability: The stream format may change unexpectedly.
  • Security: The decoder assumes input is a valid misa77 stream. Invalid or malicious input results in undefined behavior (UB), as the codec is not yet hardened against corrupted data.
  • Requirements: Building requires a C++20 compiler, CMake $\ge 3.20$, and a little-endian 64-bit system.

Community Insights and Perspectives

Discussion among technical peers highlights both the potential and the risks of the current implementation:

"If you are not robust to corrupted/malicious data, it is really in a different class of algorithm and it is hard to compare speeds directly."

Other contributors noted that the trade-off of slow encoding for fast decoding is a known strategy to streamline formats for memcpy operations, which is particularly useful for use cases like game engine map decompression or boot firmware where read speed is critical.

Sources