或るプログラマの一生

以前、AVX2 を利用してハフマンデコードにおける複数ストリーム同時デコードを試したことがありますが、今度は単一のストリームで複数シンボルを同時にデコードする話です。

ハフマンデコードは、符号語列の先頭何ビットかをテーブルインデックスとしてデコードテーブルを引き、インデックスビット数以下の長さの符号語が先頭にある場合はテーブル参照1回だけでシンボルを求めることができます（インデックスビット数より長い場合はまた別の方法になるがここでは割愛）。Ut Video Codec Suite で扱うような、8bitシンボルで出現確率が指数分布になっている（かつ圧縮比が最終的に2.5ぐらいになる）シンボル列の場合、テーブルインデックスを12bitにすればほとんど（99%以上）の場合はそれに収まります。

さて、99%以上は1つのシンボルに対応する符号語が12bitに収まるわけですが、もっと短い符号語を見てみると、半分以上は2bitに収まります。ということは、結構な確率で多くのシンボルに対応する符号語列が12bitに収まることになります。つまり、1回のテーブル参照で複数シンボルを同時に出力することができます。

ただし、このアルゴリズムにはCPUに対する前提条件がいくつかあります。複数シンボル同時出力だと「アライメントの合っていない」「範囲の重複する」ストアが頻発するため、「メモリアライメントの制約が緩いこと」「ストアバッファが十分に高性能であること」が必要になります。前者が満たされないとそもそもそのまま適用できませんし、後者が満たされないと適用できても性能が出ません。x86 は元々メモリアライメントの制約は緩く、最近の x86 （特に Core 以降）は強力なストアバッファ (Memory Ordering Buffer) を装備します。

というわけで実装します。いきなりアセンブラ版を実装して遅かったら悲しいので、ざっくりとしたものを C++ で書きます。比較対象は今現在 Ut Video Codec Suite に実装されている 8bit シンボル用ハフマンデコードルーチン。計測は手元の Core i7-2600K です。

圧倒的に速いです。さすがにここまで速いとは予想してませんでした。3倍以上とは…

さすがに3倍速いと「1シンボル同時出力の時にしか併用できない他の部分での高速化技法」を捨ててでも採用する意味があるかもしれません。