まもなくgrep 2.22リリース
GNU grep 2.22が近日中にリリースされる見込みとなりました。
GNU grep 2.22は、結果不正バグが見つかったことによるバグフィックスリリースです。そのため、目立った改善点はありませんが、それらを見ていくとともに、今後の見通しについて紹介します。
GNU grep 2.22における改善/バグフィックス
結果不正バグの修正
下記のパターンは、「hello」が行頭または行末に含まる行にマッチしますが、行内に「hello」が含まれているものにマッチしてしまっています。
$ echo aaahellobbb | grep -E '^hello|hello$' aaahellobbb
バッファオーバーランの修正
固定文字列を検索をする時は、最初にパターンの最後の文字を検索し、見つかったところからBoyer Moore法で他の部分のマッチを試みますが、パターンの最後の文字がバッファの末尾近くで見つかった場合のハンドリングに問題があり、バッファーオーバーランを引き起こすリスクがある不具合です。
また、GNU grepではアライメントを揃えるため、バッファを余分に確保し、使用されなかったメモリ部分は未初期化のままにしておくようになっていたため、coreダンプせずに未初期化のメモリ部分に書かれた内容を読み取られるリスクがありました。
そのため、本バグでは根本原因の修正に加えて、バッファの使用されなかったメモリ部分を0埋めする処理が追加されています。
このバグにはCVE-2015-1345が割り当てられセキュリティホールと認識されているため、多くのLinuxのディストリビューションベンダーからは、既に修正版がリリースされています。
バグ的な処理遅延の改善
1つ目は長いパターンに対する解析性能の改善です。下記の解析に0.85秒かかっていたものが、0.02秒に改善されたと報告されています。
$ : | env time -f %e grep -e $(seq -s '' 9999)
2つ目はgrep -Fwに対する性能改善です。下記は入力文字列がたった10万行にもかかわらず14.03秒もかかっていたと報告されています。
$ yes 'abcdefg hijklmn opqrstu vwxyz' | head -100000 >k $ time -p env LC_ALL=C grep -Fw vwxy k real 14.03 user 12.51 sys 0.74
ちなみに、シングルバイトロケールでは、grep -Fではなくgrepを使用すると非常に速く返ってきます。そのため、シングルバイトロケールでgrep -Fwした場合は、grep -wと同様の動作となるように修正されています。
$ time -p env LC_ALL=C grep -w vwxy k real 0.11 user 0.01 sys 0.09
今後追加される見込みの改善内容
マルチスレッド化
GNU grepは高速に動作しますが、シングルスレッドで動作するため、複数のプロセッサを搭載したマシン上でもそのマシン性能を十分生かすことができませんでした。現在のリリースでもGNU parallelなどと組み合わせれば並列化できますが、マルチスレッド化されることで単体で並列化できるようになります。
grep -Fで複数パターンを指定した時のアルゴリズムの変更
現在のリリースではgrep -Fで複数パターンを指定するとBeate Commentz-Walterアルゴリズムを使用します。Beate Commentz-WalterアルゴリズムはBoyer-Mooreアルゴリズムを複数パターンで使えるように拡張したものですが、プロセッサのキャッシュの仕組みを十分に活かすことができないため、あまり高速ではありませんでした。さらに、Beate Commentz-Walterアルゴリズムには、Boyer-Moore法に適用できるガリル規則を適用することができないため、最悪のケースではO(m*n)となってしまう欠点がありました。
提案されている方法は、grep -Fで複数パターンを検索するときのアルゴリズムを、Beate Commentz-Walterアルゴリズムから、Aho-Corasickアルゴリズムに置き換えるものです。これにより上記の欠点が解消され、大幅な性能改善が期待されます。
