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 海.海 $