AST-grepがTree-sitterをRustで書き直し、30%高速化を実現

AST-grepがTree-sitterをRustで書き直し、30%高速化を実現 パート1/4 — 冒険の全貌 ast-grepは、Tree-sitterのC言語コアをRustで書き換えました。AIがコードを生成しました。新しいコアは、解析が速く、完了したツリーの読み取りが速く、ast-grep自体も速くなりました。（タイトルの「30%」はパーサーのみの数値です。エンドツーエンドでは、ast-grepは約22%高速に動作します。） ソースリポジトリ: HerringtonDarkholme/tree-sitter。 数値の前に、2つの簡単な紹介があります。ast-grep — このブログが属する構造コード検索ツール — は、テキストではなく構文でコードを検索するため、処理するすべてのファイルはまず構文ツリーになる必要があります。Tree-sitterは、そのツリーを構築するパーサーフレームワークです。文法定義を与えると、その言語用の高速パーサーが生成されます。エディタの世界で生まれ、現在では膨大な文法とツールのエコシステムを支えています。 パフォーマンスとピークRSS。スループットは正規化されており、変更されていないCビルド（「C / normal」）は100を記録します。数値が高いほど良いです。RSSはピーク常駐メモリで、生の解析行は、言語フィクスチャのベンチマーク全体で変動するため、範囲として表示されます。アウトライン行はast-grepの実際のワークロードです。リポジトリ内のすべてのファイルを解析し、各完了ツリーをウォークして構造的なアウトラインを抽出します。 ベンチマーク C / normal Rust 差分 生の解析 スループット: 100 RSS: 8.48–21.41 MiB スループット: 129.74 RSS: 8.42–25.70 MiB +29.74% スループット +20.0% RSS上限 ツリーのトラバーサル スループット: 100 RSS: 20.38 MiB スループット: 110.16 RSS: 22.20 MiB +10.16% スループット +8.9% RSS ast-grepの完全なアウトライン ユーザーCPU: 1.233 s RSS: 26.52 MiB ユーザーCPU: 0.960 s RSS: 34.43 MiB −22.2% ユーザーCPU +29.8% RSS Rustはすべてのパーサーとトラバーサルフィクスチャで勝利し、ast-grepはまったく同じアウトラインを生成しました。メモリがトレードオフです。Rustビルドは、ast-grepの実行で約8 MiB多く使用します。はるかに大きなTypeScriptストレスコーパス — TypeScriptコンパイラリポジトリのテストベースラインツリー、このプロジェクトのメモリ負荷テスト — では、91.2 MiBに達します。この数値は、告白ではなく、勝利です。プロジェクトの早い段階では、同じコーパスが1 GiBを超えていました。 結果は、アップストリームのTree-sitterの1対1の置き換えではありません。これは、AIコーディングエージェントが完全なファイルスナップショットを分析するために構築された、より狭いランタイムです。既存の生成言語とパーサーは互換性を維持します。WebAssemblyコンパイル言語のネイティブロードとインクリメンタルオールドツリーの再利用は削除されました。互換性を維持するには、多くの生のポインタとunsafeブロックが必要です。この境界線により、ターゲットワークロードが不要とするエディタ固有のメカニズムを削除しながら、文法エコシステムをエージェントコーディングに役立つものに保ちます。 それが終わりです。そこに至るまでの道のりは別の話でした。 Tree-sitterを書き直す理由？ すべての真剣なast-grepパフォーマンス調査は、最終的に同じ場所にたどり着きました。Tree-sitterです。ast-grepはルールをより速くすることができました。作業を切り詰め、構成をキャッシュし、無関係な構文の訪問を回避できました。しかし、すべてのファイルは最初に構文ツリーになる必要があり、Tree-sitterはそのツリーを構築しました。パーサーは基盤であり、そしてますます天井でもありました。 長年、書き直しや深い最適化を夢見ていました。その夢は、ランタイムを開くまで続くことがほとんどでした。成熟したC実装、バイナリ互換性、外部スキャナー、エラーリカバリ、インクリメンタルパーシング、曖昧な文法、いくつかの言語バインディング、そしてそれの上に構築された膨大な文法エコシステムを壊さないという小さな問題がありました。 一人で、これは週末のプロジェクトではありませんでした。それはヘッダーファイルを着たヘラクレスの仕事でした。 だから何も起こりませんでした。 次に、Bun、pgrust、Rocなど、AI支援による書き換えの試みが everywhere に現れました。それらは、Tree-sitterを書き直すことが賢明であること、ランタイムを小さくすること、またはパーサー理論をそれほど奇妙でないことを証明しませんでした。それらは、実験が一人で試すのに十分安価になったことを示し、私が不合理な質問をして、10年が終わる前に答えを得るためのてこを提供しました。 そこで、ChatGPTにTree-sitterのC言語コアをRustで書き直すように指示しました。プロジェクトは、互換性第一の翻訳から、高速だが読みにくい最適化の試み、そしてよりシンプルなランタイムと実際のパーサーの改善へと進みました。しかし、より高速なパーサーがast-grepをさらに遅くする可能性があることが判明しました。 この記事の残りは、その旅をたどります。何がうまくいき、何が元に戻され、そしてパーサーベンチマークの勝利をアプリケーションの勝利に変えるために何が必要だったかです。 Tree-sitterの解析アーキテクチャ Tree-sitterはソースコードを受け取り、構文ツリーを生成します。サポートされている各言語は、Tree-sitterが生成された解析テーブルとレキサーコードにコンパイルする文法定義から始まります。このシリーズで「生成言語」、「生成文法」、「生成テーブル」という場合、それらの成果物を指します。実行時には、レキサーが文字を識別子、+、数値などのトークンに変換します。次に、パーサーは生成されたテーブルとスタックを使用して、各トークンが何を意味するかを決定します。 ほとんどの場合、テーブルは2つの操作のいずれかを要求します。 シフト: トークンを消費し、パーサースタックにプッシュします。 リデュース: いくつかの構文ピースがより大きな文法ルールを形成することを認識し、それらを1つの親に置き換えて続行します。 すべてのテーブルエントリに1つの有効な回答があれば、パーサーは1つのスタックで1つの履歴をたどることができます。これは通常のLRケースです。プログラミング言語の文法は、追加の入力がどちらの解釈が生き残るかを明らかにするまで、複数のアクションが有効になる可能性があるという、真の競合を時折持つことがあります。 したがって、Tree-sitterは汎用LR（GLR）を使用します。共通の過去をグラフ構造のスタックで共有しながら、複数の履歴を同時にたどることができます。一時的に分岐し、再び合流する1本の道路を考えてください。文法が曖昧な場合、グラフが必要です。パーサーがまっすぐな道路のためにグラフ機構を構築する場合、それはかなり魅力的ではありません。 もう1つの中心的なオブジェクトはサブツリーです。シフトされたトークンはリーフになり、リデュースは子を内部構文ノードに結合します。これらの値は、解析中に作成され、スタック履歴全体で共有され、最終ツリーとして公開され、ast-grepによってトラバースされ、最終的に解放されます。それらの誕生のみを最適化し、その生涯の残りを無視すると、後にかなり高価な教訓を生むことになります。 概要については、これで十分なパーサー理論です。 最初のステップ: Cの動作をRustで維持する 最初の目標は、エレガンスではありませんでした。それはパリティでした。 書き換え契約は意図的に保守的でした。 既存のテストを動作のオラクルとして使用します。もっともらしいRust実装では不十分でした。同じツリー、リカバリ動作、ナビゲーション結果、および公開APIの効果を生成する必要がありました。 手書きの例だけでなく、エコシステムをテストします。既存の生成された文法と外部スキャナーは、再生成やソースコードの変更なしで動作し続ける必要がありました。 バイナリインターフェース（ABI）を維持します。生成された言語テーブル、公開C関数、レイアウト、シンボル、および呼び出し規約は、それらの背後にある実装が言語を変更しても互換性を維持しました。 再設計する前に翻訳します。最初のRustバージョンは意図的にCの制御フローに似ていたため、パリティの失敗は限定された検索領域を持っていました。 一言で言えば、エコシステムが観察できるすべてを維持し、その後、内部を交換可能にします。 ChatGPTに、ランタイムを一度に1つの部分（基本的なユーティリティ、ツリーストレージ、レキシング、パーサースタック、ツリーナビゲーション、そして最後にパーサーループ）ずつ翻訳するように指示しました。エージェントはCとRustコードを読み、パッチを作成し、コンパイラエラーを修正し、テストを実行し、不一致を調査しました。私が目標、制約、異議、および決定を提供しました。既存の実装とテストスイートが解答集を提供しました。 この区別は重要です。私は個人的に英雄的なRustポートを入力してから、AIにコメントを磨くように頼んだわけではありません。実装、プロファイリング、インストルメンテーション、および実験コードの多くは、私の指示の下でエージェントによって生成されました。AIなしでは、このプロジェクトは私が時々話題にしてから賢明に話題を変えるというアイデアのままだったでしょう。 CコアはRustになっていました。コンパイルされました。テストに合格しました。既存の文法はそれを使用できました。これはすでに達成されたことでした。