アロケータ

この章でわかること:

Box::newやVecの確保の内部で動くアロケータの構造 (サイズクラス、フリーリスト、スレッドキャッシュ)
アロケーションが「普段は数ナノ秒、ときどき急に遅い」理由
グローバルアロケータの差し替え方法と、その効果の実測(と限界)
アリーナ確保: まとめて確保し、まとめて解放する(実測: 解放が6000倍速い)
なぜ体系に必須か: 7章は「実務のコストはヒープにある」と結論しました。その内部機構と制御手段を知らなければ、対策がwith_capacityに限られます

アロケータは何をしているか

Box::new(x)と書いたとき、メモリはどこから来るのでしょうか。

メモリはアロケータ(allocator)から来ます。アロケータは、プログラムに組み込まれたヒープの管理機構です。例えば、卸からまとめて仕入れて小口で売る問屋のようなものです。アロケータはOSから大きな領域 (14章のmmap等でページ単位)を確保し、それを小さな単位に分割してBoxやVecに渡します。 OSへのシステムコール(27章)はコストが大きいので、大きな単位でまとめて確保し、小さな単位で配分することが存在理由です。

現代のアロケータ(glibc malloc、macOSのlibmalloc、jemalloc、 mimallocなど)は、おおよそ共通の構造を持ちます。

サイズクラス(size class): 要求サイズを「16B、32B、48B…」の規格サイズに切り上げ、クラスごとに専用の未使用リストを持ちます。検索が不要になり、同じクラスの解放済み領域をそのまま再利用できます (切り上げによる無駄は内部断片化と呼びます)
フリーリスト(free list): 解放された領域を、サイズクラスごとに連結リストで管理します
スレッドローカルキャッシュ: 未使用の領域をスレッドごとに分けて持ち、確保・解放の大半をロックなしで済ませます (5章で述べた、共有を避ける方針の適用です)
大きな確保の別扱い: 一定サイズを超える要求はOSから直接確保して直接返します(境界はアロケータと履歴に依存し、 glibcでは既定128KiBを起点に変動します)

この構造から、確保のコストが決まります。 速い経路(スレッドキャッシュに空きがある場合)は数ナノ秒で、ポインタをリストから外すだけです。遅い経路(キャッシュが空になった場合、 OSからの追加確保、他スレッドとの領域の受け渡し)は数百ナノ秒からマイクロ秒単位に増えます。さらにOSから確保した直後の領域には、初回アクセスのページフォールト(14章)が続きます。アロケーションが「ときどき急に遅い」のは、この経路の分岐が原因です。長時間動くプロセスでは、使用中の領域が不連続に残って大きな連続領域が作れなくなる外部断片化も問題になります。

アロケータを差し替える

Rustはアロケータを1行で差し替えられます。

use mimalloc::MiMalloc;

#[global_allocator]
static GLOBAL: MiMalloc = MiMalloc;

これだけで、プログラム中のすべてのBox/Vec/Stringが mimalloc(Microsoft製の高速アロケータ)を使うようになります。jemallocなども同様です。

効果を実測します。筆者のMac(Apple M4)で、8スレッドが小さなVecの確保と解放を繰り返すワークロード(合計1600万回)を計測しました。

システム標準 : 61.8ms
mimalloc     : 54.9ms   (約1.1倍)

約1.1倍で、この環境では大きな差ではありません。さらに「確保したスレッドと別のスレッドで解放する」パターンでも試しましたが、チャネル通信のコストが支配的で差は出ませんでした。 macOSの標準アロケータの性能が高いこと、そしてこの規模では速い経路がほとんどであることが理由です。

それでも差し替えが定番の選択肢である理由は、 環境によっては大きな効果があるためです。Linuxのglibc mallocはスレッド数が多い確保集約型の負荷で性能が低下しやすく、 jemalloc/mimallocへの変更で数十%以上の改善が出る事例が知られています。変更も取り消しも1行で済むので、計測(8章)して判断してください。

アリーナ: まとめて確保し、まとめて解放する

差し替えよりも根本的な手段が、アリーナ確保(arena allocation)です。領域を1個ずつ確保して1個ずつ解放するからコストが高いのであれば、 同じ寿命のものは1つの大きな領域にまとめて置き、最後に領域ごと解放すればよい、という考え方です。

領域の中での確保は、ポインタ(または添字)を進めるだけです (バンプアロケーション、bump allocation)。フリーリストもサイズクラスも要りません。実験で確かめます。100万ノードの連結リストを、(1)ノードごとにBoxで確保する方法と、 (2)1本のVecをアリーナにして添字でつなぐ方法で作り、構築・走査・解放の3つを別々に測ります。

Boxの連結リスト vs アリーナの連結リスト

