grab

Grab - grep เรียบง่าย แต่เร็วมาก

นี่คือ grep เวอร์ชันทดลองและขนานของฉันเอง ดังนั้นฉันจึงสามารถทดสอบกลยุทธ์ต่างๆ เพื่อเพิ่มความเร็วในการเข้าถึงแผนผังไดเร็กทอรีขนาดใหญ่ บนที่เก็บข้อมูล Flash หรือ SSD คุณสามารถเอาชนะ Greps ทั่วไปได้อย่างง่ายดายถึง 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 -P มีความสำคัญ เนื่องจากนิพจน์ทั่วไปที่เข้ากันได้กับ Perl มีลักษณะที่แตกต่างจาก regexes พื้นฐาน

สร้าง

มีสองสาขา. master และ greppin Master เป็น โปรแกรม 'ดั้งเดิม' ที่ควรคอมไพล์และรันบนระบบ POSIX ส่วนใหญ่ greppin มาพร้อมกับเวอร์ชันที่ปรับให้เหมาะสมและขนานกันของ nftw() และ readdir() ซึ่งเพิ่มความเร็วเป็นสองเท่าอีกครั้งจากการเร่งความเร็วที่สาขา master จัดเตรียมไว้ให้แล้ว สาขา greppin ทำงานบน Linux, BSD และ OSX greppin ยังมาพร้อมกับการรองรับไลบรารีไฮเปอร์สแกนของ Intel ที่พยายามใช้ประโยชน์จากคำสั่ง SIMD ของ CPU หากเป็นไปได้ (AVX2, AVX512 ฯลฯ ) เมื่อรวบรวมรูปแบบ regex ลงในโค้ด JIT

คุณมักจะต้องการสร้างสาขา greppin :

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

ตรวจสอบให้แน่ใจว่าคุณได้ติดตั้งแพ็คเกจไลบรารี pcre และ pcre2 แล้ว บนระบบ BSD คุณต้องใช้ gmake แทน make . หากคุณต้องการทำเทคโนโลยีล้ำสมัยด้วยเอ็นจิ้น regex หลายตัว ของ greppin และรองรับไฮเปอร์สแกน คุณต้องได้รับและสร้างสิ่งนั้นก่อน:

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

สิ่งนี้จะสร้างสิ่งที่เรียกว่า รันไทม์อ้วน ของไฮเปอร์สแกน libs ซึ่งมีการรองรับตระกูล CPU ทั้งหมด เพื่อเลือกรูปแบบการคอมไพล์ที่ถูกต้อง ณ รันไทม์เพื่อประสิทธิภาพสูงสุด เมื่อการสร้างเสร็จสิ้น คุณจะสร้าง greppin เพื่อต่อต้าน:

(ภายใน repo โคลนคว้า)

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

สิ่งนี้จะสร้างไบนารี greppin ที่เปิดใช้งานตัวเลือก -H เพื่อโหลดเอ็นจิ้นอื่นในขณะรันไทม์ โดยพยายามใช้ประโยชน์จากบิตประสิทธิภาพที่เป็นไปได้ทั้งหมด

คุณสามารถเชื่อมโยงกับ libs ที่ติดตั้งไว้แล้วได้ แต่ API เพิ่งเพิ่มฟังก์ชันบางอย่างในเวอร์ชัน 5.x และ distros ส่วนใหญ่มาพร้อมกับ 4.x

ทำไมมันถึงเร็วกว่า?

