計測してから最適化する

この章でわかること:

• 計測の4つの道具の使い分け: ベンチマーク、プロファイラ、 ハードウェアカウンタ、アセンブリ
• criterionによるベンチマークの書き方と読み方
• 計測を無意味にする落とし穴(最適化による削除、遅延評価、debugビルド)
• 最適化に取り組む順番

なぜ「まず計測」なのか

ここまでの章で、直感が当てにならない例をいくつも見ました。 読み出し回数を1/8にしても速くならず(2章)、データの並び順で10倍変わり(3章)、 関数呼び出しが500万倍の差を生みました(6章)。 現代のCPUとコンパイラの振る舞いは複雑で、 どこが遅いかの推測は、経験者でも高い確率で外れます。

したがって手順は常にこうなります。

1. 計測して、遅い場所を特定する
2. 仮説を立てて、直す
3. もう一度計測して、効果を確認する(効かなければ戻す)

この章では、そのための道具を役割別に揃えます。 「どこが遅いか」を知るのがプロファイラ、 「どれだけ速くなったか」を知るのがベンチマーク、 「なぜ遅いか」を知るのがハードウェアカウンタ、 「何にコンパイルされたか」を知るのがアセンブリの確認です。

ベンチマーク — criterion

ベンチマーク(benchmark)、つまり処理単体の速度を統計的に測るには、 criterionクレートが定番です。 7章の「Vecを作る3つの方法」をベンチマークにするとこうなります。

Cargo.toml

[dev-dependencies]
criterion = "=0.8.2"

[[bench]]
name = "build_vec"
harness = false

harness = falseは「標準のテストランナーではなく、 criterion自身に実行を管理させる」ための指定です。

benches/build_vec.rs

use criterion::{Criterion, criterion_group, criterion_main};
use std::hint::black_box;

fn build_collect(src: &[u32]) -> Vec<u64> {
    src.iter().map(|&v| v as u64 * 2).collect()
}

fn bench_build(c: &mut Criterion) {
    let src: Vec<u32> = (0..1_000_000).collect();
    // iter_with_large_drop: 戻り値(Vec)の解放は計測に含めない
    c.bench_function("collect", |b| {
        b.iter_with_large_drop(|| build_collect(black_box(&src)))
    });
    // push版、with_capacity版も同様に登録する
}

criterion_group!(benches, bench_build);
criterion_main!(benches);

b.iter_with_large_drop(...)が計測の本体で、渡したクロージャを 何度も実行して統計を取ります(基本形はb.iterですが、ここでは 作ったVecの解放時間を計測から外すためこちらを使っています)。 最後のcriterion_group!とcriterion_main!は、ベンチ関数の登録と main関数の生成を行うマクロです。

cargo benchで実行します。筆者のMac(Apple M4)での結果です。

push                    time:   [975.69 µs 988.17 µs 1.0028 ms]
with_capacity           time:   [537.33 µs 541.88 µs 546.73 µs]
collect                 time:   [110.12 µs 110.56 µs 111.04 µs]

3つの数字は[下限 推定値 上限]で、推定のばらつき幅(95%信頼区間)を 示します。criterionは自動でウォームアップを行い、多数回の実行から 統計を取り、前回実行との差分(改善か悪化か)も報告してくれます。 1回きりのInstant計測と違い、ばらつきに騙されにくいのが利点です。

なお、同じ比較をPlayground(共有環境のx86-64)で行った7章の結果とは 倍率がかなり違います。性能の数字は環境に強く依存します。 本書が毎回「筆者の実測では」と断っているのはそのためで、 あなたの環境ではあなたの計測が正です。

落とし穴 — 計測したつもりが計測できていない

ベンチマークで最も怖いのは、間違った数字をもっともらしく 信じてしまうことです。代表的な落とし穴を3つ挙げます。

