ブランチレスプログラミングでフィルタ処理を最大4倍高速化する方法

概要

Rust で数値スライスを閾値でフィルタリングするコードは、直感的で高速ですが、特定のデータ分布では分岐予測の失敗が原因で性能が劣化します。本稿では、分岐予測ミスがボトルネックになるケースを検証し、ブランチレス（分岐なし）実装によって最大約4倍の速度向上を得る手法を紹介します。

問題設定

入力は 0.0〜100.0 の範囲に均等に分布した 100 万個の f64 値です。閾値を変えて、保持率が 1％、25％、50％、75％、99％ の5パターンでベンチマークを実施しました。

ベンチマーク結果

標準的な filter 実装では、保持率が 50％ のときが最も遅く、約 3.94 ms が記録されました。一方、保持率が 99％ の場合は約 1.49 ms と、データ量が増えても高速でした。

分岐予測の影響

CPU は分岐予測器で次に実行されるパスを推測しますが、ランダムなデータに対する 50％ の保持率は予測が困難となり、頻繁に予測ミスが発生します。予測ミスは 15〜20 サイクルのペナルティを伴い、合計で約 2 ms の遅延につながります。

データをソートすると、予測が容易になり、同じコードでも約 0.93 ms に短縮されました。ただし、ソート自体がコストになるため、実務上は解決策とはなりません。

ブランチレス実装

分岐を排除し、すべての要素を書き込んだ後に不要な部分を切り落とす方式です。

pub fn filter_branchless(input: &[f64], threshold: f64) -> Vec<f64> {
    let mut out = vec![0.0; input.len()];
    let mut n = 0usize;
    for &x in input {
        out[n] = x;
        n += (x > threshold) as usize;
    }
    out.truncate(n);
    out
}

この実装では比較結果は 0 または 1 の数値として利用され、制御フローの分岐は残りません。

結果と考察

ブランチレス版のベンチマークは、保持率 50％ で約 1.03 ms と、従来の実装の約 4 倍高速化を達成しました。保持率が極端に低い（1％）場合は、予測が正しく働くため従来の実装が若干有利です。

ブランチレスコードは書き込み回数が増えるため、ベストケースでは逆に遅くなることがあります。また、可読性が低下し、バグが入りやすくなる点にも留意が必要です。

結論

予測不能な分岐がホットループに存在する場合、ブランチレスプログラミングは大幅な性能改善をもたらします。ただし、一般的なコードではコンパイラが最適化を行うことが多く、必ずしも導入すべきではありません。測定対象のホットパスで分岐予測ミスが顕著なときだけ、ブランチレス手法を検討する価値があります。

元記事: https://www.greyblake.com/blog/branchless-rust/