HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

How AST-grep Rewrote Tree-sitter in Rust and Made It 30% Faster (astgrep.com)

72 pointsby herrington_d11 コメント

要約

コード検索ツールast-grepは、構文解析フレームワークTree-sitterのC言語コアをRustで書き換えました。AIの支援を受けて行われたこの書き換えにより、解析速度が30%、ast-grep自体の実行速度が約22%向上しました。メモリ使用量は若干増加しましたが、以前のバージョンと比較して大幅に削減されており、AIコーディングエージェント向けの効率的なランタイムが実現しました。

全文翻訳

AST-grepがTree-sitterをRustで書き直し、30%高速化した方法

全4部作 — 冒険の全貌

ast-grepはTree-sitterのC言語コアをRustで書き換えました。コードはAIが作成しました。新しいコアは、解析が速く、完成したツリーの読み取りが速く、ast-grep自体も高速です。(タイトルの「30%」はパーサーのみの数値です。エンドツーエンドでは、ast-grepは約22%高速に動作します。)

ソースリポジトリ: HerringtonDarkholme/tree-sitter。

数値に入る前に、簡単な紹介を2つ。ast-grep — このブログが属する構造的なコード検索ツール — は、テキストではなく構文によってコードを検索するため、処理するすべてのファイルはまず構文ツリーになる必要があります。Tree-sitterはそのツリーを構築するパーサーフレームワークです。文法定義を与えると、その言語用の高速パーサーを生成します。エディタの世界で生まれ、現在では膨大な数の文法とツールのエコシステムを支えています。

[画像: RustコアランタイムパフォーマンスとC言語との比較]

パフォーマンスとピークRSS。 スループットは正規化されており、変更されていないCビルド(「C / normal」)は100を記録します。数値が高いほど良いです。RSSはピーク時の常駐メモリ量で、生の解析行はベンチマークの言語フィクスチャによって異なるため、範囲として示されています。アウトライン行はast-grepの実際のワークロードです。リポジトリ内のすべてのファイルを解析し、完了した各ツリーをウォークして構造的なアウトラインを抽出します。

ベンチマークC / normalRust差
生の解析スループット: 100 RSS: 8.48–21.41 MiBスループット: 129.74 RSS: 8.42–25.70 MiBスループット+29.74% RSS上限+20.0%
ツリー走査スループット: 100 RSS: 20.38 MiBスループット: 110.16 RSS: 22.20 MiBスループット+10.16% RSS+8.9%
完全なast-grepアウトラインユーザーCPU: 1.233 s RSS: 26.52 MiBユーザーCPU: 0.960 s RSS: 34.43 MiBユーザーCPU-22.2% RSS+29.8%

Rustはすべてのパーサーと走査フィクスチャで勝利し、ast-grepは全く同じアウトラインを生成しました。メモリがトレードオフです。Rustビルドはast-grepの実行で約8 MiB多く使用します。はるかに大きなTypeScriptストレステストコーパス(TypeScriptコンパイラリポジトリのtest-baselineツリー、このプロジェクトのメモリ負荷テスト)では、ピーク時に91.2 MiBに達します。この数値は、告白ではなく勝利です。プロジェクトの初期段階では、同じコーパスが1 GiBを超えていました。

この結果は、アップストリームのTree-sitterの1対1の置き換えではありません。これは、完全なファイルスナップショットを分析するAIコーディングエージェントのために構築された、より狭いランタイムです。

  • 既存の生成言語とパーサーは互換性を保ちます。
  • WebAssemblyコンパイル言語のネイティブロードとインクリメンタルな古いツリーの再利用は削除されました。
  • 互換性を保つためには、多くの生のポインタとunsafeブロックが必要です。

この境界線により、エージェントコーディングにとって文法エコシステムは有用なままであり、ターゲットワークロードが不要とするエディタ固有の機構は削除されました。

これが結末です。そこに至るまでの道のりは別の話です。

Tree-sitterの書き換えはなぜか? ​

