Read OSS
oxc-project/oxc

アリーナアロケータとAST設計：Oxcのパフォーマンスの基盤

•上級

前提知識

  • ›Rustの所有権、借用、ライフタイムアノテーション
  • ›メモリアロケータの基本的な理解
  • ›第1回：アーキテクチャとクレートマップ

アリーナアロケータとAST設計：Oxcのパフォーマンスの基盤

パフォーマンスを重視するシステムには、必ずその上のすべての層に影響を及ぼす根本的な設計上の決断があります。Oxcにおけるその決断が、アリーナアロケーションです。個別にヒープ確保してASTノードをメモリ上に散在させ、参照カウントやガベージコレクションを必要とする方式を取らず、Oxcはすべてのノードを連続したメモリ領域（アリーナ）にまとめてアロケートします。これにより、O(1)での一括解放、キャッシュフレンドリーなトラバーサル、参照カウントのオーバーヘッドゼロを実現しています。本記事では、アロケータの内部実装を追いながら、最大限のパフォーマンスを引き出すためにAST設計がアリーナアロケーションをどのように活用しているかを解説します。

なぜアリーナアロケーションなのか

Rustで書かれた一般的なJavaScriptツールでは、ヒープアロケートされたノードにはBox<T>を、共有所有権にはRc<T>やArc<T>を使うのが普通です。すべてのアロケーションはグローバルアロケータ（通常はmalloc）を経由し、解放のたびに個々のライフタイムを追跡する必要があります。ノード数が数千に及ぶASTでは、これが次の2つの問題を引き起こします。

  1. アロケーションのオーバーヘッド：malloc/freeのペアはシステムコールを伴うか、少なくともアロケータのフリーリストを辿る処理が必要である
  2. キャッシュの汚染：異なるタイミングでアロケートされたノードはメモリ上に散在し、トラバーサル時のキャッシュミスを引き起こす

アリーナアロケーションはこの両方を解決します。すべてのASTノードはバンプアロケータに格納されます。これはアロケーションのたびにポインタが前進するだけのシンプルな仕組みです。解放のコストはゼロです。ASTが不要になったらアリーナをドロップするだけで、すべてのメモリが一度に解放されます。

Oxcのアーキテクチャドキュメントには、トレードオフが明確に記されています。

  • ✅ 10〜50%のパフォーマンス向上
  • ✅ 所有権モデルの簡略化
  • ❌ ライフタイム管理が必要
  • ❌ メモリパターンの柔軟性が低下

実際には、ライフタイムの制約（アロケータに紐付く'a）は十分に扱いやすいものです。コンパイラツールはファイルを解析して処理し、すべてを破棄するというバッチ処理モデルと自然に一致するからです。

アロケータの内部実装

crates/oxc_allocator/src/allocator.rsにあるAllocator構造体は、内部のBumpアロケータをラップしています。

#[derive(Default)]
pub struct Allocator {
    bump: Bump,
}

アロケータはチャンクを指数的に拡張します。新しいチャンクは必ず前のチャンクの2倍以上のサイズになります。そのため一般的なファイルでは、2〜3回の再利用でアロケータが安定します。

flowchart LR
    subgraph Allocator Chunks
        C1[Chunk 1: 4KB] --> C2[Chunk 2: 8KB] --> C3[Chunk 3: 16KB]
    end
    ptr[Bump Pointer] -.-> C3
    style C1 fill:#f9f,stroke:#333
    style C2 fill:#f9f,stroke:#333
    style C3 fill:#bbf,stroke:#333

alloc()のホットパス

allocator.rs#L300-L307にあるメインのアロケーションメソッドは積極的にインライン化されており、Drop型がアリーナに入るのをコンパイル時に防ぐチェックも含まれています。

#[inline(always)]
pub fn alloc<T>(&self, val: T) -> &mut T {
    const { assert!(!std::mem::needs_drop::<T>(), "Cannot allocate Drop type in arena") };
    self.bump.alloc(val)
}

このconstアサーションはエレガントな設計です。不正な使用をランタイムではなくコンパイル時に検出します。std::vec::Vecやその他のDrop型はアリーナにアロケートできません。コンパイラがはっきりと拒否します。

reset()による再利用

数百のファイルをlintするようなバッチ処理では、Oxcはreset()メソッドを使ってアロケータを再利用します。これにより、最大のチャンクだけを保持（小さいチャンクは破棄）し、バンプポインタを巻き戻し、再アロケーションのためのシステムコールを一切発生させません。83〜160行目のドキュメントには、同一のワークロードを3回実行するとキャパシティがどのように安定するかが詳しく説明されています。

