grab

ambil - grep sederhana namun sangat cepat

Ini adalah versi grep saya yang eksperimental dan paralel sehingga saya dapat menguji berbagai strategi untuk mempercepat akses ke pohon direktori besar. Pada penyimpanan Flash atau SSD, Anda dapat dengan mudah mengakali grep umum hingga 8 kali lipat.

Pilihan:

 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

ambil menggunakan perpustakaan pcre , jadi pada dasarnya setara dengan grep -P -a . -P penting, karena Ekspresi Reguler yang Kompatibel dengan Perl memiliki karakteristik yang berbeda dari regex dasar.

Membangun

Ada dua cabang. master dan greppin . Master adalah ambil 'tradisional' yang harus dikompilasi dan dijalankan pada sebagian besar sistem POSIX. greppin hadir dengan versi nftw() dan readdir() yang dioptimalkan dan diparalelkan, yang sekali lagi menggandakan kecepatan di atas speedup yang sudah disediakan oleh cabang master . Cabang greppin berjalan di Linux, BSD dan OSX. greppin juga dilengkapi dengan dukungan untuk perpustakaan hyperscan Intel yang mencoba mengeksploitasi instruksi SIMD CPU jika memungkinkan (AVX2, AVX512 dll.) saat mengkompilasi pola regex ke dalam kode JIT.

Kemungkinan besar Anda ingin membangun cabang greppin :

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

Pastikan Anda telah menginstal paket perpustakaan pcre dan pcre2 . Pada sistem BSD Anda memerlukan gmake alih-alih make . Jika Anda ingin melakukan teknologi mutakhir dengan beberapa mesin regex greppin dan dukungan hyperscan, Anda harus terlebih dahulu mendapatkan dan membangunnya:

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

Ini akan membangun apa yang disebut fat runtime dari lib hyperscan yang berisi dukungan untuk semua keluarga CPU untuk memilih pola kompilasi yang tepat saat runtime untuk sebagian besar kinerja. Setelah pembangunan selesai, Anda membangun greppin terhadap hal itu:

(di dalam ambil repo kloning)

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

Ini akan menghasilkan biner greppin yang memungkinkan opsi -H memuat mesin yang berbeda saat runtime, mencoba mengeksploitasi semua bit kinerja yang mungkin.

Anda dapat menghubungkannya dengan lib yang sudah diinstal, tetapi API baru saja menambahkan beberapa fungsi dalam versi 5.x dan sebagian besar distro dikirimkan dengan 4.x.

Mengapa lebih cepat?

ambil menggunakan mmap(2) dan mencocokkan seluruh gumpalan file tanpa menghitung baris baru (yang dilakukan grep meskipun tidak ada kecocokan [pada tinjauan kode grep saya pada tahun 2012; segalanya mungkin berbeda hari ini]) yang banyak lebih cepat dari read(2) -ing file dalam potongan kecil dan menghitung baris baru. Jika tersedia, grab juga menggunakan fitur PCRE JIT. Namun, percepatan hanya dapat diukur pada pohon file besar atau HDD atau SSD cepat. Dalam kasus selanjutnya, percepatannya bisa sangat drastis (hingga 3 kali lebih cepat) jika dicocokkan secara rekursif dan paralel. Karena penyimpanan adalah hambatannya, memparalelkan pencarian pada HDD tidak masuk akal, karena pencarian memerlukan lebih banyak waktu daripada sekadar melakukan hal-hal secara linear.

Selain itu, ambil melewatkan file yang terlalu kecil untuk memuat ekspresi reguler. Untuk regex yang lebih besar dalam pencarian rekursif, ini dapat melewati sejumlah file tanpa membukanya.

Diperlukan lib pcre yang cukup baru, pada beberapa sistem lama, build bisa gagal karena PCRE_INFO_MINLENGTH dan pcre_study() hilang.

File dipetakan dan dicocokkan dalam potongan 1Gig. Untuk file yang lebih besar, 4096 byte terakhir (1 halaman) dari sebuah potongan akan tumpang tindih, sehingga kecocokan pada batas 1 Gig dapat ditemukan. Dalam kasus ini, Anda melihat kecocokan menjadi dua kali lipat (tetapi dengan offset yang sama).

