ripgrep は {grep, ag, git grep, ucg, pt, sift} より速い

Andrew Gallant
2016/09/23
目次

この記事では新しいコマンドライン検索ツール ripgrep を紹介する。ripgrep は The Silver Searcher (ack クローン) の利便性と GNU grep の高い性能を併せ持つ。ripgrep は高速で、クロスプラットフォーム (Linux, Mac, Windows 用のバイナリが利用可能) で、Rust を使って書かれている。

ripgrep は Github で公開されている。

この記事では不可能なことを試みる: いくつかの有名なコード検索ツールを公平にベンチマークして比較する。具体的には、次の主張を実証する 25 個のベンチマークをこれから見ていく:

これまで二年半にわたって空き時間で Rust を使ったテキスト検索に取り組んできた者として、そして ripgrep と ripgrep で使われている正規表現エンジンの著者として、二つのコード検索ツールの性能に関する詳細な説明をここに記す。精査されないベンチマークなどあり得ない！

対象読者: Unicode とプログラミングを簡単に知っていて、コマンドラインを使った作業をしたことがある人。

検索結果のスクリーンショット

ripgrep を使った検索
ripgrep を使った検索

ripgrep の紹介

セールスポイント

他の検索ツールではなく ripgrep を使うべき理由は何か？ さて...

言い換えれば、デフォルトで行われるフィルタリング、Unicode サポート、少ないバグ、速さを気に入るなら ripgrep を使えばいい。

セールスでないポイント

ripgrep を使うべきでない理由についても納得してもらった方がいいと思う。これは ripgrep を使うべき理由よりもずっと見えにくいことが多いためだ。

ありとあらゆる機能を ripgrep に追加するつもりは当初なかったものの、開発が進むにつれ ripgrep は他のファイル検索ツールが持つ機能のほとんどをサポートするようになった。例えば複数行のテキスト検索やオプトインの PCRE2 (先読み/後読みと後方参照のサポートを提供する正規表現エンジン) サポートが ripgrep には実装されている。

現時点において、ripgrep を使うべきでない主な理由はおそらく次のいずれかであると思われる:

インストール方法

ripgrep のバイナリは rg と呼ばれる。

Windows, Mac, Linux 用のバイナリは Github のリリースページから入手できる。Linux 用のバイナリは静的実行形式である。Windows 用のバイナリは MinGW (GNU) でビルドしたものと Microsoft Visual C++ (MSVC) でビルドしたものが用意される。可能な限り GNU ではなく MSVC でビルドしたものを使ってほしい。ただし MSVC でビルドしたバイナリを使うときは Microsoft VC++ 2015 redistributable が必要になる。

あなたが Homebrew ユーザーなら、ripgrep は次のコマンドでインストールできる:

$ brew install ripgrep

あなたが Arch Linux ユーザーなら、ripgrep はオフィシャルレポジトリからインストールできる:

$ pacman -Syu ripgrep

あなたが Rust プログラマーなら、ripgrep は cargo でインストールできる:

$ cargo install ripgrep

ripgrep をソースからビルドしたい場合でも簡単に行える。ripgrep は Rust で書かれているので、コンパイルするには Rust のインストールが必要になる。ripgrep は Rust 1.9 (stable) 以降でコンパイルできる。ビルドするには次のコマンドを実行する:

$ git clone git://github.com/BurntSushi/ripgrep
$ cd ripgrep
$ cargo build --release
$ ./target/release/rg --version
0.1.2

Rust nightly コンパイラを使っているなら、オプショナルな SIMD アクセラレーションを次のコマンドで有効化できる。この記事のベンチマークでは SIMD アクセラレーションを有効にして測定している。

RUSTFLAGS="-C target-cpu=native" cargo build --release --features simd-accel

弾丸ツアー

ripgrep のコマンドラインでの使い方は同じような機能を持つツールと大きくは変わらないので、あなたは既に ripgrep の使い方を知っているはずだ。完全な説明は rg --help から確認できるが、ここにも簡単に使い方を示しておく。

ripgrep は出力先が端末かどうかを自動的に判別し、もしそうなら出力に色を付けて行番号を付け足す。これは The Silver Searcher と同じ動作である。色付けは Windows でも動作する！ 色は --color フラグから細かく調整できる。

実行を始める前にもう一つ: 通常 ripgrep は入力が UTF-8 でエンコードされることを仮定する。ただし ripgrep は入力ファイルが UTF-16 であることを検出でき、その場合でも正しく検索が行える。他のエンコーディングを扱うときは -E/--encoding フラグで明示的に指定しなければならない。

次のコマンドはカレントディレクトリを再帰的に検索する。そのとき隠しファイル、隠しディレクトリ、バイナリファイル、全ての .gitignore が指定するファイルは無視される:

$ rg foobar

このコマンドは .rgignore というファイルが指定するファイルも無視する (親ディレクトリにある .rgignore も検出される)。.rgignore ファイルは .gitignore では不十分な場合に利用できる。どんな場合でも .rgignore にあるパターンは .gitignore にあるものより優先される。

-u フラグで全ての ...ignore ファイルを無視できる。加えて隠しファイルと隠しディレクトリを検索するには -uu フラグを指定する。さらにバイナリファイルも検索するには -uuu フラグを加える (「とにかく全て検索してくれ！」を意味する)。このため rg -uuu は grep -a -r とほぼ同じコマンドとなる:

$ rg -uu foobar   # grep -r とほぼ同じ
$ rg -uuu foobar  # grep -a -r とほぼ同じ

(Tip: ...ignore ファイルが期待通りに動作しないときは、--flag フラグを付けて検索を実行すると何が起きているかを確認できる。)

大文字と小文字を区別せずに検索するには -i フラグ、検索を反転させるには -v フラグ、検索結果それぞれの二行前を表示するには -C2 フラグを利用できる。

全てのマッチが単語境界に囲まれることを強制するには -w フラグを使う。

検索と置換も行える。次のコマンドはファーストネームとラストネームを見つけて入れ替える:

$ rg '([A-Z][a-z]+)\s+([A-Z][a-z]+)' --replace '$2, $1'

名前付きグループもサポートされる:

$ rg '(?P<first>[A-Z][a-z]+)\s+(?P<last>[A-Z][a-z]+)' --replace '$last, $first'

完全な Unicode サポートに関するハードルを上げるために、Unicode における大文字に Unicode における小文字の列が続く文字列を検索するコマンドを示す (他の検索ツールで同じことをするときは幸運を祈る！):

$ rg '(\p{Lu}\p{Ll}+)\s+(\p{Lu}\p{Ll}+)' --replace '$2, $1'

次のコマンドは特定の glob にマッチするファイルだけを検索する:

$ rg foo -g 'README.*'

特定の glob にマッチするファイルを検索から除外することもできる:

$ rg foo -g '!*.min.js'

HTML ファイルと CSS ファイルだけを検索するコマンドを示す:

$ rg -thtml -tcss foobar

次のコマンドは JavaScript ファイル以外の全てのファイルを検索する:

$ rg -Tjs foobar

rg --type-list を実行するとサポートされるタイプの一覧を確認できる。新しいタイプを追加するには --type-add を使った上で検索パターンを続けて書く (rg はタイプの設定を永続化しない):

$ rg --type-add 'foo:*.{foo,foobar}' -tfoo bar

ここでは foo というタイプが .foo あるいは .foobar で終わる名前を持つ任意のファイルにマッチする。

正規表現の構文

サポートされる構文は Rust の regex ライブラリのドキュメントで説明されている。

grep の構造

ベンチマークを見ていく前に、まずは grep ライクな検索ツールの動作に関する高レベルな概観を、特に ripgrep に特別な焦点を当てながら説明しておいた方がいいと思う。この節の目標は考えている問題のコンテキストを多少でも理解し、ベンチマークの理解と解析を容易にすることだ。

背景

コマンドライン引数のパースは脇に置くとして、最初の「本当の」仕事は検索するファイルを決める処理である。grep などのツールは賢いことを何も行わない: コマンドラインに渡されたファイルを検索するだけだ。例外は -r フラグで、このフラグが指定されると grep はカレントディレクトリに含まれる全てのファイルとディレクトリを再帰的に検索する。様々なコマンドラインフラグを使うと検索される (あるいは検索されない) ファイルを制御できる。

ack はこの種のデフォルトの動作に対する考え方をくつがえした。ack は検索するファイルをスマートに決定する。例えば ack はデフォルトでカレントディレクトリを再帰的に検索し、そのときソースコントロールに関連するファイルおよびディレクトリ (.git など) を無視する。この検索手法には疑いなく独自の利点と欠点がある。というのも確かにツールは「賢く」なるが、この言葉は「不透明」の言い換えでもあるからだ。つまり、本当に全てのファイルを検索したいときに、そうツールに伝えるための正しい呪文を唱える方法を見つけるのが難しい場合が多い。そうは言ってもデフォルトでスマートになるのは便利であり、特に「スマート」が「ソースコントロールの設定を使って検索すべきファイルを求める」を意味するときは非常に便利になる。シェルのエイリアスと grep を使っては同じことを行えない。

本記事のベンチマークで使用する ripgrep 以外の全てのツールは grep または ack の流れをくんでいる。sift は grep の系統であり、ag, ucg, pt は ack の系統である。ripgrep は二つのハイブリッドと言える: grep のように巨大なファイルを効率良く検索できつつも、ack のような「スマートな」デフォルトの動作を持つようにしてある。最後に git grep も特筆に値する。サポートされるオプションを見ると git grep はプレーンの grep と非常に似ているものの、デフォルトの検索モードを見ると ack の系統に属する: git grep はソースコントロールにチェックインされたファイルだけを検索する。

もちろん、両方の種類のツールに共通する要素も数多く存在する。しかし、少し目を凝らして注目するに値する大きな違いがいくつかある:

検索するファイルの収集

ack ライクなツールでは、カレントディレクトリで検索すべきファイルがどれかを判断する処理が重要になる。これは非常に高速な再帰的ディレクトリイテレータが必要なことを意味する。このイテレータを使って素早くファイルパスをフィルタリングして、実際の検索を実行するワーカーのプールにファイルパスを送らなければならない。

ディレクトリの走査では慎重になる必要がある。というのも、再帰的ディレクトリイテレータの中には stat の呼び出しを厳密に必要な回数よりも多く行うものがあり、そうすると性能が大きく落ちるからだ。そういったイテレータの実装は標準ライブラリのどこかに埋め込まれている場合が多いので、この種の問題を調べて解決するのは非常に難しくなる場合がある。例えば Python にはつい最近までこの問題が存在した。ただ ripgrep の使うディレクトリイテレータは最小限のシステムコールを行うので安心してほしい。

ファイルパスのフィルタリングではコマンドラインフラグ (grep の --include や --exclude フラグ) に与えられた規則を解釈するだけではなく、.gitignore といったファイルを読み込んでその規則を全てのファイルパスに適用する必要がある。全てのディレクトリで .gitignore ファイルを探すだけでも観測できる程度のオーバーヘッドが生じる！ これ以外にも .gitignore に関連する性能上の重要なポイントとして、全ての規則と全てのファイルパスを個別にマッチさせてはいけない。Linux カーネルのソースツリーのような巨大なレポジトリは数百個の .gitignore と全部で数千個の規則を持つ。

最後に、他のスレッドに仕事を割り当てるには何らかの同期が必要になる。解決法の一つはミューテックスで保護されたリングバッファを用意してキューのように振る舞わせることだが、これより高速になる可能性のあるロックフリーの解決法も存在する。Rust のエコシステムは素晴らしく、私は検索を行うスレッドのプールに仕事を振り分ける処理でロックフリーの Chase-Lev work-stealing queue を再利用できた。本記事のベンチマークに登場する他の全てのツールでは、何らかのミューテックスで保護されたキューを使って仕事を並列化している (現在の sift と pt は違うかもしれない。この二つは Go チャンネルを使っており、私はここ数年で Go チャンネルの実装がどう改善されたかを知らない)。

検索

検索は本記事で考える全てのツールの心臓部に位置する。この話題について語り尽くすまで二年半ほど時間をかけることもできる (「Rust を使ったテキスト検索に私がどれだけ時間をかけたか」にようこそ) が、ここでは要点に軽く触れるだけにする。

正規表現エンジン

最初に正規表現エンジンがある。どんな検索ツールも何らかの正規表現の構文をサポートする。正規表現の構文の例を示す:

