アロケータ

この章でわかること:

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行で試せてロールバックも1行—— 計測(8章)して判断する、が答えです。

アリーナ — まとめて確保、まとめて捨てる

差し替えよりも根本的な武器が、アリーナ確保(arena allocation)です。発想を変えます——「小口を1個ずつ借りて1個ずつ返すから高い。 同じ寿命のものは、1つの大きな塊にまとめて置いて、最後に塊ごと捨てればいい」。

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

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());
}

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());

// 再帰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();
    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ミリ秒でした

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