Grab ใช้ mmap(2) และจับคู่ไฟล์ทั้งหมด blob โดยไม่นับการขึ้นบรรทัดใหม่ (ซึ่ง grep กำลังทำอยู่แม้ว่าจะไม่มีการจับคู่ก็ตาม [จากการทบทวนโค้ด grep ของฉันในปี 2012 สิ่งต่าง ๆ อาจแตกต่างกันในวันนี้]) ซึ่งมีมาก เร็วกว่า read(2) - ไฟล์เป็นชิ้นเล็ก ๆ และนับการขึ้นบรรทัดใหม่ หากมี Grab จะใช้ฟีเจอร์ PCRE JIT ด้วย อย่างไรก็ตาม การเร่งความเร็วสามารถวัดได้บนแผนผังไฟล์ขนาดใหญ่หรือ HDD หรือ SSD ที่เร็วเท่านั้น ในกรณีหลัง การเร่งความเร็วอาจเกิดขึ้นได้อย่างมาก (เร็วขึ้นถึง 3 เท่า) หากจับคู่แบบเรียกซ้ำและขนานกัน เนื่องจากพื้นที่จัดเก็บข้อมูลเป็นจุดคอขวด การค้นหา HDD แบบขนานจึงไม่สมเหตุสมผล เนื่องจากการแสวงหาใช้เวลามากกว่าการทำสิ่งต่างๆ เชิงเส้น

นอกจากนี้ Grab กำลังข้ามไฟล์ที่มีขนาดเล็กเกินไปที่จะมีนิพจน์ทั่วไป สำหรับ regex ที่ใหญ่กว่าในการค้นหาแบบเรียกซ้ำ การดำเนินการนี้สามารถข้ามไฟล์ได้ค่อนข้างดีโดยไม่ต้องเปิดไฟล์ด้วยซ้ำ

จำเป็นต้องมี pcre lib ที่ค่อนข้างใหม่ ในระบบเก่าบางระบบบิลด์อาจล้มเหลวเนื่องจาก PCRE_INFO_MINLENGTH และ pcre_study() หายไป

ไฟล์ถูกแมปและจับคู่เป็นชิ้นขนาด 1Gig สำหรับไฟล์ที่มีขนาดใหญ่กว่า 4,096 ไบต์สุดท้าย (1 หน้า) ของก้อนข้อมูลจะซ้อนทับกัน เพื่อให้สามารถค้นหารายการที่ตรงกันบนขอบเขต 1 Gig ได้ ในกรณีนี้ คุณเห็นการจับคู่เป็นสองเท่า (แต่มีออฟเซ็ตเท่ากัน)

หากคุณวัด grep vs. Grab โปรดจำไว้ว่าให้วาง dentry และแคชเพจระหว่างการรันแต่ละครั้ง: echo 3 > /proc/sys/vm/drop_caches

โปรดทราบว่า grep จะพิมพ์เฉพาะ 'ไฟล์ไบนารีที่ตรงกัน' หากตรวจพบไฟล์ไบนารี่ ในขณะที่ Grab จะพิมพ์รายการที่ตรงกันทั้งหมด เว้นแต่จะได้รับ -s ดังนั้น สำหรับการทดสอบความเร็ว คุณต้องค้นหานิพจน์ที่ ไม่มี อยู่ในข้อมูล เพื่อบังคับใช้การค้นหาไฟล์ทั้งหมด

Grab ถูกสร้างขึ้นเพื่อ grep ผ่านแผนผังไดเร็กทอรีขนาดใหญ่อย่างรวดเร็วโดยไม่มีการจัดทำดัชนี grep ดั้งเดิมมีชุดตัวเลือกที่สมบูรณ์กว่ามาก การเร่งความเร็วสำหรับการจับคู่ไฟล์เดียวนั้นน้อยมากหากสามารถวัดผลได้

สำหรับ SSD ตัวเลือกมัลติคอร์ก็สมเหตุสมผล สำหรับ HDD ไม่ได้เป็นเช่นนั้น เนื่องจากหัวจะต้องวางตำแหน่งไปมาระหว่างเธรด ซึ่งอาจทำลายหลักการของท้องถิ่นและประสิทธิภาพการทำงานที่ลดลง

สาขา greppin มีเวอร์ชันขนานที่ไม่มีการล็อคของ nftw() ดังนั้นเวลาที่ไม่ทำงานของคอร์ N - 1 เมื่อคอร์ที่ 1 สร้างแผนผังไดเร็กทอรีก็สามารถใช้สำหรับการทำงานได้เช่นกัน