ヒント： 複数のファイルを連続して処理するときは、アロケータを新しく生成するのではなく、ファイルの処理ごとに必ずリセットしましょう。システムコールを抑制し、メモリをCPUキャッシュに温かく保てます。

アリーナ版BoxとVec

Oxcはstd::boxed::Boxとstd::vec::Vecのアリーナ対応の代替型を提供しています。

Box<'a, T>

crates/oxc_allocator/src/boxed.rs#L34-L35にあるアリーナ版Boxは、シンプルなNonNull<T>ラッパーです。

#[repr(transparent)]
pub struct Box<'alloc, T: ?Sized>(NonNull<T>, PhantomData<(&'alloc (), T)>);

std::boxed::Boxとの主な違いは次のとおりです。

  • Dropなし：メモリはBoxがドロップされたときではなく、アロケータがドロップされたときに解放されます。
  • #[repr(transparent)]：Boxは生ポインタとまったく同じサイズで、オーバーヘッドはゼロです。
  • コンパイル時のDrop防止：Box::new_inはalloc()と同じconstアサーションを持っています。

Vec<'a, T>

crates/oxc_allocator/src/vec.rs#L39-L41にあるアリーナ版Vecは、内部ベクタ実装をラップしています。

#[repr(transparent)]
pub struct Vec<'alloc, T>(InnerVec<'alloc, T>);

注意すべき点があります。VecはSyncですがSendではありません。複数のスレッドが同時にVecを読むことはできます（&Bumpは共有されるため）。しかしVecを別スレッドに移動することはできません。スレッドセーフでないBumpへの並行アロケーションを許してしまうからです。この制約はvec.rs#L56の手動unsafe impl Syncによって強制されています。

AST設計の哲学：ESTreeを超えて

ほとんどのJavaScriptツールはASTノード型にESTree仕様を使っています。Oxcは型安全性、パフォーマンス、開発者体験を向上させるために、意図的にESTreeから逸脱しています。

識別子の分類

ESTreeにはIdentifierノードが一種類しかありませんが、Oxcはこれを意味の異なる3つの型に分割しています。

classDiagram
    class BindingIdentifier {
        +Span span
        +Ident name
        +Cell~Option~SymbolId~~ symbol_id
        "Variable declarations"
    }
    class IdentifierReference {
        +Span span
        +Ident name
        +Cell~Option~ReferenceId~~ reference_id
        "Variable references"
    }
    class IdentifierName {
        +Span span
        +Ident name
        "Property names, labels"
    }

この分割はcrates/oxc_ast/src/ast/js.rsに実装されており、セマンティック解析がSymbolIdをBindingIdentifierに、ReferenceIdをIdentifierReferenceに直接格納できることを意味します。ESTreeでは、Identifierがバインディングなのか参照なのかを判定するために別途ルックアップテーブルが必要でした。Oxcはこの区別を構造そのものに組み込んでいます。

型付きリテラル

同様に、ESTreeの汎用的なLiteralノードも、Oxcでは個別の型に分かれています。crates/oxc_ast/src/ast/literal.rsでは次のように定義されています。

  • BooleanLiteral — bool値を持つ
  • NullLiteral — 値フィールド不要
  • NumericLiteral — f64値とNumberBaseを持つ
  • StringLiteral — Str値を持つ
  • BigIntLiteral — 文字列表現を持つ
  • RegExpLiteral — パターンとフラグを持つ

これにより、ESTreeベースのツールが頻繁に行うランタイムの型チェック（例：if (node.type === 'Literal' && typeof node.value === 'number')）が不要になります。

Programルートとexpressionの列挙型

js.rs#L51-L67にあるルートのProgramノードは、アリーナ型の実際の使われ方を示しています。

pub struct Program<'a> {
    pub node_id: Cell<NodeId>,
    pub span: Span,
    pub source_type: SourceType,
    pub source_text: &'a str,
    pub comments: Vec<'a, Comment>,
    pub hashbang: Option<Hashbang<'a>>,
    pub directives: Vec<'a, Directive<'a>>,
    pub body: Vec<'a, Statement<'a>>,
    pub scope_id: Cell<Option<ScopeId>>,
}

すべてのコレクションはVec<'a, T>（アリーナアロケート）、所有する子ノードはすべてBox<'a, T>（アリーナアロケート）を使い、Cellは後でセマンティック解析によって埋められるIDに使われます。'aライフタイムはすべてをアロケータに紐付けます。

