コンテンツにスキップ
RustではじめるCPUとGPU

ゼロコスト抽象化の実際

この章でわかること:

  • 「ゼロコスト抽象化」の正確な意味
  • イテレータと添字ループ、境界チェックの実際のコスト
  • Optionが(多くの場合)メモリを消費しない仕組み — niche最適化
  • ジェネリクスとdyn Traitのコストの違いと使い分け
  • 抽象化より高くつくもの — ヒープ確保のコストと対策

ゼロコスト抽象化とは

Section titled “ゼロコスト抽象化とは”

Rustはしばしばゼロコスト抽象化(zero-cost abstraction)を掲げます。 この言葉の出典はC++設計者ストラウストラップの原則で、意味は2つあります。

  1. 使わない機能のコストを払わされることはない
  2. 使う場合も、同じことを手書きしたコードより遅くならない

「抽象化を使ってもプログラムが速くなる」とは言っていない点に 注意してください。主張はあくまで「手書きと同等」です。 そしてこれは宣伝文句ではなく、前章で見た最適化 (単相化+インライン化+その先の連鎖)によって実現される、 検証可能な性質です。この章では代表的な抽象化を1つずつ検証します。

イテレータと境界チェック

Section titled “イテレータと境界チェック”

Rustで配列の合計を書く方法はいくつもあります。 添字でアクセスするv[i]は、範囲外ならpanicする仕様です。 つまり素朴に考えれば毎回「i < 長さ」の検査 (境界チェック、bounds check)が入るはずで、 「イテレータのほうが検査がなくて速い」という話をよく聞きます。 本当でしょうか。4つの書き方で測ります。

添字、イテレータ、スライス。境界チェックの差は出るか
use std::time::Instant;


fn main() {
    let n = 10_000_000;
    let v: Vec<i32> = (0..n as i32).collect();
    let passes = 20;


    // (1) 添字アクセス。v[i] は範囲外なら panic する
    let start = Instant::now();
    let mut total = 0i64;
    for _ in 0..passes {
        let mut s = 0i32;
        for i in 0..n {
            s = s.wrapping_add(v[i]);
        }
        total += s as i64;
    }
    println!("添字 v[i]       : {:>9.3?} (total={total})", start.elapsed());


    // (2) イテレータ
    let start = Instant::now();
    let mut total = 0i64;
    for _ in 0..passes {
        let mut s = 0i32;
        for &x in v.iter() {
            s = s.wrapping_add(x);
        }
        total += s as i64;
    }
    println!("イテレータ      : {:>9.3?} (total={total})", start.elapsed());


    // (3) 実行時に決まる長さ m までの添字アクセス
    // (black_box で「コンパイル時には値がわからない」状況を作る)
    let m = std::hint::black_box(n - 1);
    assert!(m <= v.len());
    let start = Instant::now();
    let mut total = 0i64;
    for _ in 0..passes {
        let mut s = 0i32;
        for i in 0..m {
            s = s.wrapping_add(v[i]);
        }
        total += s as i64;
    }
    println!("添字 0..m       : {:>9.3?} (total={total})", start.elapsed());


    // (4) 先にスライスを切ってからイテレータ
    let start = Instant::now();
    let mut total = 0i64;
    for _ in 0..passes {
        let mut s = 0i32;
        for &x in &v[..m] {
            s = s.wrapping_add(x);
        }
        total += s as i64;
    }
    println!("スライス &v[..m]: {:>9.3?} (total={total})", start.elapsed());
}
stable / releasePlaygroundで開く ↗


筆者の実測(Playground)では、4つとも約45ミリ秒で差がありません。


種明かしをすると、このような単純なループでは、LLVMが境界チェックを
すべて消すか、ループの外に追い出しています。
for i in 0..v.len()の形ならiが常に範囲内であることは証明できますし、
実行時にしか決まらない長さmの場合も、このループは途中結果を
外部から観測できないため、検査をループ本体から分離した形に
変形できます。残った本体は4章で見たSIMDループと同じ形になります。
なお、コードのblack_boxは「mの値はコンパイル時にわからない」
状況を作るための道具で、この章の最後で説明します。


