grep/git grep/ripgrep(rg)の検索速度比較

# はじめに

9月に新たなファイル検索コマンドである[ripgrep(rg)](https://github.com/BurntSushi/ripgrep)がリリースされました。
公式にて

```
ripgrep supports many features found in grep
```

とあるように、他のファイル検索コマンドよりもgrepとの使用感が近いです。
また、[作者の方のベンチマーク(ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}](http://blog.burntsushi.net/ripgrep/)にもあるように、高速な検索が可能との事。
試しに[Linuxカーネルソース](https://github.com/torvalds/linux)に対しての検索速度を比較してみました。

**(10/28追記)検証漏れにより、find経由でのコマンドの使い方に重大なミスがありました**


# 環境

検証は、以下の環境で行っています。

* 構成
  * CPU: Pentium G4500 3.50GHz
  * OS: Windows 8.1 Pro
  * シェル・Linuxコマンド: Cygwin
* 各コマンド
  * grep(GNU grep): 2.24 (Cygwin)
  * rg: 0.2.3 ([windows binary](https://github.com/BurntSushi/ripgrep/releases))
  * git: 2.10.1.windows.1 ([Git for Windows](https://git-for-windows.github.io/))

# 結果



"EXPORT_SYMBOL_GPL"の文字列が含まれるファイル列挙時の速度です、事前に同じコマンドを走らせてキャッシュに載るようにしています。
検証時は[ベンチマーク用のシェルスクリプト](https://gist.github.com/wordijp/2df65e7d5bb39826c122c01fde050bff)をLinuxカーネルソースのルートに配置して実行しています。
コマンドはスペースの都合上簡略化していますが、[後述](#コマンドについて)で解説しています。

| コマンド(*パイプのパ) | 時間 |
|---|---|
| grep -lr EXPORT_SYMBOL_GPL . --exclude-dir=.git パ wc -l | 4.475s |
| rg -l EXPORT_SYMBOL_GPL . [-j 2] パ wc -l | 2.730s |
| rg -l EXPORT_SYMBOL_GPL . -j 3 パ wc -l | 1.453s |
| git grep -l EXPORT_SYMBOL_GPL パ wc -l | 1.717s |
| find列挙 パ xargs grep -l EXPORT_SYMBOL_GPL パ wc -l | 5.497s |

~~僕の環境ではgit grep < ripgrep(rg) < grepとなりました、少なくともgrepからの乗り換え候補です。~~
マルチスレッド動作の為、コア数の多いCPUだとripgrep(rg)最速となります。

# Windowsで検証するにあたって

Windowsの制約によりcheckout出来ないファイル(aux.h(auxが予約語)、xt_RATEEST.c(xt_rateest.cと文字被り)、etc)が幾つかあり、git grepが違う条件となりましたが、56215中14ファイル、それぞれが数KBの紛失なので誤差程度だと思い無視する事にしました。


# コマンドについて

各grep単体で再帰的に検索する方法と、findで全ファイルを検索し、パイプで各grepに渡す古来からの方法の2通りで検証しています。
各grep単体のコマンドは下記の通りです

```shell-session
$ grep     -lr WORD . --exclude-dir=.git | wc -l
$ rg       -l  WORD .                    | wc -l
$ git grep -l  WORD                      | wc -l
```
.gitディレクトリは、grepでは明示的に除外、ripgrep(rg)ではデフォルトで除外してくれます。
find後にパイプで渡すコマンドは下記の通りです、.gitディレクトリを無視しています。

```shell-session
$ find . \( -type d -name .git -prune -wholename .git \) -o -type f
```

-pruneで.gitディレクトリ以下を無視し、-wholenameで残った.gitディレクトリも除外します、これで綺麗に.gitディレクトリも含む配下が無視されます。
これをパイプで繋げて下記のように実行します。

```shell-session
$ find . \( -type d -name .git -prune -wholename .git \) -o -type f | \
>    xargs grep -l WORD | wc -l
$ find . \( -type d -name .git -prune -wholename .git \) -o -type f | \
>    xargs rg -l WORD | wc -l
```

~~ripgrep(rg)でxargsを使ってない点に注目してください、ripgrep(rg)では標準入力からもファイル一覧を指定できます、xargsを使い引数からも指定は出来るのですが、~~
どちらもコマンド以外の違いはありませんが、ripgrep(rg)では**ファイル数が多いとかなり低速になるので気を付けましょう**。

# まとめ

ripgrepは拡張正規表現(grepの-Eオプション)がデフォルトで有効であったり、**パイプで実行する時は~~xargsを付けずに標準入力からファイル一覧を受ける~~ファイル数が多いと低速になるのに気を付ける、**等の差異がありますが、.gitignoreのファイルを標準で除外してくれたり、なにより高速です、grepオプションとの互換性も高いのでgrepからの乗り換え時の学習コストもそれ程かからないと思います。

# ripgrep(rg)の注意点

まだ若いコマンドの為、幾つかのシグナルが未実装なのか、例えば

```shell-session
$ find . | xargs rg EXPORT_SYMBOL_GPL | head -n 10
```

とすると、10行列挙が完了してSIGPIPE(13)が飛んでいるはずなのに、実行が終了せず全検索と同じ時間がかかっている~~、この場合はgrepの方が高速(あまり遭遇しないだろうけど)~~。

また、Windows版限定ですが、Ver 0.2.3現在、

```shell-session
$ cat hoge.rs | rg foo -
```

とパイプ経由での検索の場合、明示的に標準入力を利用する-オプションが必要です、こちらはripgrepのソースを読んでいて気付いたのですが、

```rust:ripgrep/src/atty.rs
/// Returns true if there is a tty on stdin.
#[cfg(windows)]
pub fn on_stdin() -> bool {
    // BUG: https://github.com/BurntSushi/ripgrep/issues/19
    // It's not clear to me how to determine whether there is a tty on stdin.
    // Checking GetConsoleMode(GetStdHandle(stdin)) != 0 appears to report
    // that stdin is a pipe, even if it's not in a cygwin terminal, for
    // example.
    //
    // To fix this, we just assume there is always a tty on stdin. If Windows
    // users need to search stdin, they'll have to pass -. Ug.
    true
}
```

と、issuesにもあるように、Windows環境でcygwin1.dllを利用せずに解決するのは難しいようです。