HN 日本語サマリー

← 一覧へ戻る
プログラミング

Ryg_ransはライブラリではない

Ryg_rans Is Not a Library (fgiesen.wordpress.com)

3 pointsby ibobev0 コメント

要約

この記事は、rANS圧縮アルゴリズムの実装であるryg_ransが、ライブラリとして使用されることを意図したものではないことを強調しています。ryg_ransはアルゴリズムの概念を示すための玩具実装であり、実際のプロダクション環境での使用には最適化されておらず、多くの欠点があると説明されています。著者は、実際のプロジェクトでは特定のオプションを選択し、ryg_ransのような玩具実装ではなく、より堅牢で効率的なアプローチを採用することを推奨しています。

全文翻訳

ryg_rans はライブラリではありません

私が ryg_rans を書いたのは2014年のことです。今でも、ライブラリとして使いたいという人から質問やパッチの提出が定期的に届きます。しかし、それは意図された用途ではありません!

ryg_rans はライブラリではなく、かつてそうであったこともありません。これは、コア部分が約20行のコードに収まるアルゴリズムの玩具実装です。これは、金物店で時々見かける、30種類以上の異なるファスナーがねじ止め、ボルト止め、または釘打ちされている木製のボードに相当します。そのアイデアは、あなたがそれをビルド(構築)に使用することではなく、利用可能な選択肢を示すための視覚的な補助です。実際のプロジェクトでは、1つ、あるいはせいぜい2つのオプションを選んでそれに固執すべきです。

ryg_rans 自体を何かに使用すべきではありません。 その目標は、この主題に関する私の執筆に付随する小さな例となることであり、rANS エンコーディング/デコーディングライブラリとなることではありません。後者においては例外的に劣っています。速度のために特に最適化されているわけでもなく(実際、SIMDバージョンでさえ高速ではありません。これらはアイデアを示すためのもので、本番環境で使用するためのものではなく、「正規の」実装と比較して明らかに劣っています)、堅牢でもなく、「すぐに使える」状態でもありません。また、コードに含まれる静的モデルは rANS と一緒に使用するには意味がなく、tANS を使うべきです。静的なバイトモデルが含まれている唯一の理由は、コードが動作する実装として何かを必要としていたためであり、完全に静的なバイト粒度(無意味ではありますが)が最も簡単なモデルだからです。

Oodle LZNA のようなコーデックで rANS を実際に使用する場合、https://fgiesen.wordpress.com/2015/05/26/models-for-adaptive-arithmetic-coding/ で説明されている完全に適応的な「指数移動平均」タイプのモデル、または BitKnit で数百シンボルごとに更新される、実行中のカウントに基づいた半静的モデルのいずれかを使用します。詳細については、https://fgiesen.wordpress.com/2023/05/06/a-very-brief-bitknit-retrospective/ を参照してください。

エイリアステーブル(alias table)のバリアントのようなものは可愛いですが、プロダクションビットストリームに絶対に含めることは強くお勧めしません。なぜなら、それが実際に良いアイデアとなるケースを私は一つも思いつかないからです。それを書いたのは、興味深いと思ったからであり、いつかそれに対する説得力のあるユースケースを思いつくかもしれないと思ったからです。しかし、12年経った今も待っています。エイリアスエンコーディングは、エンコーダーにかなりのサイズの追加テーブルを必要とし、それでも主に静的モデルに縛られます(これは rANS の主な利点を失わせます)、そしてエンコードとデコードの両方に時間がかかります。静的な分布がある場合、tANS/FSE の方がほぼ常に好ましいです。

同様に、同じビットストリーム内で SIMD ISA の利用可能性に基づいた複数のエンコーディング/インターリービングバリアントを使用しないでください。それはひどいアイデアです。ここでも、ryg_rans はその設計空間のアイデアを説明するための玩具例であり、ライブラリの設計図ではありません。フォーマットや実際のライブラリを設計する場合は、選択をする必要があります。ビットストリームは永遠に続くか、それに限りなく近いです。すべてのインターリーブされた ANS バリアントの根本的な問題の1つは、インターリーブされたストリームの数が、実装を大幅に制約する「マジックコンスタント」であるということです。「スイートスポット」は、マシンやマイクロアーキテクチャの種類によって大きく異なり、例えば、ローエンドの32ビットARMマイクロコントローラー(Cortex Mシリーズなど)にとって意味のあるストリーム数と、GPUにとって意味のあるストリーム数との間には、文字通りの重複がありません。