イテレータについても同じことが言えます。v.iter().map(...).sum()の
チェーンは、単相化とインライン化によって展開され、
最終的なアセンブリは手書きループと同一になります。
「イテレータは遅そう」も「イテレータのほうが速い」も、
単純なケースではどちらも誤りで、同じ機械語になるが正解です。


そのうえで、2つの但し書きを添えます。


    

  • データに依存する添字(v[idx[i]]のような間接参照)の検査は
消せないため残ります。それでも1回の比較と予測されやすい分岐
(3章)なので、大きなコストになることはまれです
    • 

  • 3章で見たとおり、filterのような条件を含むチェーンでは、
イテレータの形のほうがコンパイラに構造が伝わりやすく、
手書きのifより速くなることがあります
    • 



結論: 迷ったら読みやすい書き方(多くの場合イテレータ)を選び、
疑わしければ計測します。unsafeのget_uncheckedで検査を
外すのは、計測で境界チェックがボトルネックと確定した後の最終手段です。
検査がない代わりに、範囲内であることを自分で保証できなければ
未定義動作になります。


Optionは何バイトか — niche最適化
Section titled “Optionは何バイトか — niche最適化”


次は型の抽象化です。Option<T>は「値があるか、ないか」を表す
enumで、どちらの状態かを覚えておくタグが必要に思えます。
実際のサイズを見てみます。


Optionで包むとサイズはどう変わるか
use std::mem::size_of;


fn main() {
    println!("u64            : {:2} bytes", size_of::<u64>());
    println!("Option<u64>    : {:2} bytes", size_of::<Option<u64>>());
    println!();
    println!("&u64           : {:2} bytes", size_of::<&u64>());
    println!("Option<&u64>   : {:2} bytes", size_of::<Option<&u64>>());
    println!();
    println!("Box<u8>        : {:2} bytes", size_of::<Box<u8>>());
    println!("Option<Box<u8>>: {:2} bytes", size_of::<Option<Box<u8>>>());
    println!();
    println!("bool           : {:2} bytes", size_of::<bool>());
    println!("Option<bool>   : {:2} bytes", size_of::<Option<bool>>());
    println!();
    println!("String         : {:2} bytes", size_of::<String>());
    println!("Option<String> : {:2} bytes", size_of::<Option<String>>());
}
stable / releasePlaygroundで開く ↗


Option<u64>は16バイトです(タグ1バイト+アラインメント7バイト+値8バイト)。
ところがOption<&u64>、Option<Box<u8>>、Option<bool>、
Option<String>は、中身と同じサイズです。


これはniche最適化(niche optimization)と呼ばれます。
nicheとは型の表現に存在する「使われないビットパターン」のことです。
参照やBoxはnullにならないので、コンパイラは
「全ビット0」をNoneの表現に流用できます。boolは0と1しか
使わないので、2をNoneにできます。Stringも内部にnull不可の
ポインタを持つため同様です。


つまりOption<&T>は、C言語の「nullかもしれないポインタ」と
まったく同じメモリ表現で、「nullチェック忘れがコンパイルエラーになる」
安全性だけが上乗せされています。2章で見たとおりサイズは
キャッシュ効率に直結するので、これは実行時性能の話でもあります。


補足すると、実測値は64ビット環境での結果です。参照やBoxの
Optionが中身と同サイズになることは言語として保証されていますが、
boolやStringの例は現在のコンパイラの実装による結果です。


ジェネリクスとdyn Trait
Section titled “ジェネリクスとdyn Trait”


トレイトを使う抽象化には2つの方式があります。


    

  • ジェネリクス(fn run<S: Step>(s: &S)) — コンパイラは使われる型ごとに
