50,000 ノードの AST を 16 回のアロケーションで: bumpalo 借用アリーナの実例

aozora の AST は bumpalo 単一アリーナの上に構築されている。Box<Node> を素直に並べた版に比べてパースが 6.4 倍速、ピーク RSS が 30% 減という結果が出ている。この記事は、その設計判断と Rust ライフタイムの取り回しを実装の視点から整理したもの。

handbook の対応章: Borrowed-arena AST。

問題設定

青空文庫の典型的な作品は約 500KiB のソースで、aozora がパースすると約 50,000 ノードの木に展開される。素直に Rust らしく書けば次のような形になる。

enum Node {
    Plain(String),
    Ruby { target: String, gloss: String },
    Container { kind: ContainerKind, children: Vec<Node> },
    // …
}

このまま 50,000 ノードを構築すると、

• 約 50,000 回の個別 heap allocation が走る
• ノードあたり 16 バイト前後のアロケータ管理メタデータが付く
• ノードがメモリ上にランダム配置される (prefetch が効かない)
• drop 時に 50,000 回の個別 free が必要になる

パース処理そのものより malloc / free の方が時間を食う、という素直な律速状態になる。

アリーナ版の設計

aozora は Document が bumpalo::Bump アリーナと Box<str> ソース文字列の 2 つを所有し、AozoraTree<'a> はその両方から借用する。

let source = std::fs::read_to_string("kokoro.txt")?;
let doc = aozora::Document::new(source);
let tree = doc.parse();   // tree は &doc の lifetime で生きる

// tree.to_html(), tree.serialize(), tree.diagnostics() が借用走査
let html = tree.to_html();

// doc が drop されたら tree は使えなくなる (コンパイル時にエラー)

ノード型は次のような形で、テキスト部は全てソース文字列のスライスへの参照、container は arena 内の box への参照になる。

pub enum AozoraNode<'src> {
    Plain(&'src str),
    Ruby(Ruby<'src>),
    Bouten(Bouten<'src>),
    Tcy(Tcy<'src>),
    Gaiji(Gaiji<'src>),
    Container(&'src Container<'src>),    // arena box
    BreakNode(BreakNode),
    // 30+ variants
}

AozoraNode 全体が Copy (参照と小さな primitive のタグ付き union)。木をたどるときに & を取らずにそのままコピーで済むので、ホットパスから参照解決の indirection が消える。

アロケーションの数

bumpalo は 4KiB 程度のページを単位に bump 確保する。50,000 ノードを置くのに必要なページは概ね 16 枚で、

• bump allocation 約 16 回 (4KiB ページごとにオーバーフロー時にだけ追加)
• drop 時の free は Bump::reset 1 回のみ (全ページを一括返却)
• ノードはレキサが流す順序通りに並ぶので、レンダラが走査する順序と一致する

Box<Node> 版との差は青空文庫全作品を回す corpus sweep ベンチで:

• パース時間: 約 6.4 倍速
• ピーク RSS: 約 30% 減

差は 累積する 性質のもので、CLI でも WASM でも C ABI でも Python バインディングでも同じだけ得られる。

bumpalo を選んだ理由

候補は他にもあった。aozora が選ばなかった理由を整理しておく。

bumpalo::collections::Vec<'bump, T> も提供されていて、container の子ノード列もアリーナ内に置ける (子も親と同じ lifetime になる)。

drop と lifetime

Document を drop すると、

1. Box<str> ソースが drop される (1 free)
2. Bump アリーナのバッキングバッファが drop される (16 ページ分まとめて 1 free)

合計 2 回の free でツリー全体が消える。ノードごとの destructor は無い。

トレードオフは ツリーが Document より長く生きられない こと。Vec<AozoraNode<'_>> を関数の戻り値にすることはできず、コンパイル時に弾かれる。

fn bad() -> AozoraTree<'static> {
    let doc = aozora::Document::new("…".into());
    doc.parse()        // ERROR: cannot return value referencing local
}

利用側の典型パターンは次の 3 つ。

• 即時レンダリングして捨てる: tree.to_html() は String を返すので lifetime が切れる
• 1 回走査して自前 IR に書き出す: 多くのエディタバックエンドはこの形
• Document 自体を関数境界より上で持ち、内側で parse() を呼び直す

「所有された木」が本当に必要な consumer 向けには aozora::owned が将来追加予定だが、変換は trivial なので 1.0 まではあえて出さない方針。

整理

50,000 ノード規模の AST に bumpalo 借用アリーナを選ぶと、

• アロケーションが 50,000 回から 16 回に
• drop が 50,000 回から 1 回に
• メモリレイアウトが走査順に並び、prefetch が効く
• パース時間 6.4 倍速、ピーク RSS 30% 減

代償として「木は Document より長生きできない」が乗るが、レンダリング後に捨てる消費パターンならコストにならない。aozora の AST 設計はこの利得とトレードオフのバランスの上に乗っている。

実装は aozora-syntax (型定義と arena ラッパ) と aozora-pipeline (実際のアロケーション) にある。handbook の arena.md には bumpalo の代替候補との比較表や、ライフタイム借用の安全性検証も書いてある。