Branchless Rust: if文を削除してフィルタを4倍高速化する

Branchless Rust: if文を削除してフィルタを4倍高速化する Serhii Potapov 2026年8月02日 #rust #branchless #optimization 私のキャリアのほとんどは、パフォーマンスよりも正しさがはるかに重視されるドメインワールドプログラミングに費やされました。Rustを使えば、すでに十分な速度が得られます。N+1 SQLクエリ問題などを回避すれば、通常は問題ありません。しかし最近、実際にホットパスを最適化する必要がある状況に陥りました。そこで、ブランチレスプログラミングという手法を発見し、その結果に驚愕しました。小さな例で共有させてください。 問題 シンプルに保ちましょう。数値のスライスをフィルタリングし、指定された閾値よりも大きい要素を返す必要があります（データベースエンジンが一日中解決している典型的な問題です）。通常、私は次のようなコードを書きます。 pub fn filter_iter(input: &[f64], threshold: f64) -> Vec<f64> { input.iter().copied().filter(|&x| x > threshold).collect() } 読みやすく、慣用的で、正しいコードです。通常、私はこれに二度と触れることはありません。しかし、もしこの処理がホットパスにあったらどうでしょうか？ベンチマークしてみましょう！入力は、0.0から100.0の範囲に一様に分布した100万個のランダムなf64値です。1つの閾値の代わりに、フィルタが要素の1%、25%、50%、75%、または99%を保持するように選択された、いくつかの閾値を試します。例えば、閾値50.0は、約半分を保持します。ベンチマークはcriterionを使用して行われ、branchless-rust-benchmarksリポジトリにありますので、ご自身のマシンで全て再現できます。 不可解な結果 これは私のラップトップ（Intel i7-10875H）でのcriterionのレポートです。 kept output size time 1% ~10k 0.59 ms 25% ~250k 2.69 ms 50% ~500k 3.94 ms 75% ~750k 2.75 ms 99% ~990k 1.49 ms 50%の行を見てください。要素の半分しかコピーしていないのに、すべてのケースの中で最も遅いです。99%を保持する場合、ほぼ2倍のデータをコピーしますが、それでも2.6倍高速です。入力の量はどの行でも同じであり、出力の量がタイミングを明らかに説明しているわけではありません。何か別のことが起こっています。 最初の直感：事前割り当て まず、通常の容疑者を排除しましょう。collect()は出力サイズを事前に知らないため、Vecは途中で成長し、再割り当てを行います。Rust開発者なら誰でもこれを反射的に行います：事前割り当て！ pub fn filter_prealloc(input: &[f64], threshold: f64) -> Vec<f64> { let mut out = Vec::with_capacity(input.len()); for &x in input { if x > threshold { out.push(x); } } out } 50%を保持した場合の結果：3.87 ms。約2%高速です。再割り当ては実際に行われていましたが、それらがボトルネックになることはありませんでした。では、何が原因なのでしょうか？ CPUは裏で何をしているのか 少し立ち止まって、CPUが実際にどのように動作するかを復習しましょう。現代のCPUは一度に1つの命令を実行するわけではありません。深いパイプラインを実行します。1つの命令が実行されている間に、次の命令がすでにフェッチされ、デコードされています。これは、命令ストリームが分岐点に当たるまで見事に機能します。 if x > threshold { /* keep */ } else { /* skip */ } どちらの道を行くのでしょうか？比較が実際に完了するまで、CPUは知り得ません。そして、待つことを拒否します。代わりに、推測します（推測を担当するハードウェアは分岐予測器と呼ばれます）そして、推測されたパスに沿って投機的に実行を進めます。予測器は、あなたが店に入ってきた瞬間にいつもの注文を作り始めるバリスタのようなものです。あなたが常連であれば、これは素晴らしいことです。カウンターにたどり着く頃にはコーヒーができています。毎日ランダムなものを注文する場合、バリスタはシンクに飲み物を注ぎ続けます。間違った推測は高くつきます。CPUは、投機的に開始したすべてを破棄し、パイプラインをフラッシュし、分岐点から再開する必要があります。典型的な最新のx86コアでは、これは約15〜20サイクルかかります。比較自体は約1サイクルかかります。これで、私たちの表が理解できるようになります。 1%を保持：答えはほぼ常に「スキップ」です。予測器は「スキップ」を推測し、99%の時間正解します。ほぼ無料です。 99%を保持：逆方向でも同じ話です。 50%のランダムなデータを保持：学習するパターンはありません。予測器はコイン投げに還元され、2番目の要素ごとに間違えます。これは半百万回のパイプラインフラッシュです。15〜20サイクルそれぞれかかると、4 GHzコアでは約2 msの純粋なペナルティが加算され、これは50%と99%の行のギャップとほぼ同じです。悪役は分岐そのものではないことに注意してください。予測不可能なデータに依存する分岐です。これは楽しい実験を示唆しています。 決定的な証拠 もしミスプリディクションが問題なのであれば、同じデータ、同じ閾値、同じコードを維持し、要素の順序だけを変更できるはずです。入力をソートし（もちろん測定セクションの外で）、50%のケースを再度実行してみましょう。 input, 50% kept time shuffled 4.15 ms sorted 0.93 ms 同じ100万個の浮動小数点数。同じ閾値。同じ関数。4.5倍高速です。ソートされたデータでは、分岐は最初の半分全体で「スキップ」と言い、後半全体で「キープ」と言います。このようなパターンは、最も単純な予測器でさえ、1回のミスで学習します。Stack Overflowには27K票の質問があり、それはまさにこの効果についてです。「ソートされた配列の処理がソートされていない配列の処理よりも速いのはなぜですか？」もちろん、入力のソートは修正ではありません。ソートはフィルタリング自体よりもはるかにコストがかかり、通常は元の順序も必要です。しかし、今、私たちは正確に何を修正すべきかを知っています。データをシャッフルしたまま、コイン投げを避けることはできますか？ ブランチレスプログラミングへようこそ ブランチレスプログラミングのアイデアは、予測不可能な分岐を完全に削除することなので、推測するものがなくなります。要素を書き込むかどうかを決定する代わりに、常に書き込み、比較を使用して次の要素がどこに行くかを決定します。 pub fn filter_branchless(input: &[f64], threshold: f64) -> Vec<f64> { let mut out = vec![0.0; input.len()]; let mut n = 0; for &x in input { out[n] = x; n += (x > threshold) as usize; } out.truncate(n); out } このトリックを理解するために少し時間を取ってください。すべての要素は、out[n]に無条件に書き込まれます。(x > threshold) as usize は、要素を保持する場合は1、そうでない場合は0になります。要素が保持されると、カーソルnは前進します。そうでない場合、次のイテレーションは拒否された値を単純に上書きします。最後に、nは保持された要素の数を保持し、truncate(n)はガベージの末尾を切り取ります。比較はまだありますが、その結果はもはやプログラムが次にどこへ行くかの決定ではなく、数値として使用されます。コンパイラ用語では、制御依存性をデータ依存性に変えました。実際、生成されたアセンブリでは、比較は単に0または1を生成するseta命令になります。もう分岐点はないので、予測ミスするものはありません。（注意深い読者は、out[n] = xは境界チェックを実行し、ループ条件も分岐であると異議を唱えるかもしれません。本当です！しかし、それらの分岐は100万回連続して同じ方向に進むため、予測器はそれらを無料で処理します。予測不可能な分岐だけが実行される必要がありました。） 結果： kept iter branchless 1% 0.59 ms 1.09 ms 25% 2.69 ms 1.05 ms 50% 3.94 ms 1.03 ms 75% 2.75 ms 1.02 ms 99% 1.49 ms 1.11 ms 最悪ケースはほぼ4倍高速になりました。そして、ブランチレス列がいかに平坦であるかを見てください。実行時間は、データに依存しなくなりました。まさに私たちが望んでいたことです。しかし、支払った代償に注意してください。1%を保持する場合、慣用的なバージョンが勝ちます。なぜなら、ほぼ常に正しく予測される分岐はほぼ無料ですが、ブランチレスバージョンは常に100万回の書き込みのコストを支払うからです。ブランチレスコードは一般的に高速ではありません。最良ケースを最悪ケースと交換します。 ブランチレスにするべきか？ ほとんどの場合、いいえ。ブランチレスコードは読みにくく、間違いを犯しやすいです。さらに、コンパイラは多くのトリックを知っており、すでにこれらの作業の多くを私たちに代わって行ってくれます。プロファイラがホットループを指摘し、そのループが予測不可能なデータに対する分岐を含んでいる場合にのみ、この手法は大きな見返りをもたらす可能性があります。 結論 分岐は安価です。予測ミスした分岐はそうではありません。だからこそ、シャッフルされたデータでは、同じフィルタが選択率50%付近で最も遅くなるのです。分岐予測器はコイン投げに還元されます。ブランチレスプログラミングは、予測不可能な分岐をプレーンな算術演算に置き換えます。常に書き込み、条件付きで進みます。最悪ケースはほぼ4倍高速になり、データへの依存がなくなりました。