正規表現エンジンは利用可能な機能によって大まかに二つのカテゴリに分類される。上記の機能を全てサポートする正規表現エンジンはバックトラッキング (backtracking) と呼ばれるアプローチを使っており、通常はとても高速であるものの一部の入力に対しては非常に遅くなる。ここで「非常に遅い」は検索を完了するまでの時間が指数的になる可能性があることを意味する。例えば次の Python コードを実行してみてほしい:

>>> import re
>>> re.search('(a*)*c', 'a' * 30)

正規表現と検索対象文字列はどちらも非常に短いにもかかわらず、検索には非常に長い時間がかかるはずだ。これは Python 内部の正規表現エンジンがバックトラッキングを使っており、一部のクエリに答えるのに指数時間がかかるためである。

もう一つの種類の正規表現エンジンは有限オートマトンを利用する。この種類の正規表現エンジンはバックトラッキングを使うものより一般に機能が少なく、例えば後方参照をサポートしないことが多い。ただその代わり、有限オートマトンのアプローチでは全ての検索が、正規表現と入力がどんなものであれ検索対象文字列の長さに関する線形時間で終わることがたいてい保証される。

二種類のアプローチのいずれかが平均実行時間でもう一方より優れているわけではない。非常に高速な正規表現エンジンはどちらの種類にも存在する。これを納得してもらった上で、いくつかの検索ツールとそこで使われる正規表現エンジンを次にまとめる:

Rust と Go の正規表現ライブラリはどちらも Google の RE2 を祖先に持つ。

最後に、PCRE を使うツール (The Silver Searcher と Universal Code Grep) はどちらもバックトラッキングのアプローチに特有な最悪ケースから逃れられていない。例を示す:

$ cat wat
c
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
c
$ ucg '(a*)*c' wat
terminate called after throwing an instance of 'FileScannerException'
  what():  PCRE2 match error: match limit exceeded
Aborted (core dumped)

The Silver Searcher も同様の入力に対して検索に失敗する。最初の行をマッチとして報告するものの、三行目のマッチが無視される。本記事のベンチマークに登場する他のツールはこの入力を問題なく処理できる。

リテラル検索の最適化

どんな検索ツールも最終的には正規表現エンジンを利用するので、高速なものを選択するのは重要である。ただそうは言っても、最速の正規表現エンジンを使った検索でさえ単純なリテラル検索に比べれば長い時間がかかる。Boyer-Moore のアルゴリズムは特定の部分文字列を見つける古典的なアルゴリズムであり、今日でさえ、汎用の検索でこのアルゴリズムを上回るのは難しい。Boyer-Moore のアルゴリズムの特筆すべき特徴が、検索対象文字列を数文字まとめてスキップできることだ。そのときは検索を始める前に計算される小さなスキップテーブルが利用される。

モダンな CPU で Boyer-Moore を高速に実装する上で鍵となるのはスキップできる文字数では必ずしもなく、むしろマッチの候補をどれだけ高速に特定できるかである。例えば多くの Boyer-Moore の実装ではリテラルの最後のバイトから検索を行い、検索対象文字列に含まれるそのバイトが全てマッチの候補となる。Boyer-Moore がテーブルを参照してスキップを行うのはそれからなので、候補となる箇所を見つける最初の処理を高速に行う必要がある。幸い C 標準ライブラリには、まさにこの処理を行う memchr といった特殊ルーチンが存在する。通常 memchr の実装は SIMD 命令を使って反復ごとに 16 バイトを調べられるので、memchr は非常に高速となる。私のシステムでは memchr のスループットは秒速数 GB 程度である (私が行った実験では memchr を使った Boyer-Moore アルゴリズムの実装が PCMPESTRI を使った明示的な SIMD 実装と同程度に高速だった。ただ、この点はもう一度調べてみたいと思っている)。

検索ツールが様々なベンチマークで優秀な成績を納めるには、ツール自身あるいは内部の正規表現エンジンでリテラル検索の最適化を行わなければならない。例えば Rust の正規表現ライブラリは任意のパターンから接頭辞および接尾辞のリテラルを取り出すのに大きな手間をかけている。正規表現のパターンから接頭辞のリテラルを取り出す例を示す:

こういったパターンが正規表現の先頭に現れるとき、Rust の正規表現ライブラリはその事実を検出してマッチの候補を高速に検出するのに利用する (複数のリテラルが検出されるときでさえ同様の処理が行われる)。Rust のコアにある正規表現エンジンは高速であるものの、接頭辞のリテラルを最初に検索し、マッチを検証する必要が生じたときにだけコアの正規表現エンジンを起動する方が高速になる。

最良のケースは正規表現全体が単一のリテラルあるいはリテラルの和集合になるときで、このときはコアの正規表現エンジンを全く使わないで検索が行える！

検索ツールはさらに奥の手を持っている。すなわち、多くの検索ツールは行ごとの検索を行う (The Silver Searcher は興味深い例外で、デフォルトの動作が複数行検索となっている) ので、正規表現パターンの非接頭部 (つまり「内側」) にあるリテラルを取り出し、それを使ってマッチ候補の行を検索する。例えば正規表現 \w+foo\d+ からは foo が取り出される。具体的には ripgrep が候補の行を見つけると、その行に対してだけ行頭と行末を検索し、その行全体をコアの正規表現エンジンに入力する。この工夫により ripgrep は正規表現エンジンを使うことなくファイルの大部分を高速にスキップできるようになる。私たちがベンチマークした検索ツールの大部分はこの最適化を行っておらず、性能を改善する余地がある (特にコアの正規表現エンジンがそれほど高速でないとき)。

リテラルが複数あるとき (例えば foo|bar) を扱えるのも同様に重要である。GNU grep は複数のパターンを検索する Commentz-Walter というあまり知られていないアルゴリズムを使っている。短くまとめると、Commentz-Walter は Aho-Corasick と Boyer-Moore を組み合わせたアルゴリズムと言える: 逆オートマトンを持ったスキップテーブルである。一方で Rust の正規表現ライブラリはプレーンの Aho-Corasick または (SIMD が有効なときは) Teddy と呼ばれる特別な SIMD アルゴリズムを利用する。Teddy は Intel の正規表現ライブラリ Hyperscan の一部として Geoffrey Langdale によって開発された。この SIMD アルゴリズムは ripgrep が GNU grep を上回るために鍵となる最適化 (最低でもその一つ) であることがベンチマークで判明する。

こういった最適化の結果として素晴らしいのが、ripgrep からはリテラル検索の最適化をほとんどしないで済むことだ。大部分の仕事は Rust の正規表現ライブラリがやってくれるので、そのライブラリを使う側はパフォーマンスの最適化を全て自動的に得られる！

メカニズム

リピートアフターミー: 汝検索を行ごとに行うことなかれ。

検索ツールを実装するナイーブなアプローチは、ファイルを一行ごとに読み込んで各行に対して個別にパターンの検索を行うというものだ。しかしこのアプローチには問題がある。一番の問題は、一般的なケースでマッチが稀であることだ。つまり巨大なレポジトリを検索している場合でも大部分のファイルは全くマッチを生成しないので、大汗かいて各行をパースしても何の成果も得られない可能性が高い。

各行の始まりを見つける処理が追加の仕事であるだけではなく、大きなオーバーヘッドも存在する。リテラルを検索するのであれ正規表現を検索するのであれ、ファイルの全ての行の最初で検索を初めて行末で検索を終わらなければならない。検索をやり直すオーバーヘッドは破滅的である。

その代わり、検索ツールはどれもバイトが並んだ大きなバッファを一度にまとめて検索する方法を見つけている。ファイルをメモリにマップしたり、ファイル全体をメモリに読み込んだり、定常サイズのバッファを使ってファイルをインクリメンタルに検索したりと、方式の違いはあれどツールは様々な工夫を実装する。ただ問題がないわけではない。例えばファイル全体をメモリに読み込む方式あるいはメモリマップを使うツールは (Universal Code Grep のように) stdin をサポートできなかったり、(The Silver Searcher のように) stdin を使うと行ごとの検索に切り替わったりする。ripgrep, GNU grep, git grep が採用するインクリメンタルな形式の検索は任意のファイルやストリームを問題なく扱える。

全てのツールがインクリメンタルな形式の検索を実装するわけではないのには理由がある: 実装が難しいのだ。完全な機能を持った検索ツールでは次の要素を全て考慮しなければならない:

コードの複雑性の観点から言うと安くない処理である。しかしいやはや、これは実装する価値がある。ベンチマーク結果を読み進めると、この方式がメモリマップを使うより高速であることが判明する！

出力

結果の出力は自明なステップに思えるかもしれない。しかし最低でも多少は気を使っておく必要がある。例えば検索を行うスレッドからマッチを見つけるたびに出力させても構わないものの、通常は同じファイルにおけるマッチをまとめて出力したいことが多いだろう。この処理を実装するナイーブなアプローチは、出力処理を直列化して同時に一つのスレッドだけから出力させるというものだ。ただこのアプローチにも問題がある。というのは、もし検索スレッドが出力処理のロックを取得してからファイルの検索を始める (そしてファイルの検索が終わってから解放する) と、全ての検索が直列化される。これだと並列化のアプローチが全て無駄になる。

そのため本記事のベンチマークに登場するコード検索ツールで検索を並列化するものはどれも、結果をメモリ上の中間バッファに書き込んでいる。こうすると全ての検索スレッドが完全に並列な形で検索を行えるようになる。結果の出力ではそれでも直列化が必要になるものの、その処理は中間バッファの中身を stdout に書き出すだけだ。メモリ上のバッファを使うと聞いて頭の中で警報ベルが鳴った人もいるかもしれない: 2GB のファイルを検索していて、全ての行がマッチしたらどうする？ メモリ使用量が大きくなってしまうのでは？ 答えは「なるよ。もちろん！」である。鍵となる洞察は、一般的なケースではマッチする行が検索する行よりずっと少ないことだ。もちろん、メモリ使用量を抑える方法も存在する。例えば ripgrep は stdin または単一のファイルを検索するとき結果を stdout に直接書き出し、中間バッファは必要ないので使われない (ripgrep が並列実行しないよう命令されたときも中間バッファを省略できるはずだが、これはまだ実装していない)。言い換えれば、私たちが選べるのは空間、時間、正確性の中から二つだけだ。

結果の出力に関する細かい点はツールごとに異なる点に注意してほしい。具体的に言うと、The Silver Searcher と Universal Code Grep はマッチを構造化データ (match 構造体の配列など) としてメモリに書き込み、git grep と ripgrep は実際の出力をメモリ上の動的に伸びる文字列バッファに書きこむ。いずれのアプローチも十分高速なようではあるものの、git grep と ripgrep はインクリメンタル検索をサポートするためにこの方式を使わなけれならない事情がある。これに対して The Silver Searcher は必ずファイル全体をメモリマップし、Universal Code Grep は必ずファイル全体をメモリに読み込む。後者のアプローチだと実際に結果の出力を行うときにメモリ上のファイルの内容を参照できるが、git grep と ripgrep はこれを行えない。

実験手法

概要

公平で意味のあるベンチマークを行うのは難しい。私は確実に何度も間違いを犯した。特に、制御できる変数があまりにも多いために可能な組み合わせを全て試すのは現実的でない。これは、私がここに示すベンチマークが要約されたものであることを意味する。そして私はベンチマークするツールの一つの作者でもあるから、ベンチマークにバイアスがあることも避けられない。しかし、たとえ私が作成したベンチマークスイートが公平性の観点から見て欠陥を持っていたとしても、読者にはそれぞれのベンチマークに対して私が加える解析を興味深く読んでもらえることを願っている。解析はどれも私の行ったことを多く語るよう大きくバイアスがかかっているが、これは私がそれを最も良く知っているためだ。ただ私はベンチマークを行った全てのツール (そして内部の正規表現エンジン) のソースコードを最低でも一部は確認している。

言葉を変えれば、私は解析の詳細が正しいことについては大きな自信を持っているものの、何らかの大局的な見地を見逃している可能性があるということだ。このため、まずはこのベンチマークを作る上で私が意識したポイントを説明しよう:

これで細かいことは片付いたので、本題に入ろう。何よりもまず、どのツールをベンチマークするのだろうか？

ここに無いツールとして言及しておくべきなのが ack だ。ack をベンチマークしなかったのは、執筆時点で ack がこのリストにある他のツールより格段に遅かったためである。ただ現在ベータ中の ack 3 では一部の場面で検索時間が半分になるなど性能が改善されている。

ベンチマークランナー

