grep -Fifはなぜ遅くなったか
はじめに
GNU grepのメーリング・リストを見ていると、以下のようなコマンドが遅くなったという投稿が多数なされています。実際、マルチバイト・ロケールに設定した環境で、/usr/share/dict/linux.wordsのような大きなパターン文字列を指定してgrep -Fif patternを実行すると、grep 2.19以降では非常に遅く、かつ多くのメモリを消費します。
grep -Fif pattern input
なぜ遅くなったか
grep 2.19で加えられた性能改善の修正の影響です。grep 2.18までは、-Fiオプションが指定された場合、事前にパターン文字列と入力文字列の両方を小文字に変換し、変換後の文字列を用いて-iオプションがない場合と同様の手法でマッチングを行っていました。しかし、入力文字列が巨大な場合にそれを小文字に変換するコストが無視できない状況でした。
他方、grep 2.19でDFAに大幅な品質および性能の改善が加えられました。改善されたDFAを用いることで、-iオプションが指定されても事前に入力文字列を小文字に変換することなくマッチングが行えるようになりました。そこで、マルチバイト・ロケールに設定した環境ではgrep -FiもDFAを用いるように変更されました。しかし、その副作用としてパターン文字列が巨大な場合に処理が遅延するようになりました。
なぜrevert(元に戻す)されないか
GNU grepは広く使われているコマンドなので安定性重視です。そのため、一般的には既存環境へ負の影響が大きい修正は開発側の強い意志がない限りrevertされます。しかし、この修正はgrep 2.25でもrevertされていません。なぜでしょうか。
- 回避策がある
- 元々の実装に問題がある
回避策がある
この修正の影響を受けるのはあくまでマルチバイト・ロケールに設定した環境のみです。つまり、POSIXロケール(C)では処理遅延は発生しません。実際にメーリング・リストに不具合報告の投稿がなされた際も、開発側はPOSIXロケールに設定することで回避できることを案内しており、revertを含めた修正に対してやや消極的なコメントを出しています。
env LC_ALL=C grep -Fif pattern input
元々の実装に問題がある
「なぜ遅くなったか」でも述べたとおり、元々の実装は「事前にパターン文字列と入力文字列の両方を小文字に変換してから、-iオプションがない場合と同様の手法で-Fに対するアルゴリズムを用いてマッチングを行っていました。」でした。ところが、この実装には大きな問題がありました。それは、「ある文字のバイト数は、その文字の小文字と同じとは限らない」という仕様を全く考慮していなかったことです。*1
まず、小文字に変換した後の文字列のバッファを元の文字列と同じサイズ分しか確保していませんでした。マルチバイト文字の最大バイト数は4バイト(UTF-8)ですので、実際には1バイトの大文字を小文字に変換した場合に4バイトになることを考慮して、元の文字列のバッファの4倍のサイズで確保する必要がありました。
次に、元の文字列と小文字に変換した後の文字列で、各文字が現れるバイト位置(オフセット)が同じであると仮定していました。grepは入力文字列がパターン文字列にマッチした場合、マッチした箇所のバイト位置を記憶しておいて出力に用います。たとえば、cdというパターンとAbcdeという入力文字列があったとします。これをgrep --colorで検索するとします。この場合、入力文字列の3バイト目の位置でマッチするため、出力の際にも入力文字列の3バイト目から2バイトを色付けします。
ところが、Aの小文字(xとします)が2バイトのロケールで、-oオプションに加えて-iオプションを指定して、元々のアルゴリズムでマッチングするとどうなるでしょうか。最初に入力文字列のAbcdeを小文字に変換します。xbcdeになります。パターン文字列のcdも小文字に変換します。cdのままです。ここから、変換後のバッファを用いて-iオプションがない場合と同様にマッチングを行い、入力文字列の中からcdを見つけます。それは、xは2バイトのため4バイト目になります。そして、それをそのまま元の入力文字列に適用すると、元の文字列の4バイト目はdであるため、cdではなくdeが色付けされてしまいます。しかし、これでは結果不正です。
