grabダウンロード - grabソースコードのダウンロード

grab

その他のソースコード

1.0.0

ダウンロード

grab - シンプルですが非常に高速な grep

グレッピン

これは私独自の実験用のgrepの並列バージョンであり、大規模なディレクトリツリーへのアクセスを高速化するためのさまざまな戦略をテストできます。フラッシュストレージまたは SSD では、一般的な grep を最大 8 倍も簡単に上回ることができます。

オプション:

 Usage: ./greppin [-rIOLlsSH] [-n <cores>] <regex> <path>

	-2	-- use PCRE2 instead of PCRE
	-O	-- print file offset of match
	-l	-- do not print the matching line (Useful if you want
		   to see _all_ offsets; if you also print the line, only
		   the first match in the line counts)
	-s	-- single match; dont search file further after first match
		   (similar to grep on a binary)
	-H	-- use hyperscan lib for scanning
	-S	-- only for hyperscan: interpret pattern as string literal instead of regex
	-L	-- machine has low mem; half chunk-size (default 2GB)
		   may be used multiple times
	-I	-- enable highlighting of matches (useful)
	-n	-- Use multiple cores in parallel (omit for single core)
	-r	-- recurse on directory

grab はpcreライブラリを使用するため、基本的にgrep -P -aと同等です。 Perl 互換の正規表現には基本的な正規表現とは異なる特性があるため、 -P重要です。

建てる

支店が 2 つあります。 masterとgreppin 。 Master は、ほとんどの POSIX システムでコンパイルして実行できる「従来の」グラブです。 greppin 、独自の最適化および並列化されたnftw()およびreaddir()バージョンが付属しており、これにより、 masterブランチがすでに提供している高速化に加えて、さらに速度が 2 倍になります。 greppinブランチは Linux、BSD、OSX 上で実行されます。 greppin正規表現パターンを JIT コードにコンパイルするときに、可能であれば CPU の SIMD 命令 (AVX2、AVX512 など) を利用しようとする Intel のハイパースキャンライブラリのサポートも付属しています。

おそらくgreppinブランチを構築することになるでしょう。

 $ git checkout greppin
[...]
$ cd src; make
[...]

pcreおよびpcre2ライブラリパッケージがインストールされていることを確認してください。 BSD システムでは、 makeの代わりにgmakeが必要です。 greppin の複数の正規表現エンジンとハイパースキャンのサポートを使用して最先端の技術を実行したい場合は、まずそれを入手して構築する必要があります。

 $ git clone https://github.com/intel/hyperscan
[...]
$ cd hyperscan
$ mkdir build; cd build
$ cmake -DFAT_RUNTIME=1 -DBUILD_STATIC_AND_SHARED=1 ..
[...]
$ make
[...]

これにより、実行時に最適なコンパイルパターンを選択してパフォーマンスを最大限に高めるために、すべての CPU ファミリのサポートが含まれるハイパースキャンライブラリのいわゆるファットランタイムが構築されます。ビルドが完了したら、それに対してgreppin をビルドします。

(クローンされたリポジトリを取得する内部)

 $ cd src
$ HYPERSCAN_BUILD=/path/to/hyperscan/build make -f Makefile.hs
[...]

これにより、実行時に-Hオプションで別のエンジンをロードできるようにするgreppinバイナリが生成され、可能なすべてのパフォーマンスビットを活用しようとします。

すでにインストールされているライブラリにリンクすることもできますが、API は最近 5.x バージョンにいくつかの機能を追加したばかりで、ほとんどのディストリビューションには 4.x が付属しています。

なぜ速いのでしょうか?

grab はmmap(2)使用しており、改行をカウントせずにファイル BLOB 全体と一致します (これは、一致するものがなくてもgrepが実行します [2012 年の grep コードレビューの時点では、現在は状況が異なる可能性があります])。 read(2)よりも高速で、ファイルを小さなチャンクに分割して改行をカウントします。利用可能な場合、グラブはPCRE JIT 機能も使用します。ただし、高速化は、大きなファイルツリーまたは高速な HDD または SSD でのみ測定可能です。後者の場合、再帰的かつ並列的にマッチングを行うと、速度が大幅に向上します (最大 3 倍高速になります)。ストレージがボトルネックになっているため、HDD での検索を並列化することは意味がありません。シークには単にリニアに実行するよりも時間がかかるからです。

さらに、グラブは、正規表現を含めるには小さすぎるファイルをスキップします。再帰的検索でより大きな正規表現を使用する場合、かなりの量のファイルが開かれずにスキップされる可能性があります。

