grep と sift を比較した

Linux

sift というツールがあります。
 https://sift-tool.org/
sift は better grep なツールで、上記サイトのパフォーマンスによるとすべての場合において grep より速く、場合によっては40倍速以上のパフォーマンスを出すという、嘘だろ承太郎！？な状態なのでこの怪しい伝説を検証してみます。
 https://sift-tool.org/info.html

環境

僕の環境はこちら。

CPU: Intel Corei7 4790
メモリ: 16GB
ストレージ: SSD 256GB
OS: Ubuntu 14.04 64bit

インストール

https://sift-tool.org/download.html から適切なアーカイブをダウンロードして解凍。

$ tar zvxf sift_0.3.4_linux_amd64.tar.gz 
sift_0.3.4_linux_amd64/sift
sift_0.3.4_linux_amd64/LICENSE

出てきた sift ファイルをパスの通ったディレクトリに移しましょう。

$ sudo mv sift_0.3.4_linux_amd64/sift /usr/local/bin/

実験準備

僕のリポジトリを置いてあるディレクトリ、~/Repository を対象に実験。
このディレクトリはサイズが 5.4GB, 約 12 万ファイル、約 2 万ディレクトリで構成されています。

各実験には下記の検索単語 100 個を使います。
https://gist.github.com/aoking/62c992d3f71cdc5f3156

grep, sift それぞれで実験する前に vm.drop_caches=3 してカーネルからキャッシュを追い出します。

$ sudo sysctl -w vm.drop_caches=3

実験1 : 単純な検索

grep 版
$ sudo sysctl -w vm.drop_caches=3
$ time for i in $(cat word.dat); do grep -r $i . > /dev/null; done

real 値は 6m10s でした。

sift 版
$ sudo sysctl -w vm.drop_caches=3
$ time for i in $(cat word.dat); do sift $i . > /dev/null; done

むむ、1行が長いファイルは検索できないようです。

Error: cannot process data from file 'lucene-solr/lucene/analysis/kuromoji/src/test/org/apache/lucene/analysis/ja/bocchan.utf-8': file contains very long lines (no newline in 262144 bytes)
  
この仕様はさておき、とりあえず grep と同様の条件で時間を測定。すると、 2m15s でした。
grep が 6m10s、sift が 2m15s なので、sift のほうが 2.74 倍高速。

実験2 : ignore case での検索

同じディレクトリを対象に、ignore case オプションをつけて検索。ただしあまりに時間がかかるので、word.dat の上位 10 件のみを使用。

grep 版
$ sudo sysctl -w vm.drop_caches=3
$ time for i in $(cat word.dat | head); do grep -ri $i . > /dev/null; done

25m47s.

sift 版
$ sudo sysctl -w vm.drop_caches=3
$ time for i in $(cat word.dat | head); do sift -i $i . > /dev/null; done

40s.

grep が 25m47s, sift が 40s なので、sift のほうが 38.67 倍速！

実験3 : 正規表現での検索


検索単語を正規表現にして検索してみましょう。 "[A-Z][a-z]*Set" というパターンを用いてみます。ちなみにこのパターンで HashSet や BitSet という言葉がマッチします。
grep 版
$ sudo sysctl -w vm.drop_caches=3
$ time grep -r -E "[A-Z][a-z]*Set" . > /dev/null

33s.

sift 版
$ sudo sysctl -w vm.drop_caches=3
$ time sift "[A-Z][a-z]*Set" . > /dev/null

2m48s.

grep が 33s, sift が 2m48s なので、grep のほうが 5.09 倍高速！

sift さんどうしたんでしょうか。

grep 版

別の正規表現でも実験。今度は "at[A-Za-z]+" で。atLeast とかにマッチします。
 
$ sudo sysctl -w vm.drop_caches=3
$ time grep -r -E "at[A-Za-z]+" . > /dev/null
39s.
sift 版
$ sudo sysctl -w vm.drop_caches=3
$ time sift "at[A-Za-z]+" . > /dev/null

20s.

grep が 39s, sift が 20s なので、sift のほうが 1.95 倍高速。

grep 版

一応もうひとつ。"[0-9]{3,} で３つ以上の数字が連続する文字列を見つけましょう。

$ sudo sysctl -w vm.drop_caches=3
$ time grep -r -E "[0-9]{3,}" . > /dev/null

1m37s.

sift 版
$ sudo sysctl -w vm.drop_caches=3
$ time sift "[0-9]{3,}" . > /dev/null

死亡。10GB以上空きメモリあったのですが全部食い尽くしてマシンが挙動不審になり、Ctrl+C で止めました。
sift は正規表現を使っての検索はいまいちです。僕が sift を常用することは無いでしょう。

実験4 : 検索対象を絞り込んでの検索

こういうのも実験しておきましょう。.java ファイルを対象に、100 単語で検索。

grep 版
$ sudo sysctl -w vm.drop_caches=3
$ time for i in $(cat word.dat); do grep -r --include=\*.java $i . > /dev/null; done

32s.

sift
$ sudo sysctl -w vm.drop_caches=3
$ time for i in $(cat word.dat); do sift --ext=java $i . > /dev/null; done

50s.

grep が 32s, sift が 50s なので grep のほうが 1.56 倍高速。

まとめ


確かに sift のほうが高速なシーンもある。とはいえ正規表現の検索では grep に負けたり、10GB 以上もメモリを消費して死ぬ等、性能だけでなく安定性にも疑問がある。
 まだ sift は常用できるツールではない、というのが僕の見解です。

ふつうのLinuxプログラミング Linuxの仕組みから学べるgccプログラミングの王道

ふつうのLinuxプログラミング Linuxの仕組みから学べるgccプログラミングの王道