フロントエンドとtop-down分析

この章でわかること:

CPUの前半分——命令を取ってきて実行可能な形に整える フロントエンドの構造(デコード、μop、命令キャッシュ)
「分岐先アドレスの予測」(BTB)と、間接呼び出しが刺さる条件(実測3.4倍)
コードサイズが性能資源であること — インライン化のもう1つの顔
top-down分析 — 「なぜ遅いか」を4分類で切り分ける体系的な診断法
なぜ体系に必須か — 3章で見たのは命令を「実行する」側だけでした。命令を「供給する」側の律速を知らないと、診断の地図が半分しかありません

パイプラインの前半分 — フロントエンド

3章のパイプライン図を、現代のCPUに合わせてもう一段解像度を上げます。パイプラインは大きく2つの部分に分かれます。

フロントエンド(front end) — 命令をフェッチし、デコードし、実行の材料を切らさず後ろへ送り込む部分
バックエンド(back end) — 送り込まれた命令を、アウトオブオーダー実行の仕組み(3章)で実際に計算する部分

どちらか遅いほうが全体を律速します。3章で見た依存チェーンはバックエンド側の話でした(分岐予測ミスは、後述のtop-down分類では「投機のやり直し」という独立のカテゴリに数えます)。フロントエンド側にも固有の構造があります。

デコード — 特にx86-64は命令長が1〜15バイトの可変長で、「どこからどこまでが1命令か」を切り出すだけでも重労働です。そのためCPUは命令をμop(micro-operation、マイクロオペレーション)という固定形式の内部命令に分解し、以降はμopの流れとして扱います
μopキャッシュ — 一度デコードした結果を取っておく専用キャッシュです。小さなホットループはデコードを完全にスキップして回れます
命令キャッシュ(L1i)とiTLB(命令用のTLB) — 命令もメモリ上のデータなので、データと同様にキャッシュ(2章)とアドレス変換(14章)を通ります。 L1iは32〜64KB程度です

分岐先の予測 — BTB

3章の分岐予測は「行くか、行かないか」の予測でした。フロントエンドにはもう1つの予測があります——「どこへ行くか」です。

分岐先のアドレスは、命令をデコードして初めてわかります。しかしフェッチはデコードより前段です。次にどこをフェッチするかを即断するため、CPUはBTB(branch target buffer)という「この分岐命令は前回ここへ飛んだ」を覚える表を持ち、さらに現代のCPUは、分岐履歴のパターンから飛び先を予測する間接分岐予測器を重ねています(3章の方向予測の「行き先」版です)。

これが特に効くのが間接分岐(indirect branch)——飛び先がレジスタの値で決まる分岐です。Rustコードでは、関数ポインタの呼び出し、 dyn Traitのvtable経由の呼び出し(7章)、大きなmatchが生成するジャンプテーブル、インタープリタの命令ディスパッチがこれに当たります。飛び先が毎回同じなら BTBが当て続けますが、毎回変わると予測ミス——3章と同じパイプライン破棄——が起きます。

実験します。中身のほぼ同じ関数16個を関数ポインタの配列に入れ、「順繰りに呼ぶ」場合と「ランダムな順で呼ぶ」場合を比べます。呼び出しの回数は同じです。

use std::time::Instant;

fn xorshift(state: &mut u64) -> u64 {
    *state ^= *state << 13;
    *state ^= *state >> 7;
    *state ^= *state << 17;
    *state
}

