インテル・AMDのCPUアーキテクトが明かす： GNU grep が速い理由

GNU grepの元祖作者がFreeBSD ハッカーをschoolしている。

http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

FreeBSD対GNU grepのパフォーマンスを議論していると思われるとことに「俺はgrepの初代作者だ」と名乗って現われた男がいる。

履歴書(http://duckytech.com/resume.pdf)を見ると、GNU coreutilsに貢献した後、インテルやAMDでCPUアーキテクトを勤めている男だ。これは話を聞いた方がよさそうだ。

FreeBSDユーザでもある彼はリストを観閲していたらたまたまGNU対BSDのgrep論争に当ってしまったようだ。BSDのリストにGNU grepの秘密を解く。

技1：全ての入力バイトを見ないから速い
技2：見るバイトに関しては極力少ないインストラクションを実行するから速い

GNU grepは有名な「Boyer-Mooreアルゴリズム」を使っている。これはターゲット文字列の最後のキャラクタをテーブルと照合し、できるだけ無用とわかったインプットと飛ばしていうものだ。

(Boyer-Mooreって言えば教科書には出ているが実用例はあまり見ないアルゴリズムだ。しかも、固定文字列のためのテクニックだと思っていたものが正規表現に使われているのはちょっと以外だった。)

GNU grepはさらにBoyer-Mooreの内loopを展開する。(「ループをunrollする」ってどう訳すんでしょう？) そしてBoyer-Mooreのテーブルを工夫することによって外ループで毎回当る終了テストを省けるようにしている。結果的にはそれぞれの入力バイトで平均３つ以下のx86インストラクションまで最適化されている。

Boyer-Mooreの最適化は「Andrew Hume and Daniel Sunday」を(原文)参照。

サーチが速くなったらIOを速くしなければいけない。

適切なシステムコールを使うことにより入力のコピーを避ける
改行でのライン折りを避ける

改行で区切るとなると全ての入力バイトを見ることになり、数倍遅くなる。なので、Boyer-Mooreでマッチを見付けた後で境界として必要な改行を探す。

GNU grepを書いた当時はLinuxやUNIXでread(2)をするとカーネル内で余分なコピーが行われていたので、mmapでインプットを読み込んでいた。最近はOSがreadによるこの余分なコピーを無くしたためか、mmapによる入力がディフォルトから外されている。しかし、--mapオプションでそれを呼び起すことができる。そしてそれが、今でも二割程のスピードアップを可能にすることを示している。 (原文参照)

まとめ

Boyer-Mooreを使い、内ループを展開(unroll)する
unbuffered IOでコピーを避ける。(出力のIOはあまり気にしない。少いから。)
マッチがみつかるまで\nを探すな
ページサイズや境界に合わせたバッファー管理によってカーネル内でのコピーも避ける

さすがCPUアーキテクト(になる人)がuser-landプログラムを最適化するとこうなるんだ。これを読んで少し俺のgrepも速くなった気がする。

おまけ：

hex fiend (http://ridiculousfish.com/hexfiend/)というマックプログラムの作者が「狡いUnixの賢者」と対決する
http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/
GNU grepに上記以外の「卑怯」な最適化があることを暴露する。けっこう笑える。