或るプログラマの一生

以前、AVX2 による並列ハフマンデコードを試したことがあって、その時には利点が無いという結論になっていました。

AVX2 ではハフマン符号処理をベクトル化するにはいくつかのベクトル命令が足りないため、仕方なくスカラー処理していてそれが遅さの一因になっていたのですが、AVX512 （より厳密には Ice Lake でサポートされるレベルの AVX512）だと命令が追加されていて全部ベクトル化できるようになったので、AVX2 の時よりはだいぶマシになります。

で、実装してみたのですが、結果としてエンコードで 1.3～1.5 倍速、デコードで 2倍速強、という結果になりました。ただこれ注意が必要で、AVX512なので8並列（512/64=8）でしかも2つインターリーブして16並列、さらにHT環境で処理していて、元のデータを32分割して並列処理させています。当然単純にスカラー版を置き換えられるわけではなく、UtVideo などでは圧縮フォーマットの変更が必要になります。

32並列にしてもせいぜい倍速なのは、演算（レジスタ上での計算）は並列動作するが、メモリアクセスは命令としてはベクトル化されている（VGATHER/VSCATTER）ものの実際の動作は要素分の並列にはならないせいだと考えています。アムダールの法則的にはものすごく効率の悪いことをしていますが、メモリアクセスすること自体は必須なので回避のしようがありません。8倍の計算資源を投入しても倍速にしかならないのは寂しいことです。

これを UtVideo に適用するかというと、圧縮フォーマットを変更し、発熱もかなり増える（はず）ことを受け入れてせいぜい倍速にしかならないので、難しいところです。