HN 日本語サマリー

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

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

Quadrupling code performance with a "useless" if (purplesyringa.moe)

59 pointsby birdculture8 コメント

要約

この記事では、コードの最適化中に発見された、一見無意味に見えるif文がパフォーマンスを劇的に向上させるケースについて解説しています。依存関係のあるループ処理において、CPUの分岐予測を利用することで、データ依存による遅延を回避し、スループットを向上させるテクニックが紹介されています。この手法は、コンパイラが最適化で削除してしまうような「無駄な」条件分岐を意図的に挿入することで実現されます。

全文翻訳

「無駄な」if文でコードパフォーマンスを4倍にする

2026年7月12日 Lobsters Hacker News

先日、ドメイン固有のコンプレッサーを最適化していました。

重要な問題の一つは、入力文字列をチャンクに分割し、各チャンクに最もコンパクトなエンコーディングを最適に選択することでした(異なるエンコーディングは異なる文字をより良く圧縮するため、どこで分割するかはすぐには明らかではありません)。興味があれば前回の投稿でアルゴリズムを説明していますが、要するにグリッド上の最短経路を見つけるということです。各セルについて、アルゴリズムはそれに続く最適なセルを計算します。最初のセルから最後のセルへの参照をたどることで、最適なコーディング順序が得られます。

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++ の命令に注意を払わない理由の一つです。それらは通常、CPUがより多くの作業を行うのを妨げません。

しかし、決定的に重要なのは、2つの依存関係のある命令を同時に実行できないことです。この場合、ループの各反復は前の反復が終わる前に開始できません。なぜなら、j がループを介してスレッド化されているため、キャッシュがあってもかなり顕著なメモリアクセスのレイテンシによって制限されるからです。

これを修正できるでしょうか?この特定のケースでは、はい!チャンクが多くなるとは予想していません。そのため、next_j[i][j] は j と等しい可能性が非常に高いです。CPUに j がそのまま維持されると予測させるように指示できれば、ループはレイテンシバウンドではなくスループットバウンドになります。

アドレス予測を直接制御することはできませんが、分岐予測でこれをシミュレートできます。

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}

CPUが if の本体を可能性が低いと予測した場合、それを無視するため、異なる反復間の依存関係を認識しません。条件が最終的に true に評価された場合、分岐ミス予測の解決が介入し、間違った投機的書き込みを元に戻し、正しい j で再開します。まさに私たちが望むことです!

コンパイラへの嘘

唯一の問題は、コンパイラの視点から見ると、この if は完全に無駄であるということです。もし j がメモリにあったなら、読み取り専用メモリへの書き込みを回避できたかもしれませんが、それはレジスタにあります。コンパイラヒントに手を伸ばす他のほとんどのケースとは異なり、分岐なしのコードを分岐ありに変換したいのです。そして、CSEパスが一顧だにせず削除してしまうようなコードに対しては、どのコンパイラもそれをサポートしていません!愚かなコンパイラは、整数にはハードウェアの出所があることを理解していません。

私が知る限り、これを実装する唯一の方法は、volatile へのキャストを使用して、条件と代入が独立しているかのように見せかけることです。

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;
}

7月13日編集: そう思っていました。しかし、ibookstein が発見したように、[[unlikely]] アノテーション(または __builtin_expect(..., 0))もLLVMでは同様の効果があります。ただし、volatile はより良いコードを生成し、GCCでも動作するため、依然として有用です。

合成ベンチマークでは、この変更により私のデータでループが 320 us から 80 us に高速化されました。(これは大したことないように見えますが、圧縮中にループは何度も実行されるため、積み重なります。)

より現実的な実験では、LLVMによる最適化不足のコード生成の可能性が高いため、2倍の増加しか確認できませんでした。それでも価値はありました!

余談

興味深いことに、このアルゴリズムでは具体的に、各 next_j[i][j] は2つの値のいずれかしか取り得ません。つまり、j(最も頻繁)、または* j には依存しないが i のみに依存する*ある値です。そのため、各8要素配列 next_j[i] を、その値とビットマスクのペアに置き換えることができ、これにより if が意味的に重要になり、volatile のようなトリックの必要性がなくなります。しかし、変数のビットをテストするのは(少なくともx86では)比較よりも遅いため、コードは遅くなる可能性があります。

余談 2

7月13日追加。

この方法で連結リストの走査を高速化できる別のクールな投稿を紹介します。

完全性のために、j が予測不可能である場合にこのループを最適化する方法を以下に示します。pshufb を使用してください。これはベクトル化されたインデックス操作であり、レイテンシが1サイクルなので、投機なしではそれ以上改善できません。さらに、「ベクトル化された」部分を使用して、各開始 j のパスを並列に計算することもできます。これにより、スレッド間で作業を分割し、結果をマージすることができます。