JavaScript コンパイラの構築におけるパフォーマンス追求

元記事は https://rustmagazine.org/issue-3/javascript-compiler/ に掲載されました

パフォーマンスについて

2年間のRustの書き込みを通して、パフォーマンスは私の体内に根付いた習慣になりました。それは 割り当てるメモリを減らす と 使用するCPUサイクルを減らす というシンプルな概念に集約されます。

しかし、問題領域の知識や潜在的な解決策への意識がなければ、最適なパフォーマンスを達成するのは困難です。

以下のセクションでは、私が経験したパフォーマンスと最適化の旅をご紹介します。私は研究、試行錯誤を通じて学ぶことを好みますので、以下はそのスタイルに従って構成されています。

パース

Oxcは標準的なコンパイラであり、抽象構文木（AST）、レキサ、再帰下向きパーサを含んでいます。

抽象構文木（AST）

コンパイラの最初のアーキテクチャ設計は、そのASTです。

すべてのJavaScriptツールは、このASTレベルで動作します。例えば：

リンター（例：ESLint）は、AST内のエラーをチェックします
フォーマッタ（例：prettier）は、ASTを再度JavaScriptテキストとして出力します
ミニファイア（例：terser）は、ASTを変換します
バンドラは、異なるファイルからの各AST間のインポート・エクスポートステートメントを接続します

ASTがユーザーフレンドリーでない場合、これらのツールを構築することは非常に苦痛になります。

JavaScriptにおいて最も使われているAST仕様は estree です。私の初版のASTは、これに準拠しています：

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では、木構造を宣言することは比較的簡単です。構造体と列挙型を使用すればよいだけです。

メモリ割り当て

私はこのバージョンのASTについて数ヶ月間、パーサの作成とともに取り組んでいました。ある日、プロファイリングを実施することにしました。プロファイラーの結果、プログラムがdrop関数の呼び出しに多くの時間を費やしていることがわかりました。

💡 これらのASTノードはBoxまたはVecを通じてヒープに割り当てられ、個別に割り当てられているため、順番にドロップされます。

これを緩和する方法はあるでしょうか？

そこでパーサの開発中に、いくつかの他の言語として書かれたRustのパーサを調べました。主に ratel と jsparagus です。

これら両方のパーサは、自身のASTにライフタイムアンノテーションを用いています：

rust

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

そして、それに伴うarena.rsというファイルを持っています。

当初はこれが何をしているのか理解できず、無視していました。しかしあるとき、それらのメモリアレーンの使用法について読んだことで理解が深まりました： bumpalo と toolshed。

要するに、メモリアレーンは事前にチャンクまたはページ単位でメモリを割り当て、アレーンがドロップされたときにまとめて解放します。そのため、アレーン上に置かれたASTをドロップすることは高速な操作となります。

この手法によるもう一つの利点は、構文木が特定の順序で構築され、走査時も同じ順序に従うため、訪問プロセス中には線形メモリアクセスが発生します。このアクセスパターンは効率的であり、隣接するメモリは一度にページ単位でCPUキャッシュに読み込まれるため、より速いアクセス時間が得られます。

残念ながら、初心者にとってメモリアレーンの使用は難しいです。なぜなら、すべてのデータ構造と関連する関数をライフタイムアンノテーションでパラメータ化しなければならないからです。この点については、5回の試行錯誤を経て、bumpalo内に構文木を割り当てる方法を習得しました。

構文木に対してメモリアレーンを使うように変更したことで、約20%のパフォーマンス向上が得られました。

列挙型のサイズ

構文木は再帰的性質を持っているため、「再帰的だが間接参照がない」というエラーを回避するために、型を定義する方法を工夫する必要があります：

error[E0072]: 再帰的な型 `Enum` および `Variant` は無限大のサイズを持つ
 --> crates/oxc_linter/src/lib.rs:1:1
  |
