Comment by mijoharas

2 hours ago

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?

6 comments

mijoharas

nonadhocproblem 2 hours ago

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.

sroussey 2 hours ago
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.
- nonadhocproblem 2 hours ago
  
  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).
edflsafoiewq 2 hours ago
What's the advantage of the separate streams? That presumably prevents a streaming encoder/decoder.
- nonadhocproblem 1 hour ago
  
  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).