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