1 | enum Enum {
  | ^^^^^^^^^
2 |     Variant(Variant),
  |             ------- 再帰的だが間接参照なし
3 | }
4 | struct Variant {
  | ^^^^^^^^^^^^^^
5 |     field: Enum,
  |            ---- 再帰的だが間接参照なし
  |
help: サイクルを断つために間接参照（例：`Box`、`Rc`、または`&`）を挿入する
  |
2 ~     Variant(Box<Variant>),
3 | }
4 | struct Variant {
5 ~     field: Box<Enum>,

このような状況に対処する方法は二つあります。列挙型の変分にBoxをかけるか、構造体のフィールドにBoxをかけるかのどちらかです。

2017年に、同じ質問がRustフォーラムで見られました。抽象構文木を表現するより良い方法はあるか？

Aleksey（matklad）は、Expression列挙型を小さく保つために列挙型の変分をBoxで囲むべきだと説明しています。これは一体どういう意味なのでしょうか？

実際、Rustの列挙型のメモリレイアウトは、すべての変分のサイズに依存しており、合計バイトサイズは最大の変分に依存します。たとえば、次の列挙型は56バイト（1バイトのタグ、48バイトのペイロード、8バイトのアライメント）を占めます。

rust

enum Enum {
    A, // ペイロード0バイト
    B(String), // ペイロード24バイト
    C { first: String, last: String }, // ペイロード48バイト
}

典型的なJavaScriptの構文木では、Expression列挙型には45個の変分があり、Statement列挙型には20個の変分があります。列挙型の変分でBoxをかけていない場合、200バイト以上になるのです。この200バイトは常に周囲に渡され、matches!(expr, Expression::Variant(_))のようなチェックを行うたびにアクセスされるため、キャッシュフレンドリーではありません。

したがって、メモリアクセスを効率化するためには、列挙型の変分をBoxで囲むのが最適です。

perf-book では、大きな型を見つけるための追加情報が記載されています。

また、小さな列挙型サイズを制限するテストもコピーしました。

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);
}

列挙型の変分をBoxで囲むことで、約10%のスピードアップが得られました。

スパン

データ構造をよく調べることで、小さなメモリフットプリントが可能であることに気づくことは、時折起こります。

この場合、すべての構文木ノードの葉には、ソーステキストからのバイトオフセットを格納するための小さなデータ構造「スパン」が含まれています。これは2つのusizeで構成されています。

rust

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

指摘を受けました。usizeをu32に変更することで、ピークメモリを削減できるということです。 u32を超えるサイズは4GBのファイルに該当するため、安全です。

u32に変更することで、大きなファイルでのパフォーマンスが最大5%向上しました。

文字列と識別子

構文木内で、識別子名や文字列リテラルにソーステキストへの文字列参照を使うことを試みることがあります。

rust

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

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

しかし、残念ながら、JavaScriptでは文字列や識別子にエスケープシーケンスが存在し、例えば\251、\xA9、©はすべてコピーライトシンボルとして同一です。

これは、エスケープされた値を計算して新しいStringを割り当てる必要があることを意味します。

文字列の内部統合（String Interning）

大量のヒープ割り当てされた文字列がある場合、文字列の内部統合（string interning）という技術が、各異なる文字列値を1つのコピーのみ保持することで、全体のメモリ使用量を削減できます。

string-cacheは、Servoチームによって公開された人気かつ広く使われているライブラリです。当初、私は構文木内の識別子や文字列にstring-cacheライブラリを使いました。パーサの性能はシングルスレッドで非常に速かったのですが、多スレッドで並行実行するリンターを導入しようとしたとき、全コアの50%程度の利用度に留まりました。

プロファイリングを行ったところ、parking_lot::raw_mutex::RawMutex::lock_slowが実行時間トップに表示されました。ロックやマルチコアプログラミングについてあまり知らなかったものの、グローバルロックはそもそも不自然でした。そのため、string-cacheライブラリを削除し、フルなコア利用を実現することに決めました。

構文木からstring-cacheを削除することで、並行パースのパフォーマンスが約30%向上しました。

string-cache

半年後、別のパフォーマンス重視のプロジェクトに取り組んでいる際、string-cacheライブラリが再び登場しました。並行テキストパース時に、すべてのスレッドがブロッキングされていました。

今回は、string-cacheが実際に何をしているのか調査することに決めました。前述の本 Rust Atomics and Locks（Mara Bos著）を読んだおかげで、準備ができていました。

以下は、ロック周りの関連コードコード。注意すべきは、このコードは2015年に書かれたものであることです。

rust

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

// ...別の場所で
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ではないと名乗っているだけです。 💡 もしHashMapであれば、Mutex<HashMap>は同時実行可能なHashMapです。

見たいものを見つけることができるようになると、解決策は単純に思えますが、その問題に気づかないままでは一か月ほどかかりました。この構造が単なる同時実行HashMapであることが明らかになったとき、HashMap全体ではなく、バケットごとにMutexを適用するのが明らかな論理的解決策であることがわかりました。この変更を実装してから1時間以内にプルリクエストを提出し、結果に満足しました 😃。

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

ちなみに、文字列の内部統合は、Rustコミュニティ内での戦いとも言えるでしょう。このブログ記事【このブログ記事】の例のように、シングルスレッドのライブラリ（string-interner、lasso、lalrpop-intern、intaglio、strena）があります。

