LZ4の2倍速！圧縮率も優秀な新コーデック「misa77」を自作しました

ここ数ヶ月間、新しいコーデックの開発に取り組んできました。主な特徴は以下の通りです。・同クラスの圧縮率の中でトップクラスの展開スループット・良好な圧縮率（高負荷設定時のLZ4に匹敵）・圧縮は低速。この高いパフォーマンスは、スマートなフォーマットを採用することで分岐予測ミスを減らし、アウト・オブ・オーダー実行が効きやすい構造にしたことが大きな要因です。Intel x86-64環境でのSilesiaコーパス（tar形式）を用いたベンチマーク結果を以下に示します。

  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

これすごく面白いね！今日の午後にでもチェックしてみるよ。ゲームエンジンでマップを展開する際のスループットを上げたいとずっと思っていたからさ。

良い結果だね、注目しておくよ！Oodle圧縮とのベンチマーク比較があると面白いかも。一番近いのはSelkieかな？

面白いけど、壊れたデータや悪意あるデータに対する堅牢性がないなら、アルゴリズムの分類が全く別物になるから単純に速度を比較するのは難しいね。

記憶が確かなら、最新のCPUでLZ4の2505 MB/秒っていうのは少し遅い気がするけどどうなんだろ？

展開速度がほぼ2倍で、しかもLZ4より圧縮率も高いのか？それはかなり期待できそう。

READMEを見た感じ、開発者がどうやってmisaを自分のコードに統合するのかがいまいち分かりにくいね。統合の手順がわかるような基本的なコードサンプルがあれば良いと思う。

おめでとう、クールなプロジェクトだね。

圧縮率の高いファイルに対して特に高い展開スループットを実現する

これってよくあることだと思うよ。例えば単純なRLE（ランレングス符号化）でも同じようなことが言えるでしょ。短いシーケンスを生み出す多数のRLEオペコードを処理するよりも、1つの長いシーケンスを生み出す1つのオペコードを処理する方がコストは安く済むからね。

GitHubのREADMEにあるステータスを見ると：

• misa77のフォーマットはまだv0.x.yなので、予告なく変更される可能性がある。

• デコーダーは入力が有効なmisa77ストリームであることを前提としている。無効な入力はUB（未定義動作）であり、その場合にmisa77がどうなるかの保証は一切ない。

• ローカルでのファジングは行っているが、ハードニングはされていないので実験的なものとして扱ってほしい。
  とのこと。

AArch64だとLZ4より遅いよ。

READMEで見落としていたらごめん、なぜこれが速いのか理由が知りたい。展開速度が大幅に向上している（トレードオフとして圧縮速度は低下しているみたいだけど）のはすごいけど、何がこの高速化を生んでいるの？背後にあるアイデアやアプローチを教えてほしい。

これはよく知られたトレードオフだね。このライブラリが目指しているように、フォーマットを整理してmemcpyを使いやすくすればするほど、全体的な展開速度は速くなる。圧縮率の高いデータだとlz4やsnappyの方が速いし、Snappyのレベル2は展開速度が速いよ。

ただ、エンコードが遅くなるという代償がある。一致箇所を探したり、一致長に制限をかけたり、異なるストリームにデータを分けたりするのには前もってコストがかかるからね。

とはいえ良い仕事だと思うよ、そういう需要は間違いなくあるはず。

// 私は現在GoogleでSnappyを管理しつつ、圧縮技術の仕事をしている者より

追伸：Snappyでより良い結果を出したいなら、Clangでコンパイルしてね。

追伸2：AArch64の速度を最適化したいなら、shrn命令からのmovemasksを使うといいよ。 https://developer.arm.com/community/arm-community-blogs/b/se...

圧縮って本当に奥が深いよね。

ブラウザゲームを開発していた時に圧縮実験にハマったことがあるんだ。

最大60分のシングルおよびマルチプレイヤーのゲームプレイ全編をQRコードに収めようとしていたよ。

自分のゲームは、グリッドベースのテンポの速いスネーク×スクラブルのような単語ゲームなんだけどね。

最初の圧縮試行は、ランレングス符号化と1バイトにエンコードした方位角を使う方法だった。これはかなり圧縮しやすかった。

一番うまくいったアプローチは、絶対的な方位の代わりに相対的な方向の変化を使うことだった。生のデータ（大抵は前進し続けるような動き）に一貫性があるから、さらにうまく圧縮できたんだ。

他にも、ゾーンベースの符号化、移動パターンの二重符号化（生データは小さくなるが圧縮率が下がる）、三重符号化、割り込み符号化なんかを試したよ。

今では30分のシングルプレイゲームなら全て、60分のゲームの一部、そして特殊な符号化スキームを使えば15分のN人マルチプレイヤーマッチをQRコードに収められるレベルになった。

ちなみにQRコードの最大サイズは約3000バイトだね。