同じビットストリームに多くのバリアントがあると、すべてが悪化します。今や、一部のターゲットには良く、他には悪いエンコーディングが1つあるのではなく、複数のエンコーディング、コードの複雑さと攻撃対象領域の倍増、そして各ターゲットとアプリケーションに対して、通常はインターリービングの「良い」選択肢は1つしかないのです。

さらに重要なのは、例に含まれる静的なバイトモデルの意図しない副作用として、rANS が意味をなすユースケースでは実際には持続不可能である、はるかに高いインターリーブ係数に偏ってしまうことです。適応型モデルを使用する場合(そして使用すべきです。それが rANS を使用する主な理由だからです)、達成できる実用的なインターリーブの程度は、モデルが更新を保留する状態に戻る前に実際に維持できる独立したモデル更新の数によって制限されることが多く、その数はしばしば2または3です。rANS は原理的には非常に大きなインターリーブ係数を使用できるとしても、モデリングの制限のため、ほとんどの実用的な実装では意味のあるものではありません。

ここで最後の点に移ります。rANS では、算術エンコーダーと同様に、確率モデリングと実際のエンコーディングはほとんど常に絡み合っています。静的なバイトモデルは、これら2つが実際に分離されているように見せかけますが、これは例の実装には便利ですが、このアイデアを推奨するものではありません。これは、確率モデリングについて話さない rANS コーディングに関する一連の記事を書く際に、明白な選択肢となるだけです。確率モデリングは、それとは別の懸念事項です。

最後に、時々、境界チェックの欠如のような明らかな欠陥を修正するためにコードを適応させようとするパッチを受け取ります。ryg_rans のビットストリーム決定に忠実であることが、実際の目的を果たすとは思いません。ryg_rans のビットストリーム形式はかなり悪く、私はそれに費やした思考時間は文字通り5分未満です。繰り返しになりますが、これはお勧めできるものではありません。捨てて、自分でやりなさい。

参考までに、rANS 実装を書きたい場合の実際のおすすめを以下に示します。

  • 32ビット以上のターゲットでバイトベースの正規化を使用する良い理由はありません(少なくとも私が見つけた限りでは)。そのバリアントは、推奨する点があるからというよりは、従来の算術/範囲エンコーダーとの類推によってコードに存在します。32ビットターゲットに関心がある場合、または64ビット整数除算が遅いターゲットでエンコードする場合(BitKnit が行うこと)は、32ビット状態と16ビット粒度正規化を使用するか、そうでない場合は64ビット状態と32ビット粒度正規化を使用してください。
  • インターリービングに関しては、暗黙的なインターリービングと2つの交互状態 がスイートスポットです。エンコーダーとデコーダーの両方でコーディングが非常に簡単で、通常はコーディングスループットをほぼ倍増させます。
  • 同じ投稿 には、私の好むエンコーディング/デコーディング戦略も含まれています。デコーダーは順方向に動作し、エンコーダーは逆方向に動作し、モデリングは常に順方向です。後者は、エンコーダーが順方向(「自然」)順序で確率モデリングを行い、コーディング決定をバッファに保存し、定期的に rANS エンコーディングでフラッシュする必要があることを意味します。
  • エイリアステーブル方式は、実用的にうまく機能する方法を見つけない限り、何にも使用しないでください :)。可愛らしいですが、エンコードが少し面倒でデコードが遅いため、アイデアが斬新であること以外に推奨できる点はほとんどありません。少なくとも現在の実装ではそうです。
  • モデルが静的なシンボル確率を使用する場合、tANS を使用すべきです(例外: ハードウェアまたは SIMD のユースケースで、ギャザーよりも数学が大きな利点となる場合)。
  • 実際の適応型モデルについては、上記でリンクされている指数移動平均タイプのモデルが、依然としてスイートスポットだと思います。最大17シンボルは、128ビットSIMDでかなり安価に処理できます(16ビットの確率値を使用しますが、それは十分です)。9(または8)シンボルはさらにわずかに安価です。
  • 超広帯域のインターリーブ係数は興味深い好奇心ですが、ビットストリームにマジックコンスタントが組み込まれており、他のもの(言うまでもなく、無駄なビットのオーバーヘッドがかなり追加されること)でのデコードが遅くなるというのは深刻な問題です。無用ではありませんが、私はそれに満足しておらず、推奨するかどうかはわかりません。

以上です!