まったく新しいpcreライブラリが必要です。一部の古いシステムでは、 PCRE_INFO_MINLENGTHとpcre_study()が欠落しているためにビルドが失敗する可能性があります。

ファイルは 1Gig のチャンクで mmap され、一致します。より大きなファイルの場合、チャンクの最後の 4096 バイト (1 ページ) がオーバーラップされるため、1 ギガ境界で一致するものが見つかります。この場合、一致が 2 倍になっていることがわかります (ただし、オフセットは同じです)。

grepとgrab を測定する場合は、実行ごとに dentry キャッシュとページキャッシュを削除することを念頭に置いてください: echo 3 > /proc/sys/vm/drop_caches

grep は、バイナリファイルを検出した場合、「バイナリファイルの一致」のみを出力しますが、 grab は、 -sが指定されていない限り、すべての一致を出力することに注意してください。したがって、速度テストでは、ファイル全体の検索を強制するために、データ内に存在しない式を検索する必要があります。

grab は、インデックスを作成せずに大きなディレクトリツリーをすばやく grep するために作成されました。オリジナルのgrep には、はるかに完全なオプションセットがあります。単一ファイルの一致の速度向上は、測定できるとしても非常にわずかです。

SSD の場合、マルチコアオプションが合理的です。 HDD の場合はそうではありません。ヘッドをスレッド間で前後に配置する必要があるため、局所性原理が破壊され、パフォーマンスが低下する可能性があります。

greppinブランチは、独自のロックフリー並列バージョンのnftw()を備えているため、最初のコアがディレクトリツリーを構築するときの N - 1 コアのアイドリング時間も作業に使用できます。

注意すべき点: grab はディレクトリを物理的に横断します。つまり、シンボリックリンクをたどりません。

スポット

spot findの並列バージョンです。ご存知のとおり、最も頻繁に使用されるオプションがサポートされています。それについてはこれ以上語ることはありません。試してみてください。

例

これは、SSD での検索を使用した 4 コアマシンでの高速化を示しています。

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -r foobardoesnotexist /source/linux

real	0m34.811s
user	0m3.710s
sys	0m10.936s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -r foobardoesnotexist /source/linux

real	0m31.629s
user	0m4.984s
sys	0m8.690s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 2 -r foobardoesnotexist /source/linux

real	0m15.203s
user	0m3.689s
sys	0m4.665s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 4 -r foobardoesnotexist /source/linux

real	0m13.135s
user	0m4.023s
sys	0m5.581s

greppinブランチの場合:

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -a -P -r linus /source/linux/|wc -l
16918

real    1m12.470s
user    0m49.548s
sys     0m6.162s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time greppin -n 4 -r linus /source/linux/|wc -l
16918

real    0m8.773s
user    0m4.670s
sys     0m5.837s
root@linux:~#

はい！～9秒対～72秒！これは、4 コア SSD マシンでは従来の grep の 8 倍の速度です。

同じ出力が得られたことを証明するために、次のようにします。

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# greppin -n 4 -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0  -
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# grep -P -a -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0  -
root@linux:~#

シングルコアの比較では、速度向上はカーネルが実際にgrep をスケジュールする CPU にも依存するため、 grabのほうが速い場合もあればそうでない場合もあります (ほとんどの場合は速いです)。シングルコアテスト間で負荷が等しい場合、大きなファイルツリーを検索すると、 grab の速度が向上します。マルチコア設定では、グラブは当然の利点をもたらします。

リップレップの比較

プロジェクトはここで見つけることができます。

ベンチマークテーブル内の主な高速化は、 ripgrep が特別なオプションなしで呼び出された場合に多くのファイル (特にドットファイル) を無視すること、およびバイナリファイルを ( grepと同様に) 単一一致ターゲットとして扱うという事実から生じています。同等の結果を得るには、次のことに注意してください (4 はコアの数です)。

各実行間のecho 3 > /proc/sys/vm/drop_caches
-j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap ripgrepに追加します。これは、デフォルトで 3 倍遅い Unicode に一致し、「ignore」をスキップすることで速度損失を補おうとするためです。 -ベースのファイル。 -e -Pよりも高速なので、 -e選択することをお勧めしますが、PCRE ほど強力ではありません。
tty ベースの影響を避けるために、出力を/dev/nullにリダイレクトします。
最高のパフォーマンスが必要な場合は、 greppinに-H -n 4追加します。 -H 、ごく少数の例外を除いて PCRE と互換性があります (ハイパースキャンのドキュメントによると)。
grsec システム上で実行し、rwx JIT マッピングが必要な場合はsetfattr -n user.pax.flags -v "m" /path/to/binary