その1: コンパイラが計測対象を消す。 7章のcollect実験で見たとおり、結果が使われない計算は デッドコード除去(6章)で削除されます。対策がstd::hint::black_boxです。 値を渡すと「この値は何かに使われる」とコンパイラに仮定させ、 削除と定数畳み込みを防ぎます。criterionのb.iter(...)は 戻り値を自動でblack_boxに通しますが、入力側も black_box(&src)のように包んでおくと、「入力が定数だと見抜かれて コンパイル時に計算される」事故も防げます。

その2: 遅延評価。 Rustのイテレータは、最後に消費されるまで 何も実行しません。実際に確かめてみます。

重い処理をmapしたのに一瞬で終わる?

use std::time::Instant;

fn slow_square(x: u64) -> u64 {
    // 意図的に重くした計算
    let mut acc = x;
    for _ in 0..100 {
        acc = acc.wrapping_mul(acc) ^ x;
    }
    acc
}

fn main() {
    let v: Vec<u64> = (0..1_000_000).collect();

    // (1) map を作っただけ(どこにも使っていない)
    let start = Instant::now();
    let _it = v.iter().map(|&x| slow_square(x));
    println!("mapを作っただけ: {:>12.3?}", start.elapsed());

    // (2) sum で最後まで実行する
    let start = Instant::now();
    let total: u64 = v.iter().map(|&x| slow_square(x)).sum();
    println!("sumまで実行    : {:>12.3?} (total={total})", start.elapsed());
}

