どうしてGNU Grepは高速なのか

この記事は アルゴリズム Advent Calendar 2015 24日目の記事です。 あまりアルゴリズムらしい話題でもないですがGNU grepがどうして高速なのかという話について大して詳しくもないですが最近知ったので書きます。

決して最近の投稿ではないですがwhy GNU grep is fastという投稿がFreeBSDのメーリングリストにありました。これはGNU grepの最初の作者のMike Haertelによる投稿で、当時幾つか解説記事も書かれました。FreeBSDのgrepよりGNUのgrepの方がかなり速い(今の速度は知らないですが当時はだいぶ違ったみたいです)みたいで、どうしてGNU grepが速いかということを書いた投稿です。

とりあえず前提知識について確認しておきます。grepは文字列中で正規表現を探索するプログラムで、伝統的にはThompsonのアルゴリズムでオートマトンを求めてマッチします。fgrepは文字列中で文字列を探索するプログラムで、伝統的にはAho-Corasick法で求めます。これらのアルゴリズムについてはここでは特に説明しません。

さて、本題に戻ります。この投稿によるとGNU grepではこんなことが速さの秘訣みたいです。

• すべてのバイトを読むことなく処理している
• 各バイトについて実行される命令数を少なくしている

そりゃ速くなりそうということが書かれていますがどうやってこれを実行しているのかが問題です。アルゴリズム的でない点としては例えばstdio.hにある標準関数ではなくmmapなどのシステムコールを直接叩いて入力についてはバッファリングしていないようです。また、例えばa$のような正規表現はa\nに書き換えることで読み込みを行単位でなくて済むようにしています。他にもループアンローリングとかまあやりそうな最適化はやっているらしいです。

さて、これはアルゴリズムアドベントカレンダーの記事なのでアルゴリズム的な話に触れます。主にすべてのバイトを読むことなく処理しているという点に効きます。原文ではこんな感じの内容です。

GNU grep uses heuristics to look for a fixed string that any string
matching the regex *must* contain, and uses that fixed string as the
bases for its initial Boyer-Moore search.

For example if your regex is /foo.*bar/, the initial Boyer-Moore search
is (probably) searching for foo.

GNU grepではBoyer-Mooreアルゴリズムを使っています。Boyer-Mooreアルゴリズムとは、検索対象の文字列(長さn)の中からキーの文字列(長さm)を探すアルゴリズムです。ナイーブに全探索で求めるとO(mn)になります。Boyer-Mooreアルゴリズムではキーの文字列に対して事前にあるアルゴリズムでテーブルを作り、そのテーブルにしたがって適宜文字を読み飛ばすことで高速に探索を行うことができます。文字の種類が多いというそこそこ現実的な条件で大体O(n)とかO(n/m)位の性能が出るようです。Boyer-Mooreアルゴリズムの詳細についてもここでは扱わないので調べてください。

ところでBoyer-Mooreアルゴリズムはgrepとは違って、文字列の中から正規表現ではなく文字列にマッチさせるアルゴリズムです。なのでナイーブに考えるとgrepというよりfgrepに使えそうなアルゴリズムです。GNU grepでは正規表現の中で含まれなければならない断片の固定文字列にマッチさせて、そこから正規表現マッチを行うというヒューリスティックを使っているらしいです。どうも単純にこのヒューリスティックを使っているだけでもなく、どうやら本当は色々な実装を組み合わせているらしいです。また、もっと複雑な正規表現の場合はそもそも難しいし滅多に使われないから多少遅くてもいいよねというヒューリスティック(?)の元で実装をしているらしいです(超訳)。

本当にそんな感じになっているのか気になるのでベンチマークを取ってみます。

$ time grep test /usr/share/dict/words > /dev/null

real    0m0.009s
user    0m0.007s
sys     0m0.000s

まず固定文字です。まあ速いです。

$ time grep tes.*t /usr/share/dict/words > /dev/null

real    0m0.010s
user    0m0.007s
sys     0m0.000s

多分BMでtesを探してからtを探します。固定文字とあまり時間が変わりません。固定文字部分がもう少し長いともっと速くなります。

$ time grep [a-z] /usr/share/dict/words  > /dev/null

real 0m0.074s
user 0m0.073s
sys 0m0.000s

$ time grep [A-Z] /usr/share/dict/words  > /dev/null

real 0m0.142s
user 0m0.137s
sys 0m0.003s

$ time grep [A-Z].*[A-Z] /usr/share/dict/words  > /dev/null

real    0m0.168s
user    0m0.163s
sys     0m0.003s

$ time grep [a-z].*[A-Z] /usr/share/dict/words  > /dev/null

real 0m0.337s
user 0m0.337s
sys 0m0.000s

３つ目の例では[A-Z]がなかなか見つからないので時間がかかっています。ひとつ目の[A-Z]もあまり見つからないので[A-Z]のみの場合とそこまで時間が変わらないです。４つ目の例になると[a-z]はほぼ常に見つかるのに[A-Z]がなかなか見つからないので時間がかかっています。[a-z]にかかる時間や[A-Z]にかかる時間と比べてかなり時間がかかっています。