It's a somewhat known tradeoff, you can streamline and make the format friendlier to do memcpy which this library targets, the more memcpys you do, the faster it is overall to decode. On highly compressible data lz4, snappy become faster. Snappy on level 2 has faster decompression speed

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

Thanks for the feedback!

I haven't implemented any ARM-specific dispatch yet (there are currently no NEON paths for vector ops either, and we instead trust the compiler to autovectorize), and will do so for upcoming versions.

Is there a way to regain some compression ratio in Snappy if you're okay with slow compression but need fast decompression?

Compression is so tricky.

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

From status in readme in github:

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

- Excellent of the author to call these things out.

- All 3 things are show stoppers for any real use.

An unstable format which trusts input is a CVE and data loss magnet.

I'll be resolving issues 2 and 3 in the next couple of weeks (adding a safe decoder and doing a lot of fuzzing).

The format, however, might continue to change for some time because I want to push performance even further.

Which is great and please don't take this as me being critical of the approach you are taking. I think it's perfectly reasonable during early development have your compressed stream in flux.

I've been bitten in the past with other libs that weren't as explicit about their stability.

That is a bit too harsh. Not all applications require those guarantees. It’s fine if you can trust the inputs.

The inputs can never be trusted

If inputs are part of the application bundl3, they can be trusted as much as the code itself.

So, I couldn't see it in the readme, apologies if I missed it but why?

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?

