Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

はじめに — 「速い」だけでは足りない
正規表現エンジン — バックトラックを捨てる
SIMD memchr — バイトを一度に複数個
並列ディレクトリ走査 — コアを遊ばせない
.gitignoreの尊重 — 読まないのが最速
スマートケース — 人の意図を推論する
バイナリファイルのスキップ — 無駄なデータを避ける
mmap — ファイルを丸ごとメモリにマッピング
ピースを合わせると — パイプライン全体像
速いツールを作る教訓
おわりに
参考資料

はじめに — 「速い」だけでは足りない

ripgrep（コマンド名はrg）を初めて使った人の反応はたいてい同じです。「なぜこんなに速いのか」。数十万個のファイルを含むリポジトリで文字列を一つ探すのに、結果がほぼ即座に返ってきます。grep -rやack、git grepに慣れた人にとって、体感速度は別次元です。

よくある誤解は「Rustで書いたから速い」という説明です。言語は脇役にすぎません。Rustで遅いプログラムを書くこともいくらでもできます。ripgrepの速さは単一の秘策ではなく、正規表現エンジンの選択からファイルシステム走査の戦略、バイト単位の最適化まで、数十の判断が幾重にも積み重なった結果です。この記事はその判断を一つずつ解きほぐし、速いコマンドラインツールが実際に何を違えているのかを見ていきます。

正規表現エンジン — バックトラックを捨てる

ripgrepの心臓は、Rustで書かれたregexクレートです。そしてこのエンジンの最も重要な設計選択は、バックトラックをしないということです。

Perl、Python、PCRE系の伝統的な正規表現エンジンのほとんどはバックトラック方式です。この方式は強力で、後方参照（backreference）やルックアラウンドといった表現力の高い機能をサポートします。しかし代償があります。あるパターンは入力長に対して指数時間で爆発します。いわゆる「壊滅的バックトラック（catastrophic backtracking）」です。(a+)+$のようなパターンに適当な入力を与えると、CPUが数秒、数分と張り付きます。これはReDoS（正規表現サービス拒否）攻撃の原理でもあります。

ripgrepのエンジンは別の道を行きます。正規表現を**有限オートマトン（finite automata）にコンパイルします。理論的に言えば、後方参照のない正規表現は有限オートマトンで表現でき、有限オートマトンは入力をちょうど一度、文字ごとに定数時間で走査してマッチの可否を判定します。つまり入力長に対して線形（linear）**です。最悪の場合でも爆発しません。

二つの方式の違いを整理するとこうなります。

区分	バックトラックエンジン	有限オートマトンエンジン
代表例	PCRE、Perl、Python `re`	RE2、Rust `regex`
最悪時間計算量	指数（爆発しうる）	線形（入力長に比例）
後方参照/ルックアラウンド	サポート	非サポート（意図的に排除）
ReDoS脆弱性	あり	なし

ここで核心はトレードオフです。ripgrepは後方参照などの一部機能をあえて捨てました。その代わりに、どんな入力でも爆発しない線形性能の保証を得ました。検索ツールにとってこれは正しい選択です。ユーザーがうっかり投げたパターン一つがツールを止めてしまってはいけないからです。

内部的にこのエンジンは一つのオートマトンだけを使うわけではありません。状況に応じて複数の戦略を組み合わせます。短いリテラルは専用のリテラル検索で、複雑なパターンは遅延DFA（lazy DFA）で処理し、パターンの接頭辞から抽出したリテラルで候補位置を素早く絞ります。「正規表現に出会ったら必ずオートマトンを一つ回す」ではなく、「できるだけ安い方法でまず絞り込む」が実際の動作に近いのです。

SIMD memchr — バイトを一度に複数個

正規表現マッチングの前に、より根本的なボトルネックがあります。「この大きなテキストのどこに候補があるのか」を探す作業です。ripgrepはこれをmemchrで解決します。

