Show HN: misa77 - a codec that decodes 2x faster than LZ4 (at better ratios)

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

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.

misa77 rows first, then competitors are sorted by decompression speed.

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
• These results are with the same x86-64 (Intel) setup mentioned previously.

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).

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.

• 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).

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

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:

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:

add_subdirectory(misa77)
target_link_libraries(your_app PRIVATE misa77)

Sample usage:

#include <misa77/misa77.h>
#include <vector>

// compress (pick a level with misa77::config(0/1); default is 1), returns 0 on failure
std::vector<uint8_t> compressed(misa77::compress_bound(input_size));
uint64_t csize = misa77::compress(input, input_size, compressed.data(), compressed.size());
compressed.resize(csize);

// decompress, returns original_size on success
uint64_t original_size = misa77::decompressed_size(compressed.data());
std::vector<uint8_t> output(misa77::decompressed_buffer_bound(original_size));
uint64_t written = misa77::decompress(compressed.data(), csize, output.data(), output.size());

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).

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   FILE          # -> FILE.misa77
misa decompress FILE.misa77   # -> FILE
misa suggest    FILE          # -> FILE.misap  (tuned params)

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.

misa compress -l 0 enwik8                # enwik8 -> enwik8.misa77, fastest-decode level
misa decompress enwik8.misa77            # back to enwik8

# tune on a sample, then reuse the params:
misa suggest --tune tight data.bin       # -> data.misap
misa compress --params data.misap data.bin

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/.

1. misa77's format may change unexpectedly as it's still v0.x.y.
2. 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.
3. 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.

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.

MIT (see LICENSE).