最近リリースされたgrepを使用していて遅いと感じてる方は、最新版にアップグレードした方が良いかもしれません。
GNUプロジェクトは、8月14日(現地時間)、最近のgrepで発生していた「極端なパフォーマンスの低下」問題を修正した、GNU Grepの最新版v3.7をリリースしました(Phoronix)。
パターンの数が多すぎて、バケットの数が少なすぎると、N個のパターンの前処理に最低でもO(N-2)の時間がかかるというgrepのバグが修正されています。これまで何秒かかかっていたコマンドが1秒以下の処理時間に短縮され、コマンドによっては数日かかっていたものが数秒に短縮されるとのことです。
grep 3.7の詳細とダウンロードはGNU.orgから可能です。