真剣なast-grepのパフォーマンス調査は、必ず同じ場所にたどり着きました:Tree-sitter。

ast-grepはルールをより速くすることができました。作業を削減し、設定をキャッシュし、無関係な構文の訪問を避けることができました。しかし、すべてのファイルはまず構文ツリーになる必要があり、Tree-sitterがそのツリーを構築していました。パーサーは基盤であり、そしてますます、天井でもありました。

長年、それを書き直すか深く最適化することを夢見ていました。その夢は、ランタイムを開くまで続くことがほとんどでした。成熟したC実装、バイナリ互換性、外部スキャナー、エラーリカバリ、インクリメンタル解析、曖昧な文法、いくつかの言語バインディング、そしてそれの上に構築された膨大な文法エコシステムを壊さないという小さな問題がありました。

一人でできるプロジェクトではありませんでした。それはヘッダーファイルに包まれたヘラクレスの仕事でした。

だから何も起こりませんでした。

それから、AI支援による書き換えの試みが everywhere — Bun、pgrust、そしてRoc — で現れ始めました。それらはTree-sitterを書き換えることが賢明だと証明したわけでも、ランタイムを小さくしたわけでも、パーサー理論をそれほど奇妙でなくしたわけでもありません。それらは、実験が一人で試すには十分安価になり、十年が終わる前に不合理な質問をして答えを得るための十分なてこを提供してくれたことを示しました。

そこでChatGPTにTree-sitterのCコアをRustで書き直すように指示しました。プロジェクトは、互換性優先の翻訳、高速だが読みにくい最適化の試み、よりシンプルなランタイムと実際のパーサーの利点へと進みましたが、高速なパーサーでもast-grepを遅くすることがあると判明しました。

この投稿の残りは、その旅を追います。何がうまくいったのか、何が元に戻されなければならなかったのか、そしてパーサーベンチマークの勝利をアプリケーションの勝利に変えるために何が必要だったのか。

Tree-sitterの解析アーキテクチャ ​

Tree-sitterはソースコードを受け取り、構文ツリーを生成します。サポートされている各言語は、Tree-sitterが生成された解析テーブルとレキサーコードにコンパイルする文法定義として始まります。このシリーズで「生成された言語」、「生成された文法」、または「生成されたテーブル」と言う場合、それらの成果物を指します。実行時には、レキサーが文字をidentifier、+、numberなどのトークンに変換します。次にパーサーは、生成されたテーブルとスタックを使用して、各トークンが何を意味するかを決定します。

ほとんどの場合、テーブルは2つの操作のいずれかを要求します。

  • shift: トークンを消費し、パーサースタックにプッシュします。
  • reduce: いくつかの構文ピースがより大きな文法ルールを形成することを認識し、それらを1つの親に置き換え、続行します。

すべてのテーブルエントリに1つの有効な回答があれば、パーサーは1つのスタックで1つの履歴をたどることができます。それが通常のLRケースです。プログラミング言語の文法は、追加の入力によってどの解釈が生き残るかが明らかになるまで、複数のアクションが有効なままになるという、時折本物の競合を抱えています。

したがって、Tree-sitterは一般化LR (GLR)を使用します。グラフ構造のスタックで共通の過去を共有しながら、複数の履歴を同時にたどることができます。一度分岐してから再び合流する1本の道路を想像してください。文法が曖昧な場合にグラフが必要です。パーサーがまっすぐな道路のためにグラフ機構を構築する場合は、かなり魅力的ではありません。

もう一つの中心的なオブジェクトはサブツリーです。シフトされたトークンはリーフになり、リダクションは子を組み合わせて内部構文ノードを作成します。これらの値は、解析中に作成され、スタック履歴間で共有され、最終ツリーとして公開され、ast-grepによって走査され、最終的に解放されます。それらの誕生のみを最適化し、その生涯の残りを無視することは、後にかなり高価な教訓を生むことになります。

概要としては、これでパーサー理論は十分です。

最初の一歩:RustでCの動作を維持する ​

最初の目標はエレガントさではありませんでした。それは同等性でした。