js.rs#L78-L119にあるExpression列挙型は別のパターンを示しています。各バリアントはペイロードをBox<'a, T>でラップしています。

pub enum Expression<'a> {
    BooleanLiteral(Box<'a, BooleanLiteral>) = 0,
    NullLiteral(Box<'a, NullLiteral>) = 1,
    NumericLiteral(Box<'a, NumericLiteral<'a>>) = 2,
    // ...
    Identifier(Box<'a, IdentifierReference<'a>>) = 7,
    // ...
}

明示的な判別値（= 0、= 1など）は、コード生成システムが安定したバイナリ表現を維持するために使用しています。

Span型：コンパクトさのためのu32

ソースの位置情報にはcrates/oxc_span/src/span.rsにあるSpan型を使います。startとendをu32のバイトオフセットとして保持します。

pub struct Span {
    pub start: u32,
    pub end: u32,
}

usizeではなくu32を使うことで、64ビットシステムでのSpanのサイズを16バイトから8バイトに半減できます。すべてのASTノードにSpanが含まれるため、数千のノードからなる典型的なASTでは、これが大幅なメモリ節約につながります。トレードオフとしてファイルサイズの上限が4GBになりますが、JavaScriptファイルとしては十分すぎる制限です。

アリーナ対応トレイト：CloneIn、TakeIn、Dummy

標準のRust Cloneはアリーナアロケートされた型では機能しません。クローンがどのアロケータに属するかを指定せずにBox<'a, T>をクローンすることはできないからです。Oxcはこの問題を3つのカスタムトレイトで解決しています。いずれもast_toolsによって生成されます。

flowchart TD
    CI[CloneIn] -->|"clone into allocator"| NewNode[New arena node]
    TI[TakeIn] -->|"replace with dummy"| OldNode[Original node becomes Dummy]
    DU[Dummy] -->|"create placeholder"| Placeholder[Zero-valued node]
  • CloneIn — ノードを（場合によっては別の）アロケータにクローンします。変換処理中にASTサブツリーをアロケータ間でコピーしたり、ノードを複製したりする際に使います。
  • TakeIn — ノードをダミー値に置き換えてオリジナルを返します。アリーナ版のmem::take()であり、ダングリング参照を残さずにASTからノードを取り出す際に欠かせません。
  • Dummy — ゼロ値のプレースホルダーノードを生成します。すべてのAST型には、有効（ただし無意味）なインスタンスを返すDummy実装が用意されています。

これらのトレイトは#[generate_derive(CloneIn, Dummy, TakeIn)]アノテーションによって、すべてのAST型に対して自動的に導出されます。ast_toolsコードジェネレータはこれらのアノテーションを読み取り、実装を生成します。このコード生成システムの詳細については第4回で解説します。

ヒント： 親ノードから子ノードを取り出すトランスフォームを書くときは、クローンを試みるのではなくchild.take_in(allocator)を使いましょう。O(1)の操作でノードをダミーと入れ替えるだけです。一方、クローンはサブツリー全体を走査します。

AST型のアノテーション

Programの定義を見ると、いくつかのアトリビュートマクロが付いていることに気づくでしょう。

#[ast(visit)]
#[scope(flags = ScopeFlags::Top, strict_if = ...)]
#[generate_derive(CloneIn, Dummy, TakeIn, GetSpan, GetSpanMut, ContentEq, ESTree)]
pub struct Program<'a> { ... }

#[ast]、#[scope]、#[visit]、#[generate_derive]といったアトリビュートは、ast_toolsコードジェネレータのマーカーです。これらはコンパイル時にprocマクロとして実行されるわけではありません。代わりに、just astを実行したときにast_toolsがこれらのアノテーションを読み取り、次のものを生成します。

  • ビジタートレイトのメソッド（visit_program、visit_expressionなど）
  • SemanticBuilderのスコープ生成ロジック
  • CloneIn、GetSpan、ContentEqなどのトレイト実装
  • メモリレイアウトのアサーション

#[ast]マクロ自体（crates/oxc_ast_macros/src/lib.rs#L42-L47）は構造体に#[repr(C)]を、列挙型に#[repr(C, u8)]を付加し、予測可能なメモリレイアウトを保証します。

次回予告

アロケータとASTは、その上にすべてが構築される基盤です。第3回では、ソーステキストが完全に解決されたASTへと変換される過程を追います。レキサーのトークンストリームから手書きの再帰降下パーサーを経て、スコープチェーン・シンボルテーブル・参照解決を一度のASTパスで構築するSemanticBuilderまで、一連の流れを解説します。