Repository navigation
MinLZ v1.3 "SIMD Blocks"
Compression ratio like zstd, Decompression speed like LZ4.
MinLZ adds a new block type: SIMD blocks, released for Go (v1.3.0) and Rust at the same time.
They store the output of the LZ compressor
as separate Huffman-coded streams, laid out so that a CPU can decode them with vector instructions
and almost no unpredictable branches.
The result is compression ratios in the range of Zstandard, with decompression 2.2-2.5× faster than Zstandard
(both in Go) and about 2× faster than classic MinLZ blocks, on a single core.
At the default 2 MB block size, MinLZ SIMD "Balanced" beats zstd's fastest level on all three counts:
its output is 2% smaller, it decompresses 2.5× faster on one core (6.4 against 2.6 GB/s),
and it compresses 1.6× faster on 16 threads (1.2× on one).
Against zstd's default level, SIMD Balanced output is 3.6% larger and decompresses 2.3× faster.
Geometric means over 13 data sets, 58 GB in total, Go implementations on an AMD Ryzen 9 9950X.
SIMD blocks are part of the MinLZ format (specification v1.1) and work everywhere MinLZ blocks do:
streams, concurrent compression and decompression, indexes and random access, and search.
mz c writes them by default.
MinLZ is a lossless compression algorithm developed by MinIO,
aimed at modern data formats. It is designed to compress and decompress at I/O speed,
while offering a good compression ratio.
The format has a full, open specification and is the primary compression format used in AIStor.
Goal
The goal of SIMD blocks was to make a block format that did everything possible to work well with SIMD processing.
We keep the existing scalar fixed-format blocks as an option for older CPUs, and for very small blocks.
The trigger point for the new format was when the pivco-huffman project
showed that both entropy encoding and decoding could be done efficiently with SIMD.
I had long held the belief that LZ could be expressed in a way that would be efficient to decode with SIMD,
but it was typically negated by a relatively slow entropy coding.
Goal:
Design a format that allows entropy coding of the LZ and literal data,
where entropy coding could be done with minimal overhead.
A secondary goal was to make the least amount of sacrifice to decompression speed.
I would love to have something that could compete with LZ4 for decompression speed,
and was pleasantly surprised when that was possible with no major sacrifices to compression ratio.
At a glance
Geometric means over 13 data sets on an AMD Ryzen 9 9950X. MinLZ uses 2 MB blocks and zstd a 2 MB window;
LZ4 and gzip use their fixed windows. All codecs are Go implementations, see Benchmarks.
- Against classic MinLZ, at the same level: 17-25% smaller, 1.7-2.0× faster decompression on one core,
and compression at 0.89-0.97× the speed on 16 threads (0.99-1.1× on one). - Against zstd: SIMD Fastest is 3.8% larger than zstd fastest and SIMD Balanced 3.6% larger than zstd default.
They decompress 2.5× and 2.3× faster on one core, and compress 2.6× and 2× faster on 16 threads.
SIMD Smallest is 2.9% smaller than zstd better and decompresses 2.2× faster, but compresses at less than half its speed.
And unlike zstd streams, MinLZ streams are seekable. - Against LZ4: SIMD SuperFast is 21% smaller than LZ4's fast level, decompresses 1.6× faster and compresses 2.5× faster.
- Against gzip: SIMD Fastest is 1% smaller than
gzip -6, and decompresses 8.7× faster. - Below 64 KB blocks, SIMD blocks are still smaller, but each block carries its own Huffman tables,
which costs speed: at 4 KB they decompress at 0.6-1.0× the speed of classic MinLZ. More on that below. - AVX2/NEON: While AVX-512 is the fastest, SIMD blocks decode with AVX2 or NEON too.
On Zen 5, AVX-512 is 5-20% faster than AVX2, so still above scalar speeds.
How it works
The problem with classic LZ decoders
A classic LZ format like Snappy or classic MinLZ interleaves everything in one byte stream:
a tag, some literal bytes, a match, another tag. The decoder reads a tag to learn what comes next,
so every operation starts with a data-dependent branch. Our own assembly decoder for classic MinLZ
has roughly 6-10 conditional branches per operation: the tag type, how long the length field is,
bounds checks, the size class of the copy, and whether the copy overlaps itself.
On real data many of those branches are unpredictable, and every misprediction throws away
work the CPU had started. LZ4 gets its decompression speed from mostly being branchless,
but at a significant efficiency cost.
An interleaved byte stream is also a poor fit for entropy coding. Tags, lengths, offsets and literal bytes
sit side by side, each with its own statistics, so no single code fits them all.
Formats built for entropy coding, like zstd and deflate, compress better, but their decoders pay for it
in the inner loop: deflate decodes every literal, length and distance symbol between copies,
and zstd decodes the codes of each sequence right before running it.
Those bit readers are serial: where a symbol starts depends on the lengths of the symbols before it.
These formats decompress at a fraction of LZ4's speed.
Separate streams
SIMD blocks keep the LZ77 parse, but write each field of it to its own buffer:
- Tokens, one byte per operation: the match length (0-32, or 33 for "longer, see the escapes"),
plus two flags: has literals and repeats the last offset. - Literal lengths, only for operations with literals.
- Offset symbols, only for operations with a new offset. A symbol gives the offset's magnitude.
- Escapes, for lengths over 32.
- Offset bits, the raw low bits of each new offset, which are close to random and not worth coding.
- Literals, all literal bytes of the block.
Up to 16,384 operations form a chunk (the format allows 65,535), and each stream of each chunk is stored as-is
or Huffman coded, with a new table or the one before it.
Literals get their own Huffman blocks. A new table is only written when it saves at least 64 bytes,
since every table also costs decoding time.
Because each stream holds one kind of value, each gets a Huffman table fitted to it:
tokens, lengths and offset classes all have very different statistics.
And since a chunk's streams are entropy decoded before its operations run, the inner loop does no entropy decoding:
it reads plain bytes, plus the raw offset bits.
The two flags in the token mean that operations without literals or without a new offset cost nothing in the other streams.
Splitting the streams is not a new idea. Oodle's Kraken and Mermaid decode this way, LZSSE showed that LZ decoding
can run without branches, and zstd Huffman-codes its literals apart from the sequences.
SIMD blocks combine these ideas in a format with an open specification, with SIMD Huffman decoding
and a branch-free inner loop.
Decoding with few branches
A chunk is decoded in two steps.
First its streams are Huffman decoded with pivco, a SIMD Huffman decoder based on
pivco-huffman, which decodes many symbols in parallel
with AVX-512, AVX2 or NEON. The tokens and literal lengths tell the decoder how many values each stream holds,
so all of a chunk's stream sizes are checked once, before its operations run,
instead of checking bounds on every operation.
Then the operations run. Every operation does the same work:
- copy 32 bytes of literals, and advance by the real literal length;
- pick the new offset or the last one, with a conditional move;
- copy 32 bytes of match, and advance by the real match length.
The flags in the token decide which stream cursors advance, as data, not as branches.
Most operations are shorter than 32 bytes, so this over-copies a little, and the common case has no
data-dependent branch. Copies that overlap themselves take a byte-shuffle path, and lengths over 32 continue in a loop,
so those branches are rare or their cost is spread over a longer copy.
With AVX-512 the decoder expands 64 operations at a time, with about half the instructions per operation of the AVX2 loop.
Profiling Balanced at 1 MB blocks, about three quarters of the time goes to the operations,
16% to Huffman decoding and 8% to setting up the tables.
Offsets are clamped to the output, not checked: decoding never reads or writes outside its buffers,
but a corrupted block can decode to wrong data without an error. Streams catch that with their checksum.
With the block API, add your own checksum, as the README already recommends for MinLZ blocks.
Compression
The four SIMD levels mirror the classic ones: SuperFast, Fastest, Balanced and Smallest.
Their parsers write straight into the streams, and the SuperFast, Fastest and Balanced parsers have
assembly versions for amd64 and arm64 that produce the same output as the Go code.
On one thread, SIMD blocks compress about as fast as classic MinLZ at the same level (0.99-1.1×).
LevelSIMDDelta stores literals as the difference to the bytes at the last offset.
That helps binary data, like tables of numbers, but makes text larger, and it can halve decompression speed
on numeric data with short offsets. Smallest decides this per chunk itself.
What we measured and left out
The format was settled by measuring the alternatives on real data, and dropping what didn't pay:
- FSE-coded Huffman bitmaps (pivco-huffman's PHA mode, with static tables) made Balanced and Smallest blocks
0.005-0.07% smaller, up to 0.5% at the fastest levels. The streams they coded decoded 16-45% slower,
and the decoder needed 50 extra tables. SIMD blocks use plain Huffman coding. - Predefined Huffman tables mainly help small blocks. Instead, a table can be sent as "class lengths",
5-12 bytes per stream, which saved 3.7% at 16 KB and 1.3% at 64 KB. Predefined tables on top of that added 0.3% at 16 KB. - Near-repeat offsets, an offset within ±4 of the last one as a single symbol, saved 0.005%.
SIMD blocks keep one repeat offset. - Dense Streams: Allow the encoder to combine streams into one Huffman block, which saves space on small blocks.
No clear benefit was found, and it complicates the decoder, so dropped. - Folding Literal Length 1: Literals length 1 could sometimes get above 50%, which would make the Huffman encoding
inefficient. Gain was negligible, so dropped. - Absolute Offsets Gains usually about a bit/offset, but specifying it usually costs about the same. Abandoned.
Benchmarks
Setup: AMD Ryzen 9 9950X (16 cores, Zen 5, AVX-512), Windows 11, Go 1.27.1.
Measured with the same harness for every codec, which compresses and decompresses whole files
in memory and keeps the fastest of several passes.
All codecs are Go implementations: MinLZ, klauspost/compress
v1.20.3 for zstd and gzip, pierrec/lz4 v4.1.30 (with its assembly decoder),
and klauspost/pgzip for multithreaded gzip.
The C implementations of LZ4 and zstd are faster than these Go ports, LZ4's in particular,
so the margins against them would be smaller. We haven't measured them here.
klauspost/compress has four zstd levels: fastest, default, better and best. Their compression ratios
are roughly those of C zstd's -1, -3, -7 and -11.
C zstd's higher levels, up to -19 and --ultra -22, compress more, at much lower speed.
LZ4's HC row is pierrec/lz4's level 7.
MinLZ uses its default 2 MB blocks, and zstd is set to a 2 MB window to match.
LZ4 always has a 64 KB window (here with 4 MB blocks), and gzip 32 KB.
Compression speed is measured with 16 threads, since our zstd runs with a 2 MB window were all multithreaded.
Decompression is measured on one core and with 16 threads.
zstd's single-core runs with a 2 MB window were slower than its runs with the default 4-8 MB window,
in a session that didn't match the conditions of the others. For zstd's decompression speed we use the faster of the two,
which can only favor zstd.
The data sets cover logs, JSON, CSV, text, databases, binary serialization, backups and archives:
10gb-tar, apache-log, cockroach-log, consensus-db, enwik9, github-june, github-ranks,
gob-stream, nyc-taxi, parking-citations, rawstudio, reddit and silesia.
2 GB of random data is left out of the averages, since every codec stores it,
and so is an air quality data set that has no single-core runs yet.
To explore more Go benchmarks you can see more data at gocomp.klauspost.com.
Decompression speed against compression ratio
All SIMD levels decompress at 6.4-6.9 GB/s on one core, with compression ratios from 4.7 to 6.3,
against 5.3-6.5 for zstd's levels at 2.6-2.9 GB/s.
Moving up the levels costs almost no decompression speed: the extra compression comes from the parse,
and the decoder does the same work per operation.
| Codec | Ratio | Output | Compress GB/s, 16 threads | Decompress GB/s, 1 core | Decompress GB/s, 16 threads |
|---|---|---|---|---|---|
| MinLZ SIMD | |||||
| SuperFast | 4.68 | 21.38% | 20.89 | 6.94 | 14.64 |
| Fastest | 5.14 | 19.46% | 17.79 | 6.56 | 15.26 |
| Balanced | 5.45 | 18.34% | 10.77 | 6.42 | 15.50 |
| Smallest | 6.28 | 15.92% | 0.95 | 6.44 | 15.11 |
| MinLZ | |||||
| SuperFast | 3.50 | 28.59% | 23.42 | 4.00 | 14.06 |
| Fastest | 4.15 | 24.10% | 18.67 | 3.40 | 14.34 |
| Balanced | 4.55 | 21.99% | 11.27 | 3.18 | 14.59 |
| Smallest | 5.16 | 19.38% | 0.98 | 3.62 | 14.81 |
| zstd | |||||
| fastest | 5.33 | 18.75% | 6.85 | 2.58 | 4.80 |
| default | 5.65 | 17.71% | 5.53 | 2.77 | 5.00 |
| better | 6.10 | 16.39% | 2.17 | 2.92 | 5.61 |
| best | 6.52 | 15.34% | 0.66 | 2.93 | 5.57 |
| LZ4 | |||||
| fast | 3.68 | 27.16% | 8.26 | 4.36 | 9.54 |
| HC, level 7 | 4.35 | 22.99% | 0.96 | 4.06 | 9.52 |
| gzip | |||||
| -1 | 4.43 | 22.59% | 7.01 ¹ | 0.73 | 0.77 ¹ |
| -6 | 5.08 | 19.69% | 3.75 ¹ | 0.75 | 0.80 ¹ |
| -9 | 5.33 | 18.77% | 0.71 ¹ | 0.82 | 0.87 ¹ |
Ratio and speeds are geometric means over the data sets; "Output" is the compressed size as a share of the input.
¹ pgzip.
A few comparisons the summary above doesn't cover:
- SIMD Balanced against zstd's fastest level is 2.2% smaller, decompresses 2.5× faster and compresses 1.6× faster.
- SIMD Fastest is 28% smaller than LZ4's fast level, and decompresses 1.5× faster.
- SIMD Balanced is 2.3% smaller than
gzip -9, and decompresses 7.8× faster. - On one thread, against zstd at its default window (we have no single-thread runs at 2 MB), SIMD Fastest compresses
2.2× faster than zstd fastest, SIMD Balanced 1.5× faster than zstd default,
and SIMD Smallest at 0.38× the speed of zstd better.
The README's per-block-size tables show higher speeds than these: they use the block API, without stream framing
and checksums, on a different mix of data sets.
Compression speed
SIMD SuperFast, Fastest and Balanced compress at 11-21 GB/s on 16 threads, about as fast as the classic levels,
and faster than any zstd level. At the slow end zstd's better and best levels remain ahead:
SIMD Smallest output is 2.9% smaller than zstd better, but it compresses at 0.44× its speed.
Per data set
SIMD Balanced decompresses 1.7-3.0× faster than zstd default on every data set.
Its output is within 5% of zstd default on 10 of the 13 sets, and smaller on apache-log and parking-citations.
On three sets zstd is clearly ahead: github-june (+14.7%), gob-stream (+13.2%) and cockroach-log (+6.7%).
Thread scaling
MinLZ streams compress and decompress their blocks concurrently. Here are the SIMD levels from 1 to 16 threads,
one per core, with an uncompressed MinLZ stream for reference. Writing or reading an uncompressed stream only copies
the data and checksums it, so its line shows how fast this benchmark can move data through memory at all.
Compression scales almost linearly with cores: from 1 to 16 threads, SuperFast goes from 2.1 to 20.9 GB/s (9.7×),
Fastest from 1.6 to 17.8 GB/s (11.3×) and Balanced from 0.9 to 10.8 GB/s (12.3×).
SuperFast and Fastest end above the uncompressed stream, since they write a fifth of the bytes.
Smallest scales 7.1×, to 0.95 GB/s.
Decompression runs at 6.4-6.9 GB/s on one core, reaches 12.3-13.9 GB/s with 4 threads,
and levels off at 14-15.5 GB/s from 8 threads. That is the memory limit of this benchmark: the uncompressed stream
moves 12.2 GB/s on one thread and 13.9 GB/s on 16. SIMD streams end slightly above it, since they read less input.
So 4-8 cores decompress SIMD streams as fast as the output can be written to memory here,
and the cores beyond that are free for other work.
zstd decompresses at 4.8-5.6 GB/s with 16 threads in the same benchmark. A zstd stream can't be spread over many cores
the way MinLZ streams are, since its blocks refer back to the ones before them. For the same reason zstd streams
are not seekable: reading from the middle means decompressing everything before it.
8 MB blocks: the most compression
Larger blocks find more matches. With 8 MB blocks, SIMD Smallest output is 4.8% smaller than at 2 MB,
and it decompresses at 5.8 GB/s per core, 0.9× its 2 MB speed.
Against zstd with its default 8 MB window, SIMD Smallest is 2.7% larger than zstd best and 4.3% smaller than zstd better,
and decompresses 2× faster than either. It compresses 1.6× faster than zstd best, and at half the speed of zstd better.
Unlike zstd's 8 MB window, each MinLZ block is still independent, so streams keep concurrent decompression
and random access.
Block sizes
Each SIMD block carries its own Huffman tables, so the fixed cost per block weighs more as blocks shrink.
The README's single-core block benchmark compares SIMD blocks with classic MinLZ blocks at each block size:
SIMD blocks are smaller at every block size, 10-19% at 4 KB and 17-28% from 64 KB up.
Decompression is 1.6-2.3× as fast as classic MinLZ from 256 KB up, 1.2-1.7× at 64 KB,
and 0.6-1.0× at 4 KB, where setting up the tables is the largest cost. Compression catches up with classic MinLZ at 1-8 MB,
but runs at 0.3-0.6× its speed at 4 KB (Smallest 0.9×).
For blocks below 64 KB, the classic levels are usually the better choice.
Built into MinLZ
SIMD blocks are a block type, not a separate format, so everything built on MinLZ blocks works with them:
- Block API.
EncodewithLevelSuperFastSIMD,LevelFastestSIMD,LevelBalancedSIMDorLevelSmallestSIMD.
Decodehandles both block types. - Streams.
minlz.NewWriter(w, minlz.WriterLevel(minlz.LevelBalancedSIMD)). Blocks are compressed and decompressed
concurrently, and checked with a 64-bit XXH3 hash, which runs at over 100 GB/s,
so checksumming doesn't hold back the faster decoding. - Random access. Blocks are independent, so stream indexes work as before:
WriterAddIndex,IndexStream
and(*Reader).ReadSeekerlet you seek to any offset, which zstd streams can't do.mz cadds an index by default,
andmz d -offset/-tailread from any position without decompressing what comes before. - Search. MinLZ search tables and sidecar files work on SIMD streams,
somz searchcan skip blocks that can't contain a string, without decompressing them. - Command line.
mz cwrites SIMD blocks by default, with 8 MB blocks (the Go library defaults to 2 MB).
mz c -classicwrites classic blocks, andmz statsandmz d -block-debugshow the streams and operations of SIMD blocks.
Rust
SIMD blocks are released in minlz-rs, the Rust implementation of MinLZ,
at the same time as in Go:
- All four SIMD levels, with delta literals, next to the classic levels.
The SIMD encoders write the same bytes as the Go encoders, on every CPU. - Decoding with AVX-512, AVX2 or NEON, picked at runtime, and portable Rust on other targets.
- Streams checked with XXH3, multithreaded compression and decompression, and stream indexes for random access.
Search tables are Go only for now. - A safe public API, no dependencies, and an
mzcommand-line tool like Go's.
On the same machine and buffers, the Rust crate decodes SIMD blocks at 1.07× the speed of the Go package with AVX-512,
and 1.02× with AVX2. Go has assembly parsers for SuperFast, Fastest and Balanced and Rust doesn't,
so single-threaded Rust compression runs at 0.93-0.98× of Go's.
The benchmarks above are from the Go package.
Platforms and compatibility
- amd64: decompression with AVX-512 (F, BW, VL, VBMI, VBMI2) and BMI2, or AVX2 and BMI2.
On Zen 5, AVX-512 is 5-20% faster than AVX2, and all numbers above use AVX-512.
We have measured the AVX2 code on that Zen 5 with AVX-512 turned off, not yet on Intel or older AVX2-only CPUs. - arm64: decompression with NEON, and the same assembly compressors as amd64.
We haven't published arm64 numbers yet. - Other platforms, pure Go builds and x86 CPUs without AVX2 and BMI2 decode SIMD blocks in portable code,
much slower than classic MinLZ. Keep classic blocks there. - Memory: each concurrent decoder keeps about 180 KB, plus a literal buffer of up to the block size.
- Older decoders can't read SIMD blocks. MinLZ v1.2 and older reject them as too large,
since the block type sits in the top bits of the block's size. Streams with SIMD blocks have a flag in the stream header,
so older decoders reject them before the first block.
Use-classic, or a classic level, for data that older readers must decode.
Limitations
- Blocks below 64 KB: see above.
- SIMD Smallest output is still 3.7% larger than zstd best on average at 2 MB, and 2.7% at 8 MB.
Ongithub-june,gob-streamandcockroach-log, SIMD Fastest, Balanced and Smallest output is 7-15% larger
than zstd fastest, default and best. - SIMD Smallest compresses at about 1 GB/s on 16 threads on average, 0.4-3 GB/s depending on the data.
Use it when data is written once and read many times. - Decompression speed depends on SIMD. Without AVX2 or NEON, use classic blocks.
Try it
go install github.com/minio/minlz/cmd/mz@latest
mz c file.log # SIMD Balanced, with mz's default 8 MB blocks
mz c -1 -bs=2M file.log # SIMD Fastest, 2 MB blocks like the Go library's default
mz c -3 file.log # SIMD Smallest
mz c -classic file.log # classic MinLZ blocks, for older readers
mz d file.log.mzcompressed, err := minlz.Encode(nil, src, minlz.LevelBalancedSIMD)
// ...
decompressed, err := minlz.Decode(nil, compressed)In Rust, with minlz = { git = "https://github.com/minio/minlz-rs" } in Cargo.toml:
let mut compressed = Vec::new();
minlz::encode(&mut compressed, src, minlz::Level::BalancedSimd)?;
let mut decompressed = Vec::new();
minlz::decode(&mut decompressed, &compressed)?;- Repository: https://github.com/minio/minlz, and https://github.com/minio/minlz-rs for Rust
- Format: SPEC_SIMD.md, with the Huffman blocks in SPEC_PIVCO.md
- Usage and per-block-size numbers: README.md
What's Changed
- Add SIMD Blocks by @klauspost in #86
- mz: add -search.prefixes.esc for prefix bytes a shell can't pass by @klauspost in #105
- Decode and index BuildSidecar blocks concurrently by @klauspost in #99
- Index search table boundaries for ReadFrom and EncodeBuffer by @klauspost in #97
- Fix sidecar sizes, mz d -block -offset, search exit status and BlockSearcher skip by @klauspost in #96
- Bound the SidecarSearcher coalesced ReadAt span by @klauspost in #98
- Re-call every ErrSearchForward match with contiguous context by @klauspost in #101
- Check that sidecar read pieces overlap and are waited for by @klauspost in #104
- mz: replace read-only inputs in place on Windows by @klauspost in #110
- search: keep FuzzSearchRoundtrip inputs under the fuzz worker deadline by @klauspost in #111
Full Changelog: v1.2.4...v1.3.0