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::reset1 回のみ (全ページを一括返却) - ノードはレキサが流す順序通りに並ぶので、レンダラが走査する順序と一致する
Box<Node> 版との差は青空文庫全作品を回す corpus sweep ベンチで:
- パース時間: 約 6.4 倍速
- ピーク RSS: 約 30% 減
差は 累積する 性質のもので、CLI でも WASM でも C ABI でも Python バインディングでも同じだけ得られる。
bumpalo を選んだ理由
候補は他にもあった。aozora が選ばなかった理由を整理しておく。
| クレート | 形 | 採用しなかった理由 |
|---|---|---|
typed-arena |
型ごとにアリーナ (Arena<Ruby>、Arena<Bouten>、…) |
aozora は 30+ ノード型がある。30 個のアリーナを管理するのは運用上厳しく、各型に &'a ライフタイム引数が伝搬する |
slotmap |
index で間接参照 (SlotMap::get) |
走査ごとに key → slot → node の indirection が入り、ベンチで約 25% のレンダ性能劣化。Copy キー前提なので可変長文字フィールドは intern し直しになる |
id-arena / index_vec |
同上 | 同じ間接参照コスト |
| 手書き bump | 最大限のコントロール | 正しく書けるが、bumpalo は既に成熟している。再発明する利得が無い |
bumpalo |
単一アリーナ、型消去、bump.alloc(T) で任意型 |
aozora の「Document あたり 1 アリーナ、&'a T の lifetime」要件と一致 |
bumpalo::collections::Vec<'bump, T> も提供されていて、container の子ノード列もアリーナ内に置ける (子も親と同じ lifetime になる)。
drop と lifetime
Document を drop すると、
Box<str>ソースが drop される (1 free)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 の代替候補との比較表や、ライフタイム借用の安全性検証も書いてある。
