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倍以上高速化したケースも報告されています。
grepツール「highway」をもう少し試してみました
以前に「grepツール「highway」を試してみました」を書いてから9ヶ月ほど経ちました。
GNU grepと性能比較したものの、その中身までは踏み込めていなかったので、もう少し踏み込んでみました。
highwayの改善
highwayは公開後メンテナンスされていないのかと思いきや、時折メンテナンスされているようです。少なくとも、前回検証した時に見つかった、tc_malloc、tc_calloc、tc_reallocがない環境でコンパイルに失敗する問題や、大量の出力を伴う検索でabort(3)する問題はバッチリ修正されているようです。
highwayの性能確認
まずは前回と同様の検証を行ってみました。Linux-4.6のソースコードをダウンロードし、性能確認を実施してみました。使用したマシンは前回と同様Intel Core i5-3470 3.2GHz (4コア)、Red Hat Enterprise Linux 5.11。GNU grepは2.25です。
$ time -p grep -r EXPORT_SYMBOL_GPL . >/dev/null real 1.08 user 0.32 sys 0.76 $ time -p ../highway-master/hw EXPORT_SYMBOL_GPL . >/dev/null real 0.46 user 0.70 sys 0.92 $ time -p ../highway-master/hw --worker=1 EXPORT_SYMBOL_GPL . >/dev/null real 1.35 user 0.81 sys 0.81
少し条件が変わっていますが、前回とほぼ同様の結果です。ただ、このテストで1つ考慮できていなかったことがあります。それは、GNU grepが検索結果に対して行番号の出力、色付けを行わないのに対して、highwayは行番号の出力、色付けを行うことです。そこで、GNU grep側も行番号、色付けを行うようにしてテストしてみました。
$ time -p grep -nr --color EXPORT_SYMBOL_GPL . >/dev/null real 1.55 user 0.87 sys 0.66
結果はシングル・スレッド同士*1でもhighwayがGNU grepよりも高速という結果になりました。ちなみに、影響が大きかったのは行番号の出力で、色付けの影響はほとんどありませんでした。
行番号を出力するためには、パターンにマッチした行が見つかったか見つからなかったかにかかわらず入力バッファをスキャンし、改行コードを数え上げる必要があります。つまり、入力バッファを2度スキャンする必要があります。なので、性能への影響は大きくなります。他方、色付けはパターンにマッチする行が見つからなければ追加の処理は発生しません。色付け処理自体は高負荷ですが、実行される回数が少ないため、性能への影響はあまりありません。
逆にhighwayで行番号を出力しないようにした場合にどうなるか確認してみました。highwayで行番号を出力しないようにするためには-Nオプションを指定します。
$ time -p ../highway-master/hw -N --worker=1 EXPORT_SYMBOL_GPL . >/dev/null real 1.16 user 0.62 sys 0.81
GNU grepが出したreal 1.08を超えることを期待していたのですが、残念ながらそのようにはなりませんでした。つまり、検索アルゴリズムはGNU grepが高速だが、行番号の出力が高速はhighwayの方が高速といえます。
行番号の出力処理
highwayの行番号出力が高速ということで、どのようなアルゴリズムになっているのか確認してみました。改行コードを検索する処理はsrc/search.cのscan_newline関数です。
char *scan_newline(char *from, char *to, size_t *line_count, char eol)
{
const char *start = from;
while (start <= to && (start = memchr(start, eol, to - start + 1)) != NULL) {
// Found the new line. The `start` variable points to a new line position, so it is
// increments in order to search next line.
start++;
// Also line count is incriments.
(*line_count)++;
}
return to + 1;
}他方、GNU grepで改行コードを検索する処理はsrc/grep.cのnlscan関数です。
static void
nlscan (char const *lim)
{
size_t newlines = 0;
char const *beg;
for (beg = lastnl; beg < lim; beg++)
{
beg = memchr (beg, eolbyte, lim - beg);
if (!beg)
break;
newlines++;
}
totalnl = add_count (totalnl, newlines);
lastnl = lim;
}なんと、書き方は少し違うものの、やっていることはほぼ同じです。それでは、検索アルゴリズムの差をひっくり返すくらいの大きな性能差が出るのでしょうか。
その理由はhighway側のsrc/search.cのsearch()関数にありました。
while ((read_len = read(fd, buf + buf_offset, NMAX)) > 0) {
read_sum += read_len;
........
// Break loop if file pointer is reached to EOF. But if the file descriptor is stdin, we
// should wait for next input. For example, if hw search from the pipe that is created by
// `tail -f`, we should continue searching until receive a signal.
if (fd != STDIN_FILENO && read_len < NMAX) {
break;
}
if (op.show_line_number) {
last_new_line_scan_pos = scan_newline(last_new_line_scan_pos, last_line_end, &line_count, eol);
}
last_line_end++;read(2)の結果がNMAXよりも小さい場合、ファイルの末尾に到達したとみなし、改行コードを検索しないようになっています。NMAXはinclude/search.hで65536と定義されているため、ファイルのサイズが65536バイト未満で、パターンにマッチする行がない場合、改行コードを検索する処理が実行されません。これによって高速化できているようです。
この仮定はfread(3)を使用してれば正しいですが、read(2)の場合は正しくありません。シグナルを捕捉した場合や、入力が名前付きパイプ、ソケット、/dev/randomなどの特殊なデバイス・ファイルの場合は、ファイルの末尾に達していなくてもread(2)の結果がNMAXよりも小さくなることがあります。
そこで、この処理をコメントアウトしてみました。
while ((read_len = read(fd, buf + buf_offset, NMAX)) > 0) {
read_sum += read_len;
........
// Break loop if file pointer is reached to EOF. But if the file descriptor is stdin, we
// should wait for next input. For example, if hw search from the pipe that is created by
// `tail -f`, we should continue searching until receive a signal.
//if (fd != STDIN_FILENO && read_len < NMAX) {
// break;
//}
if (op.show_line_number) {
last_new_line_scan_pos = scan_newline(last_new_line_scan_pos, last_line_end, &line_count, eol);
}
last_line_end++;この状態でテストしたところ、残念ながらGNU grepよりも遅くなってしまいました。
$ time -p ../highway-master/hw --worker=1 EXPORT_SYMBOL_GPL . >/dev/null real 1.80 user 0.10 sys 0.95
大量の出力を伴う検索の性能
冒頭で大量の出力を伴う検索でabort(3)する問題はきっちりと修正されたという話をしました。そこで、このような条件下でテストしてみました。
$ yes %040d 0 | head -10000000 >k $ time -p grep -nr --color 0 k >/dev/null real 1.42 user 1.24 sys 0.18 $ time -p ../highway-master/hw 0 k >/dev/null real 37.07 user 19.46 sys 16.21 $ time -p ../highway-master/hw --worker=1 0 k . >/dev/null real 38.06 user 18.59 sys 19.46
結果はGNU grepの圧勝です。highwayにとってこのようなケースはあまり得意ではないようです。詳細は調査していませんが、検索スレッドと出力スレッドが別になっていて、お互いに同期する必要があるため、オーバーヘッドが非常に大きいのかもしれません。今回は検索対象のファイルが1つということで、workerがデフォルトの状態でも結果はほとんど変わりませんでした。
検索アルゴリズムの比較
highwayには鬼雲がバンドルされていて、-eまたは-iオプションを指定された場合のみ鬼雲を使用した正規表現によるマッチングを行い、-eオプションと-iオプションのどちらも指定されていない場合は、独自のエンジンを使用してgrep -Fと同様の動作を行います。ただし、複数のキーワードによるマッチングには対応していないようです。
パターンの長さが1の場合でもmemchr(3)を使用せず、単純な比較によるマッチングを行います。*2パターンの長さが1よりも大きい場合はBoyer-Moore (BM)法とKnuth-Morris-Pratt (KMP)法を組み合わせたようなアルゴリズムを採用しています。Boyer-Moore (BM)法のDelta1検索でパターンに末尾の文字にマッチングする位置までポインタを進め、そこからバッファの末尾までKnuth-Morris-Pratt (KMP)法で検索します。*3
他方GNU grepは、固定文字列を検索するのに、パターンの長さが1の場合にmemchr(3)を、パターンの長さが1よりも大きい場合はBoyer-Moore (BM)法とmemchr(3)を組み合わせたようなアルゴリズムを使用します。Delta1検索を何度か行ってみて、そのシフト量の合計が基準値を超えている場合はBoyer-Moore (BM)法を継続し、小さい場合はmemchr(3)に切り替えます。*4
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が色付けされてしまいます。しかし、これでは結果不正です。
まもなくgrep 2.23リリース
GNU grep 2.23が近日中にリリースされる見込みとなりました。
GNU grep 2.23は、GNU grep 2.22に続いてバグフィックスリリースです。GNU grep 2.23では、入力データがテキストかバイナリかを判定するロジックが強化されています。GNU grep 2.21で同様の強化が行われたものの、仕様レベルの問題があり、入力データに少しでも現在のロケールに存在しないバイト列が含まれているとバイナリと判定されてしまっていました。
GNU grep 2.23における改善/バグフィックス
入力データを判定するロジックの強化
GNU grepには、入力データがテキストかバイナリかを判定し、入力データがバイナリだった場合はマッチした行を出力する代わりに「Binary file ... matches」を出力して検索を打ち切る機能が実装されています。この機能により、ユーザが誤ったバイナリファイルをgrepした場合でも、出力した制御コード等によって端末がハングしたりする問題を回避できます。
GNU grep 2.20以前では、入力データがテキストかバイナリかを入力データ中にNUL文字(文字コードが0x00)が含まれているか否かで判定しています。この実装方法は、オーバヘッドが少なく高速に動作する反面で精度が悪く、ユーザが誤ったバイナリファイルをgrepしてしまうと端末がハングしてしまう可能性があります。
そこで、GNU grep 2.21では、入力データの先頭部分(通常は最初の32768バイト)がロケールに適合していないバイトが含まれているかどうかチェックし、含まれていた場合にバイナリと判定するように変更されました。しかし、この変更によって入力データの先頭部分に1バイトでもロケールに適合しないバイトが含まれているとバイナリと判定されてしまうようになりました。例えば、入力データの先頭部分に非英語圏の人名が含まれている場合がこのようなケースに該当します。また、Javaのインストーラのように、ファイルの先頭部分だけテキスト(シェルスクリプト)で、本体部分がバイナリ(圧縮ファイル)となっているファイルをgrepした場合、相変わらず端末がハングしてしまう可能性があります。
そこで、GNU grep 2.23では、入力データではなく出力データに対してチェックを行い、出力データにロケールに適合しないバイトが含まれている場合にバイナリと判定されるように変更されました。これにより、ユーザが誤ったバイナリファイルをgrepして端末がハングしてしまう可能性はなくなると思われます。また、入力データがパターンに全くマッチしないケースではチェックが行われないため、非常に高速に結果を返すことができます。*1
grep -P/grep -Pcの不整合に対する修正
先述の通り、GNU grep 2.21、GNU grep 2.22では、入力データの先頭部分(通常は最初の32768バイト)がロケールに適合していないバイトが含まれているかどうかチェックし、含まれていた場合にバイナリと判定しています。ここで、バイナリと判定されなかった場合は、-Pオプションが指定されていない場合は、その入力データをテキストとみなしています。他方、-Pオプションが指定されている場合は、最初にパターンにマッチする行を見つける時点までチェックを続け、その時点までにロケールに適合しないバイトが見つからなかった場合にテキストと判定するようになっています。-Pオプションが指定されている場合の他と異なる振る舞いは、-Pで使用されるpcreライブラリで実装されている入力データがUTF-8に適合しているかどうかチェックする機能の性能の低さを、可能な限りGNU grep側で補うするためになされています。
ところが、後者のロジックには問題がありました。下記は、GNU grep 2.22で実行した結果です。-cオプションを指定しなかった場合は2行返されています。他方、-cオプションを指定した場合は、1が返されています。
$ printf 'a\n%032768d\nb\x0\n%032768d\na\n' | LC_ALL=C grep -P a a a $ printf 'a\n%032768d\nb\x0\n%032768d\na\n' | LC_ALL=C grep -Pc a 1
まず、前者について見てみましょう。まず、最初の32768バイトにはロケールに適合しないバイトは含まれていません。次に、入力データの先頭が「a」なので、最初の行はパターンにマッチします。この時点で入力データはテキストとみなされます。その後も入力データはテキストとして処理され、最後の行がパターンにマッチします。従って、2行返されます。
次に、後者について見てみましょう。まず、最初の32768バイトにはロケールに適合しないバイトは含まれていません。次に、入力データの先頭が「a」なので、最初の行はパターンにマッチしますが、-cオプションは入力データの最後まで検索した後にマッチした件数を出力するため、この時点では出力がありません。その結果、この時点では入力データがテキストかバイナリか判定されません。
その後「\x0」が見つかり、この時点で入力データはバイナリとみなされます。既に入力データへの1行以上のマッチが確定しているため、検索を打ち切り、この時点までにマッチした行数「1」を出力します。*2
GNU grep 2.23では、-cオプションが指定された場合には、入力データがバイナリとみなされても、検索を打ち切らないように変更されています。
printf 'a\n%032768d\nb\x0\n%032768d\na\n' | LC_ALL=C grep -Pc a 2 ||<< ただし、この変更は、-cオプションを指定した場合が、指定しなかった場合よりも遅くなる可能性がある点に注意する必要があります。 *** grep -oPが無限ループする可能性がある不具合の修正 GNU grep 2.22で下記を実行してみてください。 >|| printf '\201_\0' | LC_ALL=en_US.UTF-8 grep -aoP _
永遠に「_」が出力され続けると思います。UTF-8において、内部でコールされているpcre_exec()は、入力データがUTF-8に適合していない場合にマッチした場所を示す変数が負数を返すことがありますが、GNU grep 2.22がそれが正しくハンドリングされておらず、入力データに対するポインタが行ったり来たりすることによって発生します。GNU grep 2.23では、マッチした場所を示す変数が負数だった場合には、入力データに対するポインタを戻さないように修正されています。
知られている問題
巨大なパターンによるgrep -Fiが遅い問題
下記のように、GNU grep 2.19以降で、マルチバイトロケールにおける巨大なパターンによるgrep -Fiが遅い問題が複数報告されています。
$ ls -adFl /usr/share/dict/linux.words -rw-r--r-- 1 root root 4950996 2月 27 2009 /usr/share/dict/linux.words $ grep -Fif /usr/share/dict/words in
これは、GNU grep 2.19以降、入力データが長い場合の検索性能を改善するため、grep -Fiに対してgrep -iと同じアルゴリズムを使用するように変更されたためです。grep -iはDFAを使用しますが、DFAはパターンのコンパイルに要する時間やリソースがパターンの長さに対して指数関数的に増大するため、大きく性能に影響します。*3
ところで、変更前はパターンと入力データの両方を小文字に変換してからBoyer-Moore法やCommentz-Walter法を使用して検索していました。しかし、マルチバイトロケールにおいては長い入力データを小文字に変換コストが大きい、変換後のデータを格納するための余分なバッファが必要、大文字と小文字のバイト数が異なるロケールではパターンにマッチした位置を正確に判断できないなどといった問題がありました。その上、マルチバイトロケールにおけるgrep -Fiが遅いなら、LC_ALL=Cでgrepすればよいこともあるため、不具合報告が複数上がっているものの、対処はさほど急がれていないようです。
*1:入力データがパターンに全くマッチしないケースでは出力がなくプログラムの実装による性能への影響が大きくなるため、GNU grepではこのようなケースに対して最適化されています。
*2:入力データがバイナリだった場合はマッチした行を出力する代わりに「Binary file ... matches」を出力して検索を打ち切ります。-cオプションが指定されている場合は、「Binary file ... matches」を出力しません。
*3:GNU grepでは、DFAの状態の生成を最大限に遅延させることによって、この影響を小さくする工夫がなされていますが、条件によってはパターンのコンパイルに時間を要したり、リソースを多く消費したりします。
正規表現の実装の難しさ
正規表現はPOSIXで定義されています。しかし、POSIXで定義されている正規表現はPOSIXロケール(LANG=C)しか考慮していないため、POSIX以外のロケールをサポートしようとすると様々な問題に遭遇します。それらについて見ていくことにしたいと思います。
不適切な位置でのマッチ
マルチバイトロケールでは、不適切な位置(マルチバイト文字の途中)でマッチした場合に、そのマッチは排除されなければなりません。たとえば、SJISにおいて「\」は0x5c、「表」は0x95 0x5cで定義されています。したがって、下記はPOSIXロケールであればマッチします。しかし、ja_JP.sjisでは、2バイト目(文字の途中)でマッチしていることになるため排除されなければなりません。
$ LANG=ja_JP.sjis; export LANG $ echo 表マーク | grep '\マーク' $
同様に、EUC-JPにおいて、「海」は0xb3 0xa4、「こ」は0xa4 0xb3で定義されています。したがって、下記はPOSIXロケールであればマッチします。しかし、ja_JP.eucJPでは、2バイト目(文字の途中)でマッチしていることになるため排除されなければなりません。
$ LANG=ja_JP.eucJP; export LANG $ echo ここ | grep '海' $
UTF-8以外のマルチバイトロケールにおいて不正な位置でのマッチを見つけるには、入力文字列を最初から各文字の区切りがどの位置にあるかをチェックしていく必要があります。libcのAPIには、マルチバイト文字のバイト数を取得する関数としてmbrtowc(3)やmbrlen(3)が用意されているため、これを使用してチェックできます。ただし、これらの関数は非常に負荷が高いため、高速化するためには工夫が必要です。
GNU grepでは、この負荷を低くするため、一般的な入力文字列が多くのシングルバイト文字で構成されていることに着目し、256個の各バイト表現が対象のロケールにおいてシングルバイト文字であるかどうかをあらかじめ配列上にキャッシュします。たとえば、ja_JP.eucJPでは、0x00-0x99はシングルバイト文字であることをキャッシュします。そして、シングルバイト文字ではない文字列に遭遇した場合のみmbrtowc(3)やmbrlen(3)を使用してバイト数をチェックします。
ピリオド表現「.」へのマッチ
シングルバイトロケールの場合、1文字は常に1バイトで表現されるため、「.」はいつも1バイトにマッチします。それに対して、マルチバイトロケールでは、1文字が複数バイトで表現されることもあるため、「.」も複数バイトにマッチする可能性があります。
$ LANG=ja_JP.utf8; export LANG $ echo Ｂ | od -tx1 0000000 ef bc a2 0a 0000004 $ echo Ｂ | grep '^.$' Ｂ $
このため、マルチバイトロケールでは「.」を含む正規表現を事前に完全にコンパイルしておくことは難しく、事前にコンパイルできなかった部分は実行時にコンパイルする必要があります。しかし、それは実行時の性能劣化をもたらし、入力文字列が長ければ長いほど顕著になります。
GNU grepでは、「.」を含む正規表現の性能劣化を回避するため、汎用的とされるUTF-8においては、「.」を下記のパターンに置き換えています。これにより、「.」を含む正規表現であっても事前に完全にコンパイルできます。
([0x00-0x7f]|[0xc2-0xdf][0x80-0xbf]|[0xe0-0xef[0x80-0xbf][0x80-0xbf]|[0xf0-f7][0x80-0xbf][0x80-0xbf][0x80-0xbf])
ただ、これだけではUTF-8以外のマルチバイトロケールに対しては遅いままです。*1そこで、「.」が常に決まった文字列にマッチすることに着目し、「.」にマッチした場合の状態遷移と「.」にマッチしなかった場合の状態遷移をキャッシュすることで高速化を実現するパッチがリクエストされています。
ブラケット表現へのマッチ
ブラケット表現とは、[abc]、[A-Z]といった表現です。ブラケット表現もピリオド表現と同様にマルチバイトロケールでは複数バイトにマッチする可能性があります。
$ LANG=ja_JP.utf8; export LANG $ echo Ｂ | od -tx1 0000000 ef bc a2 0a 0000004 $ echo Ｂ | grep '^[Ａ-Ｃ]$' Ｂ $
他方、ブラケット表現はシングルバイトロケールにおいても複数文字からなる照合要素が定義されているロケールでは複数バイトにマッチする可能性があります。*2
たとえば、スペイン語のロケール(es)では、「c」と「d」の間に「cH」、「ch」といった複数文字からなる照合要素が定義されています。そのため、ブラケット表現は「ch」という2文字にマッチする可能性があります。
$ LANG=es_US.iso88591; export LANG $ echo ch | grep '^[a-z]$' ch $
また、POSIXロケールではc < cg < ch < ci < dとなるところ、スペイン語のロケールでは複数文字からなる照合要素が定義されていることによりc < cg < ci < ch < dとなります。なぜなら、「cg」は「c」+「g」、「ci」は「c」+「i」と分解され最初の文字は「c」であるのに対して、「ch」は複数文字からなる照合要素が定義されているため分解されず最初の文字は「ch」として比較されるため、「cg」と「ci」が「ch」よりも前に位置すると解釈されるからです。
加えて、ブラケット表現では文字クラス(:alpha:など)や等価クラス(=a=など)も既定されており、POSIX以外のロケールをサポートする正規表現の実装の難易度を一段と高くしています。
これらに対するマッチを実現するためには、libcで定義されているロケールの情報にアクセスするか、自身でサポートするロケールの情報や文字コードの変換テーブルを実装する必要があります。
しかし、前者についてはlibcで定義されているロケールの情報にアクセスできるAPIは非常に限られており、後者についてはlibcと同レベルのロケールをサポートしようとすると実装が極めて困難なため、POSIX以外のロケールでもブラケット表現を厳密に取り扱える正規表現を実装することは現実的ではありません。そこで、ブラケット表現を含む正規表現に対しては、libcが用意しているregex(3)ライブラリに頼るのが無難な選択といえるでしょう。
GNU grepは高速化のため独自のDFAエンジンを使用しますが、ブラケット表現に対してはregex(3)を使用します。しかし、regex(3)はブラケット表現や後方参照(\1, \2, ...)をきっちりサポートしていることで、性能面で大きなペナルティを負っています。そこで、GNU grepでは、先にブラケット表現以外の部分がマッチするかどうかをチェックし、マッチした行に対してのみregex(3)を使用します。*3
大文字/小文字の区別の無視
「大文字/小文字の区別の無視」とは、grepを-iオプション付きで起動する場合に相当します。POSIXや日本語ロケールでは、ある小文字について大文字の小文字は元の小文字に一致し、ある大文字について小文字の大文字は元の大文字に一致します。しかし、一部のロケールでは必ずしもそうではありません。
たとえば、トルコ語では、「I」と「i」にそれぞれ2つのバージョンがあります。1つはドットなし(POSIXロケールで定義されているものと同じもの)で、もう1つはドットあり(POSIXロケールでは定義されていないもの)です。
| ケース | 大文字 | 小文字 |
|---|---|---|
| ドットなし | U+0049 | U+0069 |
| ドットあり | U+0130 | U+0131 |
そして、大文字/小文字の変換ルールは下記のように定義されています。
| 文字 | toupper | tolower |
|---|---|---|
| U+0049 | U+0049 | U+0069 |
| U+0069 | U+0049 | U+0069 |
| U+0130 | U+0130 | U+0069 |
| U+0131 | U+0049 | U+0131 |
すなわち、ドットあり「I」(U+130)の小文字はドットなし「i」(U+0069)で、その大文字はドットなし「I」(U+0049)となり、元の文字には一致しません。同様に、ドットあり「i」(U+131)の大文字はドットなし「I」(U+0049)で、その小文字はドットなし「i」(U+0069)となり、元の文字には一致しません。
POSIXロケールではこのような状況は発生しないため、regexを定義しているPOSIXでもこのような点まで考慮されておらず、グレーゾーンとなっています。
また、UTF-8には合字と呼ばれる文字が存在します。たとえば、「LJ」(U01C7)であり、これで1文字を構成します。そして、これらの文字には、大文字(LJ)と小文字(lj)以外に、タイトルケース(Lj)が存在します。これについても、POSIXロケールには存在ないため、どのように扱うべきか定義されていません。グレーゾーンです。
まとめ
正規表現はPOSIXで定義されています。しかし、POSIXで定義されている正規表現はPOSIXロケール(LANG=C)しか考慮していないため、POSIX以外のロケールをサポートしようとすると様々な問題に遭遇します。本記事を読んでいただいて、POSIX以外のロケールをサポートする正規表現の実装の難しさのみならず、ロケールの奥深さや面白さを感じ取っていただければ幸いです。
*1:全てのロケールに対してパターンの置き換えを行えばよいのではないかと思われるかもしれません。しかし、OSもしくはlibcによって定義されているロケールの種類や内容には差異があります。そのため、汎用的ではないロケールまで決め打ちしてしまうと、移植性や互換性、ロケールの拡張性が失われてしまうリスクが生じます。
*2:ピリオド表現はシングルバイトロケールにおいて複数バイトにマッチすることはありません。
*3:以前は独自のDFAエンジンでマルチバイトロケールにおけるブラケット表現を部分的にサポートしていました。しかし、マルチバイトロケールにおけるブラケット表現の完全なサポートが不可能であることや、マルチバイトロケールにおけるブラケット表現のサポートが高速性が売りであるDFAエンジンの足かせになることから、現在のリリースでは残骸を除いて削除されています。
grepツール「highway」を試してみました
最近「highway」というgrepツールが公開されていたので試してみました。
highwayのビルド
まずはソースコードをダウンロード。右下の方にある「Download ZIP」をクリックすることで、ソースコード一式をzip形式でダウンロードできます。展開してhighway-masterディレクトリに入り、./tool/build.shを実行することでコンパイルまで行えました。ただ、私のマシンにはtcmallocがインストールされていないため、下記のエラーが発生しました。
$ unzip -q master.zip $ cd highway-master $ ./tool/build.sh ...... gcc -g -O2 -pthread -Wall -std=gnu99 -o hw src/highway.o src/file.o src/scan.o src/fi le_queue.o src/line_list.o src/worker.o src/search.o src/print.o src/ignore.o src/log.o src/option.o src/util.o src/regex.o src/fjs.o src/hwmalloc.o src/help.o vendor/onigmo/re gcomp.o vendor/onigmo/regenc.o vendor/onigmo/regerror.o vendor/onigmo/regexec.o vendor/o nigmo/regext.o vendor/onigmo/reggnu.o vendor/onigmo/regparse.o vendor/onigmo/regposerr.o vendor/onigmo/regposix.o vendor/onigmo/regsyntax.o vendor/onigmo/regtrav.o vendor/onigm o/regversion.o vendor/onigmo/st.o vendor/onigmo/enc/ascii.o vendor/onigmo/enc/big5.o ven dor/onigmo/enc/cp1251.o vendor/onigmo/enc/cp932.o vendor/onigmo/enc/euc_jp.o vendor/onig mo/enc/euc_kr.o vendor/onigmo/enc/euc_tw.o vendor/onigmo/enc/gb18030.o vendor/onigmo/enc /iso8859_1.o vendor/onigmo/enc/iso8859_10.o vendor/onigmo/enc/iso8859_11.o vendor/onigmo /enc/iso8859_13.o vendor/onigmo/enc/iso8859_14.o vendor/onigmo/enc/iso8859_15.o vendor/o nigmo/enc/iso8859_16.o vendor/onigmo/enc/iso8859_2.o vendor/onigmo/enc/iso8859_3.o vendo r/onigmo/enc/iso8859_4.o vendor/onigmo/enc/iso8859_5.o vendor/onigmo/enc/iso8859_6.o ven dor/onigmo/enc/iso8859_7.o vendor/onigmo/enc/iso8859_8.o vendor/onigmo/enc/iso8859_9.o v endor/onigmo/enc/koi8.o vendor/onigmo/enc/koi8_r.o vendor/onigmo/enc/mktable.o vendor/on igmo/enc/sjis.o vendor/onigmo/enc/unicode.o vendor/onigmo/enc/utf16_be.o vendor/onigmo/e nc/utf16_le.o vendor/onigmo/enc/utf32_be.o vendor/onigmo/enc/utf32_le.o vendor/onigmo/en c/utf8.o -lm src/hwmalloc.o: In function `hw_realloc': hwmalloc.c:(.text+0x15): undefined reference to `tc_realloc' collect2: ld returned 1 exit status Makefile:658: recipe for target 'hw' failed make: *** [hw] Error 1
そこで、./src/hwmalloc.cを編集し、tc_malloc、tc_calloc、tc_reallocのそれぞれから「tc_」を取り除き、再度makeを実行したところ、うまくコンパイルできました。
--- ./src/hwmalloc.c.orig 2015-10-22 14:24:58.000000000 +0900
+++ ./src/hwmalloc.c 2015-10-24 13:31:00.000000000 +0900
@@ -4,7 +4,7 @@
void *hw_malloc(size_t size)
{
- void *m = tc_malloc(size);
+ void *m = malloc(size);
if (m == NULL) {
log_e("Memory allocation by malloc failed (%ld bytes).", size);
exit(2);
@@ -14,7 +14,7 @@
void *hw_calloc(size_t count, size_t size)
{
- void *m = tc_calloc(count, size);
+ void *m = calloc(count, size);
if (m == NULL) {
log_e("Memory allocation by calloc failed (%ld count, %ld bytes).", count, size);
exit(2);
@@ -24,7 +24,7 @@
void *hw_realloc(void *ptr, size_t size)
{
- void *m = tc_realloc(ptr, size);
+ void *m = realloc(ptr, size);
if (m == NULL) {
log_e("Memory allocation by realloc failed (%ld bytes).", size);
exit(2);
highwayの性能確認
早速Linuxカーネルのソースコードをダウンロードし、性能確認を実施してみました。使用したマシンはIntel Core i5-3470 3.2GHz (4コア)、Red Hat Enterprise Linux 5.11で、GNU grep 2.21と比較しました。
$ time -p grep -r EXPORT_SYMBOL_GPL . >/dev/null real 1.05 user 0.34 sys 0.74 $ time -p ../highway-master/hw EXPORT_SYMBOL_GPL . >/dev/null real 0.52 user 0.66 sys 1.03 $ time -p ../highway-master/hw --worker=1 EXPORT_SYMBOL_GPL . >/dev/null real 1.43 user 0.61 sys 1.07
highwayをシングルスレッドに絞るとGNU grepの方が高速でしたが、highwayはマルチスレッド機能を活かすことでGNU grepよりもかなり高速に結果を返しました。
そこで、GNU grep側の対抗馬として、先日GNU grepのプロジェクトに提出されたマルチスレッド化のパッチを適用して試してみましたが、全く性能が出ませんでした。(詳細は割愛します)
続いて、全行がマッチした時に全ての結果を一旦メモリ上にバッファリングしてから出力するのか否かを確認するため、下記のテストを行ってみましたが、abort(3)してしまいました。。。
$ yes $(printf %040d 0) | head -10000000 >k $ ./hw 0 k >/dev/null
そこで、先ほど使用したLinuxカーネルのソースコードを全部catしたもの(サイズは600MB弱)を使用してテストしてみました。
$ find . -type f | sort | xargs cat >../linux-master.dat $ time -p grep EXPORT_SYMBOL_GPL linux-master.txt >/dev/null real 0.34 user 0.14 sys 0.19 $ time -p ./hw EXPORT_SYMBOL_GPL linux-master.txt >/dev/null real 0.87 user 0.69 sys 0.18
単独ファイルだとhighwayが持つマルチスレッド機能を生かせないようで、GNU grepの方が高速に結果を返しました。
highwayの機能確認
highway --helpを実行してみた結果より、かなり多くのオプションをサポートしているように見えます。
$ ./hw --help
Usage:
hw [OPTIONS] PATTERN [PATHS]
The highway searches a PATTERN from all of files under your directory very fast.
By default hw searches in under your current directory except hidden files and
paths from .gitignore, but you can search any directories or any files you want
to search by specifying the PATHS, and you can specified multiple directories or
files to the PATHS options.
Example:
hw hoge src/ include/ tmp/test.txt
Search options:
-a, --all-files Search all files.
-e Parse PATTERN as a regular expression.
-f, --follow-link Follow symlinks.
-i, --ignore-case Match case insensitively.
-w, --word-regexp Only match whole words.
Output options:
-l, --file-with-matches Only print filenames that contain matches.
-n, --line-number Print line number with output lines.
-N, --no-line-number Don't print line number.
--color Highlight the matching strings, filenames, line numbers.
--no-color No highlight.
--group Grouping matching lines every files.
--no-group No grouping.
--no-omit Show all characters even if too long lines were matched.
By default hw print only characters near by PATTERN if
the line was too long.
Context control:
-A, --after-context=NUM Print NUM lines after match.
-B, --before-context=NUM Print NUM lines before match.
-C, --context=NUM Print NUM lines before and after matches.
-h, --help Show options help and some concept guides.
--version Show version.また、正規表現エンジンとして鬼車から派生した鬼雲を採用してようですので、かなり多くの正規表現をサポートしていると思われます。
最後に、highwayは日本語もサポートしているという情報があったので、下記のテストを行ってみましたが、期待された結果を返しませんでした。ただ、highwayソースコードをのぞいてみると、setlocale(3)をコールしていないようなので、私の使い方が正しくなかったのかもしれません。
$ LANG=ja_JP.eucJP; export LANG $ echo 海海海 | grep 海.海 海海海 $ echo 海海海 | ./hw 海.海 $
まもなく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アルゴリズムに置き換えるものです。これにより上記の欠点が解消され、大幅な性能改善が期待されます。
