> ## Content Index
> Fetch the complete content index at: https://www.sakashita.page/llms.txt
> Use this file to discover other available public pages before exploring further.

# 50,000 ノードの AST を 16 回のアロケーションで: bumpalo 借用アリーナの実例
- URL: https://www.sakashita.page/aozora-bumpalo-borrowed-arena-ast/
- Published: 2026-05-03T23:00:39.000Z
- Updated: 2026-05-03T23:00:38.000Z
- Author: Sakashita Yasunobu
- Tags: 技術

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

handbook の対応章: [Borrowed-arena AST](https://p4suta.github.io/aozora/arch/arena.html)。

## 問題設定

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

```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>` はその両方から借用する。

```rust
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 への参照になる。

```rust
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 が選ばなかった理由を整理しておく。

| クレート                  | 形                                      | 採用しなかった理由                                                                                          |
| --------------------- | -------------------------------------- | -------------------------------------------------------------------------------------------------- |
| 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 すると、

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

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

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

```rust
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](https://github.com/P4suta/aozora/tree/main/crates/aozora-syntax) (型定義と arena ラッパ) と [aozora-pipeline](https://github.com/P4suta/aozora/tree/main/crates/aozora-pipeline) (実際のアロケーション) にある。handbook の [arena.md](https://p4suta.github.io/aozora/arch/arena.html) には bumpalo の代替候補との比較表や、ライフタイム借用の安全性検証も書いてある。