専用の関数を複製します。これを単相化(monomorphization)と呼びます。
複製された関数の中で呼び出し先は確定しているので、
インライン化から始まる最適化の連鎖(6章)がフルに働きます
    • 

  • トレイトオブジェクト(&dyn Step、Box<dyn Step>) — 値と一緒に
vtable(仮想関数表。メソッドの関数ポインタを並べた表)を持ち歩き、
実行時に表を引いてメソッドを呼びます。
これを動的ディスパッチ(dynamic dispatch)と呼びます
    • 



動的ディスパッチのコストを測ります。「実行時にしか中身が決まらない」
状況を作るため、2種類の処理を交互に混ぜたリストを
Box<dyn Step>版とenum+match版で用意しました。


混在リストの処理: dyn Trait vs enum
use std::hint::black_box;
use std::time::Instant;


trait Step {
    fn apply(&self, x: u64) -> u64;
}


struct AddOne;
struct XorMix;
impl Step for AddOne {
    fn apply(&self, x: u64) -> u64 {
        x.wrapping_add(1)
    }
}
impl Step for XorMix {
    fn apply(&self, x: u64) -> u64 {
        x ^ (x >> 3)
    }
}


// 同じ2種類の処理を enum でも表現する
enum StepE {
    AddOne,
    XorMix,
}
impl StepE {
    fn apply(&self, x: u64) -> u64 {
        match self {
            StepE::AddOne => x.wrapping_add(1),
            StepE::XorMix => x ^ (x >> 3),
        }
    }
}


fn main() {
    let n = 10_000_000usize;


    // 中身の型が実行時にしか決まらない、種類の混ざったリスト
    let dyns: Vec<Box<dyn Step>> = (0..n)
        .map(|i| -> Box<dyn Step> {
            if i % 2 == 0 { Box::new(AddOne) } else { Box::new(XorMix) }
        })
        .collect();
    let enums: Vec<StepE> = (0..n)
        .map(|i| if i % 2 == 0 { StepE::AddOne } else { StepE::XorMix })
        .collect();


    let start = Instant::now();
    let mut x = 0u64;
    for s in dyns.iter() {
        x = s.apply(x);
    }
    println!("Box<dyn Step>: {:>9.3?} (x={})", start.elapsed(), black_box(x));


    let start = Instant::now();
    let mut x = 0u64;
    for s in enums.iter() {
        x = s.apply(x);
    }
    println!("enum + match : {:>9.3?} (x={})", start.elapsed(), black_box(x));
}
stable / releasePlaygroundで開く ↗


筆者の実測(Playground)ではBox<dyn Step>が約21ミリ秒、enumが約9ミリ秒。
2倍強の差です。dyn側のコストの内訳は、vtableを引く間接呼び出し
そのものに加え、呼び出し先が実行時まで不明なため
インライン化が効かないこと、そして要素のサイズです。
トレイトオブジェクトは「データへのポインタ+vtableへのポインタ」の
16バイトを持ち歩くのに対し、このenumは1バイトで済むため、
リストの走査で運ぶデータ量も違います。


ちなみに、この例のAddOneとXorMixはフィールドを持たない型
(サイズ0)なので、Box::newは実際にはヒープ確保をしません
(Rustはサイズ0の型の確保を省略します)。中身のある型を
Boxで持たせれば、要素がヒープに散らばるぶん、
2章のポインタチェイシングのコストがさらに上乗せされます。



使い分けの指針です。


    

  • 数百万回まわるホットループの内側では、ジェネリクスか
enum+matchを選びます
    • 

  • 種類が動的に増える境界(プラグイン、ハンドラ登録など)や、
コンパイル時間・バイナリサイズを抑えたい場面ではdynが適切です。
単相化は型の数だけコードを複製するため、コンパイル時間と
サイズの膨張という「コンパイル時のコスト」を持つからです。
1回の呼び出しあたりの差は数ナノ秒であり、
ループの外側の呼び出しなら気にする必要はありません
    • 