書き換え契約は意図的に保守的でした。

  • 既存のテストを動作のオラクルとして使用します。 もっともらしいRust実装だけでは不十分でした。同じツリー、リカバリ動作、ナビゲーション結果、および公開APIの効果を生成する必要がありました。
  • 手書きの例だけでなく、エコシステムをテストします。 既存の生成された文法と外部スキャナーは、再生成やソースコードの変更なしに動作し続ける必要がありました。
  • バイナリインターフェース(ABI)を維持します。 生成された言語テーブル、公開C関数、レイアウト、シンボル、および呼び出し規約は、それらの背後にある実装が言語を変更しても互換性を保ちました。
  • 再設計する前に翻訳します。 最初のRustバージョンは意図的にCの制御フローに似せていたため、同等性の失敗は限定された検索範囲を持っていました。

一言で言えば、エコシステムが観測できるすべてを維持し、内部を交換可能にします。

ChatGPTにランタイムを一度に1つの部分ずつ翻訳するように指示しました。基本的なユーティリティ、ツリーストレージ、レキシング、パーサースタック、ツリーナビゲーション、そして最後にパーサーループです。エージェントはCとRustのコードを読み、パッチを作成し、コンパイラエラーを修正し、テストを実行し、不一致を調査しました。私が目標、制約、異議、決定を提供しました。既存の実装とテストスイートが解答を提供しました。

この区別は重要です。私は個人的に英雄的なRustポートを入力してから、AIにコメントの清書を依頼したわけではありません。実装、プロファイリング、インストルメンテーション、そして実験コードの多くは、私の指示の下でエージェントによって生成されました。AIなしでは、このプロジェクトは私が時々話題にして、賢明に話題を変える前に言及したアイデアのままでした。

CコアはRustになりました。コンパイルできました。テストに合格しました。既存の文法はそれを使用できました。これはすでに、プロジェクトが棚上げされていたときに不可能に見えた結果でした。

当然、私はすぐにさらに多くを求めました。

最初の最適化試行が失敗した理由 ​

リクエストは純粋なバイブコーディングでした — /goalコマンドに1行入力しました。その背後のプロセスはそれよりも慎重でした。プロファイリングツールを適切に使用し、ランタイムのデータレイアウトと所有権を理解し、個々の命令を磨くだけでなくアルゴリズムの変更を探すようにChatGPTに指示しました。ベンチマークは要求されたラインを正しく越えました。それからコードを開きましたが、追うことができませんでした。機械的なCからRustへの翻訳の上に、重なり合うAI生成の最適化のレイヤーが積み重なり、パーサーはセグメンテーション違反を起こし始めました。フレンドリーなRustのパニックも、アサーションの失敗もなく、プロセスは単に終了しました。20%速いが時々消えるパーサーは最適化ではありません。それはジャンプスケア付きのベンチマークです。

私は最適化作業を完全に元に戻しました。20%も一緒に消え、プロジェクトが最終的に達成したパフォーマンスは、以下に説明するクリーンでレイヤードな作業から後で来ました。パート2はこの話を完全にカバーしています。ここで重要なのは、それがプロジェクトをどのように逆転させたかです。ChatGPTに山を速くするように依頼するのをやめ、システムを説明可能にするように依頼し始めました。

第二段階:スコープを縮小し、可読性を向上させる ​

クリーンアップには2つの部分がありました。

  1. ターゲット製品の外部にある機能と表現を削除する。
  2. 保持されたCスタイルのRustを、所有権と制御フローをローカルで推論できるコードに変換する。

どちらのステップも英雄的なベンチマークを約束しませんでした。どちらも次のステップを信頼するための前提条件でした。

ターゲットランタイムからインクリメンタル解析を削除する ​

当初、「Tree-sitterを書き直す」とは、すべての機能を維持することを意味していました。次に、ターゲットワークロードはより良い質問を強制しました。誰のためにそれを維持するのか?