ベンチマークランナーは Python プログラム (最低でも Python 3.5 が必要) であり、ベンチマークの実行だけではなくベンチマークで利用されるコーパスのダウンロードも行う。このスクリプトは ripgrep のレポジトリの benchsuite/benchsuite に置いてある。次のように実行する:

$ git clone git://github.com/BurntSushi/ripgrep
$ cd ripgrep/benchsuite
# 注意！ 以下のコマンドは数 GB のデータをダウンロードして
# Linux カーネルをビルドするので、高速な回線があっても 15 分ほどの時間がかかる。
# Tip: --download subtitles-ru を指定すると一番小さいコーパスだけが
# ダウンロードされる。ただその場合はダウンロードしたコーパスに対する
# ベンチマークしか実行されない。
$ ./benchsuite --dir /path/to/data/dir --download all
# 実行可能なベンチマークを表示する。
$ ./benchsuite --dir /path/to/data/dir --list
# ベンチマークを実行する。
# ベンチマークの名前を省略すると全てのベンチマークが実行される。
# 完全なスイートの実行にはデフォルトの設定だと 30 分ほどかかり、
# --warmup-iter 3 --bench-iter 10 だと 120 分ほどかかる。
$ ./benchsuite --dir /path/to/data/dir '^subtitles_ru_literal$'

ベンチマークで使われるコード検索ツールの一部を持っていない場合は --allow-missing を benchsuite に渡すと実行を飛ばすようにできる。生データ (実行された全てのコマンドの測定結果) を保存するには --raw /path/to/raw.csv を指定する。

誤解を招きかねないデータが得られる可能性を小さくするために、ベンチマークランナーはいくつかの基本的な対策を行っている:

それぞれのベンチマークの定義は各コマンドが同じような仕事をすることを保証する責任がある。例えば GNU grep で完全な Unicode サポートを有効にすると実行速度が大きく低下する場合があるので、注意して正しく設定する必要がある。一つのベンチマークで注目すべき変数が複数ある場合が多いので、私はプログラムを表す文字列に (ASCII) や (whitelist) といったラベルを付けるようにしている。このラベルについては後述する。

自分でコードをいじるときは、新しいベンチマークを自分で書くことを推奨する。ベンチマークは benchsuite ファイルの前半部分にあり、コピペして改変するのは簡単なはずだ。新しいベンチマークを定義するだけで利用可能になる。ファイルの後半部分はベンチマークランナー本体なので、おそらく改変するべきではない。

環境

本記事で示されるベンチマーク結果を得るのに使われた実際の環境は Amazon EC2 の c3.2xlarge インスタンスである。このインスタンスは Ubuntu 16.04 を実行し、Xeon E5-2680 2.8 GHz CPU と 16 GB のメモリ、80 GB の SSD を持つ (コーパスは SSD に保存される)。これはコーパス全体が収まるだけのメモリである。インスタンスはベンチマークを実行するためだけに起動され、他にプログラムは実行されない。

システムのセットアップおよび検索ツールのインストールとベンチマークの実行に利用したコマンドの完全なログはここから確認できる。またベンチマークランナーの出力 (ネタバレ注意！) と生の出力もキャプチャしてある。生の出力には実行時間、完全なコマンドライン引数、それぞれのコマンドを実行するときに設定された環境変数がベンチマークごとに記録されている。

コード検索ベンチマーク

これはベンチマークの前半部分であり、大量のコードを含むレポジトリから特定のパターンを検索するエンドユーザーに対応する。

このベンチマークで使われるコーパスは Linux カーネル (コミット d0acc7) をチェックアウトしてビルドしたディレクトリである。Linux カーネルを実際にビルドするのは、ビルドによって検索に含めるべきでないファイルが大量に生まれるためだ。これは検索ツールが返す結果の適合度だけではなく性能にも影響する。

本節で実行結果が示されるベンチマークは全てレポジトリのルートで実行された。もし見たければ各コマンドの生の出力を確認できる。ベンチマークの名前は以降の節の名前に対応する。

ベンチマークが実行された EC2 インスタンスは VM を使っているので、メモリマップを利用する検索ツールが不利になる可能性があることには注意が必要である。そこで私は自分のローカルマシンでもベンチマークを実行した。このローカルマシンは 16 スレッド 3.2 GHz の Intel i7-6900K CPU と 64 GB のメモリ、SSD を持つ。このマシンだと ag が高速になることに気が付くだろう (ただそれでも ripgrep よりは遅い)。rg の結果が良く見えるように EC2 マシンの結果を使ったのではないかと思うかもしれないが、そうではないので安心してほしい。具体的に言うと、ローカルマシンで rg は一つを除く全てのベンチマークで他のツールを上回った。これに対して EC2 インスタンス上で rg はいくつかのベンチマークで他のツールに負けている。

前置きはこれくらいにして、ベンチマークを見ていこう。

linux_literal_default

説明: このベンチマークは各ツールのデフォルト設定で単純なリテラル検索を実行したときの実行時間を比較する。これはツールの「そのままの」設定を比較するベンチマークであり、不公平なのは意図的である。

パターン: PM_RESUME

結果:

rg         0.349 +/- 0.104 (lines: 16)
ag         1.589 +/- 0.009 (lines: 16)
ucg        0.218 +/- 0.007 (lines: 16)*+
pt         0.462 +/- 0.012 (lines: 16)
sift       0.352 +/- 0.018 (lines: 16)
git grep   0.342 +/- 0.005 (lines: 16)

解析: まず各ツールが行う処理を説明する:

このベンチマークからはまず、性能という観点からは検索ツールのナイーブな比較が全く公平でないことが分かる。ただ結果の適合度について話をするなら、この比較は非常に重要な意味を持つ。sift および grep -r は全てのファイルから文字列を検索して返すので、このベンチマークで試した他のツールとかなり異なる哲学を持つ: 他のツールはユーザーが気にするであろうファイルだけを検索対象とする。例えば .git フォルダの中身をユーザーはおそらく気にしない (sift の哲学が間違っているわけではない。明らかに sift はユーザーに自分で検索を設定させるようにしており、その方式には利点と欠点がある)。

性能に関して言うと、注意しておくべき重要な変数が二つある。この二つの変数はこれからのベンチマークで何度も登場する:

.gitignore をサポートすると全体の検索が遅くなる具体的な理由は次の通りである:

これと比べると、ucg が採用するホワイトリスト方式は高速に実装しやすい。考えるべき glob の集合が最初に分かるので、ファイルツリーの走査中に追加のチェックは必要にならない。さらに glob の多くは *.ext の形をしているので、そういった glob をまとめておけばファイルパスの拡張子を見るだけで効率的にマッチが判定できる。

ホワイトリスト方式の欠点は明らかだ: ucg に伝えていない拡張子のファイルに対しては検索結果が得られない可能性がある。ucg に新しい拡張子を伝えることはいつでもできるものの、「知らないことを知らないこと (unknown unknown)」には気付けない (検索した方がいいことを知らないと何もできない)。

linux_literal

説明: このベンチマークが実行するクエリは linux_literal_default と同じだが、ここでは公平な比較ができるよう設定を調整してある。具体的に言うと、ripgrep は二つのモードで実行される: .gitignore を解釈するモード (ラベル (ingore) に対応) と、ホワイトリストを使って .gitignore を無視するモード (ラベル (whitelist) に対応) である。一つ目のモードは rg, pt, sift, git grep と比較でき、二つ目のモードは ucg と比較できる。また ag と同様に検索でメモリマップを使うよう明示的に指示した rg も実行している。sift は .gitignore を解釈し、バイナリファイル、隠しファイル、PDF ファイルを無視する設定で実行される。また全てのコマンドは行数をカウントする (ag と ucg が行数カウントの無効化をサポートしないため)。

パターン: PM_RESUME

結果:

rg (ignore)          0.334 +/- 0.053 (lines: 16)
rg (ignore) (mmap)   1.611 +/- 0.009 (lines: 16)
ag (ignore) (mmap)   1.588 +/- 0.011 (lines: 16)
pt (ignore)          0.456 +/- 0.025 (lines: 16)
sift (ignore)        0.630 +/- 0.004 (lines: 16)
git grep (ignore)    0.345 +/- 0.007 (lines: 16)
rg (whitelist)       0.228 +/- 0.042 (lines: 16)+
ucg (whitelist)      0.218 +/- 0.007 (lines: 16)*

解析: このベンチマークからはたくさんのことを読み取れる。

まず、(ignore) と (whitelist) を比べると rg の性能が大きく変化しているのが分かる。linux_literal_default で行った解析を繰り返すことはしないが、rg をホワイトリストモードに切り替えると実行速度は ucg と同程度になる。

次に、ベンチマークしたツールの中だと ripgrep が最速だと前に言ったにもかかわらず、ucg は rg (whitelist) と同程度に高速であり、git grep (ignore) は rg (ignore) と同程度に高速である。ここから ucg, git grep, rg は大きなレポジトリからプレーンなリテラルを検索するとき同じような速度となることが分かる。以降のベンチマークでは速度の差異が分かりやすく現れる。ただ、ucg が速いのはなぜだろうか？

git grep についてはどうだろうか？ git grep の主な性能上の利点はディレクトリツリーを歩き回る必要がないことであり、これによって時間を大きく節約できる。また git grep の正規表現エンジンも非常に高速で、GNU grep および Rust の正規表現エンジンや RE2 と同様の方式で (DFA を使って) 動作する。

sift と pt はどちらも ripgrep と同じような性能を示している。実は sift と pt は .gitignore を解釈しながらも並列に行えるディレクトリ走査を実装しており、これが速度が出ている理由だと思われる。ただ以降のベンチマークで見るように、ここでの sift と pt の速度はミスリーディングである。具体的には、この二つのツールが速いのはパターンがリテラルであるために Go の正規表現エンジンを使っていないためだ (この点は後で詳しく議論する)。

最後に、The Silver Searcher はどうしたのだろうか？ 本当に他のツールのどれよりもあれほど遅いのか？ 鍵となるのは、The Silver Searcher がメモリマップを使うことで検索を遅くしている事実だ。メモリマップがあっても検索は速くならない (README にある主張とは正反対である)。

OK、少し時間を取って、この結果が意味することについて話そう。まず、それぞれの検索ツールが実際にどのように動作するかを考える必要がある。一般に言って、検索ツールがディスク上のファイルを検索する方法は二つある:

  1. ファイルをメモリマップして、ファイル全体が連続するメモリ領域に存在するかのような状態にしてから検索をまとめて行う。ファイルをメモリの連続領域にあるかのように見せる処理はオペレーティングシステムが裏で行ってくれる。二つ目のアプローチと比べると、このアプローチは非常に簡単に実装できる。
  2. ...あるいは中間バッファをアロケートして、固定サイズのバイトブロックをそこに読み込んで検索を行うという処理を繰り返すこともできる。バッファが行の途中で終わる可能性があるので、このアプローチは実装の難易度が恐ろしく高い。さらに一行がバッファより長くなる可能性も考慮しなければならない。最後に、マッチの前後の行 (「文脈」) を表示する機能を (grep や ripgrep と同様に) サポートしたい場合は、バッファの先頭でマッチが起こったときでも一つ前のバッファのデータが正しく出力されるように追加でデータの管理が必要になる。

ナイーブに考えると、明らかに一つ目のアプローチが速いように思える。二つ目のアプローチではデータのコピーや管理が必要だから、ずっと遅いに決まってるじゃないか！ しかし実際には、この考え方は全く正しくない。一つ目のアプローチだとプログラマーはデータの管理をせずに済むかもしれないが、メモリマップを行うために Linux カーネル内部で起きるデータ管理処理は非常に多い (リンク先はかなり古いメーリングリストの投稿だが、現在でも同じことが言える)。

ripgrep を書き始めたとき、私はメモリマップのアプローチを使っていた。中間バッファを使う二つ目の道を試してみようと思うまでには長い時間がかかった (CPU プロファイルや strace からはメモリマップに時間がかかっていることが分からなかったからだ) ものの、プロトタイプを実装するとすぐにメモリマップのアプローチより速いことが判明した。

ただそうは言っても、メモリマップに良い所が何もないわけではない。今考えている「数千個の小さなファイルを開いてスキャンし、すぐに閉じる」という処理に対してはたまたま相性が悪かっただけだ。別の処理、例えば「巨大なファイルを開いて、一度だけ検索する」といった処理ではメモリマップの方が優れる。これは後で見る単一ファイルのベンチマークで実際に確認できる。

この結論を支える重要なデータ点が rg (ignore) と rg (ignore) (mmap) である。具体的に言えば、この二つでは検索の戦略だけが異なるので、メモリマップが問題であることがほぼ決定的になる。

