Show HN: misa77 - a codec that decodes 2x faster than LZ4 (at better ratios) (github.com)
I've spent the last few months working on this codec.
It has the following characteristics:
- SOTA decompression throughput in its ratio class
- Decent ratios (comparable to LZ4 at high effort levels)
- Slow compression
Most of the gains can be attributed to reducing branches and making decompression very friendly to out-of-order cores, by using a smart format.
Results on the tarred silesia corpus on Intel x86-64 follow:
codec decode ratio encode
misa77 -0 5219 MB/s 42.64% 54.5 MB/s
misa77 -1 4274 MB/s 39.65% 51.2 MB/s
lz4 2505 MB/s 47.59% 371 MB/s
lz4hc -12 2531 MB/s 36.45% 7.31 MB/s
32 comments
[ 2.8 ms ] story [ 44.1 ms ] threadmisa77 primarily targets textual data (ie. byte-aligned data formats where each byte corresponds to a symbol), so I hadn't tested it on game assets much until now.
After seeing your comment, I pulled some random assets from Pathfinder WoTR (in fact, Unity compresses them with lz4hc) and DOS2. The gains are much more modest here due to asset data being mostly floats, but level 0 performs decently nevertheless.
Results on a map asset (WoTR):
Results on equipment asset (WoTR): Results on texture asset (DOS2): Note: the benchmarking setup is identical to the intel x86-64 one described in the readme.misa77 and oodle are both supported in turbobench (see: https://github.com/powturbo/turbobench), so it's easy to compare them.
Results on the silesia corpus on the same Intel setup described in the README, using turbobench:
Note: selkie -4 corresponds to the "Normal" level here.From memory, 2505 MB/sec also sounds on the low side for LZ4 on a modern CPU?
In short, my decompressor is very simple, and a naive safe version of the decompressor is only about 5% slower than the current unsafe one (and I will add this safe version in v0.3.0).
As for the raw throughput numbers being low here, it's because Intel Turbo (frequency boost) was disabled for stability, and the CPU was running at a fixed frequency of 2.1 GHz (I've confirmed that the relative performance scales similarly even with Turbo enabled).
I don't see much in your README that talks about how a developer would integrate misa into their code. I might suggest some basic code samples to help a developer integrate misa decode into their project.
Congrats, looks like a cool project.
You know, you would expect that this is commonly observed. You'd expect, say, simple RLE (run length encoding) to be like this. It's more expensive to produce output requiring the processing of a large number of RLE opcodes that produce short sequences than one opcode that produces one long sequence.
- 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.
- All 3 things are show stoppers for any real use.
An unstable format which trusts input is a CVE and data loss magnet.
The format, however, might continue to change for some time because I want to push performance even further.
I've been bitten in the past with other libs that weren't as explicit about their stability.
It's a very significant speedup in decompression speed (albeit with a compression speed slowdown as a trade-off), but what's the insight that makes it faster? What was the idea or approach behind it?
But you have to pay the price that you need a slower encoding, because finding matches, putting restrictions on match lengths, putting things in different streams have costs you need to pay upfront.
Anyway good work, there is probably a need for that.
// Currently own Google's snappy and do compression at Google
P.S. if you want better snappy's results, compile with clang.
P.S.S you can optimize aarch64 speed by movemasks from shrn instruction. https://developer.arm.com/community/arm-community-blogs/b/se...
I got really into compression experimenting while I was developing my browser game.
I was trying to compress entire human gameplay matches into a QR code, for upto 60 minutes of gameplay both single player and multiplayer.
My game is a fast paced, grid based, snake x scrabble word game.
My first compression attempt was to do run length encoding and cardinal directions, encoded into 1 byte. This was really compressible data.
The best approach was to use relative direction changes instead of cardinal directions. Compressed even better as the raw data was more consistent (for the most part you are moving forward etc).
Some other attempts were: zone based encoding, double movement pattern encoding (much smaller raw data but less compressible), triple movement pattern encoding, interrupt encoding.
I am at a point where I can fit all 30 minute single player games into a QR code, some 60 minute games, and with a special encoding scheme I can fit 15 minute N player multiplayer matches in a QR code
For reference qr code max size is about ~3000 bytes