アップストリームのTree-sitterはエディタ内で非常に役立ちます。人間が1文字挿入し、2文字削除し、次のフレームの前にハイライトが更新されることを期待します。インクリメンタル解析により、ランタイムは古いツリーを再利用し、影響を受けた領域のみを再構築できます。その世界では、キーストロークごとにファイル全体を再解析するのは無駄な作業です。

このブランチの世界ではありませんでした。ast-grepと私が気にかけていたAIコーディングエージェントツールは、完全なファイルスナップショットで動作します。エージェントはファイルを読み、分析または書き直し、ツールに新しいスナップショットを処理するように依頼します。エディタが所有する構文ツリーがキーストロークごとに進むわけではありません。新しい解析は、劣化したフォールバックではなく、通常の操作です。

そこで、インクリメンタルな古いツリーの再利用を削除することを決定し、ChatGPTにそれを実行するように指示しました。互換性のために公開パラメータは残っていますが、このランタイムは新しく解析します。古いツリーの断片を見つけて再利用するための機構 — そしてそれは驚くほど多くのコア構造にまで及びました — はホットな実装から削除されました。パート2は、正確に何がなくなったかをリストアップしています。

2番目の独立したスコープカットがそれに沿って進みました。ネイティブWasmコンパイル文法のロードです。Tree-sitterは文法をWebAssemblyにコンパイルし、実行時にロードできます — ブラウザのWasmビルドとは異なる機能で、それは残りました。ネイティブツールがこのプロジェクトのパフォーマンスターゲットを設定し、実行時のWasm文法ロードはそのワークロードの一部ではありませんでした。

これは、アップストリームのTree-sitterがインクリメンタル解析を放棄すべきだという提案ではありません。これは、ファイルごとの分析とエージェントツールを対象とした、より狭いランタイムの製品決定です。このブランチがインタラクティブなエディタ使用に戻る場合は、決定を再開する必要があります。それがルールでした。機能が単に不便だったから削除するのではなく、宣言された境界線の後ろでのみ削除します。

削除は、最初の実際の最適化手法であることが判明しました。ユースケースがすでに終わっている作業を削除することです。

保留されたランタイムを保守性のためにリファクタリングする ​

行ごとの翻訳は、読者が元の行をすでに知っている場合にのみ読みやすいです。ChatGPTに、モノリシックでポインタが多いポートを、より慣用的な内部Rustに分割するように指示しました — ABIに直面する型を既存の文法を壊すような方法で「慣用的」にすることなく。

クリーンアップは再設計というよりは、一連の小さな昇格でした。内部の生のポインタパラメータは、そのライフタイムがローカルで証明可能であれば、参照またはスライスになりました。「ノードなし」を意味するセンチネルポインタは、正直なOptionになりました。アウトパラメータは、C ABIがそれらを要求しない場合は戻り値になり、大きなモジュールは責任によって分割され、変更がその状態の近くに配置され、残さなければならなかった密集したトリック(ツリーへのコンパクトなインデックス、ポインタ演算)は、狭く名前付きの操作の後ろに隠されました。互換性が現実であった場所では、コードは意図的に醜いままでした。生成された言語のレイアウトとエクスポートされた関数はCの形状を保ちました。別のバイナリがすでにその形状にコミットしていたからです。

そのクリーンアップにより、質問に答えられるようになりました。このツリーの一部は誰が所有していますか?ストレージが増加したときにこの参照は存続できますか?なぜ1つのリダクションが一時的なパーサー状態を作成してすぐに削除するのですか?

重要な出力は、よりきれいな構文ではありませんでした。それは、セグメンテーション違反、不変条件の失敗、または疑わしい割り当てがアーキテクチャ上のアドレスを持っていた、十分に整理されたランタイムでした。

GLRとメモリレイアウトの最適化 ​

ランタイムを理解できるようになると、リダクション、つまり上記のアーキテクチャセクションの「reduce」、パーサーが常に実行する操作にChatGPTを再び指示しました。