さらに言っておくと、メモリマップの性能は環境によって大きく変化するので rg (ignore) と rg (ignore) (mmap) はミスリーディングである可能性がある。特にベンチマークを実行する EC2 インスタンス c3.2xlarge はおそらく仮想マシン上で実行されるので、メモリマップの性能に影響があると考えられる。これを検証するために、私は同じベンチマークを机の下にある私のマシン (16 スレッド 3.2 GHz の Intel i7-6900K CPU と 64 GB メモリ、そして SSD を持つ) で実行した。次に結果を示す:

rg (ignore)          0.156 +/- 0.006 (lines: 16)
rg (ignore) (mmap)   0.397 +/- 0.013 (lines: 16)
ag (ignore) (mmap)   0.444 +/- 0.016 (lines: 16)
pt (ignore)          0.159 +/- 0.008 (lines: 16)
sift (ignore)        0.344 +/- 0.002 (lines: 16)
git grep (ignore)    0.195 +/- 0.023 (lines: 16)
rg (whitelist)       0.108 +/- 0.005 (lines: 16)*+
ucg (whitelist)      0.165 +/- 0.005 (lines: 16)

ここでも rg (ignore) は rg (ignore) (mmap) より高速であり、メモリマップに関する先ほどの結論はこのデータからも支持される。ただ rg (ignore) と rg (ignore) (mmap) の違いは少し小さくなったようだ！

linux_literal_casei

説明: このベンチマークは基本的に linux_literal と同様で、検索ツールに大文字と小文字を同一視する検索 (case insensitive search) を行うよう伝えている点だけが異なる。

パターン: PM_RESUME (加えて -i フラグを設定する)

結果:

rg (ignore)          0.345 +/- 0.073 (lines: 370)
rg (ignore) (mmap)   1.612 +/- 0.011 (lines: 370)
ag (ignore) (mmap)   1.609 +/- 0.015 (lines: 370)
pt (ignore)          17.204 +/- 0.126 (lines: 370)
sift (ignore)        0.805 +/- 0.005 (lines: 370)
git grep (ignore)    0.343 +/- 0.007 (lines: 370)
rg (whitelist)       0.222 +/- 0.021 (lines: 370)+
ucg (whitelist)      0.217 +/- 0.006 (lines: 370)*

解析: 一つ前のベンチマークとの最も大きな違いは、pt が次に遅いツールより一桁遅くなっていることだ。

pt がこれほど遅くなったのはなぜだろうか？ 特に、sift と pt はどちらも Go の regexp パッケージで検索を行っているのに、片方だけが格段に遅くなりもう一方は少ししか遅くなっていないのはどうしてだろうか？ 実は大文字と小文字を同一視する検索を示す -i フラグを pt が検出すると、Go の regexp エンジンに i フラグが設定される。そのため、例えば CLI から pt -i foo と起動すると (?i)foo という Go の正規表現が生成され、正規表現エンジンが大文字と小文字を同一視する検索を行う。

これに対して、-i を検出した sift は別の道を行く: sift はパターンと検索するバイトの両方を小文字に変換してから検索を行う。一つ前の linux_literal からの性能低下が sift で小さい主な理由は検索対象の文字列全てに対するこのフィルタであると思われる (正確に言うとこの最適化は正しくないことも言及に値するだろう。バイトごとの変換では ASCII の大文字と小文字しか考慮されないからだ。Go の正規表現エンジンを利用する pt は Unicode の大文字と小文字を完全にサポートする)。

ただそれでも疑問は残る。Go の正規表現エンジンはそれほど遅いのだろうか？ 残念ながら、その通りである。Go の正規表現エンジンは全ての検索で線形の最悪実行時間を保証する (そのため一部の正規表現とコーパスに対しては PCRE2 より指数的に高速になる) ものの、実際の実装はあまり成熟していないようだ。実際、有限オートマトンベースの高速な正規表現エンジンで私が知っているものはどれも DFA エンジンの一種を実装する。例えば GNU grep, Google の RE2, Rust の正規表現ライブラリはどれも実装している。しかし Go の正規表現エンジンは実装していない (ただ DFA エンジンを実装する作業は進行中なので、将来 pt は何もしなくてもこのベンチマークの結果が改善するかもしれない！)。

次の話題に移る前に説明したいことがもう一つある。rg, ag, git grep, ucg の性能は一つ前のベンチマークからほとんど変化がない。大文字と小文字を同一視する検索ではオーバーヘッドがいくらか生じるはずではないだろうか？ この疑問への解答は込み入っており、それぞれのツールが内部に持つ正規表現エンジンに関して私が持っているより深い知識が必要になる。ただ幸いにも、Rust の正規表現エンジンについては私が答えられる。

ここで重要な洞察として、大文字と小文字を区別する PM_RESUME の検索は PM_RESUME の大文字と小文字を入れ替えて得られる全ての文字列の大文字と小文字を同一視する検索と等しい。例えば今考えている検索は PM_RESUME|pM_RESUME|Pm_RESUME|PM_rESUME|... といった形の正規表現の検索に等しい。ただもちろん、大文字と小文字を入れ替えて得られる文字列は (たとえ今考えている短いリテラルであっても) 非常に数が多くなる。ここで鍵となる事実は入れ替えた文字列の接頭辞が簡単に取り出せる事実である。Rust の正規表現エンジンが入れ替えた文字列の接頭辞として取り出す文字列を次に示す (この情報は rg に --debug フラグを渡すと stderr に表示される):

PM_RE
PM_Re
PM_rE
PM_re
Pm_RE
Pm_Re
Pm_rE
Pm_re
pM_RE
pM_Re
pM_rE
pM_re
pm_RE
pm_Re
pm_rE
pm_re

(この処理には Unicode サポートが組み込まれているので安心してほしい。例えば S の大文字と小文字を同一視する検索では S, s, ſ のリテラルが取り出される。)

大文字と小文字を入れ替えたリテラルが手に入ったら、何ができるだろうか？ 古典的な解答 (Aho-Corasick など) は DFA にコンパイルして検索対象のテキストを高速にスキップするというものだ。テキストがリテラルのどれかにマッチすると、正規表現エンジンが起動してマッチの検証が行われる。この方法だと速度が劣る正規表現エンジンを検索対象のテキスト全体に対して実行せずに済む。

ただし、Rust の正規表現エンジンはこの処理に Aho-Corasick を使っていない。SIMD アクセラレーションが有効なとき (本記事のベンチマーク、および私が配布しているバイナリでは有効になっている)、Teddy と呼ばれる特別な多パターン検索アルゴリズムが使われる。Teddy は未発表であり、Intel の正規表現ライブラリ Hyperscan の一部として Geoffrey Langdale によって開発された。このアルゴリズムはリテラルがマッチする可能性のある位置を packed comparison により一度に 16 バイトずつ判定する。私は Hyperscan プロジェクトに含まれるこのアルゴリズムを採用し、Rust に移植した。README に詳しい解説を書いてあるので、気になる人は読んでほしい。

このベンチマークでは Teddy があっても特に得るものはないものの、以降のベンチマークでは大きな性能向上が得られる。

linux_word

説明: このベンチマークでは PM_RESUME をもう一度使う。ただ今回は -w フラグを各ツールに渡す。この -w フラグを付けるとき、「単語」だけがマッチとして報告される。ここで「単語」とは単語境界で始まり単語境界で終わる文字の並びであり、単語境界とは検索対象のテキストで単語文字と非単語文字が隣接する箇所を言う。

パターン: PM_RESUME (加えて -w フラグを設定する)

結果:

rg (ignore)         0.362 +/- 0.080 (lines: 6)
ag (ignore)         1.603 +/- 0.009 (lines: 6)
pt (ignore)         14.417 +/- 0.144 (lines: 6)
sift (ignore)       7.840 +/- 0.123 (lines: 6)
git grep (ignore)   0.341 +/- 0.005 (lines: 6)
rg (whitelist)      0.220 +/- 0.026 (lines: 6)*+
ucg (whitelist)     0.221 +/- 0.007 (lines: 6)

解析: この結果は linux_literal および linux_literal_casei と大きくは変わらない。一番に記しておくべきは -w フラグが性能に大きな影響を及ぼさないことだが、それ以外にも言及したいことがある。

rg は Unicode 的に正しい単語境界を認識するのに対して、他のツールは全て ASCII の単語境界だけしか認識しない (git grep ではシステムロケールを調整すると Unicode の単語境界を使うようにできる。このベンチマークでは ASCII の単語境界を利用する)。

一つ前のベンチマークと比べると、pt と sift だけが実行速度を大きく落としている。この理由は pt が linux_literal_casei で遅くなったのと同じで、Go の正規表現ライブラリがボトルネックになる。pt と sift では最初にリテラル PM_RESUME を検索して、そこで見つかったマッチが単語境界にあるかどうかを判定させることで性能を改善できるはずだ。こうしても Go の regexp ライブラリは使われるかもしれないが、その頻度は低くて済む。

linux_unicode_word

説明: このベンチマークは Ah (アンペア時) に接頭辞を付けた文字列を検索する単純なクエリの速度を測定する。例えば mAh (ミリアンペア時) や µAh (マイクロアンペア時) がマッチする。これが興味深い理由は Unicode に対応するとき \w が µ にマッチしなければならず、ASCII だけに対応するときマッチしてはいけないことだ。ここでも .gitignore を解釈するかどうかを制御する。

パターン: \wAh

結果:

rg (ignore)                 0.355 +/- 0.073 (lines: 186)
rg (ignore) (ASCII)         0.329 +/- 0.060 (lines: 174)
ag (ignore) (ASCII)         1.774 +/- 0.011 (lines: 174)
pt (ignore) (ASCII)         14.180 +/- 0.180 (lines: 174)
sift (ignore) (ASCII)       11.087 +/- 0.108 (lines: 174)
git grep (ignore)           13.045 +/- 0.008 (lines: 186)
git grep (ignore) (ASCII)   2.991 +/- 0.004 (lines: 174)
rg (whitelist)              0.235 +/- 0.031 (lines: 180)
rg (whitelist) (ASCII)      0.225 +/- 0.023 (lines: 168)*+
ucg (ASCII)                 0.229 +/- 0.007 (lines: 168)

解析: このベンチマークでは新しい変数が導入される: Unicode サポートを有効にするかどうかである。Unicode を解釈する検索は ASCII だけを解釈する検索よりいくつか多いマッチを報告する。

このベンチマークで考えているツールの中では rg と git grep だけが Unicode サポートの切り替えに対応する。Unicode サポートはパターン内でフラグを通して設定される (例えば \w は Unicode をサポートし、(?-u)\w はサポートしない)。また git grep では Unicode サポートを環境変数 LC_ALL を通して有効にできる (en_US.UTF-8 だと有効になり、C だと無効になる)。より一般的に言うと git grep の Unicode サポートはシステムロケールと一致するようになっているので、LC_ALL を設定するのはハックの一種と言える。

しかし問題はさらに深い。Unicode サポートの切り替えに対応する rg と git grep だけであるだけではなく、そもそも Unicode をサポートするツールがこの二つしかない。ag, pt, sift, ucg では文字クラス \w が必ず ASCII 文字だけから構成される (pt と sift では Go の regexp ライブラリが Unicode を解釈する \w に対応していない。ag と ucg では PCRE に Unicode をサポートするフラグが存在するものの、ツールがその機能に対応していない)。

このベンチマークで注目すべき重要な結果は、Unicode サポートを有効にしたとき git grep では性能が大きく低下するのに対して、rg では目立った性能低下が見られないことだ。もちろん rg (ignore) と git grep (ignore) は同じ個数のマッチを報告している。

一つ前のベンチマークと同様に、pt と sift はリテラル Ah を最初に検索してから Go の regexp ライブラリでマッチを検証することで高速化ができるはずだ。

ベンチマークの結果を見ると、重要な疑問が二つ思い浮かぶ:

  1. git grep (ignore) (ASCII) が rg (ignore) (ASCII) より格段に遅いのはなぜか？ また直接比較できるわけではないものの、git grep (ignore) (ASCII) は ucg (ASCII) と比べても遅くなっている。
  2. rg (ignore) (Unicode を解釈する検索) が rg (ignore) (ASCII) (Unicode を解釈しない検索) と同程度に高速なのはなぜか？

