misa77 (0.2.0)
misa77 is an LZ-based codec that targets the write-once, read-many niche. In particular, it aims to satisfy the following criteria:
Extremely high decompression throughput (single-threaded).
Modest compression ratios (it has no entropy backend, so one can obviously not compare it to something like zstd, but LZ4 at high effort levels is a good reference point).
Constant memory use, regardless of input size (<= 5 MB across all compression modes, and 0 MB for decompression).
Slow compression is the obvious tradeoff that one makes to achieve the above.
In addition, misa77 has a somewhat synergizing tendency to decompress highly compressed files faster, leading to the following results:
It offers particularly high decompression throughput on highly compressible files.
Even for moderately compressible files, spending more effort during compression to get a more compressed result leads to better decompression throughput (alongside the natural advantage of better ratios).
This makes high-effort compression particularly attractive for misa77, and inspires some experimental compression modes (refer to src/experimental/) that aim to spend more effort at compression time to produce a compressed stream that is friendlier to the microarchitectures of most CPUs when decompressing said streams.
misa77 also has two compression effort levels as of v0.2.0:
level 0: offers better decode throughput, slightly worse ratio, similar encode throughput
level 1 (default): offers slightly worse decode throughput, better ratio, similar encode throughput
Benchmarks
Detailed results are listed ahead, but here's a terse summary:
misa77 lies on the pareto frontier for decompression throughput vs compression ratio on most shapes of data.
It very frequently decompresses faster even when competitors have a significantly worse ratio.
It is quite slow at compression.
Cross-Platform results for v0.1.0 (across Intel x86-64, AMD x86-64, ARM64) can be found here. Note that these are likely outdated at the time of you reading this.
Some detailed results for Intel x86-64 follow.
Setup:
CPU: Intel(R) Core(TM) i7-14650HX (@2.2 GHz) (Intel Turbo disabled).
Single threaded, pinned to a single performance core.
CPU governor set to performance.
The benchmarking harness is a public fork of lzbench, and can be accessed here.
Results for the Silesia Corpus.
misa77 rows first, then competitors are sorted by decompression speed.
Results for enwik8.
As misa77's performance is quite "spiky" (depending on the shape of the data being compressed), a file-level breakdown for the silesia corpus yields some interesting insights into its performance.
Note:
The visuals that follow are derived from the benchmark results at misc/lzbench-results-archive/0.2.0/intel.txt
misc/lzbench-results-archive/0.2.0/intel.txt
These results are with the same x86-64 (Intel) setup mentioned previously.
Decode speed relative to lz4
At level 0, misa77 decodes faster than lz4 on all 12 files (some by huge margins). All other levels decode faster on 11/12 files. The exception is x-ray, which is highly incompressible (lz4 has a ratio of nearly 1.0 on this file and essentially devolves to a memcpy).
Throughput vs ratio, against popular fast-decode codecs
On the compressible files, misa77 sits on the decode-throughput/ratio Pareto frontier: it decodes fastest while ~matching or beating the ratio of the other fast-LZ codecs. sao and x-ray are exceptions due to the reasons stated before.
Requirements
A C++20 compiler (both GCC and Clang are fine).
CMake >= 3.20.
A little-endian 64-bit system.
The misa CLI needs POSIX (Linux, macOS).
Note: On x86-64, AVX2/SSE2 are selected at runtime. Other architectures use a portable path that has no explicit intrinsics, but is easily auto-vectorizable by compilers (and from my testing, does auto-vectorize on Apple ARM at the very least).
Building
This produces the misa CLI at build/misa. For a binary tuned to the exact machine you'll run it on, add -DMISA77_MARCH=native (I recommend this). To run the round-trip test:
Library Usage
The build produces a static library (CMake target misa77) with a small C++ API in misa77/misa77.h. The easiest integration is a git submodule (or CMake FetchContent) plus:
Sample usage:
Two things to keep in mind:
You must size the destination buffers with compress_bound / decompressed_buffer_bound.
As of v0.2.x, decompress assumes that the input is valid (see Status). An input-safe decoder will be added in v0.3.0.
The experimental modes are declared in misa77/experimental.h, with usage documented in comments (these keep changing frequently so I don't wanna "formally" document them here just yet).
CLI Usage
misa is a single, dependency-free binary with three file-based subcommands. It operates on single files only (there's no directory or pipe support, so tar first if you need those).
misa compress takes -l N / --level N to pick the compression level (default is 1).
There are also some experimental compression modes (at most one at a time, not combinable with --level):
--adaptive and suggest also take --tune loose / --tune tight (similar tradeoffs as level 0/1, and the default is loose) and --sample MB (how much input to sample when picking params, default is 2 MB). Everywhere, -o PATH sets the output path and -f overwrites without asking.
Documentation
The underlying stream format (used by the library functions) and the container format for .misa77 files (produced by the CLI) can be found in docs/.
Status
misa77's format may change unexpectedly as it's still v0.x.y.
The decoder assumes that the input is a valid misa77 stream. Invalid input is UB and I offer no guarantees for whatever misa77 does in this case.
It's been through some local fuzzing but is not hardened, so treat it as experimental.
Note: misa77 has evolved out of a less polished endeavour to learn performance engineering, and its history can be found in this archived repository.
Acknowledgement
Inspiration has been taken from:
LZ4
zxc
lizard
Lastly, Claude Opus 4.8 and Fable 5 helped a lot with scripting, tooling, and building the CLI.
License
MIT (see LICENSE).