Wie läuft grep so schnell?

113

Ich bin wirklich erstaunt über die Funktionalität von GREP in der Shell. Früher habe ich die Teilstring-Methode in Java verwendet, aber jetzt verwende ich GREP dafür und es wird in Sekundenschnelle ausgeführt. Es ist unglaublich schneller als der Java-Code, den ich früher geschrieben habe. (Nach meiner Erfahrung könnte ich mich jedoch irren)

Davon abgesehen konnte ich nicht herausfinden, wie es passiert? Es ist auch nicht viel im Web verfügbar.

Kann mir jemand dabei helfen?

Kumpel
quelle
5
Es ist Open Source, so dass Sie sich selbst davon überzeugen können. gnu.org/software/grep/devel.html
driis
6
Ridiculous Fish hat eine großartige Zusammenfassung, die genau Ihre Frage beantwortet: lächerlichfish.com
blog/posts/old-age-
@WilliamPursell Wenn die Ausführungszeit in den Sekunden vergeht, hat sich die JIT wahrscheinlich erwärmt und der verblüffende Unterschied ist darauf zurückzuführen, dass (1) grep unglaublich klug ist und (2) der Java-Code eine ziemlich schlechte Algorithmusauswahl trifft für das spezifische problem konzentriert sich grep auf.
3
Wie viel Zeit verbringt Ihre Java-Implementierung mit dem Starten der JVM und wie viel Zeit verbringt sie mit der tatsächlichen Ausführung Ihres Codes? Oder es hängt vom Algorithmus ab, den Sie in Ihrem Java-Code verwendet haben. Ein O (N ^ 2) -Algorithmus ist in jeder Sprache wahrscheinlich langsam.
Keith Thompson

Antworten:

169

Angenommen, Ihre Frage bezieht sich GNU grepspeziell. Hier ist eine Notiz des Autors Mike Haertel:

GNU grep ist schnell, weil es vermeidet, jedes Eingangsbyte zu betrachten.

GNU grep ist schnell , weil es sehr wenige Befehle für jedes Byte ausführt , die es tut Blick auf.

GNU grep verwendet den bekannten Boyer-Moore-Algorithmus, der zuerst nach dem letzten Buchstaben der Zielzeichenfolge sucht und anhand einer Nachschlagetabelle angibt, wie weit die Eingabe übersprungen werden kann, wenn ein nicht übereinstimmendes Zeichen gefunden wird.

GNU grep rollt auch die innere Schleife von Boyer-Moore ab und richtet die Delta-Tabelleneinträge von Boyer-Moore so ein, dass der Schleifen-Exit-Test nicht bei jedem entrollten Schritt durchgeführt werden muss. Dies hat zur Folge, dass GNU grep im Grenzfall im Durchschnitt weniger als 3 x 86-Befehle ausführt, die für jedes tatsächlich betrachtete Eingangsbyte ausgeführt werden (und viele Bytes vollständig überspringt).

GNU grep verwendet rohe Unix-Eingabesystemaufrufe und vermeidet das Kopieren von Daten nach dem Lesen. Darüber hinaus vermeidet GNU grep, den Eingang in Zeilen zu unterbrechen. Das Suchen nach Zeilenumbrüchen würde das Grep um ein Vielfaches verlangsamen, denn um die Zeilenumbrüche zu finden, müsste jedes Byte überprüft werden!

Anstatt zeilenorientierte Eingaben zu verwenden, liest GNU grep Rohdaten in einen großen Puffer, durchsucht den Puffer mit Boyer-Moore und sucht erst dann nach den Begrenzungszeilen, wenn eine Übereinstimmung gefunden wird (bestimmte Befehlszeilenoptionen wie - n Deaktivieren Sie diese Optimierung.)

Diese Antwort ist eine Teilmenge der hier entnommenen Informationen .

Steve
quelle
41

Zu Steves hervorragender Antwort hinzufügen.

Es ist vielleicht nicht allgemein bekannt, aber grep ist fast immer schneller, wenn nach einer längeren Pattern-Zeichenfolge gesucht wird als nach einer kurzen, da Boyer-Moore in einem längeren Pattern in längeren Schritten vorwärts springen kann, um noch bessere sublineare Geschwindigkeiten zu erzielen :

Beispiel:

# after running these twice to ensure apples-to-apples comparison
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log
28
0.168u 0.068s 0:00.26

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log
28
0.100u 0.056s 0:00.17

Die längere Form ist 35% schneller!

Woher? Boyer-Moore erstellt aus der Musterzeichenfolge eine Sprung-Vorwärts-Tabelle. Wenn eine Nichtübereinstimmung vorliegt, wird der längste mögliche Sprung (vom letzten zum ersten Zeichen) ausgewählt, bevor ein einzelnes Zeichen in der Eingabe mit dem Zeichen in der Sprung-Tabelle verglichen wird.

Hier ist ein Video, das Boyer Moore erklärt (Dank an kommradHomer)

Ein weiteres häufiges Missverständnis (für GNU grep) ist, dass fgrepes schneller ist als grep. fin fgrepsteht nicht für 'schnell', sondern für 'fest' (siehe Manpage), und da beide dasselbe Programm sind und beide Boyer-Moore verwenden , gibt es keinen Unterschied in der Geschwindigkeit zwischen ihnen bei der Suche nach fest- Zeichenfolgen ohne reguläre Zeichen. Der einzige Grund , warum ich Gebrauch fgrepist , wenn es gibt ein regexp spezielles Zeichen (wie ., [], oder *) Ich will sich nicht als solche interpretiert werden. Und selbst dann wird die tragbarere / Standardform von grep -Fbevorzugt fgrep.

arielf
quelle
3
Es ist intuitiv, dass längere Muster schneller sind. Wenn das Muster ein Byte wäre, müsste grep jedes Byte überprüfen. Wenn das Muster 4 Byte groß ist, kann es zu 4-Byte-Sprüngen kommen. Wenn das Muster so lang wie Text wäre, würde grep nur einen Schritt ausführen.
Noel
12
Ja, es ist intuitiv - wenn Sie verstehen, wie Boyer-Moore funktioniert.
Arielf
2
Auch sonst ist es intuitiv. Es wäre einfacher, eine lange Nadel im Heuhaufen zu finden als eine kürzere
RajatJ
2
Das Gegenbeispiel zu "schneller sein, wenn länger" sind Fälle, in denen Sie viele Tests durchführen müssen, bevor Sie versagen, und trotzdem nicht weitermachen können. Angenommen, die Datei xs.txtenthält 100000000 'x, und Sie tun dies grep yx xs.txt, dann findet sie tatsächlich keine Übereinstimmung früher als wenn Sie dies tun grep yxxxxxxxxxxxxxxxxxxx xs.txt. Die Verbesserung von Boyer-Moore-Horspool gegenüber Boyer-Moore verbessert in diesem Fall das Überspringen, aber im allgemeinen Fall werden es wahrscheinlich nicht nur drei Maschinenanweisungen sein.
lrn
2
@Tino danke. Ja, es scheint, dass die Zeiten, in denen (GNU) grep/fgrep/egrepalle Hardlinks zu derselben ausführbaren Datei waren, vorbei sind. Sie (und andere Erweiterungen wie die z*grep bz*grepUtils, die im laufenden Betrieb dekomprimiert werden) sind jetzt kleine Shell-Wrapper grep. Einige interessante historische Kommentare zum Wechsel zwischen einer einzelnen ausführbaren Datei und Shell-Wrappern finden Sie in diesem Commit: git.savannah.gnu.org/cgit/grep.git/commit/…
arielf