view release on metacpan or  search on metacpan

RIPGREP-STUDY.md  view on Meta::CPAN

# greple 高速化検討資料 — ripgrep の取り込みを中心に

- 作成日: 2026-07-02
- 対象: App-Greple 10.04 (master 6625a99)
- 計測環境: macOS 15 (Darwin 24.6) / Apple Silicon / perl 5.42.2 / ripgrep 15.1.0 (+pcre2, NEON SIMD)

## 1. 要旨

ripgrep の高速性を greple に取り込む方法として、以下の 5 案を検討した。

| 案 | 概要 | 効果 | 工数 | 判定 |
|----|------|------|------|------|
| A | rg をファイルレベルのプリフィルタに使う | 大（多ファイル検索） | 小 | **推奨** |
| B | rg --json の位置情報を greple 内部位置に変換 | ほぼ無し〜逆効果 | 中 | 非推奨 |
| C | Rust ライブラリ (grep crates) を FFI で呼ぶ | 小 | 大 | 非推奨 |
| D | greple 全体を Rust で書き直す | 大 | 特大 | 非推奨（別プロジェクトなら可） |
| E | Perl 内部の改善（並列化・マッチ後処理最適化） | 中 | 小〜中 | **併用推奨** |

結論を先に述べると、**実測の結果、greple の遅さの主因は正規表現スキャンではない**。
ボトルネックは (1) マッチ後の Perl データ構造処理、(2) ファイルごとの逐次処理オーバーヘッド、(3) 並列性の欠如であり、
「ripgrep に正規表現マッチを肩代わりさせて位置情報をもらう」方式（案 B/C）は、
高速化したい部分がそもそも支配的コストでないため効果が出ない。
ユーザーが以前試して「うまく使えなかった」のは位置表現の非互換だけでなく、この構造的な理由による。

一方、**「マッチしないファイルに greple の処理を一切走らせない」プリフィルタ方式（案 A）は、
rg の並列走査・ファイルスキップの強みをそのまま享受でき、位置変換も不要**。
実測でも大規模ツリー検索で 5 倍以上（ツリーが大きくマッチが疎なほど拡大）の改善を確認した。

## 2. 現状分析: greple のアーキテクチャ

サブエージェントによるコード調査結果の要点（file:line は現 master 基準）。

### 2.1 処理モデル

- **slurp 方式**: ファイル全体を 1 スカラ文字列として読む（`script/greple:989-1023`）。
  行単位ストリーミングではない。
- **文字単位オフセット**: 入力は `binmode STDIN, ":encoding($file_code)"`（`script/greple:1226`）で
  読み込み時にデコードされ、以後の検索・領域演算はすべて **Perl 内部文字列上の文字オフセット**で行われる。
  `Regions.pm` の `match_regions`（`lib/App/Greple/Regions.pm:97-117`）は
  `pos() - length(${^MATCH})` で `[from, to]` を算出する。
- **領域代数**: `--inside/--outside/--include/--exclude`、ブロック構築、must/need/allow 判定は
  すべて `[from, to]` ペア配列に対する集合演算（`Regions.pm`, `Grep.pm`）。
- **Perl 正規表現への依存**: `/p` + `${^MATCH}`、`pos()`、`\G` + `\X`（`Pattern.pm:134`）、
  可変長後読み、ユーザーパターンの Perl 方言全般。
- **モジュール結合点**: `--inside '&func'` 等の関数パターンは `$_` にファイル内容が入った状態で
  呼ばれ、`[from, to]` の領域リストを返す（`Grep.pm:444-457`）。`--begin/--end/--postgrep/--print`
  も同様に Perl コードが検索パイプラインへ直接介入する。
- **逐次処理**: ファイルループ（`script/greple:1119-1162`）は単一プロセス・単一スレッド。
  並列処理は一切ない（fork は find.pm の外部コマンド起動と PGP 復号のみ）。
- **入力フィルタ**: `--if` は外部コマンドの出力を STDIN 経由で検索対象にする（`Filter.pm:87-111`）。
  検索対象が元ファイルのバイト列と一致しない場合がある点は、外部エンジン統合時の制約になる。

### 2.2 ベンチマーク

コーパス: UTF-8 日英混在テキスト 26MB / 30 万行（および同内容を 100 行 × 3000 ファイルに分割したツリー）。
warm cache、3 回計測の代表値。

**単一ファイル（26MB）**

| コマンド | マッチ行数 | 時間 |
|---|---:|---:|
| `rg -c fox` | 95,984 | 0.010s |
| `grep -c fox` | 95,984 | 0.009s |
| `perl -ne '$c++ if /fox/'`（UTF-8 デコード込み） | 95,984 | 0.035s |
| `greple -c fox` | 95,984 | **0.82s** |
| `greple -c 高速` | 115,860 | **0.96s** |
| `greple -c <マッチ0件>` | 0 | **0.12s** |
| `greple`（/dev/null、起動コストのみ） | — | 0.044s |

**多ファイル（3000 ファイル / 計 26MB）**

