egrep と fgrep の性能比較

英文テキストから、 ランダムに選んだ複数の英単語のどれかを含む行を抽出する時間を測ってみる例。

計測環境

• Sun SparcStation5
• NetBSD-1.3
• GNU grep v2.0。古典的な egrep の多くでは、選択(|)で接続できるパターンの上限がかなり小さい。よって、そもそもこういう実験ができないのである。
• 対象英文テキストは、Programmers' Supplementary Document 中の pmake の tutorial を 10 回繰り返したもの。約 1.5MBytes あった。
• time(1) コマンドで要した CPU 時間(system time + user time)を計測。 ５回実行して平均を取った。
• 実験に使った実際のプログラム

計測結果

パターンで指定した単語数の増加に従って、 使った CPU 時間がどのように変化したかを以下に示す。

単語数が多くなるにつれ、 Aho-Corasick アルゴリズムを採用している fgrep の方が有利になることが観察できる。

参考文献

• lazy transition evaluation や egrep/fgrep の比較についての Netnews への投稿記事。