RustではじめるCPUとGPU
ゼロコスト抽象化の実際
この章でわかること:
- 「ゼロコスト抽象化」の正確な意味
- イテレータと添字ループ、境界チェックの実際のコスト
Optionが(多くの場合)追加のメモリを消費しない仕組み(niche最適化)- ジェネリクスと
dyn Traitのコストの違いと使い分け - 抽象化よりコストの大きいヒープ確保と、その対策
ゼロコスト抽象化とは
Rustはゼロコスト抽象化(zero-cost abstraction)を設計目標の1つとしています。 この言葉の出典はC++設計者ストラウストラップの原則で、意味は2つあります。
- 使わない機能のコストは発生しません
- 使う場合も、同じ処理を手書きしたコードより遅くなりません
この原則の主張は「手書きと同等」であり、 「抽象化を使うとプログラムが速くなる」ではありません。 この性質は、前章で見た最適化 (単相化、インライン化、それに続く最適化の連鎖)によって実現され、 アセンブリと実測で検証できます。この章では代表的な抽象化を1つずつ検証します。
イテレータと境界チェック
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());
}
筆者の実測(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最適化
次は型の抽象化です。Option<T>は「値があるか、ないか」を表す
enumで、どちらの状態かを記録するタグが必要に思えます。
実際のサイズを確認します。
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>>());
}
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
トレイトを使う抽象化には2つの方式があります。
- ジェネリクス(
fn run<S: Step>(s: &S))では、コンパイラは使われる型ごとに 専用の関数を複製します。これを単相化(monomorphization)と呼びます。 複製された関数の中で呼び出し先は確定しているので、 インライン化から始まる最適化の連鎖(6章)がすべて適用されます - トレイトオブジェクト(
&dyn Step、Box<dyn Step>)では、値と一緒に vtable(仮想関数表。メソッドの関数ポインタを並べた表)を保持し、 実行時に表を参照してメソッドを呼びます。 これを動的ディスパッチ(dynamic dispatch)と呼びます
動的ディスパッチのコストを測ります。「実行時にしか中身が決まらない」
状況を作るため、2種類の処理を交互に混ぜたリストを
Box<dyn Step>版とenum+match版で用意しました。
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));
}
筆者の実測(Playground)ではBox<dyn Step>が約21ミリ秒、enumが約9ミリ秒で、
2倍強の差があります。dyn側のコストの内訳は、vtableを参照する
間接呼び出しそのものに加え、呼び出し先が実行時まで不明なため
インライン化が適用されないこと、そして要素のサイズです。
トレイトオブジェクトは「データへのポインタ+vtableへのポインタ」の
16バイトを占めるのに対し、このenumは1バイトで済むため、
リストの走査で読み込むデータ量も異なります。
なお、この例のAddOneとXorMixはフィールドを持たない型
(サイズ0)なので、Box::newは実際にはヒープ確保をしません
(Rustはサイズ0の型の確保を省略します)。中身のある型を
Boxで持たせれば、要素がヒープ上の離れた位置に配置されるため、
2章のポインタチェイシングのコストがさらに加わります。
コンパイラが動的ディスパッチを除去する場合
この実験の前に、単一の具体型を&dyn Stepに渡すだけの
単純な版を測ったところ、ジェネリクス版と差が出ませんでした。
呼び出し先の型を追跡できる単純な場面では、コンパイラが
動的ディスパッチを静的呼び出しに置き換えます
(脱仮想化、devirtualization)。「dynと書けば必ず遅くなる」
わけではありません。
使い分けの指針は次のとおりです。
- 数百万回繰り返すホットループの内側では、ジェネリクスか
enum+
matchを選びます - 種類が動的に増える境界(プラグイン、ハンドラ登録など)や、
コンパイル時間・バイナリサイズを抑えたい場面では
dynが適切です。 単相化は型の数だけコードを複製するため、コンパイル時間と バイナリサイズの増大というコンパイル時のコストがあるためです。 1回の呼び出しあたりの差は数ナノ秒であり、 ループの外側の呼び出しでは無視できます
実務で最も大きいコスト: ヒープ確保
ここまで見た抽象化のコストは、消えるか、数ナノ秒程度でした。 Webアプリケーション開発者がRustで実際に遭遇しやすい大きなコストは、 ヒープ確保(heap allocation)です。
VecやStringは、要素の追加で容量が足りなくなると、
より大きな領域を確保し直します。現在の実装では容量はおおよそ
倍ずつ増え、多くの場合は新領域への要素のコピーを伴います
(言語として保証されているのは「追加1回あたりの平均コストが一定」
という点です)。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());
}
筆者の実測(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ナノ秒という
見かけ上の結果になりました。計測を誤らせる要因と計測の手段は、
次章で扱います。
まとめ
- ゼロコスト抽象化とは「手書きと同等」という意味です。 イテレータと境界チェックは、単純なループでは文字どおりコストが消えます
Option<&T>やOption<Box<T>>はniche最適化により中身と同サイズです- ジェネリクスは単相化により実行時コストがゼロになります
(代わりにコンパイル時間とバイナリサイズが増えます)。
dynは間接呼び出しとインライン化の阻害により、ホットループでは 2倍程度の差になりえます。境界の設計で使い分けます - 実務で効果が出やすいのはヒープ確保の削減です。
with_capacity、collect、バッファの再利用を習慣にします
ここまでの検証はすべて筆者の実測でした。読者のコードの ボトルネックは、読者の環境で測る必要があります。 次章では、そのための手段(ベンチマーク、プロファイラ、 アセンブリの確認方法)を説明します。