GNU grep 2.19 リリース
5/23にGNU grep 2.19 がリリースされました。
GNU grep 2.19 の最大の目玉はパフォーマンスの改善です。今回のリリースはメディアには取り上げられませんでしたが、メディアに取り上げられたGNU grep 2.17 よりも、はるかに多くのパフォーマンスの改善がなされています。
特に注目すべき点は、マルチバイト・ロケールに対してはもちろん、シングルバイト・ロケールに対してもパフォーマンスの改善がなされていることです。少なくとも私の知る限りでは、GNUgrep 2.6以降でシングルバイト・ロケールに対するパフォーマンスの改善がなされたことありません。試しにシングルバイト・ロケールにおいて、Wikipedia 日本語版のデータベースを「Wikipedia」 で検索した結果、GNU grep 2.19 は従来のリリースよりも約10% 速く結果を返しました。また、Oracle Database をインストールしたディレクトリを、「Oracle」で検索した結果も同様でした。
それでは、主な改善点について、例をあげながら見て行くことにしましょう。
Boyer-Moore法 におけるワースト・ケースの改善
GNU grepは固定文字列の検索に対してBoyer-Moore 法を使用しますが、従来のリリースにおいては、ワースト・ケースに対するパフォーマンスがよくありませんでした。GNU grep 2.19では、Boyer-Moore 法の2 つのワースト・ケースに対してパフォーマンスの改善がなされています。
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k $ env LC_ALL=C time -p grep kjjjjjjjjjjjjjjjjjjj k grep-2.18: real 4.12 user 4.06 sys 0.05 grep-2.19: real 0.46 user 0.40 sys 0.05 <<★９倍高速化 $ env LC_ALL=C time -p grep jk k grep-2.18: real 1.45 user 1.41 sys 0.04 grep-2.19: real 0.09 user 0.02 sys 0.06 <<★１６倍高速化
DFA スーパーセットの利用
DFA スーパーセットとは、GNU grepが苦手とする後方参照 (「\1、「\2」など) や、マルチバイト・ロケールにおけるワイルドカード (「.」や [a-z] など) を省いた別の正規表現です。事前にDFA スーパーセットを使用して、マッチし得ない行をフィルタすることで、GNU grepが苦手としていたパターンに対するパフォーマンスが大きく改善されています。
$ yes abcdabc | head -50000000 >l $ env LC_ALL=C time -p grep '\(a\)bcd\1bd' l grep-2.18: ... slow extreamly ... grep-2.19: real 1.48 user 1.40 sys 0.07 <<★超高速化 $ env LC_ALL=ja_JP.eucjp time -p grep 'abcd.bd' l grep-2.18: ... slow extreamly ... grep-2.19: real 1.45 user 1.38 sys 0.07 <<★超高速化 $ env LC_ALL=ja_JP.eucjp time -p grep -i k k grep-2.18: real 13.27 user 13.17 sys 0.08 grep-2.19: real 1.40 user 1.33 sys 0.06 <<★９倍高速化
Boyer-Moore 法の-iオプションが利用されたケースへの適用
従来のリリースでは、-iオプションが利用された場合、[Tt][Ee][Ss][Tt]のような、同等の正規表現に置き換えて処理していました。GNU grep 2.19 では、シングルバイト・ロケールにおいて、ワースト・ケースが改善されより高速になったBoyer-Moore 法を使用します。*1
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k $ env LC_ALL=C time -p grep -i abc k grep-2.18: real 1.07 user 1.01 sys 0.05 grep-2.19: real 0.15 user 0.08 sys 0.06 <<★７倍高速化
行頭または行末指定を含む固定文字列検索の改善
従来のリリースでは、行頭「^」または行末「$」指定を含む固定文字列検索に対しては、Boyer-Moore 法とDFA*2の合わせ技で検索していました。GNU grep 2.19 では、このようなケースに対しても、Boyer-Moore 法のみで検索するようになりました。
$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjk | head -10000000 >m $ env LC_ALL=C time -p grep -i j$ m grep-2.18: real 2.12 user 2.07 sys 0.05 grep-2.19: real 0.53 user 0.47 sys 0.05 <<★４倍高速化
