JavaScript コンパイラを構築するうえでのパフォーマンス探求

原文: https://rustmagazine.org/issue-3/javascript-compiler/

パフォーマンスについて

Rust を二年ほど書いたあと、パフォーマンスは身についた規律になった。要するに メモリを減らして割り当てる と CPU サイクルを減らす ことだ。

ただし、問題領域の知識や取りうる解に気づかないと、最適な性能は難しい。

以下では、自分の性能・最適化の旅を紹介する。学び方は調べ試行錯誤の合わせ技が好きなので、章立てもそのトーンになる。

パース

Oxc は、抽象構文木（AST）、レキサ、再帰下降パーサを含む標準的なコンパイラだ。

抽象構文木（AST）

コンパイラの最初の設計判断は AST だ。

JavaScript ツールはだいたい AST 上で動く。例えば：

リンター（例: ESLint）は AST を検査してエラーを探す
フォーマッタ（例: Prettier）は AST を JavaScript テキストへ戻す
ミニファイア（例: terser）は AST を変形する
バンドラーは別ファイルの AST 同士で import/export をつなぐ

AST が使いにくいと、これらのツールを作るのは苦しくなる。

JavaScript で最も使われる AST 仕様は estree だ。最初の AST は estree をなぞった：

rust

pub struct Program {
    pub node: Node,
    pub body: Vec<Statement>,
}

pub enum Statement {
    VariableDeclarationStatement(VariableDeclaration),
}

pub struct VariableDeclaration {
    pub node: Node,
    pub declarations: Vec<VariableDeclarator>,
}

Rust では struct と enum を使えば、木構造の宣言は比較的まっすぐだ。

メモリ割り当て

この版の AST をパーサと一緒に数ヶ月書いたあと、プロファイルを取った。プロファイラは drop 呼び出しに多くの時間を使っていた。

💡 AST のノードは Box や Vec でヒープに個別に確保されているため、順番に drop される。

緩和策はないか。

パーサを書きながら、Rust で書かれた他の JavaScript パーサ、主に ratel と jsparagus を調べた。

どちらも AST にライフタイム注釈を付けている。

rust

pub enum Statement<'ast> {
    Expression(ExpressionNode<'ast>),
}

そして arena.rs という付属ファイルがある。

何をしているか分からず無視していたが、メモリアリーナの話を読み始めて理解した： bumpalo と toolshed。

要するにメモリアリーナはチャンクやページ単位で先にメモリを取り、アリーナを drop するときにまとめて解放する。 AST をアリーナ上に置けば、AST を捨てるのは高速な操作になる。

もう一つの副作用として、AST は特定の順で構築され、走査も同じ順になり、訪問時は線形にメモリにアクセスできる。近傍メモリがページ単位で CPU キャッシュに載るので、アクセスは速くなりやすい。

残念ながら Rust 初心者にはメモリアリーナは難しく、データ構造と関係する関数すべてにライフタイムを載せる必要がある。 bumpalo の中に AST を確保するのに、自分は五回試した。

AST をメモリアリーナに変えた結果、性能はおおよそ 20% 改善した。

enum のサイズ

AST は再帰的なので、「間接参照なしの再帰」エラーを避ける型の定義が必要になる：

error[E0072]: recursive types `Enum` and `Variant` have infinite size
 --> crates/oxc_linter/src/lib.rs:1:1
  |
