まもなく GNU grep 2.21 リリース

GNU grep 2.21のリリースが秒読み段階に入りました。

GNU grep 2.21 では、特筆すべきものはないものの、いくつかの点で機能やパフォーマンスが改善されています。それでは、主な改善点を見ていくことにしましょう。

スパースファイルに対する改善

スパースファイルとは

プログラムがクラッシュした際に生成されるcoreファイルはメモリイメージを書き出したものですが、プロセスがマップされていない部分は書き出されません。また、仮想マシンでは巨大な仮想ディスクを作成しても全ての領域が直ぐに使用されるわけではないでしょう。これらのような使用されていない領域にまで前もってディスク上の領域を割り当てるのは無駄といえます。

このようなニーズに答えるため、XFSやReiserFSではスパースファイルをサポートしています。スパースファイルとはホールを含むファイルです。ホールとはファイルの中でディスク上の領域が割り当てらていない領域であり、read() すると 0 が埋められているように見えます。ファイルの中で直ぐに使用しない部分をホールにすることで、write () されるまでディスク上の領域の割り当てを遅延させることができ、ディスクを有効活用できます。

スパースファイルに対する改善

GNU grep 2.21 では、ファイルの中のホールを読み飛ばすことで、スパースファイルに対するパフォーマンスが改善しています。

$ dd if=/dev/zero bs=32M seek=32 count=0 of=m
$ time -p grep -z ^a$ ~/m
  grep-2.20: real 4.13    user 0.95     sys 0.87
  grep-2.21: real 0.12    user 0.00     sys 0.04

GNU grep 2.21 では、1GB ものファイルに対して、一瞬で結果が返されています。

パターンの最初の部分にさえマッチしないデータに対する改善

DFA*1を使った検索では、状態毎の遷移テーブル*2をあらかじめ作成しておき*3、入力データから 1 文字受け取って状態が遷移するたびに遷移テーブルを新しい状態のものに差し替えます。

ところで、パターンの最初の部分にさえマッチしない間は、入力データから何文字受け取ろうとも初期状態 0 です。従来のリリースでは、そのような場合でも遷移テーブルを差し替えていました。入力データから 1 文字受け取るたびに状態 0 の遷移テーブルを状態 0 の遷移テーブルに差し替えていました。GNU grep 2.21 では、パターンの最初の部分にさえマッチしない間は、状態 0 の遷移テーブルを差し替えることなく使用し続けるように改善されています。

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k
$ env LC_ALL=C grep '\(a\|b\)' k
  grep-2.20: real 0.96    user 0.85     sys 0.10
  grep-2.21: real 0.46    user 0.35     sys 0.10

$ yes j | head -100000000 >l
$ env LC_ALL=C grep '\(a\|b\)' l
  grep-2.20: real 0.64    user 0.60     sys 0.03
  grep-2.21: real 0.54    user 0.49     sys 0.04

-P オプションに対する改善

GNU grep では、-P オプションを使用することで PCRE (Perl Compatible Regular Expression) ライブラリを使用した検索が可能になっています。ところが、UTF-8 ロケールで -P オプションを使用すると、PCRE ライブラリによって事前に入力データが正しい UTF-8 シーケンスかどうかチェックする処理が実行され、不正な UTF-8 シーケンスが見つかるとそこでアボートしていました。

そこで、GNU grep 2.16 では、PCRE ライブラリの関数をコールする際に PCRE_NO_UTF8_CHECK オプション*4を指定するように変更されました。ところが、このオプションが指定された状態で不正な UTF-8 シーケンスを含む入力データを指定するとクラッシュする可能性があることが判明しました。そのため、GNU grep 2.19 では PCRE_NO_UTF8_CHECK オプションを指定しないように戻された上で、入力データに不正な UTF-8 シーケンスが含まれていた場合にはアボートするのではなくエラーを返すように変更されました。

GNU grep 2.21 では、入力データの中に不正な UTF-8 シーケンスが含まれていてもそれを検出しスキップして処理を継続できるように改善されました。この改善により、UTF-8 ロケールで -P オプションを指定した場合でもバイナリファイルを検索対象に含めることができるようになりました。

$ env LC_ALL=ja_JP.utf8 src/grep -P a src/grep
  grep-2.15: Aborted (core dumped)
  grep-2.20: src/grep: invalid UTF-8 byte sequence in input
  grep-2.21: Binary file src/grep matches

その他の主な改善

非常に長いパターンに対する改善

GNU grep では、最初にパターンから固定文字列を取り出し、それを使ってマッチする可能性がある行を絞り込みます。従来のリリースでは、パターンから固定文字列を取り出す処理のロジックに問題があり、パターンが非常に長い場合には多くのメモリを消費していました。

以下にテストケースを示しますが、結果は省略します。

$ echo '' | src/grep -f /usr/share/dict/linux.words
UTF-8マルチバイトロケールで「^」と「\|」を含むパターンに対する結果不正の修正

EUC-JPで「\244\263」は「こ」であり、「\263\244」は「海」です。「\263\244\263\244」は「\244\263」が含まれているものの「海海」と解釈されるべきです。従って、下記はマッチするべきではありませんが、従来のリリースではマルチバイト文字の境界を正しく認識できずマッチしていました。

$ pattern=$(printf '^x\|\244\263')
$ printf '\263\244\263\244\n' | env LC_ALL=ja_JP.eucJP src/grep "$pattern"

*1:DFA は、Boyer-Moore 法では処理できないやや複雑なパターンを処理します。

*2:次の状態に遷移するためのテーブルです。例えば、次に a を受け取ったら状態 1 に、b を受け取ったら状態 2 に、それ以外の文字を受け取ったら初期状態 0 に遷移といった内容が記録されています。

*3:ある状態の遷移テーブルは、初めてその状態の遷移テーブルが必要になった時点で作成されます。

*4:PCRE_NO_UTF8_CHECK オプションを指定すると、入力データに不正な UTF-8 シーケンスが含まれていないかを事前にチェックする処理がスキップされます。