「役に立たない」if文でコードパフォーマンスを4倍にする

「役に立たない」if文でコードパフォーマンスを4倍にする2026年7月12日先日、ドメイン固有のコンプレッサーを最適化していました。重要な問題は、入力文字列をチャンクに分割し、各チャンクに最適なエンコーディングを選択することでした（異なるエンコーディングは異なる文字をより良く圧縮するため、どこで分割するかはすぐには明らかではありません）。興味があれば、前の投稿でアルゴリズムを説明していますが、要するにグリッド上の最短経路を見つけるということです。各セルについて、アルゴリズムは次に続く最適なセルを計算します。最初のセルから最後のセルへの参照をたどると、最適なコーディング順序が得られます。 ```c uint8_t next_j[n_symbols][8]; // 次のセルへの参照 // `next_j` を生成するアルゴリズムのコア。 // 理解に深入りする必要はありません。完全性のためにここにあります。 __m128i best_path_length = _mm_setzero_epi16(); for (int i = n_symbols - 1; i >= 0; i--) { __m128i tmp = _mm_add_epi16(cost[i], best_path_length); __m128i minpos = _mm_minpos_epu16(tmp); __m128i cost_without_switching = _mm_sub_epi16(tmp, _mm_broadcastw_epi16(minpos)); __m128i cost_with_switching = _mm_set1_epi16(switch_cost); best_path_length = _mm_min_epu16(cost_without_switching, cost_with_switching); __m128i choice = _mm_blendv_epi8( _mm_set1_epi16(_mm_extract_epi16(minpos, 1)), _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0), _mm_cmpeq_epi16(best_path_length, cost_without_switching) ); _mm_storeu_si64(&next_j[i], _mm_packs_epi16(choice, choice)); } // 各シンボルの最適なエンコーディングを見つけます。 // チャンクの境界はエンコーディングが変更される場所にあります。 uint8_t encoding[n_symbols]; uint8_t j = 0; // 簡単のために常にエンコーディング0から開始します for (int i = 0; i < n_symbols; i++) { j = next_j[i][j]; encoding[i] = j; } ``` この長いループは本稿のトピックではありません。よく最適化されています。私たちが話すのは、一見もっと単純に見える2番目のループです。 レイテンシ 書き込みを除くと、ループ本体は `j = next_j[i][j]` だけで、これは単一の `mov` 命令にコンパイルされます。どうしてこれが最適でない可能性があるのでしょうか？ もし私たちが1984年にプログラミングしていたなら、それはそうだったでしょう。しかし、現代のプロセッサは命令レベルの並列性を持っています。つまり、複数の命令を並列に実行できるということです。これはループの反復をまたいでさえ機能し、ループパフォーマンスを評価する際に `i < n_symbols` や `i++` の命令に通常注意を払わない理由の1つです。それらは通常、CPUがより多くの作業を行うのを妨げません。 しかし、決定的に重要なのは、依存関係のある2つの命令を同時に実行できないということです。この場合、ループの各反復は前の反復が終わる前に開始できないため、`j` がループをスレッド化しているため、キャッシュがあってもかなり目立つメモリアクセスのレイテンシによって制限されます。 これを修正することはできますか？この特定のケースでは、はい！多くのチャンクを期待しているわけではないので、`next_j[i][j]` は単に `j` と等しくなる可能性が非常に高いです。CPUに `j` がそのまま維持されると予測させることができれば、ループはレイテンシバウンドではなくスループットバウンドになります。 アドレス予測を直接制御することはできませんが、分岐予測でこれをシミュレートできます。 ```c for (int i = 0; i < n_symbols; i++) { if (j != next_j[i][j]) { j = next_j[i][j]; } encoding[i] = j; } ``` CPUがifブロックを予測不可能と判断した場合、それを無視するため、異なる反復間の依存関係は見えなくなります。条件が最終的に真と評価されると、分岐ミス予測の解決が機能し、間違った投機的書き込みを元に戻し、正しい `j` で再開します。まさに私たちが望むことです！ コンパイラへの嘘 唯一の問題は、コンパイラから見ると、このifは完全に無駄だということです。もし `j` がメモリにあれば、読み取り専用メモリへの書き込みを回避できたかもしれませんが、レジスタにあります。他のほとんどのケースでコンパイラヒントに頼る場合とは異なり、ブランチレスコードをブランチありに変換したいのであって、その逆ではありません。そして、CSEパスがすぐに削除してしまうようなコードに対しては、それをサポートするコンパイラは皆無です。愚かなコンパイラは、整数にハードウェアの出所があることを理解していません。 私が知る限り、これを実装する唯一の方法は、`volatile` へのキャストを使用して、条件と代入が独立しているように見せかけることです。 ```c for (int i = 0; i < n_symbols; i++) { if (j != next_j[i][j]) { j = *(uint8_t volatile *)&next_j[i][j]; } encoding[i] = j; } ``` 合成ベンチマークでは、この変更により、私のデータではループが320マイクロ秒から80マイクロ秒に高速化されました。（これは大したことではないように見えますが、ループは圧縮中に何度も実行されるため、積み重なります。） より現実的な実験では、LLVMによる最適化不足のコード生成のためか、2倍の増加しか確認できませんでした。それでも価値はありました！ サイドノート 興味深いことに、このアルゴリズムでは、各 `next_j[i][j]` は2つの値のいずれかしか取れません。つまり、`j`（最も頻繁）、または `j` に依存しない `i` のみに依存する値です。そのため、各8要素配列 `next_j[i]` を、ビットマスクとペアになったその値に置き換えることができ、これによりif文が意味的に重要になり、`volatile` のようなトリックの必要性がなくなります。しかし、変数のビットをテストすることは（少なくともx86では）比較よりも遅いため、コードが遅くなる可能性があります。