use std::time::Instant; fn slow_square(x: u64) -> u64 { // 意図的に重くした計算 let mut acc = x; for _ in 0..100 { acc = acc.wrapping_mul(acc) ^ x; } acc } fn main() { let v: Vec<u64> = (0..1_000_000).collect(); // (1) map を作っただけ(どこにも使っていない) let start = Instant::now(); let _it = v.iter().map(|&x| slow_square(x)); println!("mapを作っただけ: {:>12.3?}", start.elapsed()); // (2) sum で最後まで実行する let start = Instant::now(); let total: u64 = v.iter().map(|&x| slow_square(x)).sum(); println!("sumまで実行 : {:>12.3?} (total={total})", start.elapsed()); }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground)では、mapを作っただけの行は約110ナノ秒、 sumまで実行すると約116ミリ秒。100万倍違います。 (1)ではslow_squareは一度も呼ばれていません。それどころか、 使われないイテレータは構築自体が最適化で消えている可能性が高く、 測れているのは時刻取得などのオーバーヘッド程度です。「この処理をここまでで 打ち切って測る」つもりが何も測っていなかった、という事故は、 非同期のFuture(こちらも.awaitまで実行されません)でも起きます。

その3: debugビルドで測る。 1章で見たとおり、debugビルドの 速度に意味はありません。cargo benchとcargo run --releaseは 最適化が有効ですが、cargo runやcargo testは既定でdebugです。

このほか、ノートPCの電源設定や発熱によるクロック変動、 他のプロセスの負荷も数字を揺らします。「数回実行して傾向が 安定しているか見る」だけでも、事故はかなり減ります。

プロファイラ — どこが遅いかを知る

ベンチマークは「この関数を測る」道具でした。 「プログラム全体のどこで時間が使われているか」を知るには プロファイラ(profiler)を使います。実行中のプログラムを 高頻度で標本化(サンプリング)し、「どの関数の中にいたか」を 集計する仕組みです。

• samply — cargo install samplyしてsamply record ./target/release/myappを 実行するだけで、ブラウザに結果が開きます。macOS/Linux/Windows対応で、 最初の1本としておすすめです
• perf — Linux標準の定番。samplyやflamegraphの土台でもあります
• Instruments — macOS標準(Xcode付属)のGUIプロファイラです

結果の可視化でよく使われるのがフレームグラフ(flame graph)です。 横幅が消費時間の割合、縦の積み重ねが関数の呼び出し関係を表します。 「幅の広い箱」を上へたどれば、時間を食っている呼び出し経路が 一目でわかります。

プロファイルを取るときは、releaseビルドのままデバッグ情報だけ 有効にしておくと、関数名が正しく表示されます。

[profile.release]
debug = true  # 最適化はそのまま、シンボル情報だけ付ける

ハードウェアカウンタ — なぜ遅いかを知る

プロファイラで「この関数が遅い」とわかっても、 なぜ遅いのか(キャッシュミスなのか、分岐予測ミスなのか、 純粋に計算量なのか)はまだわかりません。 そこで使うのがCPU内蔵のハードウェアパフォーマンスカウンタ (hardware performance counter)です。CPUは実行した命令数、 キャッシュミス回数、分岐予測ミス回数などを数える専用レジスタを 持っています。

Linuxではperf statで読めます(出力例)。

$ perf stat ./target/release/myapp

     4,381,297,063      instructions   #  1.02  insn per cycle
       912,438,571      branches
        41,282,946      branch-misses  #  4.52% of all branches
       102,381,842      cache-references
        38,472,013      cache-misses   # 37.6 % of all cache refs

読み方はPart Iの知識がそのまま使えます。おおよその目安として——

• insn per cycle(IPC)が低い — 何かを待っています。 cache-missesが多ければメモリ待ち(2章)、 branch-missesが多ければ分岐予測ミス(3章)が疑われます
• IPCがそのCPUの上限(1サイクルに実行できる命令数、3章)に近い — 実行ユニットはよく埋まっています。これ以上は 命令数そのものを減らす(アルゴリズム、SIMD)方向です

ただし「いくつなら低いか」はCPUと命令構成に依存します。また、 cache-missesのようなイベント名が正確に何を数えるかもCPUごとに 異なります(多くの場合は最終レベルキャッシュのミスです)。 実際に使うときはperf listで対象CPUのイベントを確認してください。

macOSではperfは使えず、Instrumentsの「CPU Counters」が対応します。

アセンブリ — 何になったかを知る

最後の道具は、コンパイル結果を直接見ることです。 「ベクトル化されているはず」「境界チェックは消えるはず」の 確認は、アセンブリを見れば議論の余地がありません。

• Compiler Explorer(1章) — 小さな関数の 確認に最適です。Rustを選び-Oを付けます
• cargo-show-asm — 手元のクレートの関数をcargo asm my_crate::my_fnで表示します

全部を読む必要はありません。4章で見たように、 ループ本体にpadddやvpadddのようなSIMD命令が並んでいるか、 callが残っていないか、といった「形」を見るだけでも 多くのことがわかります。

最適化の優先順位

道具が揃ったところで、取り組む順番を整理します。 上にあるものほど効果が大きく、下にあるものほど労力対効果が 悪くなりがちです。

1. 計測して場所を特定する — すべての前提です
2. アルゴリズムとデータ構造 — O(n²)をO(n log n)にする改善に 勝てる小手先の最適化はありません
3. アロケーションを減らす — with_capacity、collect、 バッファ再利用(7章)。Webアプリケーション系のコードでは 最初に効くことが多い項目です
4. メモリアクセスの形を整える — 連続アクセス、AoS→SoA、 サイズ削減(2章)
5. 並列化 — rayonで割れる形なら(5章)
6. SIMDと低水準の調整 — 自動ベクトル化が効く形へ(4章)、 target-cpu、プロファイル設定(6章)
7. unsafeによる最終手段 — 境界チェック除去など。 計測で確定した場合のみ

まとめ

• 推測は外れます。計測→変更→再計測のループだけが信頼できます
• ベンチマークはcriterion。black_boxで計測対象の削除を抑え、 遅延評価とdebugビルドに注意します
• どこが遅いかはプロファイラ(samply)、なぜ遅いかは ハードウェアカウンタ(perf stat)、何になったかはアセンブリ (Compiler Explorer / cargo-show-asm)で確認します
• 優先順位は、アルゴリズム → アロケーション → メモリ → 並列 → SIMD

これでPart IIは終わりです。CPUの仕組み(Part I)と、 それをRustコンパイラがどう活かすか(Part II)が揃いました。 Part IIIでは、まったく設計思想の異なるもう1つの計算機——GPU——に 進みます。CPUの知識は、対比としてすべて活きてきます。