logoalt Hacker News

mijoharas • today at 6:24 PM • 2 replies • view on HN

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?

Replies

nonadhocproblem • today at 6:34 PM

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.

➕ show 2 replies