私は一つ目の疑問に対するはっきりとした解答を持ち合わせていない。ただ少なくとも rg について言えば、rg はパターンから取り出した接尾辞のリテラル Ah を使ってマッチの候補を見つけてから接頭辞 \w を検索している。GNU grep は同様の洗練されたリテラル抽出処理を持つものの、git grep はリテラルを見つける処理にそこまで力を入れないようだ (私は git grep のソースコードを軽く読んだだけなので、間違っている可能性もある)。

ucg に関しては、PCRE2 が rg と似たリテラル最適化を行っているものと思われる。

二つ目の疑問には幸いずっと簡単に答えられる。鍵となるトリックは rg 自体ではなく rg が使う正規表現ライブラリの内部にある。具体的に言うと、この正規表現エンジンはUTF-8 デコーディングを有限オートマトンに組み込む (このトリックは最初 Ken Thompson によって提案され、その後 Russ Cox によって詳しく説明された)。こうしたとき高速になるのは、追加のデコーディングステップが必要にならないためだ。UTF-8 でエンコードされたバイト列に正規表現を一バイトずつ直接マッチさせることができる。UTF-8 として不当なバイト列があっても問題は起こらない: 有限オートマトンはそのバイト列を認識しないだけで、マッチは起こらずそのまま処理が進む。

これに対して、git grep (および GNU grep) は \w といった Unicode を解釈する機能が有効なとき全く異なるコードでマッチが判定される。公平のため言っておくと、git grep は UTF-8 以外のテキストエンコーディングを処理できるのに対して、現在の rg は UTF-8 (および「ASCII 互換な」テキストエンコーディング) しか扱えない。

linux_re_literal_suffix

説明: このベンチマークではリテラルで終わる単純な正規表現パターンを使った検索の性能が測定される。ここでも .gitignore を解釈するかどうかを制御する。

パターン: [A-Z]+_RESUME

結果:

rg (ignore)         0.318 +/- 0.034 (lines: 1652)
ag (ignore)         1.899 +/- 0.008 (lines: 1652)
pt (ignore)         13.713 +/- 0.241 (lines: 1652)
sift (ignore)       10.172 +/- 0.186 (lines: 1652)
git grep (ignore)   1.108 +/- 0.004 (lines: 1652)
rg (whitelist)      0.221 +/- 0.022 (lines: 1630)*+
ucg (whitelist)     0.301 +/- 0.001 (lines: 1630)

解析: このベンチマークから分かる新しいことは特にない。これまでのベンチマークで見たことがまた現れている。具体的には、rg と ucg はどちらも非常に高速であり、pt と sift では Go の regexp ライブラリがボトルネックとなり、git grep は linux_unicode_word と同様に性能が低下している (git grep の性能が落ちる理由も同じだろうと私は考えている)。最後に、ag はメモリマップを使っているために性能が優れない。

rg はパターンから取り出したリテラルの接尾辞 _RESUME を最初に検索することで、テキスト全体に対する正規表現を避けている。ucg もまず間違いなく PCRE2 を通して同じ最適化を行っており、パターンが多少複雑になってもこれらのツールで性能が落ちない理由はこれで説明できる。rg が少しだけ ucg より速いのは、内部の正規表現ライブラリによるリテラル検索方式の違いによると思われる。

linux_alternates

説明: このベンチマークでは四つのリテラルの和集合を検索する。最適化を難しくするために、四つのリテラルは異なる文字から始まるようにしてある。

パターン: ERR_SYS|PME_TURN_OFF|LINK_REQ_RST|CFG_BME_EVT

結果:

rg (ignore)         0.351 +/- 0.074 (lines: 68)
ag (ignore)         1.747 +/- 0.005 (lines: 68)
git grep (ignore)   0.501 +/- 0.003 (lines: 68)
rg (whitelist)      0.216 +/- 0.031 (lines: 68)+
ucg (whitelist)     0.214 +/- 0.008 (lines: 68)*

解析: パターンは単純なリテラルではなくなったが、ここでもまた rg と ucg が高い速度を達成している。今回のパターンではマッチの候補を高速に見つけるのに使えるリテラルは一つも存在しない。それでも優れた正規表現エンジンは検索を高速化する方法を見つけている。

rg について言えば、四つのリテラルを検出した rg は SIMD を利用する多文字列検索アルゴリズム Teddy を使った検索に切り替える (Teddy については linux_literal_casei でも説明した)。実はこのパターンの検索では正規表現エンジンが全く使われない。和集合に含まれるリテラルのマッチがどれもパターン全体のマッチとなることに正規表現エンジンは気が付くので、検証ステップは飛ばされる。これによってリテラルの和集合の検索は非常に高速となる。

linux_alternates_casei

説明: このベンチマークは基本的に linux_alternates と同じで、大文字と小文字と区別しない検索を指示する -i フラグを設定した点だけが異なる。git grep は高速に実行できるように ASCII モードで実行した。

パターン: ERR_SYS|PME_TURN_OFF|LINK_REQ_RST|CFG_BME_EVT (加えて -i フラグを設定する)

結果:

rg (ignore)         0.391 +/- 0.078 (lines: 160)
ag (ignore)         1.968 +/- 0.009 (lines: 160)
git grep (ignore)   2.018 +/- 0.006 (lines: 160)
rg (whitelist)      0.222 +/- 0.001 (lines: 160)*+
ucg (whitelist)     0.522 +/- 0.002 (lines: 160)

解析: 大文字と小文字を同一視するフラグを設定したときの結果を linux_alterates の結果と比較すると、ツールごとに様子が大きく異なるのが分かる。例えば git grep は四倍遅くなっており、ucg さえ二倍遅くなっている。これに対して rg の速度はほぼ変わらない！

rg の秘密は linux_alternates と同じく Teddy アルゴリズムである。トリックは大文字と小文字を同一視するリテラルの集合を Teddy アルゴリズムが利用できる通常のリテラルの (大きな) 集合に変換する方法にある。実は、この処理は linux_literal_casei で説明したのと全く同じように進む: リテラルに含まれる各文字を大文字および小文字に入れ替えて得られる文字列全体の集合が計算され、それを使ってマッチの候補が検索される。この集合は非常に大きくなる可能性があるので、実際には各文字列の接頭辞に対して大文字と小文字を入れ替えた集合が使われる。今考えているパターンであれば、Rust の正規表現ライブラリは次の文字列集合を計算する (この情報は rg に --debug フラグを渡すと stderr に表示される):

CFG_
CFg_
CfG_
Cfg_
ERR_
ERr_
ErR_
Err_
LIN
LIn
LiN
Lin
PME_
PMe_
PmE_
Pme_
cFG_
cFg_
cfG_
cfg_
eRR_
eRr_
erR_
err_
lIN
lIn
liN
lin
pME_
pMe_
pmE_
pme_

この文字列集合が Teddy アルゴリズムの入力となり、検索対象のテキストに含まれるマッチの候補が素早く特定される。マッチの候補が必ずマッチになるわけではないので、候補には検証が必要になる。完全な正規表現エンジンはここで初めて呼び出される。

linux_unicode_greek

説明: このベンチマークは Unicode で定義される符号位置のクラスを表す正規表現を使ったときの性能を測定する。Rust の正規表現エンジンと Go の正規表現エンジンはどちらもネイティブにこの機能をサポートし、他のツールはサポートしない。

パターン: \p{Greek} (任意のギリシャ文字にマッチする)

rg     0.414 +/- 0.021 (lines: 23)*+
pt     12.745 +/- 0.166 (lines: 23)
sift   7.767 +/- 0.264 (lines: 23)

解析: このベンチマークは非常に単純である。rg が使う Rust の正規表現エンジンは \p{Greek} を決定的有限オートマトンに変換する。これに対して Go の正規表現エンジン (pt と sift が使うもの) も有限オートマトンを使うのだが、こちらでは非決定的なシミュレーションが使われる。二つのアプローチの決定的な違いは、前者ではオートマトンが任意の時点で一つの状態しか取らないのに対して、後者では常に複数の状態を管理する必要が生じることだ。

linux_unicode_greek_casei

設定: このベンチマークは基本的に linux_unicode_greek と同じだが、大文字と小文字を同一視する検索を行うフラグを設定する。このクエリは少し風変わりではあるものの、rg の優れた Unicode サポートを示すには都合がいい。

パターン: \p{Greek} (加えて -i フラグを設定する)

rg     0.425 +/- 0.027 (lines: 103)
pt     12.612 +/- 0.217 (lines: 23)
sift   0.002 +/- 0.000 (lines: 0)*+

解析: sift は rg より優れているわけではない: sift は検索リクエストを正しく認識できず、諦めてマッチを報告せずに終わっている。pt は検索を行っているようだが、大文字と小文字の判定が Unicode に即していない。これに対して rg はリクエストを正しく処理しており、それでいて高速である。

rg において、大文字と小文字を含む Greek カテゴリ全体を検索するこのパターンは高速に実行できる単一の有限オートマトンにコンパイルされる。

この検索に関して興味深いのが、実行すると µ が含まれる結果が多く報告されることだ。この文字は大文字と小文字を区別する検索で報告される μ と同じではない。予想が付いたかもしれないが、この二つの文字は同じ見た目を持つものの、Unicode 符号位置としては異なる:

後者の符号位置は \p{Greek} グループに含まれるものの、前者の符号位置は含まれない (Linux カーネルでは前者を使うのが正しいようだ)。しかし Unicode simple case folding tables によると MICRO SIGN は GREEK SMALL LETTER MU にマップされる。そのため -i が指定されるとき、それ自身は Greek グループに入っていない MICRO SIGN も rg によって検出される。

linux_no_literal

説明: これは Linux カーネルに対する最後のベンチマークであり、linux_unicode_greek_casei と同様少し風変わりなパターンを利用する。具体的には「一つ以上の空白文字で区切られた五文字の単語が五つ並ぶ文字列」を検索する。本記事の他のベンチマークで使うパターンとの重要な違いは、このパターンがリテラルを全く含まないことだ。\w と \s には Unicode 的な解釈と ASCII 的な解釈があるので、このベンチマークでは Unicode サポートの有無も制御する。

パターン: \w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}

結果:

rg (ignore)                 0.577 +/- 0.003 (lines: 490)
rg (ignore) (ASCII)         0.416 +/- 0.025 (lines: 490)
ag (ignore) (ASCII)         2.339 +/- 0.010 (lines: 766)
pt (ignore) (ASCII)         22.066 +/- 0.057 (lines: 490)
sift (ignore) (ASCII)       25.563 +/- 0.108 (lines: 490)
git grep (ignore)           26.382 +/- 0.044 (lines: 490)
git grep (ignore) (ASCII)   4.153 +/- 0.010 (lines: 490)
rg (whitelist)              0.503 +/- 0.011 (lines: 419)
rg (whitelist) (ASCII)      0.343 +/- 0.038 (lines: 419)*+
ucg (whitelist) (ASCII)     1.130 +/- 0.003 (lines: 416)

解析: このパターンはリテラルを一つも含まないので、検索の性能は内部の正規表現エンジンだけに依存する。入力を賢くスキップすることはできず、全体を正規表現エンジンに通さなければならない。私の経験上リテラルを全く含まないパターンは非常に稀なので、このベンチマークは内部の正規表現エンジンの動作をテストする人工的な手立てとして存在する。

他のツールと比較すると、rg は .gitignore の解釈の有無、Unicode サポートの有無に関わらず非常に高い性能を示している。特に git grep は Unicode をサポートするとき実行時間が 6 倍になっているのに対して、rg は 1.3 倍程度しか遅くなっていない。興味深いことに、ucg は Unicode サポートを持たないにもかかわらず、PCRE2 の JIT を使っても rg より遅くなっている！

なぜ rg はこれほど速いのだろうか？ 具体的には何が 30 % の性能低下を引き起こしたのだろうか？

このベンチマークで rg が高速な理由は、Unicode に注目した他のベンチマークで rg が高速な理由と同じである: UTF-8 のデコード処理を決定的有限オートマトンに直接コンパイルするためだ。これは検索対象のテキストを最初 Unicode の符号位置にデコードする追加ステップが必要にならないことを意味する。生のバイトに対して直接マッチを判定できる。

大ざっぱに言うと、30% の性能低下はパターンとのマッチを判定するのに使う DFA のコンパイル処理で生じる。Unicode サポートが有効なときの DFA は ASCII だけを考えるときの DFA よりずっと大きい。だいたいのサイズの違いを実感してもらうために、具体的な数字を示しておく:

(この数字は Rust の正規表現ライブラリ内部のコンパイラから直接取り出されたものであり、必ずしも最小のオートマトンを表すわけではない。)

