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

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

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.

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

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.

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

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

  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

  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

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

It has the following characteristics:

  - SOTA decompression throughput in its ratio class
  - Decent ratios (comparable to LZ4 at high effort levels)
  - Slow compression

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

Comments URL: https://news.ycombinator.com/item?id=48922838

Points: 114

# Comments: 37

https://github.com/welcome-to-the-sunny-side/misa77/blob/777...