nonadhocproblem

the next few years are going to be rough for you...

> uses a specific, objectively nonsensical critique of LLMs (the idea that an algorithm using matrix operations as a primitive cannot emulate "true" intelligence)

> receives pushback on the specific, objectively nonsensical critique

> "oh so you're saying that LLM computation and human cognition are equivalent? they're glorified calculators that disprove the Jacobian conjecture!!!"

just like they RPed disproving the erdos conjecture

> It's matrix multiplication.

Hilarious critique. If you weren't as mathematically illiterate as you likely are, you would know how general matrix operations are, and how essentially any algorithm (including human cognition) can be implemented using them as an intermediate.

I haven't estabilished the jumble of neurons in your skull to be a "mind" either.

So you're distraught at losing the ability to abuse digital minds? Excellent, I'm glad Anthropic introduced this.

update: a safe decoder has been released in v0.3.0, and it's nearly as performant as the unsafe one

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

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.

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.

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

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.

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

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.

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

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.

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

I've also been working on a compressor recently, and the same general idea (letting the compiler know that a data dependency occurs very infrequently, and it should therefore assume none exists to exploit ILP) has allowed me to speed up my decompression by a lot:

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

Please seek help. These levels of copium can't possibly be healthy.

Are you trolling? OpenAI's models resolved the Cycle Double Conjecture yesterday, which has been an open problem for 50 years.