grab

grab – einfaches, aber sehr schnelles grep

Dies ist meine eigene, experimentelle, parallele Version von grep, sodass ich verschiedene Strategien testen kann, um den Zugriff auf große Verzeichnisbäume zu beschleunigen. Auf Flash-Speichern oder SSDs können Sie gängige Greps problemlos um den Faktor 8 überlisten.

Optionen:

 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 verwendet die pcre- Bibliothek und entspricht im Grunde einem grep -P -a . Das -P ist wichtig, da Perl-kompatible reguläre Ausdrücke andere Eigenschaften haben als einfache reguläre Ausdrücke.

Bauen

Es gibt zwei Zweige. master und greppin . Master ist das „traditionelle“ Grab , das auf den meisten POSIX-Systemen kompiliert und ausgeführt werden sollte. greppin verfügt über eine eigene optimierte und parallelisierte Version von nftw() und readdir() , die zusätzlich zur Beschleunigung, die der master Zweig bereits bietet, die Geschwindigkeit noch einmal verdoppelt. Der greppin -Zweig läuft unter Linux, BSD und OSX. greppin bietet außerdem Unterstützung für die Hyperscan-Bibliotheken von Intel, die nach Möglichkeit versuchen, die SIMD-Anweisungen der CPU auszunutzen (AVX2, AVX512 usw.), wenn sie das Regex-Muster in JIT-Code kompilieren.

Sie werden höchstwahrscheinlich den greppin -Zweig erstellen wollen:

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

Stellen Sie sicher, dass die Bibliothekspakete pcre und pcre2 installiert sind. Auf BSD-Systemen benötigen Sie gmake anstelle von make . Wenn Sie modernste Technologie mit der multiplen Regex-Engine und der Hyperscan-Unterstützung von greppin nutzen möchten, müssen Sie zunächst Folgendes besorgen und erstellen:

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

Dadurch wird eine sogenannte „Fat Runtime“ der Hyperscan-Bibliotheken erstellt, die alle CPU-Familien unterstützt, um zur Laufzeit das richtige Kompilierungsmuster für die größtmögliche Leistung auszuwählen. Sobald der Build abgeschlossen ist, erstellen Sie greppin dagegen:

(im geklonten Repo greifen)

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

Dadurch wird eine greppin Binärdatei erstellt, die es der Option -H ermöglicht, zur Laufzeit eine andere Engine zu laden und dabei zu versuchen, alle möglichen Leistungsbits auszunutzen.

Sie könnten es mit bereits installierten Bibliotheken verknüpfen, aber die API hat erst kürzlich einige Funktionen in der 5.x-Version hinzugefügt und die meisten Distributionen werden mit 4.x ausgeliefert.

Warum ist es schneller?

grab verwendet mmap(2) und gleicht den gesamten Datei-Blob ab, ohne Zeilenumbrüche zu zählen (was grep auch dann macht, wenn es keine Übereinstimmung gibt [nach einer grep-Codeüberprüfung von mir im Jahr 2012; die Dinge könnten heute anders sein]), was eine ganze Menge ist schneller als read(2) die Datei in kleinen Teilen bearbeiten und die Zeilenumbrüche zählen. Sofern verfügbar, nutzt Grab auch die PCRE-JIT-Funktion. Geschwindigkeitssteigerungen sind jedoch nur bei großen Dateibäumen oder schnellen Festplatten oder SSDs messbar. Im letzteren Fall kann die Beschleunigung sehr drastisch sein (bis zu dreimal schneller), wenn ein rekursiver und paralleler Abgleich erfolgt. Da der Speicher den Engpass darstellt, macht eine Parallelisierung der Suche auf Festplatten keinen Sinn, da die Suche mehr Zeit in Anspruch nimmt als nur lineare Aufgaben.

Darüber hinaus überspringt Grab Dateien, die zu klein sind, um den regulären Ausdruck zu enthalten. Bei größeren regulären Ausdrücken in einer rekursiven Suche können dadurch recht viele Dateien übersprungen werden, ohne sie überhaupt zu öffnen.

Es ist eine recht neue pcre- Bibliothek erforderlich. Auf einigen älteren Systemen kann der Build aufgrund fehlender PCRE_INFO_MINLENGTH und pcre_study() fehlschlagen.

Dateien werden mmaped und in Blöcken von 1 GB abgeglichen. Bei größeren Dateien werden die letzten 4096 Byte (1 Seite) eines Blocks überlappt, sodass Übereinstimmungen auf einer 1-GB-Grenze gefunden werden können. In diesem Fall wird die Übereinstimmung verdoppelt (jedoch mit demselben Versatz).

