Tree-sitter の Rust 化と ast-grep パフォーマンス向上の物語（パート 4）

ast-grep は AI の支援により、Tree-sitter の C コアを Rust に書き換えるという大冒険を成功させました。この移行により、パーシング速度、ツリー読み込み速度、そして ast-grep 自体の動作速度がすべて向上しています。

パフォーマンス改善の概要

今回の変更による具体的な数値成果は以下の通りです（※「30%」はパーサー単体の数値、「22%」はエンドツーエンドでの数値）：

ベンチマーク結果比較表

ベンチマーク項目	C / normal (基準)	Rust (新コア)	差額
生パーシング (Raw Parsing)	スループット: 100 RSS: 8.48–21.41 MiB	スループット: 129.74 RSS: 8.42–25.70 MiB	スループット +29.7% RSS 上限 +20.0%
ツリー遍歴	スループット: 100 RSS: 20.38 MiB	スループット: 110.16 RSS: 22.20 MiB	スループット +10.2% RSS +8.9%
ast-grep の概要抽出 (Outline Extraction)	ユーザー CPU: 1.233 s RSS: 26.52 MiB	ユーザー CPU: 0.960 s RSS: 34.43 MiB	ユーザー CPU −22.2% RSS +29.8%

主要な発見

• 勝利: Rust バージョンはすべてのパーサーおよび遍歴テストケースで勝利し、生成されるツリーも完全にはじめと同じものでした。
• メモリトレードオフ: 実行時のメモリ使用量は約 8 MiB 増えました（ピークメモリ使用量については後述）。
• 大規模負荷への耐性: TypeScript コパイラーリポジトリを使ったストレステストでは、初期段階で記録されていた 1 GiB を超えるピークメモリ使用量が大幅に抑制され、91.2 MiB まで削減されました。これは敗北ではなく快挙です。

機能の境界線（Trade-off）

今回の Rust コアはアップストリームの Tree-sitter の 1:1 代替品ではありません。AI コーディングエージェント向けの狭い範囲のランタイムとして設計されています：

• ✅ 互換性の維持: 既存の生成された言語とパーサーテーブルはそのまま利用可能です。
• ❌ 機能の廃止:
  • WebAssembly にコンパイルされた言語のネイティブ読み込み
  • 旧ツリーの一部を利用するインクリメンタルパーシング（incremental old-tree reuse）
• ⚠️ 残存するコード: 互換性のために、より多くの生ポインターと

  unsafe

  ブロックが残っています。

結論: 文法エコシステムがエージェント型コーディングに有用性を保ちつつ、編集器固有の機構（インクリメンタルパーシングなど）は排除されました。

---

なぜ Tree-sitter を書き換えたのか？

パフォーマンスのボトルネック

ast-grep は構文ツリー化を行いますが、その作業を担う Tree-sitter が天井（ボトルネック） となっていました。パーサーの高速化こそが真の最適化ポイントです。

なぜ今、AI 支援で書き換えか？

• 過去の試み: C コアからの脱却は一人では不可能な「ヘーグルスの仕事」でしたが、Bun や pgrust などの成功事例により、AI を活用すれば実現可能であることが示されました。
• アプローチ: ChatGPT に指示し、まずは互換性を最優先に C コアを Rust に翻訳させました。その後、高速化と最適化を試みました。

最初の失敗：「バイブコーディング」の限界

純粋な「もっと高速に」という指令だけでコードを書かせると、意図せぬ AI 生成の最適化層が積み重なり、セグメンテーションフォールト（segfault） を引き起こしました。

• 結果：20% の性能向上は幻でした。
• 教訓：AI に「システムを説明可能に」させ、「山盛り（pile）のコードで高速化」するよう求めるのを止めました。

---

開発プロセスと最適化のポイント

ステップ 1: 同等性の確保

まずは C コアの動作を完全に再現することを目指しました。

• 契約: 既存のテストを正解基準（オーラクル）とし、API やバイナリインターフェース（ABI）は変更しない。
• 手法: ChatGPT に基本ユーティリティから順に翻訳させ、AI がパッチ適用やコンパイラエラー修正を行った。