ファイルを並行にパースしているため、マルチスレッド対応の文字列内部統合ライブラリ（例：ustr）を利用する選択肢もあります。ただし、ustrと改良版string-cacheの両方をプロファイリングした結果、私が後述するアプローチよりもパフォーマンスが期待を下回ることが明らかになりました。

パフォーマンスが低いと考えられる理由の一例：

ハッシュ計算：内部統合ライブラリは、重複除去のために文字列をハッシュする必要がある
間接参照：ヒープ上の「遠い」場所から文字列値を読み取る必要があるため、キャッシュフレンドリーではない

文字列のインライン化

ここでは、多数の文字列を割り当てるという根本的な問題に戻りました。幸いなことに、扱っているデータの種類に注目すると、部分的な解決策が見つかります：短いJavaScript変数名や一部の短い文字列。このテクニックは「文字列インライン化」と呼ばれ、文字列のすべてのバイトをスタック上に格納します。

本質的には、以下のような列挙型が文字列を格納したいと考えています。

rust

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

列挙型のサイズを最小限に抑えるために、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>());
}

多くのライブラリが、メモリ使用量の最適化を目指しています。これもコミュニティ内の新たな戦いです。特に人気のあるものには

があります。それぞれが独自の特徴とメモリ最適化アプローチを持ち、選択時のトレードオフや考慮点が異なります。たとえばsmol_strとflexstrのクローンは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の列挙型として定義されます。列挙型の変分は、それぞれのトークンに対応するデータを保持しています。

rust

pub enum Kind {
    // キーワード
    For,
    While,
    ...
    // リテラル
    String(String),
    Num(f64),
    ...
}

現在のこの列挙型は32バイトを使用しており、レキサはしばしば何百万ものこのKindトークンを構築する必要があります。毎回Kind::ForやKind::Whileを構築するたびに、スタック上に32バイトのメモリを割り当てる必要があります。

賢い改善策として、列挙型の変分を分割してKindを1バイトに保ち、値を別の列挙型に移動することがあります。

rust

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

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

すべてのパースコードを私たちが管理しているため、対応するトークン値をその種類に常に宣言することで、安全を確保する責任があります。

TokenValueが32バイトというのはすでに非常に小さいですが、頻繁に割り当てられるため、パフォーマンスに悪影響を与える可能性があります。

では、String型を見てみましょう。コードエディタの「定義へジャンプ」機能を使って、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

私は最初、Cowという言葉をjsparagusのコードを勉強していたときに初めて目にしました。そのコードにはAutoCowと呼ばれるインフラストラクチャがありました。 https://github.com/mozilla-spidermonkey/jsparagus/blob/212f6bdbc2cae909e7d5cfebf36284560c3c4ef4/crates/parser/src/lexer.rs#L2256

コードの内容を曖昧に理解していました。 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型は、クローンオンライト機能を提供するスマートポインタです。借りられたデータを包み込み、不変アクセスを提供し、変更や所有権が必要になったときに遅延的にデータをクローンします。この型は、Borrowトレイトを介して一般の借りられたデータと連携するように設計されています。

もしあなたが、私同様の初心者（新参者）であれば、この説明は役に立ちません（今でも、何について言っているのかよく理解できません）。

指摘されました。clone-on-writeはこのデータ構造の使い方の一つにすぎません。より良い名前はRefOrOwnedであるべきです。なぜなら、これは所有データまたは参照のいずれかを含む型だからです。

SIMD

古いRustブログを読んでいたとき、パーソナライズ可能なSIMDプロジェクトグループの発表に目を止めました。私は昔から、一度くらいはSIMDを遊び倒してみたいと思っていましたが、機会がなく、ずっと待っていました。調査の結果、パーサに適用可能なユースケースを見つけました：文字列から空白を削除する速度はどれくらい？（Daniel Lemire著）。どうやらこの話題はすでに先人によって行われており、RapidJSONという名のJSONパーサが[空白を削除するのにSIMDを使用]しています。

結局、ポータブル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のブログ記事急速なパース、第1部：スキャナーの最適化に詳しいコードが記載されていました。そのキーワードマッチングコードを詳細に説明しています。

キーワードリストは静的であるため、各識別子に対して高精度のハッシュ関数を計算でき、1つの候補キーワードしか与えません。V8はgperfを使ってこの関数を計算しています。この結果は、長さと最初の2文字からハッシュを計算し、唯一の候補キーワードを見つけます。入力識別子の長さとキーワードの長さが一致する場合にのみ、識別子とキーワードを比較します。

したがって、素早いハッシュ計算と整数比較は、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氏が非常に有益なユーチューブ動画『RustとC++よりも速い：完璧なハッシュテーブル』を投稿しました。この動画は、パフォーマンス問題を細部まで調整するための体系的なアプローチを教えてくれました。

