計測してから最適化する

この章でわかること:

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

なぜ「まず計測」なのか

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

したがって、手順は常に次の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());
}

筆者の実測(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も、 Linuxでは同じカーネル機能(perf_event)を使います
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が残っていないか、といった構造を確認するだけでも多くのことがわかるため、全部を読む必要はありません。

最適化の優先順位

計測の手段を説明したので、取り組む順番を整理します。上にあるものほど効果が大きく、下にあるものほど労力対効果が悪くなりがちです。

計測して場所を特定する: すべての前提です
アルゴリズムとデータ構造: O(n²)をO(n log n)にする改善を上回る局所的な最適化はありません
アロケーションを減らす: with_capacity、collect、バッファ再利用(7章)です。Webアプリケーション系のコードでは最初に効果が出ることが多い項目です
メモリアクセスの形を整える: 連続アクセス、AoS→SoA、サイズ削減(2章)です
並列化: rayonで分割できる形なら適用します(5章)
SIMDと低水準の調整: 自動ベクトル化が適用される形への書き換え(4章)、 target-cpu、プロファイル設定(6章)です
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の知識は、対比の基準としてすべて使います。