CPUの分岐予測：コードに潜む見えないボトルネック
タイトなループの性能は分岐予測で大きく左右されます。CPUが分岐をどう予測するのか、予測ミスがなぜ痛いのか、コードを速くする書き方を解説します。
James Whitfield
3百万回以上閲覧されている有名なStack Overflowの回答があります。質問は「ソート済みの配列の方が、ソートされていない配列より処理が速いのはなぜか」というものです。コードは同一で、if文を含むループがあるだけです。違うのは入力配列がソート済みかどうかだけで、ソート済みの方は6倍速く動きます。その理由がCPUの分岐予測で、現代のコンピューティングにおいて最も影響の大きい性能要因の一つです。
if文、ループの条件式、switch文のcase。これらはすべてコード中の分岐です。CPUは毎秒何十億回もの分岐に遭遇し、実際の結果が分かる前にそれぞれの結果を予測しなければなりません。予測が当たれば全速力で実行が続きます。外れると、CPUは10〜20サイクル分の作業を捨てて最初からやり直します。この仕組みを理解すると、性能が重要なコードの見方が変わります。
なぜCPUは予測が必要なのか
現代のCPUはパイプライン化されていて、一つの命令が終わるのを待ってから次を始めるわけではありません。典型的なCPUのパイプラインは12〜20段あります。ある命令が実行されている間に、その後の15個ほどの命令がフェッチ、デコード、準備されています。このパイプライン化のおかげで、一つの命令が完了するまでに何サイクルもかかるのに、CPUはおおむね1クロックにつき1命令を実行できるのです。
しかし、CPUが分岐（if x > 0）に出会うと問題が生じます。次に実行すべき命令は、分岐が成立するかしないかに依存するからです。比較結果がパイプラインを流れてくるまでに数サイクルかかるため、CPUはそれまで答えを知りません。取れる選択肢は二つ。パイプラインを止めて待つ（15サイクル以上を何もせずに浪費する）か、分岐の向きを推測して作業を続けるかです。
CPUは必ず推測します。分岐予測器が予測を立て、CPUはその予測された経路に沿って命令をフェッチして実行します。予測が当たれば無駄はありません。外れた場合は、誤って実行された命令をフラッシュし、結果を破棄して正しい経路からやり直す必要があります。この「パイプラインフラッシュ」は最新のx86 CPUで約15〜20サイクルのコストがかかります。これは、15〜20命令分の作業が失われるのと同じことです。
分岐予測器の仕組み
現代の分岐予測器は驚くほど高度です。基本的には、各分岐命令の履歴から学習するパターンマッチング用のハードウェアだと考えてください。
単純なケース：偏りのある分岐
多くの分岐は強く偏っています。ほとんどの場合、同じ方向に進むのです。99.9%成功するエラーチェックや、999回は真で1回だけ偽になるループ条件などがそうです。分岐予測器はこうしたパターンをすぐに学習し、ほぼ完璧な精度を達成します。99%の確率で同じ方向に進む分岐の予測ミス率は、最大でも1%です。
パターン認識
現代の予測器は、単純な偏りの追跡を超えています。繰り返しパターンを認識するのです。分岐が「成立・成立・不成立・成立・成立・不成立…」（周期3）というパターンに従うなら、予測器はそれを学習して正しく予測します。現代のIntelやAMDのCPUで使われているTAGE（TAgged GEometric history length）予測器は、異なる履歴長の複数の履歴テーブルを持ち、周期2から数百までのパターンを捉えます。
相関のある分岐
最も高度な予測器は、分岐同士の相関も学習します。分岐Aが成立すれば、（コード上でその後にある）分岐Bは必ず不成立になる、という関係があれば、予測器はその関係を学べます。これは「2レベル適応型予測」と呼ばれ、次のようなコードパターンを扱えます：
// These branches are correlated
if (x > 0) { // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) { // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracyソート済み配列の謎を解く
有名なStack Overflowの質問に戻りましょう。問題のコードは次のようなものです：
int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128) // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cyclesソート済みデータでは、分岐は完全に予測可能です。配列の前半は不成立、後半は成立が続きます。予測器は各区間をすぐに学習し、予測がミスするのは切り替わりの一点だけです。一方、ランダムなデータでは、分岐はほぼコイン投げと同じです。予測器は約50%の精度を超えられず、半分の反復で15サイクルがパイプラインフラッシュに消えます。
10万回の反復で予測ミス率が約50%なら、5万回のミス × 15サイクル = 75万サイクルの無駄になります。3GHzのCPUでは約0.25ミリ秒です。この単純なループ全体の実行時間の中では、無視できない割合です。
CPUはいくつの分岐を扱えるのか
分岐予測器の記憶容量には限りがあります。分岐ターゲットバッファ（BTB）と関連する履歴テーブルを使い、有限の数の分岐箇所の履歴を追跡します。現代のCPUは数万もの分岐箇所を追跡できますが、大規模なコードベースではそれを超えることもあります。
異なる分岐命令が、BTBのインデックス（命令アドレスのハッシュ）によって同じ予測器エントリにエイリアスすると、互いの予測に干渉します。通常のコードではまれですが、非常に大きな関数や、分岐を含む小さな関数が大量にある場合に問題になります。
Daniel Lemireは、さまざまなCPUの分岐予測器の容量を測定する優れた研究を公開しています。その結果によると、現代のIntel CPU（Alder Lake以降）は、履歴が約200分岐分まで効果的に予測できます。つまり、現在の分岐を予測する際に直近約200分岐の結果を考慮しているということです。AMDのCPUも同程度の容量を持っています。ARMチップは幅があり、特にAppleのMシリーズは非常に強力な分岐予測器を持っています。
分岐予測に優しいコードの書き方
ほとんどのコードでは、分岐予測はあまり問題になりません。予測器で十分ですし、分岐がホットなループ内にないことがほとんどです。しかし、内側のループ、データ処理パイプライン、パーサー、コーデックなど、性能が重要な経路を最適化する場合、分岐の振る舞いが実行時間を支配することがあります。
分岐を算術演算に置き換える
最速の分岐は、存在しない分岐です。多くの条件パターンは、分岐を使わない算術演算で置き換えられます。
// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo; // CMOV
return t < hi ? t : hi; // CMOV
}現代のコンパイラは、単純な条件分岐をCMOV（条件付きムーブ）命令に変換するのが概ね得意で、これは分岐を完全に避けられます。ただし、分岐に副作用がある場合や「then」側の処理が重い場合など、常にできるわけではありません。コンパイラが最適なコードを生成していないホットループでは、明示的に分岐を使わない書き方が効果的です。
処理の前にソートする
分岐を使ってデータをフィルタリングするなら、先にソートすると分岐が完全に予測可能になります。ソートはO(n log n)のオーバーヘッドがかかるため直感に反するように聞こえますが、処理ループが何度も回る大規模データや、分岐ミスのコストが大きい場合には、ソートの元が取れることがよくあります。
ルックアップテーブルを使う
複雑な条件分岐（多くのcaseを持つswitch文など）は、テーブル検索で置き換えられることがあります。比較の連鎖の代わりに、配列をインデックス参照します。配列アクセスでキャッシュミスが起きることもありますが、それは通常、予測ミスした分岐の連鎖よりは安上がりです。
// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}コンパイラにヒントを与える
GCCとClangは、どちらの分岐方向が起こりやすいかをコンパイラに伝える__builtin_expectをサポートしています。これはCPUの分岐予測器（実行時に学習する）を直接制御するわけではありません。しかし、コンパイラがコードをどう配置するかに影響します。起こりやすい経路を、ジャンプなしで直線的に配置するのです。命令キャッシュの効果により、これは高速化につながります。
// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}分岐の振る舞いを計測する
ハードウェアのパフォーマンスカウンタを使えば、分岐予測の性能を直接計測できます。Linuxでは、perf statで任意のプログラムの予測ミス率を確認できます。
# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256 branches # 892.7M/sec
3,271,842 branch-misses # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.マイクロベンチマークでは、Google Benchmarkのようなツールで反復ごとのbranch-misses（分岐ミス数）を追跡できます。これにより、コードの変更が分岐の振る舞いを改善したかどうかを正確に確認できます。他のシステム活動によるノイズを含む実時間よりも、はるかに行動に移しやすい指標です。
いつ気にすべきか（そして気にしなくてよいとき）
分岐予測の最適化が意味を持つのは、大量のデータを処理する狭いが重要なカテゴリのコード、すなわちタイトな内側のループです。パーサー、圧縮処理、画像処理、数値計算、データベースのクエリ評価などで、分岐の振る舞いが支配的になります。
それ以外、たとえばビジネスロジック、APIハンドラ、CRUD操作では、分岐予測は関係ありません。Webサーバーのリクエストルーターにある分岐は、ボトルネックではありません。HTTPリクエストごとに一度だけ実行されるコードで、読みやすいif/elseの連鎖を読みにくい分岐なしの算術演算に書き換えるのはやめましょう。最適化は、理論上問題がありそうな場所ではなく、プロファイラが示す場所で行いましょう。
分岐予測を理解する本当の価値は、手作業での最適化にあるのではなく、コードがなぜそのように動くのかを理解することにあります。プロファイラが、if文を含む単純なループが想定より遅いと示したとき、分岐の予測ミスが説明になることがよくあります。入力データをソートするだけで処理が劇的に速くなるとき、その理由も分岐予測です。このメンタルモデルがあれば、そうでなければ謎に見える性能問題を診断できるようになります。