สิ่งที่เหลืออยู่ที่ควรทราบ: Grab จะสำรวจไดเร็กทอรี ทางกายภาพ กล่าวคือ มันจะไม่ติดตามซิมลิงก์

จุด

spot เป็นเวอร์ชันคู่ขนานของ find รองรับตัวเลือกที่ใช้บ่อยที่สุดตามที่คุณทราบ ไม่มีอะไรจะเล่ามากไปกว่านั้น ลองดูสิ

ตัวอย่าง

นี่แสดงการเร่งความเร็วบนเครื่อง 4 คอร์พร้อมการค้นหาบน 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

ด้วยสาขา 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:~#

ใช่! ~ 9s ปะทะ ~ 72s! เร็วกว่า grep แบบเดิมถึง 8 เท่าบนเครื่อง SSD แบบ 4 คอร์

เพียงเพื่อพิสูจน์ว่ามันให้ผลลัพธ์เดียวกัน:

 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 ดังนั้น การคว้า อาจจะเร็วขึ้นหรือไม่ก็ได้ (ส่วนใหญ่เป็นอย่างนั้น) หากโหลดเท่ากันในการทดสอบแบบคอร์เดี่ยว การคว้า จะเห็นการเร่งความเร็วหากค้นหาบนแผนผังไฟล์ขนาดใหญ่ ในการตั้งค่าแบบมัลติคอร์ การคว้า จะได้รับประโยชน์จากคอร์

การเปรียบเทียบริปเกรป

โครงการสามารถพบได้ที่นี่

การเร่งความเร็วหลักที่อยู่ในตารางเบนช์มาร์กนั้นเกิดจากการที่ ripgrep ละเว้นไฟล์จำนวนมาก (โดยเฉพาะ dotfiles) เมื่อถูกเรียกใช้โดยไม่มีตัวเลือกพิเศษ เช่นเดียวกับการปฏิบัติต่อไฟล์ไบนารี่เป็นเป้าหมายที่ตรงกันเพียงครั้งเดียว (คล้ายกับ grep ) เพื่อให้มีผลลัพธ์ที่เปรียบเทียบได้ โปรดทราบว่า (4 คือจำนวนคอร์):

• echo 3 > /proc/sys/vm/drop_caches ระหว่างการรันแต่ละครั้ง
• เพิ่ม -j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap ไปที่ ripgrep เนื่องจากโดยค่าเริ่มต้นจะจับคู่ Unicode ซึ่งช้ากว่า 3 เท่าและพยายามชดเชย speedloss โดยการข้าม 'ละเว้น' - ไฟล์พื้นฐาน -e เร็วกว่า -P ดังนั้นควรเลือก -e แต่นั่นไม่ทรงพลังเท่า PCRE
• เปลี่ยนเส้นทางเอาต์พุตไปที่ /dev/null เพื่อหลีกเลี่ยงเอฟเฟกต์แบบ tty
• เพิ่ม -H -n 4 ใน greppin หากคุณต้องการประสิทธิภาพที่ดีที่สุด -H คือ PCRE เข้ากันได้กับข้อยกเว้นเพียงไม่กี่อย่างเท่านั้น (ตามเอกสารไฮเปอร์สแกน)
• setfattr -n user.pax.flags -v "m" /path/to/binary หากคุณทำงานบนระบบ grsec และต้องการการแมป rwx JIT

จากนั้นเพียงไปข้างหน้าและตรวจสอบการกำหนดเวลา แม้ว่าจะไม่ได้ใช้ไฮเปอร์สแกนก็ตาม greppin จะเร็วกว่า rg อย่างมากเมื่อใช้นิพจน์ PCRE2 (PCRE2 กับ PCRE2) และยังเร็วกว่าเมื่อเปรียบเทียบนิพจน์ที่เร็วที่สุด (-e กับ Hyperscan)