// 中身のほぼ同じ関数を16個用意する
macro_rules! ops {
    ($($name:ident, $k:expr;)*) => {
        $(#[inline(never)] fn $name(x: u64) -> u64 { x.wrapping_mul(2).wrapping_add($k) })*
        const OPS: [fn(u64) -> u64; 16] = [$($name),*];
    };
}
ops!(f0,0; f1,1; f2,2; f3,3; f4,4; f5,5; f6,6; f7,7; f8,8; f9,9; f10,10; f11,11; f12,12; f13,13; f14,14; f15,15;);

fn main() {
    let n = 20_000_000;
    let mut state = 0x2545_F491_4F6C_DD1D_u64;

    // 呼び出し先の並び: 規則的(順繰り) vs ランダム
    let regular: Vec<u8> = (0..n).map(|i| (i % 16) as u8).collect();
    let random: Vec<u8> = (0..n).map(|_| (xorshift(&mut state) % 16) as u8).collect();

    for (name, idx) in [("規則的 ", &regular), ("ランダム", &random)] {
        let start = Instant::now();
        let mut x = 0u64;
        for &i in idx.iter() {
            x = OPS[i as usize](x);
        }
        println!("{name}: {:>9.3?} (x={x})", start.elapsed());
    }
}

use std::time::Instant;

fn xorshift(state: &mut u64) -> u64 {
    *state ^= *state << 13;
    *state ^= *state >> 7;
    *state ^= *state << 17;
    *state
}

// 中身のほぼ同じ関数を16個用意する
macro_rules! ops {
    ($($name:ident, $k:expr;)*) => {
        $(#[inline(never)] fn $name(x: u64) -> u64 { x.wrapping_mul(2).wrapping_add($k) })*
        const OPS: [fn(u64) -> u64; 16] = [$($name),*];
    };
}
ops!(f0,0; f1,1; f2,2; f3,3; f4,4; f5,5; f6,6; f7,7; f8,8; f9,9; f10,10; f11,11; f12,12; f13,13; f14,14; f15,15;);

fn main() {
    let n = 20_000_000;
    let mut state = 0x2545_F491_4F6C_DD1D_u64;

// 呼び出し先の並び: 規則的(順繰り) vs ランダム
    let regular: Vec<u8> = (0..n).map(|i| (i % 16) as u8).collect();
    let random: Vec<u8> = (0..n).map(|_| (xorshift(&mut state) % 16) as u8).collect();

for (name, idx) in [("規則的 ", &regular), ("ランダム", &random)] {
        let start = Instant::now();
        let mut x = 0u64;
        for &i in idx.iter() {
            x = OPS[i as usize](x);
        }
        println!("{name}: {:>9.3?} (x={x})", start.elapsed());
    }
}

筆者の実測(Playground)では、規則的な順が約56ミリ秒、ランダムな順が約188ミリ秒。3.4倍の差です (2つの出力xが違うのは、適用順が違うためで正常です)。規則的な側が速いのは、履歴ベースの予測器が16個の周期を学習できるからです。ランダム側は学習のしようがなく、予測ミスのペナルティ(3章)を払い続けます。

7章でBox<dyn Step>の混在リストが2倍遅かった実験を思い出してください。あのコストの内訳として挙げた「間接呼び出し」の実体はこれです。間接分岐そのものは飛び先が安定していればほぼ無料で、不規則なときに高くつく—— dynのコストは、リストの中身の並びにも依存するのです。

コードサイズという資源

フロントエンドの視点に立つと、6章のインライン化の注意書き——「#[inline(always)]の乱用は逆効果になりえます」——の理由がはっきりします。

インライン化はコードを複製します。展開しすぎたホットパスは L1iとμopキャッシュから溢れ、フロントエンドの供給が追いつかず、バックエンドの実行ユニットに手待ちが生まれます。データのキャッシュミスとまったく同じ構造の問題が、命令側でも起きるのです。

コードサイズに効く道具を整理しておきます。

opt-level = "s" / "z"(6章) — サイズ優先の最適化
#[cold]属性と#[inline(never)] — エラー処理のような滅多に通らないコードを「冷たい」と宣言し、ホットパスから遠ざける配置のヒントを与えます(コンパイラはpanic経路などを自動で同様に扱います)
PGO(21章) — 実測に基づいてホット/コールドのコード配置を最適化します。PGOの効果のかなりの部分は、実はこのフロントエンド改善です

top-down分析 — 律速の4分類

ここまでで、性能を制限する場所の候補が出揃いました。これらを体系的に切り分ける方法論がtop-down分析 (top-down microarchitecture analysis)です。

考え方は単純です。パイプラインの発行スロット(1サイクルに何μop送れるか)を全数として、各スロットが毎サイクルどうなったかを4つに分類します。

分類	意味	主な対応章
Retiring	有効な仕事を完了した	それ自体は良い状態。さらに速くするなら命令数を減らす(4章)
Bad Speculation	投機が外れて捨てた	分岐予測ミス(3章)、この章の間接分岐
Frontend Bound	命令の供給が追いつかない	この章(L1i/μopキャッシュ/デコード)
Backend Bound	実行資源かデータ待ち	さらにMemory Bound(2章/14/15章)とCore Bound(3章の依存・実行ユニット)に分かれる

8章で「IPCが低ければ何かを待っている」と書きましたが、top-down分析はその「何か」を計器で特定する方法です。 Linuxのperfはこの分類を直接出せます(出力例)。

$ perf stat -M TopdownL1 ./target/release/myapp

    18.5 %  tma_frontend_bound
     4.2 %  tma_bad_speculation
    51.8 %  tma_backend_bound
    25.5 %  tma_retiring

この例ならBackend Boundが過半なので、次はMemory/Coreの内訳 (-M TopdownL2)へ降りる——というように、大分類から順に掘るのが「top-down」の名前の由来です。むやみに個別イベントを眺めるより、はるかに迷いません。macOSではInstrumentsの CPU Countersで同種のカウンタを読めます。

まとめ

CPUの前半分(フロントエンド)は命令の供給係です。x86-64は可変長命令をμopに分解し、μopキャッシュで再デコードを避けます
分岐には「行き先」の予測(BTB)もあります。間接呼び出しは飛び先が不規則だと刺さります(実測3.4倍)。dynやインタープリタのコストの一部はこれです
コードサイズは性能資源です。過剰なインライン化はL1i溢れという形で祟ります。#[cold]やPGOが対策です
top-down分析は律速をRetiring/Bad Speculation/Frontend/Backendの 4分類で切り分ける診断法です。本書の各章がそれぞれの分類の「治療法」に対応します

次章はPart IVの締めくくりとして、5章で入り口だけ見たメモリオーダリングの下部構造——ストアバッファ、ハードウェアのメモリモデル、そしてロックフリーデータ構造の基礎——に降ります。