その小さな操作は、2つの主要なデータ構造に触れます。パーサーのワーキングスタックから子を削除し、次にそれらを新しい親の下に構文ツリーに格納します。プロファイルは、Tree-sitterが通常のケースで必要とされるよりも、それらの子に関するはるかに多くの作業を行っていることを示しました。

成功した変更は、最終的に4つの単純な原則に分類されました。

  • まれなケースの作業を避ける。 観測されたパーサースタックの約99%は1本のまっすぐなパスだったので、入力が実際に分岐するまでパーサーはグラフを構築しなくなりました。編集に主に必要な作業も、可能な限り新しい解析から除外されます。
  • 割り当てを安価にし、インデックスを小さくする。 各内部構文ノードのために汎用アロケータに要求することは高価です。アリーナは成長するブロックを取得し、そこから多くのノードを提供します。別途、コンパクトなインデックスは、パーサースタックとツリー間で移動するバイト数を削減します。
  • 繰り返しの作業を一度だけ行う。 パーサーは一般的な文法ルックアップを事前に準備し、ツリーリーダーは同じ子を繰り返しルックアップすることを避けます。
  • 最も単純なケースに短いパスを与える。 1つのパーサーアクションは直接処理され、通常のASCII入力は完全な文字デコードパスを回避します。単純なパスが適用されない場合はいつでも、完全なフォールバックが利用可能です。

text

通常の解析:1つのスタックパスを維持
実際の曖昧さ:フルグラフに切り替え

99%という数字は問題を説明しましたが、解決策ではありませんでした。一般化パーサーに関する学術研究をレビューするようにChatGPT(今回はコーディングモードではなくリサーチモード)に指示したところ、古い教訓が示されました。入力が実際に必要になるまで一般的な構造を構築しないことです。アリーナは別のアイデアであり、独自の実験が必要でした。線形スタックはグラフのブックキーピングを回避し、アリーナは汎用アロケータへの呼び出しを削減しました。インデックスを小さくすることは、さらに別のレイアウトの選択であり、自動的に高速にはなりませんでした。いくつかのバージョンは、ピースが元を取る前に失われました。

重要な結果:通常の解析は、まれな曖昧さと各内部構文ノードの個別の割り当ての完全なコストを支払うことをやめました。

一瞬、パーサーベンチマークは素晴らしく見えました。

それからChatGPTに、それに対してast-grepをビルドするように依頼しました。

エンドツーエンドのパフォーマンス結果 ​

エージェントはそのバイナリをopencode、実際のTypeScriptリポジトリで実行しました。その時点で、パーサーのみのベンチマークでは、このRust実装はCランタイムより約30%高速でした。

アプリケーションは遅くなりました。

パーサーが30%速くなったのに、アプリケーションが遅くなったのはなぜでしょうか?

パーサーベンチマークは1つのパーサーを再利用していました。ast-grepは数千のファイルのパーサーを作成し、完了した各ツリーをウォークしてアウトラインを抽出しました。ベンチマークは、その旅の途中部分のみを測定していました。

最初のアリーナは、パーサーが作成されるたびに巨大な仮想メモリ領域を予約しました。物理メモリ全体をすぐに消費しなかったため、設計は無害に見えました。しかし、リポジトリ全体で、その予約は何千回も発生し、それぞれに実際の作業が必要でした。新しいラウンドの予約と解放のシステムコール、それに伴うページフォールトとページテーブルのチャーンが、ファイルごとに繰り返されました。そのチャーン — 解析ではなく — がopencodeコーパスでのCPUの低下でした。ChatGPTに、その予約を、必要になるまで成長する通常の小さな割り当てに置き換えるように指示しました。

それは1つの問題を解決し、別の問題(メモリ)を露呈しました。別のTypeScriptストレステストコーパスでは、1つのast-grepワーカー全体で測定したところ、アリーナの初期成長戦略は古いブロックを保持し続け、ピークメモリを1.04 GiBに押し上げました。そこから最終的な91.2 MiBに至るまでには、アリーナの数回の手術が必要でした — メモリを回収するようにChatGPTに指示し続けたにもかかわらず、実際には無駄にされていたメモリではなかったというひねりもありました。パート4にはトレースと犯人がいます。ここではネタバレはしません。