memchrはその名の通り「メモリから特定のバイトを探す」演算です。素朴に実装するとバイトを一つずつ比較するループです。しかし現代のCPUにはSIMD（Single Instruction, Multiple Data）命令があります。x86のSSE2/AVX2、ARMのNEONといったものです。この命令は一度に16バイト、32バイト、さらには64バイトを同時に比較します。

核心のアイデアはこうです。正規表現であれリテラルであれ、検索したいパターンにはたいてい「必ず登場しなければならないバイト」があります。たとえばfunctionを探すなら、fがない場所にマッチはありません。そこでripgrepはまずSIMD memchrでfが出る位置を超高速で走査して候補を探し、その近くでだけ実際の正規表現マッチングを試みます。ほとんどのテキストは候補ですらないので、高価なマッチングロジックを丸ごとスキップします。

  大きなテキストバッファ
  ├─ (1) SIMD memchrで必須バイトの位置を超高速スキャン
  │       → ほとんどの領域はここで即座に脱落
  ├─ (2) 候補位置の近くでだけ
  │       → 実際の正規表現/リテラルマッチングを実行
  └─ 結果

この「安いフィルタでまず絞り、高価な検査は最小限だけ」戦略は、ripgrep全体を貫く哲学です。memchrはその最初の関門です。ちなみにこのmemchrクレートは非常によく作られていて、Rustエコシステムのあちこちで単独で広く使われています。

並列ディレクトリ走査 — コアを遊ばせない

ファイル一つを速く探すことと、リポジトリ全体を速く探すことは別の問題です。数十万個のファイルを走査するときは、「どれだけ並列に処理するか」が決定的です。

伝統的なgrep -rは基本的に単一スレッドでディレクトリを走査します。一方ripgrepは複数のスレッドを立ち上げ、ディレクトリツリーを並列に走査します。ワーカースレッドが作業キューを共有し、見つけたサブディレクトリをキューに入れ、ファイルが出てきたら検索します。コアが8個あれば8個のファイルを同時に探せます。

ここで微妙ですが重要な設計が出てきます。出力順序です。並列で検索すると、結果がばらばらの順序で出ることがあります。ripgrepは基本的には性能のために順序を保証しませんが、--sort pathのようなオプションを与えると決定論的な順序に整えて出します。つまり並列性と再現性の間の選択権をユーザーに与えます。

並列化はタダではありません。スレッド間の調整コスト、ファイルシステム自体のボトルネック（特にネットワークファイルシステムや遅いディスク）があります。そこでripgrepはワーカー数を論理コア数に合わせて自動調整し、--threadsで直接制御することもできるようにしています。並列化の教訓は「とにかくスレッドをたくさん立てれば速い」ではなく「仕事をバランスよく分け、調整コストを最小化する」ことです。

.gitignoreの尊重 — 読まないのが最速

ripgrepの速さの半分は「速く読む」ことではなく、**「読まない」**ことから来ます。これがripgrepの最も実用的な洞察です。

grep -rは素朴です。命じればnode_modules、.git、ビルド成果物、ログディレクトリまで全部ひっくり返します。肝心のユーザーが探しているソースコードは全体のごく一部なのに、残りの巨大なゴミの山を全部走査するのに時間を使います。

ripgrepは基本的に.gitignoreを尊重します。無視ルールに引っかかったファイルとディレクトリはそもそも読まずにスキップします。実際のプロジェクトで.gitignoreに登録されているもの（依存関係、ビルドキャッシュ、成果物）は、たいていリポジトリ容量の大部分を占めます。それを丸ごとスキップすれば、検索すべきデータ量そのものが劇的に減ります。

ripgrepが参照する無視ルールは何層にもなっています。

.gitignore — 各ディレクトリごとに階層的に適用
.ignore — ripgrepと他のツールが共有する汎用の無視ファイル
.rgignore — ripgrep専用の無視ファイル
グローバルなgitignoreと.git/info/exclude

.gitignoreの文法自体が一筋縄ではいきません。グロブパターン、否定（!）、ディレクトリ限定、階層ごとのオーバーライドまで正確に実装する必要があります。ripgrepはこのルールマッチングを別の、よく最適化されたライブラリで処理します。たとえば以下のような.gitignoreがあれば:

# 依存関係とビルド成果物を検索対象から除外
node_modules/
dist/
*.log
build/

# ただし、このログは追跡する
!important.log

ripgrepはこのルールを正確に解釈し、node_modules/、dist/、build/とすべての*.logをスキップしつつ、important.logだけは検索します。もちろん無視ルールを切って本当にすべてを探したければ、rg -uuuで無視を段階的に解除できます。

この設計には考え方の転換が込められています。grepは「すべてを検索するのが基本、除外が例外」です。ripgrepは「意味のあるソースだけを検索するのが基本、全体検索が例外」です。開発者が実際に望むものにデフォルトを合わせたのです。

スマートケース — 人の意図を推論する

スマートケースは速度よりも使い勝手の最適化ですが、ripgrepの「人が望むものをデフォルトに」という哲学をよく表しています。

ルールは単純です。

検索語がすべて小文字なら → 大文字小文字を区別せず検索（case-insensitive）
検索語に大文字が一つでもあれば → 大文字小文字を正確に区別して検索（case-sensitive）

たとえばrg errorはerror、Error、ERRORをすべて見つけます。小文字だけ打ったので「なんでも見せて」という意図と解釈します。一方rg Errorは正確にErrorだけを見つけます。大文字をわざと打ったので「正確にこの形」を望んでいると解釈します。

この動作は開発者の実際の習慣と驚くほどよく合います。ざっくり探すときは小文字でざっくり打ち、特定のシンボル（MyClass、HTTPError）を探すときは正確に打ちます。その習慣をツールが読み取ります。明示的に強制したければ、-s（大文字小文字を区別）や-i（無視）フラグで上書きできます。

バイナリファイルのスキップ — 無駄なデータを避ける

もう一つの「読まない」最適化です。ripgrepは基本的にバイナリファイルを検知してスキップします。

画像、実行ファイル、圧縮ファイルの中でテキストを正規表現で探すのは、たいてい意味がありません。しかもこうしたバイナリはしばしばサイズが大きいです。それを全部走査すれば時間の無駄なだけでなく、ターミナルに制御文字が溢れて画面が壊れることもあります。

ripgrepの検知方法は実用的です。ファイルの先頭を少し読んでNULバイト（\0）があるかを見ます。テキストファイルには普通NULバイトがなく、バイナリには多いです。NULが見つかればそのファイルはバイナリとみなして処理を止めます。完璧な判別ではありませんが、実戦で非常によく機能する安価なヒューリスティックです。

もちろん必要なら強制できます。rg -a（または--text）はバイナリもテキストのように扱って走査し、--binaryはバイナリでもマッチを報告します。デフォルトが「スキップ」なのは、それが開発者の望む場合が圧倒的に多いからです。

mmap — ファイルを丸ごとメモリにマッピング

ファイルを読む方法にも最適化があります。ripgrepは状況に応じてmmap（メモリマップ）を使います。

一般的なファイル読み込みはread()システムコールでカーネルバッファからユーザー空間バッファへデータをコピーします。一方mmapはファイルをプロセスの仮想アドレス空間に直接マッピングします。すると、ファイルの内容を巨大なバイト配列のように扱え、実際のディスク読み込みはページフォルトを通じて必要なときに遅延して（lazily）起こります。データコピーが一段減るわけです。

mmapが有利なのは主に一つの大きなファイルを検索するときです。マッピングのオーバーヘッドを大きなファイル全体にわたって償却（amortize）できるからです。逆に多数の小さなファイルを検索するときは、ファイルごとにマッピングを作って解放するコストがかえって大きく、一般的なバッファ読み込みのほうが速いです。

そこでripgrepは一つに固執しません。ファイルの数とサイズを見て、mmapと通常の読み込みのうち有利なほうを経験的に選びます。必要なら--mmapや--no-mmapで直接強制することもできます。ここの教訓は「mmapが常に速い」ではなく「状況に合ったI/O戦略を選ぶ」ことです。万能な解はありません。

ピースを合わせると — パイプライン全体像