Wenn Sie grep vs. grab messen, denken Sie daran, die Dentry- und Seiten-Caches zwischen jedem Lauf zu löschen: echo 3 > /proc/sys/vm/drop_caches

Beachten Sie, dass grep nur „Binärdatei-Übereinstimmungen“ ausgibt, wenn es Binärdateien erkennt, während grab alle Übereinstimmungen ausgibt, es sei denn, -s ist angegeben. Für einen Geschwindigkeitstest müssen Sie also nach einem Ausdruck suchen, der nicht in den Daten vorhanden ist, um die Suche in den gesamten Dateien zu erzwingen.

Grab wurde entwickelt, um schnell große Verzeichnisbäume ohne Indizierung zu durchsuchen. Das ursprüngliche grep verfügt über einen weitaus umfassenderen Optionssatz. Die Beschleunigung für eine einzelne Dateiübereinstimmung ist sehr gering, wenn überhaupt messbar.

Bei SSDs ist die Multicore-Option sinnvoll. Bei Festplatten ist dies nicht der Fall, da der Kopf zwischen den Threads hin und her positioniert werden muss, was möglicherweise das Lokalitätsprinzip zerstört und die Leistung beeinträchtigt.

Der greppin -Zweig verfügt über eine eigene sperrenfreie Parallelversion von nftw() , sodass die Leerlaufzeit von N - 1 Kernen, wenn der 1. Kern den Verzeichnisbaum aufbaut, auch zum Arbeiten genutzt werden kann.

Was noch zu beachten ist: Grab durchläuft Verzeichnisse physisch , dh es folgt keinen symbolischen Links.

Stelle

spot ist die parallele Version von find . Es unterstützt die am häufigsten verwendeten Optionen, wie Sie es kennen. Viel mehr gibt es dazu nicht zu erzählen, probieren Sie es einfach aus.

Beispiele

Dies zeigt die Beschleunigung auf einem 4-Kern-Rechner bei einer Suche auf einer 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

Mit greppin -Zweig:

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

Ja! ~ 9s vs. ~ 72s! Das ist auf einer 4-Kern-SSD-Maschine achtmal so schnell wie beim herkömmlichen grep.

Nur um zu beweisen, dass es zur gleichen Ausgabe geführt hat:

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

Im Single-Core-Vergleich hängt die Beschleunigung auch davon ab, auf welcher CPU der Kernel den grep tatsächlich einplant, sodass ein Grab schneller sein kann oder auch nicht (meistens ist er es). Wenn die Last bei den Single-Core-Tests gleich ist, wird Grab bei der Suche in großen Dateibäumen eine Beschleunigung feststellen. Bei Multi-Core-Setups kann Grab von Vorteil sein.

Ripgrep-Vergleich

Das Projekt finden Sie hier.

Die Hauptbeschleunigung in ihren Benchmark-Tabellen ergibt sich aus der Tatsache, dass ripgrep viele Dateien (insbesondere Punktdateien) ignoriert, wenn es ohne spezielle Optionen aufgerufen wird, und Binärdateien als Single-Match-Ziel behandelt (ähnlich wie grep ). Um vergleichbare Ergebnisse zu erhalten, beachten Sie (4 ist die Anzahl der Kerne):

• echo 3 > /proc/sys/vm/drop_caches zwischen jedem Lauf
• Fügen Sie -j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap zu ripgrep hinzu, da es standardmäßig mit Unicode übereinstimmt, das dreimal langsamer ist, und versucht, den Geschwindigkeitsverlust durch Überspringen von „Ignorieren“ zu kompensieren. -basierte Dateien. -e ist schneller als -P , also wählen Sie besser -e , aber das ist nicht so leistungsstark wie ein PCRE
• Leiten Sie die Ausgabe nach /dev/null um, um TTY-basierte Effekte zu vermeiden
• Fügen Sie -H -n 4 zu greppin hinzu, wenn Sie die beste Leistung wünschen. -H ist bis auf wenige Ausnahmen PCRE-kompatibel (laut Hyperscan-Doku)
• setfattr -n user.pax.flags -v "m" /path/to/binary wenn Sie auf grsec-Systemen laufen und rwx-JIT-Zuordnungen benötigen

Dann machen Sie einfach weiter und prüfen Sie die Zeitangaben. Auch wenn kein Hyperscan verwendet wird, ist greppin deutlich schneller als rg , wenn PCRE2-Ausdrücke verwendet werden (PCRE2 vs. PCRE2) und immer noch schneller, wenn die schnellsten Ausdrücke verglichen werden (-e vs. Hyperscan).