完成したツリーには、もう1つの驚きがありました。コンパクトなインデックスは構築中に役立ちましたが、ast-grepはそれを読み取る際にルックアップする必要がありました。一部のパーサー時間は、ツリー走査に移動しただけでした。ChatGPTはツリーリーダーを変更して、各子グループを繰り返しではなく一度だけルックアップするようにし、そのコストを回収しました。

それらの修理 — パーサーごとの仮想メモリの儀式ではなく通常の割り当て、そして各子グループを一度解決するツリーリーダー — は、低下を解消しました。そして、その後のパーサー側のチューニングラウンドと合わせて、この投稿の冒頭の数値になりました。アウトライン実行は、CビルドよりもユーザーCPUで22.2%少なく終了しました。エンドツーエンドの失敗は、パーサー作業を無効にするものではありませんでした。それは「作業した」の古い意味を無効にしました。それ以降、パフォーマンス結果は、解析、メモリ、ツリーの読み取り、および完全なアプリケーションライフサイクルをカバーする必要がありました。

これらの結果の背後には、単一の魔法のパッチはありませんでした。一部の変更はパーサー時間を節約し、一部はメモリ災害を防ぎ、他の変更は完了したツリーを読み取る間に時間を回収しました。この概要は、個々の実験を接続する原則を維持しています。詳細な投稿はそれらを分解します。

AI支援による書き換えからの教訓 ​

当初、AIは単一の命令で実行できるコードの量を増やしました。それは書き換えを可能にするには十分でしたが、それを良くするには全く不十分でした。

初期のループは次のようになりました。

text

/goal 20%のパフォーマンス向上
        -> 多くのもっともらしいコード
        -> 混乱したベンチマーク
        -> もう1つのもっともらしいパッチ

後に次のようになりました。

text

高価な作業を見つける
        -> なぜそれが起こるのか説明する
        -> 1つのメカニズムを変更する
        -> 前のRustリビジョンと比較する
        -> 完全なアプリケーションをテストする
        -> 保留、修正、または却下する

ChatGPTは徐々に無謬になったわけではありません。私はランタイムについて十分に学び、より狭い問題を与え、バンドルされた仮定に異議を唱え、正しい境界で証拠を要求するようになりました。セグメンテーション違反を起こした初期のスピードアップ、アリーナのメモリ爆発、そして遅くなったアプリケーションはすべて、もっともらしく見えるコードと励みになるローカル結果の背後に現れました。プロファイルとテストは、私たち両方が見逃したものを捉える必要がありました。

最終的に、コラボレーションは適切な分業を見つけました。ChatGPTは、私が手作業では決して追いつけないペースで実装空間を探索できました。私の仕事は、プロファイル、不変条件、およびエンドツーエンドの制御がそれに答えることができるまで、質問を狭め続けることでした。スピードが遠征を可能にし、証拠がどの部分が戻ってくるかを決定しました。

それが冒険のすべてです。残りの投稿はそれを遅くします。

  1. Tree-sitterのCコアをRustで書き直す:移行と互換性は、移行自体、/goal実行とその元に戻し、このブランチが削除したもの、そして互換性境界がどのように生き残ったかをカバーしています。
  2. Tree-sitterのGLRアルゴリズムとメモリレイアウトの改善は、パーサーがほとんど常に線形なワークロードのためにグラフを構築した理由を説明し、次に「アリーナを使用する」に隠された多くの決定を追跡します。
  3. Tree-sitterのエンドツーエンドast-grepパフォーマンスの最適化には、メモリトレース、走査調査、ベンチマークルール、そしてアプリケーションプロファイルによって推進されたパーサー側のさらなるチューニングラウンド(ルックアップインデックス、シングルアクションディスパッチ)が含まれています。

短いバージョンは、AIが私に負荷のかかる壁を動かす機会を与えたということです。プロジェクトの残りは、その壁が支えていた他のすべてを、一度に1つのベンチマークで発見することでした。