ここまでの最適化を一つの流れに描くとこうなります。

  rg PATTERN 実行
        │
        ▼
  [1] 並列ワーカーでディレクトリ走査を開始
        │
        ▼
  [2] .gitignore / .ignore ルールで
      読む必要のないパスを丸ごと除外
        │
        ▼
  [3] 残ったファイルごと: バイナリか検査（NULバイト）
        │           バイナリならスキップ
        ▼
  [4] テキストファイル: mmapまたはバッファ読み込みでロード
        │
        ▼
  [5] SIMD memchrで必須バイトの候補位置を超高速スキャン
        │
        ▼
  [6] 候補の近くでだけ有限オートマトン正規表現マッチング
        │
        ▼
      マッチ結果を出力

各段階が次の段階へ渡すデータ量を減らすことに注目してください。.gitignoreがファイル数を減らし、バイナリ検知がさらに減らし、memchrがマッチングを試みる位置を減らします。高価な演算（正規表現マッチング）に到達するころには、処理すべきデータはすでに最小限に絞られています。

速いツールを作る教訓

ripgrepを解きほぐすと、特定のドメインを超えた一般的な性能原則が見えてきます。

最速の作業は、しない作業だ。 .gitignoreの尊重とバイナリのスキップが与えた利得が、精巧なマッチングアルゴリズムが与えた利得より大きいことがよくあります。何を処理しないかをまず設計しましょう。
安いフィルタでまず絞り、高価な検査は最小限だけ。 SIMD memchrで候補を絞ってから正規表現を回します。ほとんどのデータが高価な経路に到達しないようにするのが核心です。
最悪の場合を保証せよ。 有限オートマトンで線形時間を保証した選択は、平均性能より「どんな入力でも爆発しない」を優先した判断です。ツールは最悪の瞬間に信頼を失います。
良いデフォルトはそれ自体が機能だ。 スマートケース、.gitignoreの尊重、バイナリのスキップは、すべて「ユーザーがたいてい望むもの」をデフォルトにしました。設定なしでも正しく動くことが本当の使い勝手です。
一つの戦略に固執するな。 mmap対バッファ読み込みのように、状況に応じて有利なほうを選ぶ適応的な選択が単一の解より優れます。
言語は土台を敷くだけだ。 Rustはゼロコスト抽象化と安全な並列性を与えましたが、速さの本質は上記のアルゴリズム的・構造的な判断にあります。

最後の項目を強調したいです。「Rustで書いたから速い」は半分だけ正しいです。Rustは軽い抽象化と恐れなき並行性という良い土台を与えましたが、ripgrepが速い本当の理由は、読まないものを読まず、高価な仕事を最小限だけ行い、最悪の場合を保証する設計にあります。これらの原則は、コマンドラインツールであれ、Webサーバーであれ、データパイプラインであれ、どこにでも当てはまります。

おわりに

ripgrepの速さは単一の魔法ではなく、抑制の効いた工学の総和です。正規表現エンジンでは表現力を一部あきらめて線形時間を得て、I/Oでは読まないことをデフォルトにし、CPUではSIMDでバイトを一度に処理し、ファイルシステムでは並列に走査しました。それぞれは小さな判断ですが、合わさると体感がまったく違うツールになります。

次にrgで巨大なリポジトリを一瞬で探すとき、その裏でこれらのピースがどう噛み合っているかを思い浮かべてみてください。そして、あなたが作るツールにも同じ問いを投げてみてください。「この作業、そもそもしないで済ませられないか?」

参考資料

ripgrepリポジトリ: https://github.com/BurntSushi/ripgrep
ripgrepはなぜそんなに速いのか（著者Andrew Gallantの記事）: https://blog.burntsushi.net/ripgrep/
Rust regexクレート: https://docs.rs/regex/
memchrクレート: https://docs.rs/memchr/
RE2（有限オートマトン正規表現エンジン）: https://github.com/google/re2
正規表現マッチングは単純で高速でありうる（Russ Cox）: https://swtch.com/~rsc/regexp/regexp1.html