Grep -E, Sed -E - geringe Leistung, wenn '[x] {1,9999}' verwendet wird, aber warum?

9

Wenn grepoder sedmit der Option verwendet werden --extended-regexpund das Muster {1,9999}Teil des verwendeten regulären Ausdrucks ist, wird die Leistung dieser Befehle gering. Um klarer zu sein, werden im Folgenden einige Tests angewendet. [1] [2]

  • Die relative Leistung grep -E, egrepund sed -Eist fast gleich, so dass nur der Test, der mit gemacht wurden grep -Ezur Verfügung gestellt.

Test 1

$ time grep -E '[0-9]{1,99}' < /dev/null

real    0m0.002s

Test 2

$ time grep -E '[0-9]{1,9999}' < /dev/null

> real    0m0.494s

Test 3

$ time grep -E '[0123456789] {1,9999}' </ dev / null

> echte 21m43.947s

Test 4

$ time grep -E '[0123456789]+' < /dev/null
$ time grep -E '[0123456789]*' < /dev/null
$ time grep -E '[0123456789]{1,}' < /dev/null
$ time grep -P '[0123456789]{1,9999}' < /dev/null

real    0m0.002s

Was ist der Grund für diesen signifikanten Leistungsunterschied?

command-line grep regex pa4080
quelle
3
Das ist eine interessante Beobachtung - ich vermute, Sie müssten tief in die Interna von grep [0-9]+
eintauchen
3
Die Eingabe spielt keine Rolle. Wie @steeldriver vorschlägt, geht die Verlangsamung dem Abgleich voraus . Ein einfacher Test ist time grep -E '[0-9]{1,99}' </dev/nullgegenüber time grep -E '[0-9]{1,9999}' </dev/null. Auch ohne Eingabe ist der zweite Befehl langsam (am 16.04.). Wie erwartet ist das Weglassen -Eund Entkommen {und }das gleiche Verhalten und Ersetzen -Edurch -Pnicht langsam (PCRE ist eine andere Engine). Besonders interessant ist , wie viel schneller [0-9] ist als ., xund sogar [0123456789]. Bei jedem dieser und {1,9999}, grepverbraucht eine große Menge an RAM; Ich habe es nicht gewagt, es länger als ~ 10 Minuten laufen zu lassen.
Eliah Kagan
3
@ αғsнιη Nein, die { }werden ' 'zitiert ; Die Shell übergibt sie unverändert an grep. Auf jeden {1,9999}Fall wäre eine sehr schnelle und einfache Klammererweiterung . Die Shell würde es einfach erweitern 1 9999.
Eliah Kagan
4
@ αғsнιη Ich weiß nicht genau, was du meinst, aber das hat definitiv nichts mit der Shell zu tun. Während eines lang laufenden Befehls habe ich die erwarteten Argumente verwendet psund topüberprüft, ob sie grepübergeben wurden und dass sie nicht bashviel RAM und CPU verbrauchen. Ich erwarte grepund sedbeide verwenden die in libc implementierten POSIX-Regex-Funktionen für den BRE / ERE-Abgleich. Ich hätte eigentlich nicht speziell über Design sprechen sollen , es sei denn, die Entwickler haben sich für diese Bibliothek entschieden. grepgrep
Eliah Kagan
3
Ich schlage vor, dass Sie die Tests durch ersetzen time grep ... < /dev/null, damit die Leute das eigentliche Problem nicht mit den eingespeisten Daten grepund anderen irrelevanten Dingen in Konflikt bringen .
Muru

Antworten:

10

Beachten Sie, dass nicht das Matching Zeit braucht, sondern der Aufbau des RE. Sie werden feststellen, dass es auch ziemlich viel RAM verbraucht:

$ valgrind grep -Eo '[0-9]{1,9999}' < /dev/null
==6518== HEAP SUMMARY:
==6518==     in use at exit: 1,603,530,656 bytes in 60,013 blocks
==6518==   total heap usage: 123,613 allocs, 63,600 frees, 1,612,381,621 bytes allocated
$ valgrind grep -Eo '[0-9]{1,99}' < /dev/null
==6578==     in use at exit: 242,028 bytes in 613 blocks
==6578==   total heap usage: 1,459 allocs, 846 frees, 362,387 bytes allocated
$ valgrind grep -Eo '[0-9]{1,999}' < /dev/null
==6594== HEAP SUMMARY:
==6594==     in use at exit: 16,429,496 bytes in 6,013 blocks
==6594==   total heap usage: 12,586 allocs, 6,573 frees, 17,378,572 bytes allocated

Die Anzahl der Zuweisungen scheint ungefähr proportional zur Anzahl der Iterationen zu sein, aber der zugewiesene Speicher scheint exponentiell zu wachsen.

Das hängt davon ab, wie GNU-Regexps implementiert werden. Wenn Sie GNU grepmit kompilieren CPPFLAGS=-DDEBUG ./configure && makeund diese Befehle ausführen, sehen Sie den exponentiellen Effekt in Aktion. Tiefer zu gehen würde bedeuten, eine Menge Theorie über DFA durchzugehen und in die Implementierung von Gnulib Regexp einzutauchen.

Hier können Sie stattdessen PCREs verwenden, die nicht das gleiche Problem zu haben scheinen: grep -Po '[0-9]{1,65535}'(das Maximum, obwohl Sie immer Dinge wie [0-9](?:[0-9]{0,10000}){100}1 bis 1.000.001 Wiederholungen ausführen können ) benötigt weder mehr Zeit noch Speicher als grep -Po '[0-9]{1,2}'.

Stéphane Chazelas
quelle
Gibt es eine Möglichkeit, dies zu umgehen?
Sergiy Kolodyazhnyy
3
@SergiyKolodyazhnyy, können Sie verwenden grep -Po '[0-9]{1,9999}, die das Problem nicht zu haben scheint.
Stéphane Chazelas
1
Es ist nicht nur in sed -Eoder grep -Eaber in awkauch hat diese geringe Leistung (über letzten awk - Befehl). Vielleicht awkkann PCRE auch nicht verwendet werden?
αғsнιη