結局のところ、1〜2%のパフォーマンスに貢献するだけの単純なキーワードマッチは十分であると判断しました。数日間費やした結果、その努力は価値がないと感じたため、リファクタリングを諦めました。Rustはこの完璧なハッシュマップを作るために必要なすべての要素を持っていません。

リンター

リンターとは、ソースコードの問題を分析するプログラムのことです。

最もシンプルなリンターは、各構文木ノードを訪れ、ルールをチェックします。ビジターパターンが使えます：

rust

pub trait Visit<'a>: Sized {
    // ... 多くの訪問関数

    fn visit_debugger_statement(&mut self, stmt: &'a DebuggerStatement) {
        // エラー報告
    }
}

親へのポインタを持つ木構造

ビジターを使って構文木を下るには簡単ですが、木を上に進んで情報を収集したい場合はどうすればよいでしょうか？

この問題は、特にRustでは解決が難しいです。なぜなら、構文木のノードにポインタを追加することは不可能だからです。

一時的に構文木を忘れて、親へのポインタを持つノードを持つ一般の木構造について考えましょう。一般的な木構造を構築するには、各ノードが同じ型Nodeでなければなりません。親への参照はRcを使って行います：

rust

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

ミューテーションが必要な場合、このパターンは面倒で、ノードが異なるタイミングでドロップされるため、パフォーマンスにも悪影響があります。

より効率的な解決策は、Vecをバックストレージとして使い、インデックスをポインタとして使う方法です。

rust

struct Tree {
    nodes: Vec<Node>
}

struct Node {
    parent: Option<usize> // `nodes`内のインデックス
}

indextree はこのタスクにぴったりのライブラリです。

構文木に戻ると、各ノードが、すべての構文木ノードの種類をラップする列挙型を指すようにして、indextreeを構築できます。これを「未型の構文木」と呼びます。

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を呼ぶことで、任意のノードの親を得ることができます。

親へのポインタを持つ木構造を作成した利点は、ビジターを実装せずに構文木ノードを簡単に訪問できることです。リンターは単にindextree内のすべてのノードをループするだけになります：

rust

for node in nodes {
    match node.get().kind {
        AstKind::DebuggerStatement(stmt) => {
        // エラー報告
        }
        _ => {}
    }
}

完全な例はこちらにあります。

一見すると、このプロセスは遅く非効率に思えるかもしれません。しかし、メモリアレーンを通じて型付き構文木を訪問し、indextreeにポインタをプッシュするという操作は、効率的な線形メモリアクセスパターンです。現在のベンチマークによると、このアプローチはESLintの84倍速いので、私たちの目的には十分に速いと言えます。

ファイルを並行処理

リンターは、ignoreライブラリを使ってディレクトリトラバーサルを行います。 .gitignoreをサポートし、.eslintignoreなども追加の無視ファイルとして利用可能です。

このライブラリの小さな問題点は、並行インターフェイスが提供されていないことです。 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のイシューを検索し、関係するものを見つけました：

要するに、println!呼び出しは改行文字を検出するたびにstdoutをロックし、これは「行バッファリング」と呼ばれます。より速く出力するためには、ブロックバッファリングを有効にする必要があります。これはここで説明されています。

rust

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

let stdout = io::stdout(); // グローバルなstdoutエンティティを取得
let mut handle = io::BufWriter::new(stdout); // 必要に応じてハンドルをバッファでラップ
writeln!(handle, "foo: {}", 42); // エラーを気にするなら`?`を追加

あるいは、stdoutのロックを取得する方法もあります。

rust

let stdout = io::stdout(); // グローバルなstdoutエンティティを取得
let mut handle = stdout.lock(); // それをロック
writeln!(handle, "foo: {}", 42); // エラーを気にするなら`?`を追加

JavaScript コンパイラの構築におけるパフォーマンス追求 ​

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

パース ​

抽象構文木（AST） ​

メモリ割り当て ​

列挙型のサイズ ​

スパン ​

文字列と識別子 ​

文字列の内部統合（String Interning） ​

string-cache ​

文字列のインライン化 ​

レキサ ​

トークン ​

Cow ​

SIMD ​

キーワードマッチ ​

リンター ​

親へのポインタを持つ木構造 ​

ファイルを並行処理 ​

出力は遅い ​

JavaScript コンパイラの構築におけるパフォーマンス追求

パフォーマンスについて

パース

抽象構文木（AST）

メモリ割り当て

列挙型のサイズ

スパン

文字列と識別子

文字列の内部統合（String Interning）

string-cache

文字列のインライン化

レキサ

トークン

Cow

SIMD

キーワードマッチ

リンター

親へのポインタを持つ木構造

ファイルを並行処理

出力は遅い