フロントエンドと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バイトの可変長で、 命令の境界を切り出すだけでも多くの処理を要します。 そのため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());
    }
}

筆者の実測(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つに分類します。

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章で概要だけ説明した メモリオーダリングの下部構造(ストアバッファ、ハードウェアの メモリモデル、ロックフリーデータ構造の基礎)を扱います。