Grep -e, Sed -e – Geringe Leistung bei Verwendung von „[x]{1,9999}“, aber warum?

Wenn grep oder sed werden mit der Option --extended-regexp verwendet und das Muster {1,9999} Teil des verwendeten regulären Ausdrucks ist, wird die Leistung dieser Befehle gering. Um es klarer zu machen, werden unten einige Tests angewendet.

• Die relative Leistung von grep -E , egrep und sed -E ist fast gleich, also nur der Test, der mit grep -E gemacht wurde bereitgestellt werden.

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

> real    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?

Akzeptierte Antwort:

Beachten Sie, dass nicht das Matching Zeit braucht, sondern das Erstellen 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 grep kompilieren mit CPPFLAGS=-DDEBUG ./configure && make , und führen Sie diese Befehle aus, Sie werden den exponentiellen Effekt in Aktion sehen. Tiefer zu gehen würde bedeuten, viel Theorie über DFA durchzugehen und in die gnulib-Regexp-Implementierung einzutauchen.

Hier können Sie stattdessen PCREs verwenden, die anscheinend nicht das gleiche Problem haben:grep -Po '[0-9]{1,65535}' (das Maximum, obwohl Sie immer Dinge wie [0-9](?:[0-9]{0,10000}){100} tun können für 1 bis 1.000.001 Wiederholungen) benötigt nicht mehr Zeit und Speicherplatz als grep -Po '[0-9]{1,2}' .