use std::hint::black_box;
use std::time::Instant;

struct BoxNode {
    value: u64,
    next: Option<Box<BoxNode>>,
}

struct ArenaNode {
    value: u64,
    next: u32, // アリーナ内の添字。u32::MAXを終端とする
}

fn main() {
    let n = 1_000_000u32;

    // (1) ノードごとにヒープ確保する連結リスト
    let start = Instant::now();
    let mut head: Option<Box<BoxNode>> = None;
    for i in 0..n {
        head = Some(Box::new(BoxNode { value: i as u64, next: head.take() }));
    }
    println!("Box   構築: {:>9.3?}", start.elapsed());

    let start = Instant::now();
    let mut sum = 0u64;
    let mut cur = head.as_deref();
    while let Some(node) = cur {
        sum = sum.wrapping_add(node.value);
        cur = node.next.as_deref();
    }
    println!("Box   走査: {:>9.3?} (sum={sum})", start.elapsed());

    // 再帰dropのスタックオーバーフローを避けるため手動で解体しつつ計測
    let start = Instant::now();
    let mut cur = head;
    while let Some(mut node) = cur {
        cur = node.next.take();
    }
    println!("Box   解放: {:>9.3?}", start.elapsed());

    // (2) アリーナ(1本のVec)にまとめて置く連結リスト
    let start = Instant::now();
    let mut arena: Vec<ArenaNode> = Vec::with_capacity(n as usize);
    let mut head = u32::MAX;
    for i in 0..n {
        arena.push(ArenaNode { value: i as u64, next: head });
        head = i;
    }
    println!("アリーナ構築: {:>9.3?}", start.elapsed());

    let start = Instant::now();
    let mut sum = 0u64;
    let mut cur = head;
    while cur != u32::MAX {
        let node = &arena[cur as usize];
        sum = sum.wrapping_add(node.value);
        cur = node.next;
    }
    println!("アリーナ走査: {:>9.3?} (sum={sum})", start.elapsed());

    let start = Instant::now();
    drop(arena);
    black_box(());
    println!("アリーナ解放: {:>9.3?}", start.elapsed());
}

筆者の実測(Playground)です。

	Box(個別確保)	アリーナ(Vec)	差
構築	34.5ms	9.8ms	3.5倍
走査	3.0ms	2.1ms	1.4倍
解放	9.5ms	1.5µs	約6000倍

構築の差(アロケータ呼び出し100万回のコスト)も大きいですが、注目は解放です。Box版は100万個を1個ずつフリーリストへ返す作業に9.5ミリ秒かかるのに対し、アリーナ版はVecを1回解放するだけなので、ほぼゼロです(この差は要素がデストラクタを持たない場合の話です。Drop実装を持つ要素なら、アリーナでも全要素分のデストラクタ実行は残ります)。dropにもコストがあることは、プロファイルで頻繁に確認されます (巨大な構造を関数の最後でdropしてレイテンシが増える、という形で現れます)。

実務でこのパターンが合うのは、寿命が揃った大量の小さな確保です。

Webサーバの1リクエスト中に作る一時オブジェクト群が該当します (リクエスト終了で全部解放します)
コンパイラやパーサの構文木も該当します(ASTのノード群を解析終了で全部解放します)
ゲームの1フレーム中の一時データも同様です

既製の実装としてはbumpalo (バンプアロケータ)やtyped-arenaがあります。bumpaloの Bump::allocは参照&'bump Tを返し、アリーナより長い寿命の参照をコンパイル時に禁止します。寿命をまとめて管理する設計は、 Rustのライフタイムと整合します。

なお、実験(2)のように「アリーナ=Vec+添字」で済ませる設計は、 Rustでは広く使われます。参照の代わりにu32の添字を使うことで借用検査との衝突がなくなり、ポインタより小さく(2章のキャッシュ効率)、シリアライズも容易になるためです。グラフ構造や、ゲームのECS(entity component system、エンティティを添字で管理する設計)の定石です。

まとめ

アロケータはOSからまとめて確保し小さな単位で配分する管理機構です。サイズクラス+ スレッドキャッシュで普段は数ナノ秒、補充が必要な瞬間に急に遅くなります
#[global_allocator]で1行差し替えできます。効果は環境依存で、筆者のmacOSでは1.1倍でした。効果が大きい環境(Linux多スレッド等)もあるので計測で判断します
寿命の揃った確保はアリーナにまとめます。構築3.5倍、解放6000倍の実測差です。 Vec+添字のアリーナはRustの定石でもあります
dropにもコストがあります。100万個の個別解放は9.5ミリ秒でした

次章では、async/awaitが実行時に何になっているかを扱います。 Webアプリケーション開発者にとって最も重要なRustの深層です。