So it's essentially "LZ4 unshackled". I've made several modifications to the LZ4 format, most of which are in service of eliminating branches/making them more predictable, and making decompression very friendly to out-of-order cores by hiding false data dependencies behind a rarely taken branch (similar to this: https://news.ycombinator.com/item?id=48889148).

Some concrete changes in the format are:

  - match length per block is capped to 32
  - distance to a match must be >= a fixed constant
  - unlike lz4, tokens and literals have separate streams
  - format of the token byte has been changed

Now, this format allows our decompressor's hot loop to be very simple (in terms of the number of branches it has). This simplicity in turn allows our compressor to create a compressed stream that is friendly to the (small number of) branches in the decompressor.

The experimental compression modes (see readme) attempt to exploit this even further (but are even slower at compression). I define a "cost", which is a linear function of the branches induced by a compressed stream (this function serves as a proxy for decompression time), and then do a DP to minimise this cost.

How much of the speed-up is attributed to not hardening the code?

And i do not mean this in a flippant way, as how to harden with speed in mind might alter how to design the format and the codec.

Almost none. Once again, simplicity comes to our rescue here. The decompressor is simple and a naive safe version I implemented but haven't merged into main yet (see: https://encode.su/threads/4514-misa77-ridiculously-fast-deco...) is only ~5% slower than the current unsafe version (and can very likely be made faster).

What's the advantage of the separate streams? That presumably prevents a streaming encoder/decoder.

Yes, that prevents streaming for now.

What is the advantage of this? Out-of-order execution (see my decoder's hot loop: https://github.com/welcome-to-the-sunny-side/misa77/blob/3a9...).

In particular, on even moderately compressible data most blocks take the following form:

  - 1 token byte + 2 distance bytes 
  - a somewhat unpredictable number of literal bytes

If these streams are interleaved, then it's harder for the out-of-order core to process the token bytes of several blocks in advance (as the position of the next token byte depends on the unpredictable number of literal bytes in the current block). However, if you separate them (all token bytes in a prefix, and literal bytes in a suffix), the CPU can speculatively parse token bytes of a lot of blocks in advance (as most of the time, it just has to step forward by three bytes to go to the next block's token byte).

I used the same "separate stream" design (one of them coded backwards from the end, to eliminate the need to send a separate offset) when working on video compression, to separate out arithmetic-coded bits from literal bits. It's a good idea. The only reason it isn't in AV1 is because hardware wanted to do DRM decryption in order.

Nice results, I will keep a watch on this! Would be interesting to see benchmarks vs Oodle compression, I think the most similar one is Selkie?

Yes, the most similar one is indeed Selkie.

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:

  codec       decode      ratio    encode
  misa77 -0   5309 MB/s   42.64%   58.2 MB/s
  misa77 -1   4332 MB/s   39.65%   54.5 MB/s
  selkie -1   3095 MB/s   43.48%   197 MB/s
  selkie -2   3013 MB/s   41.80%   163 MB/s
  selkie -3   3081 MB/s   39.58%   95.8 MB/s
  selkie -4   3498 MB/s   36.95%   43.3 MB/s
  selkie -5   2607 MB/s   33.58%   2.97 MB/s
  lz4         2530 MB/s   47.60%   373 MB/s

Note: selkie -4 corresponds to the "Normal" level here.

Any chance you can throw lzop into that table just as a reference point?

Added memcpy in here too, same setup as before:

  codec       decode        ratio     encode
  misa77 -0   5302 MB/s     42.64%    58.7 MB/s
  selkie -3   3078 MB/s     39.58%    97.0 MB/s
  lzo1x -1    421 MB/s      47.48%    314 MB/s
  memcpy      12135 MB/s    100.00%   11952 MB/s

Almost double the decompression speed, *and* a higher compression ratio than LZ4? That's very promising.

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.

Interesting, but 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.

From memory, 2505 MB/sec also sounds on the low side for LZ4 on a modern CPU?

Someone asked this on encode.su too (see my reply here: https://encode.su/threads/4514-misa77-ridiculously-fast-deco...).

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

You mean some kind of error detection? LZ4 doesn't have that.

Have defined behaviour on any input, i.e not causing security issues, memory safety issues on untrusted inputs. Lz4 has this.

> It offers particularly high decompression throughput on highly compressible files.

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.

this is super interesting! im excited to give this a look this afternoon, since I specifically have wanted faster throughout for decompressing maps in a game engine.

Hey, glad to hear that you found it interesting.

misa77 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):

  codec       decode      ratio    encode
  misa77 -0   4061 MB/s   61.52%   40.4 MB/s
  misa77 -1   2851 MB/s   59.04%   36.2 MB/s
  lz4         2561 MB/s   62.66%   488 MB/s
  lz4hc -12   2428 MB/s   55.53%   6.23 MB/s

Results on equipment asset (WoTR):

  codec       decode      ratio    encode
  misa77 -0   4675 MB/s   54.33%   48.6 MB/s
  misa77 -1   3752 MB/s   51.96%   40.9 MB/s
  lz4         3101 MB/s   55.21%   497 MB/s
  lz4hc -12   3036 MB/s   47.62%   6.25 MB/s

Results on texture asset (DOS2):

  codec       decode      ratio    encode
  misa77 -0   5546 MB/s   67.99%   47.0 MB/s
  misa77 -1   2991 MB/s   63.79%   31.5 MB/s
  lz4         3602 MB/s   68.53%   623 MB/s
  lz4hc -12   2689 MB/s   59.30%   9.01 MB/s

Note: the benchmarking setup is identical to the intel x86-64 one described in the readme.

You can look at the LZ4 decompression implementation in ClickHouse: https://presentations.clickhouse.com/2018-highload-siberia/ (the presentation is quite old, but the implementation was updated recently). It uses the same LZ4 format, just decompresses faster.

It is slower than LZ4 on AArch64.

Could you tell me what your test setup and corpus was?

For reference, to test ARM64, I tested v0.1.0 on an M3 mac with this fork of lzbench: https://github.com/welcome-to-the-sunny-side/lzbench/tree/ad...

Here, lz4's decompression speed was far slower than misa77 and zxc. Results are here: https://github.com/welcome-to-the-sunny-side/misa77/blob/mai...

Source?

Just tested a few minutes ago on the ClickBench dataset. Overall quite good, but, depending on particular columns, most of the time slower - e.g., ~2.0 vs ~2.8 GB/sec on Graviton 4 machine in AWS.

You probably meant MB/sec not GB.

No? Decompression is rated in GB/s per core now.

Parent fixed the error I pointed out since making my post by dividing by a thousand instead of changing the units so now my comment looks wrong.

It used to say 2800 GB/s which is obviously bonkers.

Yes, it was a typo. Thank you!

Can you use it in parquet?

This looks awesome for boot firmware. How large is the decompressor code?

how does it compare to macklin71?

What's the Weissman score?

so whats the actual use case for this ? streaming ? games?

cool, now do zstd!

Zstd already follows the pareto line very closely and also decompresses pretty fast. In case you're looking for a memory-safe version in Rust that avoids the FFI penalty in hot loops, optimized to hell and back, this here is the new kid on the block: https://github.com/paddor/zrip