本当のコストはヒープ確保にある
Section titled “本当のコストはヒープ確保にある”


ここまで見た抽象化のコストは、消えるか、数ナノ秒の桁でした。
Webアプリケーション出身のRustプログラマが実際に踏みやすいのは、
もっと目立たない相手——ヒープ確保(heap allocation)です。


VecやStringは、要素の追加で容量が足りなくなると、
より大きな領域を確保し直します。現在の実装では容量はおおよそ
倍々で成長し、多くの場合は新領域への要素のコピーを伴います
(言語として保証されているのは「追加1回あたりの平均コストが一定」
という点です)。3つの書き方で比べます。


1000万要素のVecを作る3つの方法
use std::hint::black_box;
use std::time::Instant;


fn main() {
    let n = 10_000_000usize;
    let src: Vec<u32> = (0..n as u32).collect();


    // (1) 空の Vec に push: 容量が足りなくなるたびに再確保+コピー
    let start = Instant::now();
    let mut out = Vec::new();
    for &v in src.iter() {
        out.push(v as u64 * 2);
    }
    black_box(&out);
    println!("Vec::new + push     : {:>9.3?}", start.elapsed());
    drop(out);


    // (2) 容量を先に確保してから push
    let start = Instant::now();
    let mut out = Vec::with_capacity(n);
    for &v in src.iter() {
        out.push(v as u64 * 2);
    }
    black_box(&out);
    println!("with_capacity + push: {:>9.3?}", start.elapsed());
    drop(out);


    // (3) イテレータから collect
    let start = Instant::now();
    let out: Vec<u64> = src.iter().map(|&v| v as u64 * 2).collect();
    black_box(&out);
    println!("collect             : {:>9.3?}", start.elapsed());
}
stable / releasePlaygroundで開く ↗


筆者の実測(Playground)では、Vec::new+pushが約71ミリ秒、
with_capacity+pushが約65ミリ秒、collectが約44ミリ秒でした。


    

  • with_capacityは途中の再確保とコピーをなくします
    • 

  • collectはさらに速くなります。要素数がイテレータから
正確にわかる場合(この例では元のVecの長さ)、現在の標準ライブラリは
ちょうどの容量を1回で確保し、pushの容量検査すら省いた
書き込みループを使うためです
    • 



指針は単純です。最終的な大きさの見当がつくならwith_capacity、
変換の形にできるならcollect。さらに、ループの中で毎回
VecやStringを作っている場所は、外で1回作ってclear()で
使い回すだけで改善することがよくあります。


black_boxという見慣れない関数がコードに入っていることに
気づいたでしょうか。これは「この値は使われている」とコンパイラに
仮定させて、計測対象の削除(デッドコード除去)を抑える最適化ヒントです
(絶対の保証ではありませんが、実用上はこれで機能します)。
実はこの実験の最初の版では、collectの結果が使われていないことを
見抜いたLLVMが確保もコピーも丸ごと削除し、80ナノ秒という
見かけの結果を出しました。計測の落とし穴と道具は、次章のテーマです。


まとめ
Section titled “まとめ”


    

  • ゼロコスト抽象化とは「手書きと同等」という意味です。
イテレータと境界チェックは、単純なループでは文字どおりコストが消えます
    • 

  • Option<&T>やOption<Box<T>>はniche最適化により中身と同サイズです
    • 

  • ジェネリクスは単相化で実行時コストゼロ(その代わりコンパイル時に払う)。
dynは間接呼び出し+インライン化阻害で、ホットループでは
2倍程度の差になりえます。境界の設計で使い分けます
    • 

  • 実務で効きやすいのはヒープ確保の削減です。
with_capacity、collect、バッファの再利用を習慣にします
    • 



ここまでの検証はすべて「筆者の実測」でした。あなたのコードの
ボトルネックは、あなたの環境で測るしかありません。
次章では、その道具立て——ベンチマーク、プロファイラ、
アセンブリの確認方法——を揃えます。