こういったパターンから作成される DFA が同じ数の状態を持つとは限らない。なぜなら、通常 DFA の状態は複数の NFA の状態に対応するからだ (Wikipedia の Powerset construction のページを読むことを勧める。Rust の正規表現エンジンでは異なる実装戦略が使われるものの、直感的な理解が得られるだろう)。

しかし、この説明は少し誤解を生じさせかねない点がある。Rust の正規表現エンジンは事前処理としてコンパイルフェーズを持つものの、そこには NFA を DFA に変換する処理が含まれない。実はこの処理を実際に行うと指数的な時間が必要になる可能性がある！ その代わり、Rust の正規表現エンジンは検索対象のテキストを見ていきながらその場で (on the fly に) DFA を構築する。このとき ASCII のパターンでは NFA の状態が非常に少ないのでその構築にはほとんど時間がかからない。しかし Unicode のパターンでは NFA の状態が非常に多いので、新しい DFA 状態のコンパイルに長い時間がかかる (私は perf が生成するプロファイルを調べることでこれを確認した)。さらに深く調べると、ここで実際に起こることはもっと入り組んでいるかもしれない。例えば、このベンチマークでは大部分が ASCII 文字からなる同じ文字列を Unicode のパターンおよび ASCII のパターンで検索するので、二つのパターンで DFA の状態の個数はほぼ同じになると思われる。つまり性能の低下は個々の DFA 状態のコンパイル時間が長くなったことによるものであるに違いない。そのため Unicode のパターンにおける DFA の状態は (ASCII のパターンにおける DFA の状態より) 多くの NFA の状態を含むはずである。検索対象のテキストの組成を検索するより前に知ることはできないので、これより効率的な検索方法は明らかでない (もちろん Unicode の \w をもっと小さい集合に置き換えることならできる)。

これを改善するアイデアとして、異なる種類の DFA を用意する方法が考えられる。例えば最初は ASCII のみに対応した DFA を使ってマッチを行い、その途中で ASCII でないバイトを検出したら Unicode に対応する DFA に遷移するということだ。ただ性能の低下は非常に小さいので、これを実装することで生じる複雑さを正当化するのは難しい！

単一ファイルのベンチマーク

ベンチマークの後半部分ではギアを変えて、単一の巨大なファイルに対する検索ツールの性能を詳しく見ていく。それぞれのベンチマークは OpenSubtitles2016 データセットから取った英語とロシア語の二つのサンプルに対して実行される。もちろん英語のサンプルは大部分がアルファベット (ASCII 文字) から構成され、ロシア語のサンプルは大部分がキリル文字から構成される。ロシア語のサンプルを検索するときのパターンは英語のパターンから Google 翻訳を使って翻訳された (残念ながら私はロシア語が読めないのだが、検索を自分で試して結果を英語に翻訳することで似た文章が検索できていることを確認した)。英語のサンプルは約 1 GB で、ロシア語のサンプルは約 1.6 GB である。

このベンチマークでは内部の正規表現エンジンとリテラル最適化の性能がずっと大きな影響を持つ。私たちが制御しなければならない重要な変数として、行数カウントと Unicode サポートがある。基本的に各ツールには行数をカウントしないように要請するが、The Silver Searcher と Universal Code Grep は行数カウントの無効化をサポートしない。Unicode サポートは一部のベンチマークで制御が難しくなる: ripgrep は非 ASCII 文字列で検索するとき ASCII 文字についてだけ大文字と小文字を同一視する検索をサポートしないためだ。必ず Unicode の意味での大文字と小文字の区別が使われ、それを無効化する手立てが存在しない。後で見るように、少なくとも ripgrep に関して言えば、Unicode の意味での大文字と小文字の同一視をサポートしたとしても ASCII に設定した他のツールより速くなる。

Linux カーネルを使ったベンチマークと同様に、実行したコマンドと記録実行時間の生データは github から確認できる。

ripgrep はこのラウンドでも性能と正確性の両方で他のツールを大きく上回る。

subtitles_literal

説明: このベンチマークは単一のリテラル文字列の検索という最も単純なケースの性能を測定する。(lines) とラベルの付いた結果は出力に行数を加える -n フラグ (またはそれと同じ意味のフラグ) を付けたときの結果を表す。

英語のパターン: Sherlock Holmes

結果:

rg             0.268 +/- 0.000 (lines: 629)*+
rg (no mmap)   0.336 +/- 0.001 (lines: 629)
pt             3.433 +/- 0.002 (lines: 629)
sift           0.326 +/- 0.002 (lines: 629)
grep           0.516 +/- 0.001 (lines: 629)
rg (lines)     0.595 +/- 0.001 (lines: 629)
ag (lines)     2.730 +/- 0.003 (lines: 629)
ucg (lines)    0.745 +/- 0.001 (lines: 629)
pt (lines)     3.434 +/- 0.005 (lines: 629)
sift (lines)   0.756 +/- 0.002 (lines: 629)
grep (lines)   0.969 +/- 0.001 (lines: 629)

ロシア語のパターン: Шерлок Холмс

結果:

rg             0.325 +/- 0.001 (lines: 583)*+
rg (no mmap)   0.452 +/- 0.002 (lines: 583)
pt             12.917 +/- 0.009 (lines: 583)
sift           16.418 +/- 0.008 (lines: 583)
grep           0.780 +/- 0.001 (lines: 583)
rg (lines)     0.926 +/- 0.001 (lines: 583)
ag (lines)     4.481 +/- 0.003 (lines: 583)
ucg (lines)    1.889 +/- 0.004 (lines: 583)
pt (lines)     12.935 +/- 0.011 (lines: 583)
sift (lines)   17.177 +/- 0.010 (lines: 583)
grep (lines)   1.300 +/- 0.003 (lines: 583)

解析: 全ての検索ツールは内部の正規表現エンジンの一部あるいは検索ツール自身の一部としてリテラル最適化を行う。ag はパターンを調べ、正規表現の特殊文字が使われていなければ Boyer-Moore の亜種を使って PCRE を使わずに検索を行う。GNU grep も同様の最適化を行うが、大きな改善が可能だと指摘されている。

もしこれが本当なら、rg が GNU grep より倍近く高速なのはどうしてだろうか？ さて、何よりもまず、sift と ucg も GNU grep より速いことに注目しよう。私は PCRE2 の JIT をよく理解していないので ucg の速さについて詳しく説明できない。ただ rg と sift が GNU grep より速い理由ははっきりしている:

リテラル検索の秘密がこれで明らかになった。次はロシア語のパターンで性能の差が生じる理由を詳しく調べよう。答えはここでもスキャンに使うバイトにある。sift と pt はどちらも Go のランタイムに含まれる AVX2 ルーチンを利用する。であればどうして、ロシア語で検索するときこの二つのツールの性能が他のツールより大きく落ちているのだろうか？ この疑問の答えは検索したパターン Шерлок Холмс を UTF-8 でエンコードしたときのバイト列を見ると明らかになる:

\xd0\xa8\xd0\xb5\xd1\x80\xd0\xbb\xd0\xbe\xd0\xba \xd0\xa5\xd0\xbe\xd0\xbb\xd0\xbc\xd1\x81

このバイト列から分かる重要な事実が二つある:

  1. パターン Шерлок Холмс に含まれる全ての文字は二つの UTF-8 符号単位でエンコードされる。二つの UTF-8 符号単位は二バイトに対応する。
  2. 全ての文字は \xD0 または \xD1 で始まる。

検索対象のロシア語字幕の UTF-8 バイト列を見ると、全く同じパターンが並んでいるのが確認できる。このパターンが生じるのはファイルのほとんどがキリル文字で書かれており、キリル文字の大部分が Unicode で小さな範囲を占めるためだ。これは検索対象の文章に \xD0 と \xD1 が大量に出現することを意味する。

上述の説明を思い出せば、Go の正規表現エンジンはパターンの一つ目のバイトを使ってスキャンを行う。しかし、もし今の例のように一つ目のバイトが検索対象のテキストに頻繁に表れるようなことがあると、スキャンのオーバーヘッドが上昇して検索全体が遅くなってしまう。これは memchr を使うとき避けられないトレードオフである。

予想できたかもしれないが、rg は出現頻度の低いバイトを推測することでこの問題を回避する。rg は事前に計算された 256 個のバイトそれぞれの頻度を記した表から引いた値を使う。例えば \xD0 や \xD1 といったバイトは頻度が高いとみなされ、\xA8 や \x81 といったバイトは頻度が低いとみなされる。そのため rg は \xD0 と \xD1 を避け、これら以外のバイトを memchr に渡す。

GNU grep がこのベンチマークで優れた性能を示すのはほぼ偶然と言える: Boyer-Moore が選択する最後のバイト \x81 がたまたま \xD0 や \xD1 より格段に優れるためだ。

ギアを変えて、メモリマップについても少し話しておくべきだろう。このベンチマークでは rg が rg (no mmap) を 25% ほど上回っている。この二つの唯一の違いは、前者がファイルをメモリ上にメモリマップするのに対して、後者はファイルを少しずつ中間バッファに読み込むという点だ。このベンチマークではファイルが一つだけでメモリマップのオーバーヘッドが非常に小さいためにこういった結果となる。これは前半の Linux カーネルを使ったベンチマークとは正反対の結果である。Linux カーネルの検索では検索対象の全てのファイルに対して新しくメモリマップを作成しなければならずオーバーヘッドが大きくなるので、中間バッファを使った方が高速だった。rg は経験的なアプローチを取り、検索するファイルが数個だけならメモリマップを使って、そうでなければ中間バッファを使って検索を行う。

最後にもう一つ: (lines) についてはこれといって言うべきことがないので、特に話さなかった。行数のカウントには追加で処理が必要であり、カウントしなくていいならその処理を飛ばせるというだけだ。行数カウントのために ucg はかなり洗練された SIMD アルゴリズムを持っており、rg も先述した memchr の実装に似た packed comoparison を利用するアルゴリズムを持つ。

私の好きにできるなら、行数カウントを有効にしたベンチマークは削除してしまうだろう。どのツールも多少の処理を追加することで安定して行数カウントを行えているからだ。ただ ag と ucg では行数カウントを無効にできないので、公平な比較のため他のツールで行数カウントを有効にした計測も行わなければならない。

subtitles_literal_casei

説明: このベンチマークは基本的に subtitles_literal と同様で、大文字と小文字を同一視する検索を行う点だけが異なる。(lines) のラベルが付いたツールは行数を表示し、(ASCII) のラベルが付いたツールは ASCII だけを認識する検索を行う。逆に (ASCII) が付いていないツールでは Unicode を認識する検索が行われる。

英語のパターン: Sherlock Holmes (加えて -i をフラグを設定する)

rg                    0.366 +/- 0.001 (lines: 642)*+
grep                  4.084 +/- 0.005 (lines: 642)
grep (ASCII)          0.614 +/- 0.001 (lines: 642)
rg (lines)            0.696 +/- 0.002 (lines: 642)
ag (lines) (ASCII)    2.775 +/- 0.004 (lines: 642)
ucg (lines) (ASCII)   0.841 +/- 0.002 (lines: 642)

ロシア語のパターン: Шерлок Холмс

rg                    1.131 +/- 0.001 (lines: 604)
grep                  8.187 +/- 0.006 (lines: 604)
grep (ASCII)          0.785 +/- 0.001 (lines: 583)
rg (lines)            1.733 +/- 0.002 (lines: 604)
ag (lines) (ASCII)    0.729 +/- 0.001 (lines: 0)*+
ucg (lines) (ASCII)   1.896 +/- 0.005 (lines: 583)

解析: rg の Unicode サポートの素晴らしさが明らかになるので、このベンチマークは興味深い。rg の結果は正確であるだけではなく、高速でもある。他のツールが ASCII だけを認識する検索を行うときと比べたとしても rg の方が速い。

英語のパターンに対する結果を見よう。まず分かることとして、GNU grep では Unicode をサポートする大文字と小文字を区別しない検索が非常に高くついている。ここで GNU grep が直面している問題は、簡単で高速な Boyer-Moore による検索が行えないために他のリテラル検索アルゴリズムあるいは完全な正規表現エンジンにフォールバックすることだ。GNU grep は ASCII だけを認識する大文字と小文字を区別する検索ではずっと高速になるものの、rg の Unicode を認識する大文字と小文字を区別しない検索はその速度を軽々と上回る。