1 | enum Enum {
  | ^^^^^^^^^
2 |     Variant(Variant),
  |             ------- recursive without indirection
3 | }
4 | struct Variant {
  | ^^^^^^^^^^^^^^
5 |     field: Enum,
  |            ---- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
2 ~     Variant(Box<Variant>),
3 | }
4 | struct Variant {
5 ~     field: Box<Enum>,

やり方は二つ。enum のバリアント側を box するか、struct のフィールドを box するか。

2017 年の Rust フォーラムにも同じ質問があった。 Is there a better way to represent an abstract syntax tree?

Aleksey (matklad) は、enum のバリアントを box して Expression enum を小さく保てと言っている。それはどういうことか。

Rust の enum のメモリ配置は、すべてのバリアントのサイズに依存し、バイト数は最大のバリアントに合わせられる。例えば次の enum は 56 バイト（タグ 1 バイト、ペイロード 48 バイト、アライン用 8 バイト）を占める。

rust

enum Enum {
    A, // 0 byte payload
    B(String), // 24 byte payload
    C { first: String, last: String }, // 48 byte payload
}

典型的な JavaScript AST では Expression が 45 バリアント、Statement が 20 バリアントを持ち、バリアントを box しないと 200 バイト超になる。この 200 バイトはどこへでも運ばれ、matches!(expr, Expression::Variant(_)) のたびにアクセスする。性能の観点ではキャッシュに優しくない。

メモリアクセスを効率化するには、enum のバリアントを box するのがよい。

perf-book に大きな型の見つけ方がまとまっている。

小さな enum サイズを縛るテストも真似した。

rust

#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn no_bloat_enum_sizes() {
    use std::mem::size_of;
    use crate::ast::*;
    assert_eq!(size_of::<Statement>(), 16);
    assert_eq!(size_of::<Expression>(), 16);
    assert_eq!(size_of::<Declaration>(), 16);
}

enum バリアントの box 化で、おおよそ 10% ほど高速化した。

Span（スパン）

データ構造をじっくり見ないと、もっと小さくできることに気づかないことがある。

ここでは、すべての AST ノードの葉に「span」と呼ばれる小さな構造体があり、ソーステキスト上のバイトオフセットを二つの usize で持っていた。

rust

pub struct Node {
    pub start: usize,
    pub end: usize,
}

指摘されて、u32 に安全に変えられる。u32 を超えるのは 4GB 超のファイルだけだ。

u32 へ変えると、大きなファイルで最大 5% 程度の性能向上があった。

文字列と識別子

AST では識別子名や文字列リテラルにソースへの参照 &str を使いたくなる。

rust

pub struct StringLiteral<'a> {
    pub value: &'a str,
}

pub struct Identifier<'a> {
    pub name: &'a str,
}

しかし JavaScript では文字列や識別子にエスケープ列があり、 '\251'、'\xA9'、'©' は著作権記号として同じになる。

つまりエスケープ後の値を計算して新しい String を確保しなければならない。

文字列のインターン化

ヒープ文字列が大量にあるとき、string interning で重複を減らし、それぞれの異なる文字列を一つだけ保持できる。

string-cache は Servo チームの広く使われているクレートだ。最初は識別子と文字列に string-cache を使った。単一スレッドのパーサでは速かったが、rayon で複数パーサを並列に回すリンタを書き始めると、CPU 利用率は全コアのおおよそ 50% だった。

プロファイルすると parking_lot::raw_mutex::RawMutex::lock_slow が上位に出てきた。ロックやマルチコアについてはよく知らなかったが、グローバルロックはおかしいと感じ、string-cache を外してフルに CPU を使うことにした。

AST から string-cache を外すと、並列パースはおおよそ 30% 速くなった。

string-cache

半年後、別の性能クリティカルなプロジェクトで string-cache が再び問題になった。並列テキストパース中に全スレッドを止めていた。

Mara Bos 著 Rust Atomics and Locks を読んだあとなら理解できると思い、string-cache の中身を調べた。

ロックまわりの関連コードである。2015 年、八年前のコードだ。

rust