| コマンド | 時間 |
|---|---:|
| `rg -c <マッチ0件> tree/`（並列） | 0.034s |
| `rg -j1 -c <マッチ0件> tree/`（単一スレッド） | 0.036s |
| `rg -l 高速 tree/`（全ファイルマッチ） | 0.047s |
| `greple -Mdig -c <マッチ0件> --dig tree` | **0.88s** |
| `greple -Mdig -c 高速 --dig tree` | **1.6s** |

**プリフィルタ効果（3000 ファイル中 5 ファイルのみにマッチする希少パターン）**

| コマンド | 時間 |
|---|---:|
| `greple -Mdig -l zebra --dig tree` | 0.30s |
| `rg -l zebra tree/ \| greple --readlist -l zebra` | **0.058s** |

### 2.3 ボトルネックの分解

上の数値から greple の 1 実行あたりのコスト内訳を分解できる。

| フェーズ | 実測値 | 備考 |
|---|---|---|
| 起動（モジュールロード・オプション処理） | 44ms | Getopt::EX 等。どの方式でも残る下限 |
| デコード + 正規表現スキャン | 約 80ms / 26MB | マッチ 0 件時 0.124s − 起動 44ms |
| **マッチ後処理**（Match/Block 構築・領域演算・カウント） | **約 7µs / マッチ** | 10 万マッチで 0.7〜0.9s。**支配的コスト** |
| ファイルごとのオーバーヘッド | 約 0.25ms / ファイル | open・binmode・slurp 等 |

**含意**: rg が 26MB を 10ms で走査するのに対し greple のスキャンフェーズは 80ms — 差は 8 倍だが
絶対値は小さい。マッチが多い場合の 0.8〜1.0s の大半はスキャンではなく
**マッチ後の Perl 側処理**であり、これは初期マッチ列挙を外部化しても消えない。
つまり「rg に位置を出させる」方式の理論上の改善上限は、このワークロードでは 1 割程度しかない。

## 3. ripgrep 側の事実確認

### 3.1 `--json` 出力（実測確認済み）

```json
{"type":"match","data":{"path":{"text":"sample.txt"},
 "lines":{"text":"foo 高速 bar\n"},"line_number":1,"absolute_offset":0,
 "submatches":[{"match":{"text":"高速"},"start":4,"end":10}]}}
```

- `absolute_offset` は行頭の絶対バイトオフセット、`submatches` の `start/end` は行内バイトオフセット。
- **トランスコード時（`-E euc-jp` や BOM 検出時）のオフセットは、変換後 UTF-8 バイト列基準**
  （EUC-JP ファイルで実測確認: `高速` → start:4, end:10 = UTF-8 バイト位置）。
  `--pre` フィルタや解凍も同様に変換後基準。
- 非 UTF-8 データは base64（`bytes` キー）で表現される。

したがって「rg の出すオフセットは常に UTF-8 バイト単位」とみなせ、greple の文字オフセットへの
変換は数学的には整合的に定義できる（オフセットは昇順に届くので O(N) の一回走査で変換可能）。
**位置変換そのものは技術的障害ではない**。障害は次節以降で述べるコスト構造にある。

### 3.2 案 B の実測: JSON 経由のオーバーヘッド

| 処理 | 時間 |
|---|---:|
| `rg --json fox corpus.txt`（96k マッチ、JSON 26MB 出力） | 0.09s |
| ↑を Perl (JSON::PP) でパース | **8.0s** |
| （参考）現行 greple の同検索全体 | 0.82s |

マッチ多数時、JSON のパースだけで現行 greple の 10 倍の時間がかかる（コア モジュール JSON::PP の場合。
JSON::XS を追加依存にすれば数百 ms 程度まで縮むが、それでも byte→char 変換・
ブロック構築を加えると現行との差はほぼ消える）。
マッチ少数時はそもそもスキャンフェーズ（80ms）しか削れない。**どちらのケースでも割に合わない。**

### 3.3 libripgrep（grep crates）

ripgrep は `grep-matcher` / `grep-searcher` / `grep-printer` 等のクレート群に分割されており
（[libripgrep PR #1017](https://github.com/BurntSushi/ripgrep/pull/1017)）、
ライブラリとして再利用可能。正規表現エンジンは Rust regex（有限オートマトン + SIMD）と
PCRE2（`--pcre2` / `-P`、後読み・後方参照対応）の 2 系統。

- Rust regex は後読み・後方参照・`(?{...})` 非対応。greple ユーザーのパターン資産とは方言差がある。
- PCRE2 モードは Perl にかなり近いが、完全互換ではない。

## 4. 各案の詳細検討

### 案 A: rg をファイルレベルのプリフィルタに使う 【推奨】

**仕組み**: `rg -l pattern dir` で「マッチを含むファイル一覧」だけを rg に高速列挙させ、
greple は該当ファイルのみを従来どおり処理する。位置情報を受け渡さないので
バイト/文字オフセット問題・正規表現方言問題の影響を最小化できる。

```
rg -l --null pattern dir | greple --readlist pattern
```