このベンチマークで rg が高速な理由は linux_literal_casei と同様である: rg は Sherlock Holmes というパターンに含まれる各文字を Unicode の simple case folding rules に従って変化させて得られる文字列を考え、それぞれの短い接頭辞からなる集合を検索する。今の例であれば次の集合が検索される:

SHER
SHEr
SHeR
SHer
ShER
ShEr
SheR
Sher
sHER
sHEr
sHeR
sHer
shER
shEr
sheR
sher
ſHER
ſHEr
ſHeR
ſHer
ſhER
ſhEr
ſheR
ſher

(長い S (ſ) が含まれていることに注目してほしい。これは Unicode 的に正しい。)

このリテラルの集合はその後 SIMD を使った複数パターン検索アルゴリズム Teddy に入力される。このアルゴリズムは未発表であり、Intel の正規表現ライブラリ Hyperscan の一部として Geoffrey Langdale によって開発された。このアルゴリズムはリテラルがマッチする可能性のある位置を packed comparison により一度に 16 バイトずつ判定する。私は Hyperscan プロジェクトに含まれるこのアルゴリズムを採用し、Rust に移植した。README に詳しい解説を書いたので、気になる人は読んでほしい。

ロシア語のパターンに対する結果でも同じことが言えるが、それ以外にもいくつか興味深いことがある。まず grep (ASCII) は非常に高速であるものの、パターンが ASCII 文字列ではないので明らかに -i は無視されている。よく見ると、測定結果は一つ前の subtitles_literal ベンチマークとほぼ同一なことが分かる。もう一つ興味深いのは、ag が 0 個のマッチを報告していることだ。これが全く理解できない動作というわけではない: 「Unicode をサポートしない状態で非 ASCII 文字列を大文字と小文字を区別せずに検索せよ」という要求は実現不可能だと ag が判断したのかもしれない。おそらくは PCRE (例えば pcre_exec) で起きたエラーがユーザーに表示されていないだけだと思うが、これは全くの当て推量だ。

subtitles_alternate

説明: このベンチマークではいくつかのリテラルからなる集合を検索する速度を計測する。それぞれのリテラルは異なる接頭バイトを持つ。行数カウントも有無も制御する。

英語のパターン: Sherlock Holmes|John Watson|Irene Adler|Inspector Lestrade|Professor Moriarty

rg             0.294 +/- 0.001 (lines: 848)*+
grep           2.955 +/- 0.003 (lines: 848)
rg (lines)     0.619 +/- 0.001 (lines: 848)
ag (lines)     3.757 +/- 0.001 (lines: 848)
ucg (lines)    1.479 +/- 0.002 (lines: 848)
grep (lines)   3.412 +/- 0.004 (lines: 848)

ロシア語のパターン: Шерлок Холмс|Джон Уотсон|Ирен Адлер|инспектор Лестрейд|профессор Мориарти

rg             1.300 +/- 0.002 (lines: 691)*+
grep           7.994 +/- 0.017 (lines: 691)
rg (lines)     1.902 +/- 0.002 (lines: 691)
ag (lines)     5.892 +/- 0.003 (lines: 691)
ucg (lines)    2.864 +/- 0.006 (lines: 691)
grep (lines)   8.511 +/- 0.005 (lines: 691)

解析: このベンチマークでは英語とロシア語の両方で rg が非常に優れている。これは subtitles_literal_casei の解析で説明した Teddy アルゴリズムによるところが大きい。特に英語のパターンでは rg が GNU grep より一桁近く高速になっている。

結果からは行数を数える処理の性能に与えるコストもよく分かる。少なくとも rg では、行数を数えると検索時間が倍程度になる。

ベンチマークの説明でも述べたように、検索するリテラルはそれぞれ異なる接頭バイトを持つことに注意してほしい。これは正規表現エンジンが共通の接頭バイトを検出し、それに対して memchr を実行する最適化を避けるためにある。この最適化はもちろん重要で rg も行うものの、それより少しだけ複雑なケースに対するベンチマークを行った方がずっと有用な情報が得られる。

subtitles_alternate_casei

説明: このベンチマークは基本的に subtitles_alternate と同様だが、大文字と小文字を同一視する検索を行う点が唯一異なる。またここでは行数を数える処理の有無ではなく Unicode サポートの有無を制御する (全てのコマンドで行数を数えるものとする)。

英語のパターン: Sherlock Holmes|John Watson|Irene Adler|Inspector Lestrade|Professor Moriarty (加えて -i フラグを設定する)

rg             2.724 +/- 0.002 (lines: 862)*+
grep           5.125 +/- 0.006 (lines: 862)
ag (ASCII)     5.170 +/- 0.004 (lines: 862)
ucg (ASCII)    3.453 +/- 0.005 (lines: 862)
grep (ASCII)   4.537 +/- 0.025 (lines: 862)

ロシア語のパターン: Шерлок Холмс|Джон Уотсон|Ирен Адлер|инспектор Лестрейд|профессор Мориарти

rg             4.834 +/- 0.004 (lines: 735)
grep           8.729 +/- 0.004 (lines: 735)
ag (ASCII)     5.891 +/- 0.001 (lines: 691)
ucg (ASCII)    2.868 +/- 0.005 (lines: 691)*+
grep (ASCII)   8.572 +/- 0.009 (lines: 691)

解析: rg の速度は他のツールを (Unicode をサポートしないものさえも) 大きく上回るものの、subtitles_alternate と比べると一桁遅くなっている。このベンチマークが示す重要な事実は Teddy アルゴリズムの限界である。実はこのベンチマークで rg は Teddy の性能が優れないだろうと判断し、Teddy を利用しない。

Teddy が高速にならないのはなぜだろうか？ この疑問への答えは検索するパターンから生成されるリテラルの集合にある。rg は Unicode の simple case folding rules に従ってマッチする可能性のあるリテラルを全て生成し、それらの接頭辞を取ることで扱える量まで検索すべきリテラルを減らす。この例では次の 48 個のリテラルを使ったリテラル検索が行われる:

INS
INs
INſ
IRE
IRe
InS
Ins
Inſ
IrE
Ire
JOH
JOh
JoH
Joh
PRO
PRo
PrO
Pro
SHE
SHe
ShE
She
iNS
iNs
iNſ
iRE
iRe
inS
ins
inſ
irE
ire
jOH
jOh
joH
joh
pRO
pRo
prO
pro
sHE
sHe
shE
she
ſHE
ſHe
ſhE
ſhe

これらのリテラルを全て Teddy に渡すと、Teddy は圧倒されてしまう。具体的な話をしよう。Teddy はマッチの候補を非常に高速に見つけることで動作する。そのため見つかるマッチ候補の個数とマッチの個数が同程度なら、Teddy はとても高速に動作する。しかし Teddy に入力するリテラルの個数が増えるとマッチでないマッチ候補を見つける可能性が高くなり、マッチの検証に費やされる時間が増えてしまう。

(Teddy の実装に関してさらに細かい特徴を言っておくと、リテラルの個数を増やすとたとえ生成されるマッチ候補の個数が変わらない場合でも検証のコストが増加する。先述したように、もし Teddy について詳しい説明が必要なら実装にある詳細なコメントを確認してほしい。Teddy に関してさらに細かいことを説明するにはブログ記事がもう一つ必要になるだろう！)

リテラルの個数が多いことを検出したときに rg が取れる手段は次の二つだ:

  1. リテラルの集合をさらに小さくする。例えば今考えている例であれば、接頭辞の最後の文字を削除すれば集合はずっと小さくなる。しかし残念ながら、こうしても手に入るのは二文字のリテラルからなるそれなりに大きい集合であり、加えてリテラルが短いので偽陽性が増えてしまう。
  2. Aho-Corasick などの異なる多パターン検索アルゴリズムを使う。

以前に一つ目の選択肢を実装したことがあるのだが、どうしても「モグラ叩き」になってしまうようだった。何らかの一般的なケースを速くできても、他の一般的なケースが大きく遅くなってしまう。このような場合は平均的な性能に優れるアプローチが上手く行くことが多い。幸い Aho-Corasick はまさにこの特徴を持つ。

ただ Aho-Corasick を教科書通りに実装すれば済むわけではない。例えば多くの Aho-Corasick 実装は失敗遷移を後方ポインタに設定したトライを構築するが、これより優れた方法が存在する。失敗遷移を DFA にコンパイルし、そのとき遷移テーブルをメモリの連続領域に置くことができる。こうすると入力の各バイトが遷移テーブルを一度だけ見て次の状態を調べる処理に対応する。バイトを一つ読んだときにポインタをたどったり失敗遷移をいくつも行う必要はない。

もちろん、この遷移テーブルベースのアプローチはメモリを多く消費する。必要なメモリ量は number_of_literals * number_of_states に比例し、number_of_states は全リテラルのバイト数にほぼ等しい。長さ 3 のリテラル 48 個は Teddy では多すぎるのに対して、Aho-Corasick ならメモリを多く必要とする遷移テーブルベースのアプローチを使ったとしても軽々と扱える (参考: Aho-Corasick のこの実装は専門的な文献で Advanced Aho-Corasick と呼ばれることが多い)。

subtitles_surrounding_words

説明: このベンチマークは単語に囲まれた Holmes というリテラル文字列を検索する。このパターンは接頭辞と接尾辞に関するリテラル最適化を起こさないように作ってある。

英語のパターン: \w+\s+Holmes\s+\w+

rg             0.605 +/- 0.000 (lines: 317)
grep           1.286 +/- 0.002 (lines: 317)
rg (ASCII)     0.602 +/- 0.000 (lines: 317)*+
ag (ASCII)     11.663 +/- 0.008 (lines: 323)
ucg (ASCII)    4.690 +/- 0.002 (lines: 317)
grep (ASCII)   1.276 +/- 0.002 (lines: 317)

ロシア語のパターン: \w+\s+Холмс\s+\w+

rg             0.957 +/- 0.001 (lines: 278)*+
grep           1.660 +/- 0.002 (lines: 278)
ag (ASCII)     2.411 +/- 0.001 (lines: 0)
ucg (ASCII)    2.980 +/- 0.002 (lines: 0)
grep (ASCII)   1.596 +/- 0.003 (lines: 0)

解析: このベンチマークで優れた成績を収めるには、いわゆる「内部リテラル最適化 (inner literal optimization)」が検索ツールに必要となる。この最適化が何を意味するかは想像がつくだろう: パターン内の任意の位置に出現するリテラル文字列を見つけ、それが全てのマッチに現れるかどうかを判定し、もしそうなら完全な正規表現ではなくそのリテラルを検索対象の文字列から高速に見つけ出す最適化が内部リテラル最適化と呼ばれる。

内部リテラル最適化が正しく動作する上で鍵となるのは多くの検索ツールが結果を行ごとに報告するという事実である。例えば今回のベンチマークで使った \w+\s+Holmes\s+\w+ というパターンを検索するなら、最初に Holmes というリテラルが含まれる行を検索し、そこから行の始まりと終わりを検索してその行だけに対して完全なパターンの検索を行って構わない。取り出された内部リテラルの頻度が低いときは検索のほとんどを正規表現エンジンを使わずに行える。それからもちろん、内部リテラルがコーパスに全く現れないとき正規表現エンジンは一度も起動されない。

内部リテラル最適化を完全に行うには、パターンをパースして抽象構文木 (abstract syntax tree, AST) を作ってから内部リテラルを取り出す必要がある。これより単純なヒューリスティックでもおそらくは大きな速度向上が得られるものの、内部リテラル最適化をロバストに行うには実際にパーサーを使うしかないことは指摘に値する。ここでの問題は多くの正規表現エンジンでパターンのパースは公開されない実装詳細となっていることだ。このとき検索ツールは正規表現からリテラルを取り出すために独自にパーサーを書かなければないが、現代的な正規表現パーサーは簡単に書けるものではない！ 幸い Rust では正規表現ライブラリが公開する追加ライブラリ regex-syntax が完全なパーサーを提供する。rg は regex-syntax の手を借りることで比較的簡単に内部リテラル最適化を実装している。これに対して、GNU grep が同じ最適化を実装できるのは検索ツールと内部の正規表現エンジンが密に結合しているためだ。

