GNU grep 2.26リリース
ちょっと執筆が遅れてしまいましたが、先日GNU grep 2.26がリリースされました。
GNU grep 2.26では、いくつかの性能改善とバグフィックスが行われています。ここでは、GNU grep 2.26における改善点について見てきたいと思います。
まず、最初に動作環境について少し述べておきます。grepは1つ前のバージョンすなわち2.25、src/grepは2.26です。
$ grep --version grep (GNU grep) 2.25 Copyright (C) 2016 Free Software Foundation, Inc. ライセンス GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. 作者 Mike Haertel および その他の方々は <http://git.sv.gnu.org/cgit/grep.git/tree/AUTHORS> を参照してください。 $ src/grep --version grep (GNU grep) 2.26 Copyright (C) 2016 Free Software Foundation, Inc. ライセンス GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. 作者 Mike Haertel および その他の方々は <http://git.sv.gnu.org/cgit/grep.git/tree/AUTHORS> を参照してください。
GNU grep 2.26における主な改善
/dev/nullへの出力に対する性能改善
標準出力が /dev/null に出力されている場合は、パターンにマッチする行が見つかっても画面には何も出力されないため、結果は grep -q と同じになります。
GNU grep 2.26では、標準出力が/dev/null にリダイレクトされた場合に、grep -qと同じ動作をするように変更されています。
grep -qでは、パターンにマッチする行を見つけた時点で処理を打ち切り正常の終了ステータスとともに終了するため、-qを指定しない場合に比べて高速である可能性があります。
ただ、「/dev/null」はハードコードされているため、/dev/nullがキャラクタ・デバイスであれば中身がなんであれ本機能が動作していしまいます。/dev/nullを置き換えれば多くのプログラムが動作しなくなるため普通はそのようなことをしないでしょうが。
# ls -l /dev/null crw-rw-rw-. 1 root root 1, 3 7月 6 15:56 2016 /dev/null # mknod null c 1 3 # time -p env LC_ALL=C src/grep 0 >null real 0.82 user 0.76 sys 0.05 # time -p env LC_ALL=C src/grep 0 >/dev/null real 0.00 user 0.00 sys 0.00
複数パターンを指定した時のgrep -Fの性能改善
長年の間、grep -Fは、複数パターンが指定されたとき、Boyer-MooreアルゴリズムとAho-CorasickアルゴリズムをかけあわせたCommentz-Walterアルゴリズムを使用していました。ただ、Commentz-Walterアルゴリズムには、パターンの中に短い文字列が含まれているときの性能が良くなかったり、パターンの後ろからマッチングを試みるためにCPUが持つキャッシュ機能をうまく行かせないといった問題があり、パターンと入力文字列の組み合わせによっては、通常のgrepと比べてもかなり遅いことがありました。GNU grep 2.26では、grep -Fは複数パターンが指定されたときに、Commentz-Walterアルゴリズムではなく、Aho-Corasickアルゴリズムを使用するように変更されています。この変更により数倍の性能改善が報告されています。
$ echo '' | env LC_ALL=C time -p grep -Ff /usr/share/dict/linux/words real 1.32 user 1.25 sys 0.07 $ echo '' | env LC_ALL=C time -p src/grep -Ff /usr/share/dict/linux/words real 0.45 user 0.39 sys 0.05
grep -iFの改善
従来、grep -iFに対する検索では、常にgrepと同じアルゴリズムが使用されてきました。しかし、パターンにシングルバイト文字しか含まないケースでは、grep -Fと同じアルゴリズムを使用するように変更されました。この変更により、性能やパターンが膨大な場合のメモリ使用量が改善されています。
$ yes $(printf %040d 0) | head -10000000 >k $ time -p env LC_ALL=ja_JP.utf8 grep -iF abc k real 0.42 user 0.37 sys 0.03 $ time -p env LC_ALL=ja_JP.utf8 src/grep -iF abc k real 0.15 user 0.11 sys 0.04
これはパターンの解析速度が改善した例ですが、実際にはマッチング速度も向上しています。
その他の改善点
fastmapの使用による性能改善
fastmapとは、regexで使用されるパターンの最初の文字へのマッチングを高速化するためのハッシュです。後方参照が使用されているなどのケースでは、GNU grepが持つ高速化エンジンを使用するだけでマッチングを終えることができません。GNU grepでは、そのようなケースに対してglibcやgnulibが提供するregexライブラリを使用します。ただ、regexライブラリは多くの正規表現をサポートしている反面、性能はあまりよくありません。そのため、fastmapの機構が取り入れられ、使用することでパターンの最初の文字へのマッチングを高速化できるようになっています。多くのケースでは、パターンの最初の文字にマッチせずrejectされるため、fastmapを使用することにより性能は大きく改善することが期待できます。GNU grep 2.26では、-iオプションが指定されない場合に、fastmapを使用するように変更されています。この変更により100倍以上高速化したケースも報告されています。