pub(crate) static DYNAMIC_SET: Lazy<Mutex<Set>> = Lazy::new(|| {
    Mutex::new({

// ... in another place
let ptr: std::ptr::NonNull<Entry> =
    DYNAMIC_SET.lock().insert(string_to_add, hash.g);

素直だ。文字列を挿入するたびに Set をロックする。パーサではこのルーチンが頻繁に呼ばれるので、同期が性能を落とす。

Set のデータ構造を見て何をしているか：

rust

pub(crate) fn insert(&mut self, string: Cow<str>, hash: u32) -> NonNull<Entry> {
    let bucket_index = (hash & BUCKET_MASK) as usize;
    {
        let mut ptr: Option<&mut Box<Entry>> = self.buckets[bucket_index].as_mut();

        while let Some(entry) = ptr.take() {
            if entry.hash == hash && *entry.string == *string {
                if entry.ref_count.fetch_add(1, SeqCst) > 0 {
                    return NonNull::from(&mut **entry);
                }
                entry.ref_count.fetch_sub(1, SeqCst);
                break;
            }
            ptr = entry.next_in_bucket.as_mut();
        }
    }
    debug_assert!(mem::align_of::<Entry>() >= ENTRY_ALIGNMENT);
    let string = string.into_owned();
    let mut entry = Box::new(Entry {
        next_in_bucket: self.buckets[bucket_index].take(),
        hash,
        ref_count: AtomicIsize::new(1),
        string: string.into_boxed_str(),
    });
    let ptr = NonNull::from(&mut *entry);
    self.buckets[bucket_index] = Some(entry);

    ptr
}

バケットを探して、なければ挿入しているように見える。

💡 線形探索か？線形探索ならこの Set は名指ししない HashMap のようなものでは？ 💡 HashMap なら Mutex<HashMap> は並行ハッシュマップだ。

何を探せばいいか分かれば単純に見えるが、問題に気づかないまま一ヶ月かかった。並行ハッシュマップだと分かったあと、ハッシュマップ全体ではなくバケット単位に Mutex をかけるのが明確な解だった。実装して一時間以内に PR を出し、結果に満足した 😃。

https://github.com/servo/string-cache/pull/268

文字列のインターン化は Rust コミュニティでも激戦区だ。このブログ記事の例のように、単スレッド向けの string-interner、lasso、lalrpop-intern、intaglio、strena などがある。

ファイルを並列パースするなら、ustr のようなマルチスレッド向けインターナも選択肢だ。が、ustr と改良版 string-cache の両方をプロファイルしても、後述のアプローチには性能で及ばなかった。

推測される理由：

ハッシュ — 重複排除のため文字列のハッシュが要る
間接参照 — 文字列を「遠い」ヒープから読むのはキャッシュに優しくない

文字列のインライン化

大量の文字列確保という最初の問題に戻る。扱うデータを見ると部分的な解がある：短い JavaScript 変数名や短い文字列。スタックに文字列バイトを全部載せる string inlining という手法だ。

本質的には、次のような enum で文字列を持ちたい。

rust

enum Str {
    Static(&'static str),
    Inline(InlineReprensation),
    Heap(String),
}

enum を小さくするには、InlineRepresentation を String と同じサイズにする。

rust

#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
#[test]
fn test_size() {
    use std::mem::size_of;
    assert_eq!(size_of::<String>(), size_of::<InlineReprensation>());
}

メモリ最適化を目指すクレートは Rust 界でもまた戦場だ。人気どころは：

特性とトレードオフがそれぞれ違う。例: smol_str と flexstr の clone は O(1)。 flexstr は 22 バイト、smol_str と smartstring は 23 バイト、compact_str は 64 ビットで 24 バイトをインラインできる。

https://fasterthanli.me に深掘り記事がある。

String を compact_str::CompactStr に変えると、メモリ割り当てが大きく減った。

レキサ

トークン

レキサ（トークナイザ）の仕事は、ソーステキストをトークンという構造化データに変えること。

rust

pub struct Token {
    pub kind: Kind,
}

扱いやすくするため、トークン種別は Rust ではだいたい enum。各バリアントがトークンごとのデータを持つ。

rust

pub enum Kind {
    // Keywords
    For,
    While,
    ...
    // Literals
    String(String),
    Num(f64),
    ...
}

この enum は今 32 バイトで、レキサは何百万という Kind を作る。 Kind::For や Kind::While のたびにスタックに 32 バイトを割り当てる。

改善の妙手は、バリアントを分けて Kind を 1 バイトにし、値を別 enum に逃がすこと。

rust

pub struct Token<'a> {
    pub kind: Kind,
    pub value: TokenValue
}

pub enum TokenValue {
    None,
    String(String),
    Num(f64),
}

パースコードは自分たちが全部押さえているので、種別と値の対応を常に正しく保つのが仕事。

TokenValue が 32 バイトでも、頻繁に割り当てると性能に悪影響がありうる。

エディタの定義ジャンプで String -> Vec -> RawVec と辿る：

rust

pub struct String {
    vec: Vec<u8>,
}

pub struct Vec {
    buf: RawVec<T, A>,
    len: usize,
}

pub struct RawVec {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

String は u8 の Vec で、Vec は長さと容量を持つ。この文字列を変更しないなら、容量フィールドを捨ててスライス &str にするのがメモリの最適化になる。

rust

pub enum TokenValue<'a> {
    None,
    String(&'a str),
    Num(f64),
}

TokenValue は 24 バイトになる。

TokenValue で String の代わりにスライスを使うとメモリは減るが、ライフタイム注釈の負担があり、借用チェッカやコード全体に波及する。借用チェックのゲームには 8 ヶ月負けたが、再訪のあと勝てた。

状況が合えば、参照の代わりに所有の不変表現も選べる。例: String なら Box<str>、Vec<u8> なら Box<[u8]>。

要するにデータ構造を小さく保つ工夫はいくらでもあり、ときに性能の報酬になる。

Cow

jsparagus のコードで Cow という語に初めて触れた。 AutoCow という基盤がある。

ぼんやり理解していた。JavaScript 文字列をトークナイズするとき、エスケープ列に当たったら新しい文字列を確保し、そうでなければ元のスライスを返す：

rust

fn finish(&mut self, lexer: &Lexer<'alloc>) -> &'alloc str {
    match self.value.take() {
        Some(arena_string) => arena_string.into_bump_str(),
        None => &self.start[..self.start.len() - lexer.chars.as_str().len()],
    }
}

賢い。99.9% はエスケープが無いので新規確保は起きない。

Cow や「clone-on-write スマートポインタ」という名前はしっくりこなかった。

Cow は clone-on-write を提供するスマートポインタで、借用データへの不変アクセスを包み、変更や所有が必要になったときに遅延コピーする。Borrow トレイト経由の一般的な借用データ向けに設計されている。

Rust が初めて（当時の自分のように）なら、この説明は助けにならない（今でも何と言っているのかよく分からない）。

指摘されて、clone-on-write は一用途に過ぎず、RefOrOwned と名付けるほうがよい。所有データか参照かを含む型だ。

SIMD

古い Rust ブログを読んでいたとき Announcing the Portable SIMD Project Group が目に止まった。 SIMD は触ってみたかったが機会がなかった。調べたあと、パーサに使えそうな例を見つけた： Daniel Lemire の How quickly can you remove spaces from a string?。 JSON パーサ RapidJSON が SIMD で空白を飛ばす実装をしていた。

portable-SIMD と RapidJSON のコードの助けを借りて、空白スキップに加え複行コメントのスキップも実現した。

どちらも数パーセント程度性能が上がった。

キーワードマッチ

プロファイルの上位に、全体実行時間の 1〜2% ほどを占めるホットパスがあった。

文字列を JavaScript キーワードに合わせている：

rust

fn match_keyword(s: &str) -> Self {
    match s {
        "as" => As,
        "do" => Do,
        "if" => If,
        ...
        "constructor" => Constructor,
        _ => Ident,
    }
}

TypeScript 込みで 84 個の文字列がある。調査の末、V8 のブログ Blazingly fast parsing, part 1: optimizing the scanner を見つけ、キーワードマッチのコードが詳しい。

キーワード一覧は静的なので、各識別子に対して候補キーワードが高々一つになる完全ハッシュ関数を計算できる。V8 は gperf でこの関数を求める。結果として長さと識別子の最初の二文字からハッシュを計算し、単一の候補を引く。そのキーワードの長さが入力識別子の長さと一致するときだけ比較する。

だから素早いハッシュに整数比較なら 84 回の文字列比較より速いはず。だが何度か試しても上手くいかなかった。

結局 LLVM がすでに最適化していた。 rustc に --emit=llvm-ir を付けると、該当コードはこうなる：

switch i64 %s.1, label %bb6 [
  i64 2, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit.i"
  i64 3, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit280.i"
  i64 4, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit325.i"
  i64 5, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit380.i"
  i64 6, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit450.i"
  i64 7, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit540.i"
  i64 8, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit590.i"
  i64 9, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit625.i"
  i64 10, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit655.i"
  i64 11, label %"_ZN4core5slice3cmp81_$LT$impl$u20$core..cmp..PartialEq$LT$$u5b$B$u5d$$GT$$u20$for$u20$$u5b$A$u5d$$GT$2eq17h46d405acb5da4997E.exit665.i"
], !dbg !191362

%s が文字列、%s.1 が長さ… 文字列の長さで分岐している。コンパイラのほうが賢い 😃。

（本気で LLVM IR とアセンブリを読み始めたほどだ。）

あとで @strager が Faster than Rust and C++: the PERFECT hash table という教育的な動画を出した。微調整の性能問題をどう考えるか、体系的に学べる。

結局、単純なキーワードマッチで十分だと結論した。全体の 1〜2% だし、数日かけても割に合わない — この完全ハッシュマップを Rust で揃えるピースはまだ足りない。

リンター

リンターはソースの問題を解析するプログラムだ。

最も単純なリンターは AST の各ノードを訪問してルールを検査する。ビジタパターンが使える：

rust

pub trait Visit<'a>: Sized {
    // ... lots of visit functions

    fn visit_debugger_statement(&mut self, stmt: &'a DebuggerStatement) {
        // report error
    }
}

親を指す木

ビジタで AST を下へ降りるのは簡単だが、上へ登って情報を集めたいときは？

Rust では AST ノードにポインタを足せないので、この問題は特に難しい。

AST を忘れて、ノードが親を指す一般の木だけ考える。各ノードを同じ型 Node にし、親を Rc で参照する：

rust

struct Node {
    parent: Option<Rc<Node>>,
}

変更が必要だと扱いが面倒だし、ノードが別々のタイミングで drop されるので性能も良くない。

より効率的なのは、Vec を裏ストレージにしてインデックスで親を指すこと。

rust

struct Tree {
    nodes: Vec<Node>
}

struct Node {
    parent: Option<usize> // index into `nodes`
}

indextree がこの用途に向いている。

AST に戻ると、すべての AST ノード種を包む enum を指すようにすれば indextree を構築できる。これを非型付け AST と呼ぶ。

rust

struct Node<'a> {
    kind: AstKind<'a>
}

enum AstKind<'a> {
    BlockStatement(&'a BlockStatement<'a>),
    // ...
    ArrayExpression(&'a ArrayExpression<'a>),
    // ...
    Class(&'a Class<'a>),
    // ...
}

最後のピースは、ビジタパターンの中でこの木を組み立てるコールバックである。

rust

pub trait Visit<'a> {
    fn enter_node(&mut self, _kind: AstKind<'a>) {}
    fn leave_node(&mut self, _kind: AstKind<'a>) {}

    fn visit_block_statement(&mut self, stmt: &'a BlockStatement<'a>) {
        let kind = AstKind::BlockStatement(stmt);
        self.enter_node(kind);
        self.visit_statements(&stmt.body);
        self.leave_node(kind);
    }
}

impl<'a> Visit<'a> for TreeBuilder<'a> {
    fn enter_node(&mut self, kind: AstKind<'a>) {
        self.push_ast_node(kind);
    }

    fn leave_node(&mut self, kind: AstKind<'a>) {
        self.pop_ast_node();
    }
}

最終的なデータ構造は indextree::Arena<Node<'a>> で、各 Node が AstKind<'a> へのポインタを持つ。 indextree::Node::parent で任意のノードの親を得られる。

親を指す木にすると、ビジタを実装しなくても AST ノードを扱いやすくなる。リンターは indextree 内のすべてのノードを単純にループするだけになる：

rust

for node in nodes {
    match node.get().kind {
        AstKind::DebuggerStatement(stmt) => {
        // report error
        }
        _ => {}
    }
}

完全な例はこちら。

一見ゆっくりで非効率に見える。だが型付き AST をメモリアリーナで辿り、indextree にポインタを押し込むのは線形でキャッシュに優しいアクセスパターンだ。現状のベンチマークでは ESLint の 84 倍ほど速く、目的には十分速い。

ファイルの並列処理

リンターはディレクトリ走査に ignore クレートを使う。 .gitignore を踏襲し、.eslintignore などの無視ファイルも足せる。

このクレートの小さな問題は並列 API が無いこと。 ignore::Walk::new(".") に par_iter はない。

代わりにプリミティブを組み合わせる：

rust

let walk = Walk::new(&self.options);
rayon::spawn(move || {
    walk.iter().for_each(|path| {
        tx_path.send(path).unwrap();
    });
});

let linter = Arc::clone(&self.linter);
rayon::spawn(move || {
    while let Ok(path) = rx_path.recv() {
        let tx_error = tx_error.clone();
        let linter = Arc::clone(&linter);
        rayon::spawn(move || {
            if let Some(diagnostics) = Self::lint_path(&linter, &path) {
                tx_error.send(diagnostics).unwrap();
            }
            drop(tx_error);
        });
    }
});

これで有用な機能が開く。診断は単一スレッドですべて出力できる。本文最後の話題につながる。

出力は遅い

診断の表示自体は速かったが、巨大モノレポでリンターを回すたびに数千件のメッセージを出すのが永遠に感じられた。 Rust の GitHub issue を調べ、次に辿り着いた：

要するに println! は改行のたびに stdout をロックする。これがラインバッファリングだ。速く出したければブロックバッファリングを選ぶ。手順はここに記載がある。

rust

use std::io::{self, Write};

let stdout = io::stdout(); // get the global stdout entity
let mut handle = io::BufWriter::new(stdout); // optional: wrap that handle in a buffer
writeln!(handle, "foo: {}", 42); // add `?` if you care about errors here

または stdout のロックを取る。

rust

let stdout = io::stdout(); // get the global stdout entity
let mut handle = stdout.lock(); // acquire a lock on it
writeln!(handle, "foo: {}", 42); // add `?` if you care about errors here

JavaScript コンパイラを構築するうえでのパフォーマンス探求 ​

パフォーマンスについて ​

パース ​

抽象構文木（AST） ​

メモリ割り当て ​

enum のサイズ ​

Span（スパン） ​

文字列と識別子 ​

文字列のインターン化 ​

string-cache ​

文字列のインライン化 ​

レキサ ​

トークン ​

Cow ​

SIMD ​

キーワードマッチ ​

リンター ​

親を指す木 ​

ファイルの並列処理 ​

出力は遅い ​

JavaScript コンパイラを構築するうえでのパフォーマンス探求

パフォーマンスについて

パース

抽象構文木（AST）

メモリ割り当て

enum のサイズ

Span（スパン）

文字列と識別子

文字列のインターン化

string-cache

文字列のインライン化

レキサ

トークン

Cow

SIMD

キーワードマッチ

リンター

親を指す木

ファイルの並列処理

出力は遅い