内部リテラル最適化を検索ツールが行うのはどうしてだろうか？ 内部の正規表現エンジンが行わないのはなぜ？ この疑問について私は長いこと頭を悩ませているのだが、納得いく答えが見つかっていない。一番の問題は内部リテラルを見つけたときに完全な正規表現の検索をどこから始めるべきかが分からないことだ。汎用の正規表現エンジンではパターンが任意に長い文字列とマッチする可能性がある。例えば \w+\s+Holmes\s+\w+ が数ギガバイトのドキュメントの最後にしかマッチしないこともある。完全なマッチを見つける問題を解決する方法はいくつかある。例えば正規表現を三つの部分 \w+\s+, Holmes, \s+\w+ に分解し、リテラル Holmes を見つけるたびにリテラルの先頭から \w+\s+ を後ろに向かって検索してマッチの先頭を特定し、さらにリテラルの末尾から \s+\w+ を前に向かって検索することでマッチの末尾を特定する方法が考えられる。この方法の大きな問題は最悪ケースで振る舞いが二次関数的になることだ (\w+\s+ あるいは \s+\w+ の検索で既に見た文字列をもう一度スキャンする必要が生じる可能性がある)。この問題を線形時間の保証付きで汎用的に解決することは可能だろうと私は思っているものの、優れた解決法は見つけられていない。

このベンチマークの結果から判断すると、rg と GNU grep だけが内部リテラル最適化を行っている。ag と ucg はどちらもパターン内部のリテラルを取り出して検索を高速化することはなく、PCRE もそこまで賢いことを行わないようだ (もちろん Rust の正規表現ライブラリも行わない。この最適化は rg の側で行われる)。

ロシア語のパターンに対する結果を見ると、Unicode をきちんとサポートするツールでのみクエリが正しく処理されていることが分かる。この理由は ucg と ag では \w が ASCII 文字だけからなるために、ロシア語のサンプルに含まれるほぼ全ての単語文字 (キリル文字) とマッチしないためである。この二つ以外の rg と GNU grep はどちらも高速なままであり、これは主に内部リテラル最適化による。

subtitles_no_literal

説明: このベンチマークでは意図的にリテラルを含まないパターンを使って検索を行う。エンドユーザーが検索するパターンはたいていの場合リテラルを含むので、このパターンは少し奇妙と言えるものの、内部の正規表現エンジンの一般的な性能を測定するには適している。

英語のパターン: \w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}

rg             2.777 +/- 0.003 (lines: 13)
rg (ASCII)     2.541 +/- 0.005 (lines: 13)*+
ag (ASCII)     10.076 +/- 0.005 (lines: 48)
ucg (ASCII)    7.771 +/- 0.004 (lines: 13)
grep (ASCII)   4.411 +/- 0.004 (lines: 13)

ロシア語のパターン: \w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}\s+\w{5}

rg             4.905 +/- 0.003 (lines: 41)
rg (ASCII)     3.973 +/- 0.002 (lines: 0)
ag (ASCII)     2.395 +/- 0.004 (lines: 0)*+
ucg (ASCII)    3.006 +/- 0.005 (lines: 0)
grep (ASCII)   2.483 +/- 0.005 (lines: 0)

解析: ここでも rg と同程度の成績を収めたツールは存在しない。英語のパターンに対する rg と rg (ASCII) の結果を比べると、rg では Unicode がサポートされるにもかかわらず二つは非常に似た性能を示すのが分かる。

このベンチマークで rg が GNU grep より高速になった具体的な理由はなんだろうか？ どちらのツールも最終的には DFA を使ってパターンを検索するので、ほぼ同じ性能が得られるはずだ。この疑問に対するはっきりとした答えを私は持ち合わせていない。GNU grep と rg はどちらも正規表現ライブラリが DFA のインナーループを展開し、状態を on the fly に計算する。ただ理由の推測はできる。

Rust の正規表現ライブラリでは状態の遷移でポインタのデリファレンスが一回分少なくなるように DFA が実装されている。具体的な処理は複雑だが、状態を表すのに単純なインクリメンタル ID ではなく遷移テーブルに対する添え字を使うことで実装される。この工夫があると遷移先の位置を単純な加算で計算でき、この計算はアドレッシングモードを使った単一の命令で行える (特に、この最適化があるとき状態の遷移を計算するのに乗算が必要にならない)。「ポインタのデリファレンスが一度減る」というのは大したことない最適化に思えるかもしれないが、今回のような大きなコーパスの全てのバイトで起こる処理では大きな効果がある。

そういった細かなことはロシア語のパターンではそれほど重要にならない。GNU grep では検索に分単位の時間がかかっているためだ。この結果は GNU grep が UTF-8 のデコード処理を DFA に組み込んでおらず、その場で一文字ごとにデコードするといったオーバーヘッドの大きい処理を行っていることを示唆する。ただ私は GNU grep の処理を深く理解したわけではないので、このコストモデルが間違っている可能性もある。それから公正を期すために言っておくと、GNU grep のロケールおよびエンコーディングのサポートは rg のものを大きく上回る。ただ現在の世界では UTF-8 が広く普及しており、UTF-8 だけをサポートすれば十分なことも多い。さらに UTF-8 がこれだけ普及していることを考えれば、Unicode をサポートしたときでも実行を高速に保つことが重要である (GNU grep はこれができていない)。

残念ながら他のツールは Unicode をサポートしないので、ロシア語のパターンに対して意味のあるベンチマークが行えない。

ボーナスベンチマーク

この節では、これまでよりさらにおかしなベンチマークをいくつか見ていく。これらのベンチマークは公開されているスイートに含まれていない。結果を見れば分かるが、これらのベンチマークではツール間の性能差があまりにも大きくなって細かな解析が必要とならない場合も多い。さらに使われるパターンが一般的な使い方を代表するわけでもないので、性能の差はそれほど重要でない。ただ、そういった極端なパターンを rg がどれだけ上手く扱えるかを見るのはなかなか面白い。

everything

説明: このベンチマークでは、各ツールが全ての行をマッチとして報告するのにかかる時間を比較する。コマンドは Linux カーネルレポジトリのルートで実行された。

パターン: .*

rg                 1.081 (lines: 22065361)
ag                 1.660 (lines: 55939)
git grep           3.448 (lines: 22066395)
sift             110.018 (lines: 22190112)
pt                 0.245 (lines: 3027)
rg (whitelist)     0.987 (lines: 20936584)
ucg (whitelist)    5.558 (lines: 23163359)

解析: 全ての行が報告される検索をユーザーが行うことはおそらく決してないので、ある意味このベンチマークは馬鹿げている。ただマッチが膨大なときでも rg が問題なくスケールすることを確認するのにはちょうどいい。

このベンチマークのような場合に優れた正規表現エンジンが行う工夫の一つとして、ユーザーがマッチの有無だけを気にしているときはマッチを一つでも見つけた時点で次の検索に移るというものがある。今の例であれば、検索ツールは各行の先頭でマッチを見つけ、検索を中断し、次の行の始まりまで進んでから検索を再開できる。rg と Rust の正規表現ライブラリはどちらも .* に対して特別に用意された最適化を持たない (しようと思えば実装はできる)。

興味深いことに、ar と pt はいずれも全ての行を報告していない。マッチ数に何らかの制限があるようだ。これが不合理な挙動というわけでは必ずしもない。結局 ar や pt は検索ツールなのだから、大量に見つかった結果を全て報告しても役に立たないだろうと判断されてもおかしくはない。

nothing

説明: これは everything の逆であり、結果を一行も報告しないのが正しい挙動となる。このベンチマークも Linux カーネルレポジトリのルートで実行された。

パターン: .* (加えて -v フラグあるいは --invert-match フラグを設定する)

rg                0.302 (lines: 0)
ag                数分
git grep          0.905 (lines: 0)
sift             12.804 (lines: 0)
pt                -----
rg (whitelist)    0.251 (lines: 0)
ucg (whitelist)   -----

解析: このベンチマークは一つ前の everything よりさらに奇妙なこと (「全てをマッチとして見つけて、何も報告しないでくれ」) を要求しており、他のツールの欠点や省略されている処理が明らかになる。具体的に挙げると、ag はマッチを逆転させると一気に実行が遅くなる。また pt と ucg はマッチの逆転をそもそもサポートしない。sift は前回のベンチマークにおける汚名を挽回している (おそらくマッチの出力に関連するオーバーヘッドが大きいのだろう)。rg と git grep は問題なく処理を行えている。

context

説明 このベンチマークはマッチの文脈 (マッチ前後の行) を表示する機能の性能を計測する。具体的には、各ツールに全てのマッチの前後それぞれ二行を表示させる。英語の字幕コーパスを行数をカウントする状態で検索した。

パターン: Sherlock Holmes (加えて --context 2 フラグを設定する)

rg        0.612 (lines: 3533)
ag        3.530 (lines: 3533)
grep      1.075 (lines: 3533)
sift      0.717 (lines: 3533)
pt       17.331 (lines: 2981)
ucg       -----

解析: ここでも rg は優れた性能を見せているが、sift との差はかなり小さい。一般に文脈の計算は稀に (マッチごとに一度) しか起こらないのでコストは大きくならないはずである。ただ ag と pt は性能を大きく落としている。また pt はバグがあるようだ (文脈を正しく実装するのは難しいので理解できることではある)。最後に、ucg は文脈の機能をサポートしないためベンチマークしていない。

huge

説明: このベンチマークでは単純なリテラル検索を 9.3GB のファイルに対して行う。実はこのファイルは英語の字幕コーパス全体である (ベンチマークスイートでは 1GB のサンプルを取っていた)。

パターン: Sherlock Holmes

rg                1.786 (lines: 5107)
grep              5.119 (lines: 5107)
sift              3.047 (lines: 5107)
pt               14.966 (lines: 5107)
rg (lines)        4.467 (lines: 5107)
ag (lines)       19.132 (lines: 5107)
grep (lines)      9.213 (lines: 5107)
sift (lines)      6.303 (lines: 5107)
pt (lines)       15.485 (lines: 5107)
ucg (lines)       4.843 (lines: 1543)

解析: 一見すると行数カウントが有効なとき ucg の速度が rg と同程度かのように見える。しかし ucg は間違った結果を返している！ ucg では 2GB を超えるファイルの検索で問題が起きているのではないかと私は疑っている。

もう一つ興味深いのが、sift が高速であるにもかかわらず pt が行数をカウントしないときでさえ遅いことだ。sift と pt はどちらも Go の regexp に含まれる正規表現エンジンを使っており、単純なリテラルなら高速に検索できるはずである。pt が遅い理由は明らかでない。行数をカウントせよと伝えないときでもカウントした上で無視している可能性が仮説の一つとして考えられる。

まとめ

私はこのブログ記事の最初で、次の主張を裏付ける証拠を示すと書いた:

私は最初の主張を実証するためにまず有名なレポジトリ (Linux カーネル) に対してエンドユーザーが入力するであろう様々なパターンを使ったベンチマークを行った。全てのベンチマークで rg がトップになったわけではないものの、明らかに rg より優れると言えるツールは存在しなかった。例えば git grep は単純なパターンで rg より数ミリ秒だけ速くなることがあったものの、パターンが複雑になる (特に Unicode サポートを有効になる) と rg が git grep よりずっと高速になる (linux_unicode_word のように速度が一桁違うこともある)。rg が git grep と同程度の、The Silver Searcher を上回る速度を達成できた理由は次の通りである:

続いて単一の大きなファイルに対する rg と他のツールのベンチマーク結果も示した。こちらでは rg が全てのベンチマークでトップであり、他のツールを大きく引き離すことも多かった。この結果には次の最適化が影響している:

二つ目の主張を実証するために、Unicode の simple case folding rules や Unicode に対応した文字クラス \w といった機能を正しく実装できているかどうかを確かめるベンチマークを示した。Unicode を正しく扱えるツールは rg, GNU grep, git grep のみだった。また GNU grep と git grep の性能は Unicode を完全にサポートすると非常に低くなるのに対して rg の性能はほとんど落ちなかった。

三つ目の主張を実証するために、メモリマップの有無を制御した rg のベンチマークをいくつか示した。具体的にはメモリマップを有効にした状態と無効にした状態で rg の性能を計測し、(少なくとも Linux x86_64 では) たくさんの小さなファイルを並列に検索するときはメモリマップを使うと性能が落ちるのに対して、単一の大きなファイルを検索するときはメモリマップを使うと性能が向上することを見た。また VM の中ではメモリマップに追加でオーバーヘッドが生じることも分かった。

私の願いはこの記事を読んだ読者が rg は非常に高速だと納得することだけではない。それより重要なこととして、それぞれのベンチマークに対して行った解析から読者が何かを学ぶことを願っている。文字列検索は情報科学で古くからある問題であるものの、真に最先端の文字列検索ツールを書くには膨大な手間が必要となる。

広告
このページの文章はテキストゆれないくんを使って校正されました。