ステップ 2: スコープの縮小と可読性の向上

「機能保存」から「必要最小限の実装」へ方針を転換しました。

• インクリメンタルパーシングの削除: アジャストメントツール（ast-grep）はファイルスナップショット全体を処理するため、旧ツリーの再利用は不要です。この機構を除去。
• Wasm 読み込みの廃止: ブラウザ向けとは異なり、ランタイム内での Wasm コンパイルされた文法の読み込みは必要ありませんでした。
• コードの整理: C 風のポインタ操作や

  unsafe

  ブロックを、Rust の標準的な所有権モデル（参照、スライス、Option など）に変換し、メモリーセーフ性を向上。

ステップ 3: GLR アルゴリズムとメモリレイアウトの最適化

ランタイムが理解できるようになった後、ChatGPT に GLR（グラフ構造スタック）の挙動を改善させました。

• 非通常ケースの回避: パーサーは 99% の場合直線的に動作するため、不要なグラフ構築コストを削減。
• 安価なアロケーション: 一般的なアロケーターではなく、成長するブロック（アリーナ）を使用。
• 単一アクション処理: 複雑なルックアップを事前に準備し、単純なケースへのショートカット経路を確保。

メモリー管理の劇的変化

初期のアリーナ設計は「予約だけを行い実際の解放を先送り」する方式でしたが、これによりファイルごとに数千回にわたり仮想メモリの予約・解放が繰り返され、CPU レジスタスが引き起こされていました。

• 修正: アリーナ戦略を変更し、必要な時だけの適切なアロケーションへ置換。
• 結果: ページフォールトの激減と、ストレステストでのメモリ使用量を 1.04 GiB → 91.2 MiB に抑制することに成功。

ステップ 4: ツリーリーダーの最適化

生成されたツリーを遍歴する際も効率化を行いました。

• 問題: 緊密なインデックスを持つツリーを読み取る際、反復的な検索がボトルネックとなっていた。
• 解決: ChatGPT に「各子グループを一度で検索し直す」ようなリーダー実装へ書き換えさせ、コストを取り戻した。

---

エンドツーエンドパフォーマンスの検証

測定項目	C / normal	Rust (最終版)	改善率
概要抽出実行時間 (opencode リポジトリ使用)	1.233 s	0.960 s	-22.2%

重要な視点: パーサー単体で 30% 高速化しても、アプリケーション全体が遅くなる原因は「パーシング速度」だけではありません。

• メモリの予約解放による CPU レジスタス
• ツリー遍歴における反復検索コスト

これらの要因を全て修正し、初めてエンドツーエンドでの 22% の高速化が実現しました。

AI 支援による書き換えから学んだ教訓

1. 役割の明確化

• 初期:

  パフォーマンスを向上させる

  → 無意味なコード生成と崩壊。
• 最終:

  この機構の問題点を説明し、なぜこれが起こるか

  → 具体的な改善点へ。
• 結論: AI は「万能神」ではなく、高速化するための実装空間を探るパートナーです。人間がプロファイルやテスト結果を分析し、適切な問いかけを行うことが不可欠です。

2. プロセスの進化

【失敗パターン】
目標: パフォーマンス向上
↓ (AI にコード生成)
多くの合理的なコードが生成される
↓
ベンチマーク結果が悪化する（混乱）
↓ (追加のパッチ)
さらに不合理なコードが蓄積

【成功パターン】
expensive work を特定
↓
なぜそれが遅いのかを説明させる
↓
一つの機構のみを変更してテスト
↓
完全なアプリケーションでの検証
↓
維持・修正・拒否の判断

次のステップ（パート 2-4 のまとめ）

この物語にはまだ続きがあります：

• 移行と互換性: 互換性の境界線をどのように守ったか。
• GLR アルゴリズムの詳細: グラフ構造を直線動作に変える仕組み。
• 最適化の積み重ね: メモリートレースやベンチマークルールに基づく追加チューニング。

結論: AI は私に「荷重を持つ壁」を動かす機会を与えました。残りの課題は、その壁を支えていた他の全ての要因を見つけ出し、一つずつ克服していくことにあります。