Jika Anda mengukur grep vs. grab , ingatlah untuk menghilangkan dentry dan cache halaman di antara setiap proses: echo 3 > /proc/sys/vm/drop_caches

Catatan, grep hanya akan mencetak 'kecocokan file biner', jika ia mendeteksi file biner, sedangkan grab akan mencetak semua kecocokan, kecuali -s diberikan. Jadi, untuk tes kecepatan Anda harus mencari ekspresi yang tidak ada dalam data, untuk menegakkan pencarian seluruh file.

ambil dibuat untuk dengan cepat menelusuri pohon direktori besar tanpa mengindeks. Grep asli memiliki rangkaian opsi yang jauh lebih lengkap. Kecepatan untuk satu kecocokan file sangat kecil, jika bisa diukur.

Untuk SSD, opsi multicore masuk akal. Untuk HDD tidak demikian, karena head harus diposisikan bolak-balik di antara thread, yang berpotensi merusak prinsip lokalitas dan mematikan kinerja.

Cabang greppin memiliki versi paralel lockfree nftw() sendiri, sehingga waktu idle N - 1 core ketika inti pertama membangun pohon direktori juga dapat digunakan untuk bekerja.

Yang perlu diperhatikan: ambil akan melintasi direktori secara fisik , yaitu tidak akan mengikuti symlink.

titik

spot adalah versi paralel dari find . Ini mendukung opsi yang paling sering digunakan seperti yang Anda tahu. Tidak banyak lagi yang perlu diceritakan, cobalah saja.

Contoh

Ini menunjukkan percepatan pada mesin 4-inti dengan pencarian di SSD:

 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

Dengan cabang 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:~#

Ya! ~ 9 detik vs. ~ 72 detik! Itu 8x lebih cepat pada mesin SSD 4-inti dibandingkan grep tradisional.

Sekadar untuk membuktikan bahwa itu menghasilkan keluaran yang sama:

 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:~#

Dalam perbandingan inti tunggal, percepatan juga bergantung pada CPU mana yang sebenarnya dijadwalkan oleh kernel grep , jadi pengambilan mungkin lebih cepat atau tidak (kebanyakan memang begitu). Jika bebannya sama di antara pengujian inti tunggal, ambil akan melihat percepatan jika mencari di pohon file besar. Pada pengaturan multi-core, grab dapat memperoleh manfaat yang sangat buruk.

perbandingan ripgrep

Proyek ini dapat ditemukan di sini.

Percepatan utama yang ada di dalam tabel benchmark mereka berasal dari fakta bahwa ripgrep mengabaikan banyak file (terutama dotfiles) ketika dipanggil tanpa opsi khusus serta memperlakukan file biner sebagai target pencocokan tunggal (mirip dengan grep ). Untuk mendapatkan hasil yang sebanding, perlu diingat (4 adalah jumlah inti):

• echo 3 > /proc/sys/vm/drop_caches di antara setiap proses
• Tambahkan -j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap ke ripgrep , karena secara default akan cocok dengan Unicode yang 3 kali lebih lambat, dan mencoba mengkompensasi kehilangan kecepatan dengan melewatkan 'abaikan' file berbasis. -e lebih cepat dari -P , jadi lebih baik pilih -e , tapi itu tidak sekuat PCRE
• arahkan output ke /dev/null untuk menghindari efek berbasis tty
• tambahkan -H -n 4 ke greppin jika Anda menginginkan kinerja terbaik. -H kompatibel dengan PCRE dengan hanya sedikit pengecualian (menurut dokumen hyperscan)
• setfattr -n user.pax.flags -v "m" /path/to/binary jika Anda menjalankan sistem grsec dan memerlukan pemetaan JIT rwx

Kalau begitu lanjutkan saja dan periksa waktunya. Bahkan saat tidak menggunakan hyperscan, greppin secara signifikan lebih cepat daripada rg saat menggunakan ekspresi PCRE2 (PCRE2 vs. PCRE2) dan masih lebih cepat saat membandingkan ekspresi tercepat (-e vs. hyperscan).