Show HN: misa77 - a codec that decodes 2x faster than LZ4 (at better ratios)

nnonadhocproblem about 2 hours ago 7 commentsRead Article on github.com

FR version is available. Content is displayed in original English for accuracy.

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

⚡ Community Insights

Discussion Sentiment

100% Positive

Analyzed from 289 words in the discussion.

Discussion (7 Comments)Read Original on HackerNews

scottchiefbaker•7 minutes ago

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.

Sesse__•13 minutes ago

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?

nonadhocproblem•9 minutes ago

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

logdahl•14 minutes ago

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?

bootlegbilly•about 1 hour ago

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.

nonadhocproblem•2 minutes ago

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.

throwaway74747•14 minutes ago

What's the Weissman score?