Grep -e, Sed -e – Nízký výkon při použití „[x]{1,9999}“, ale proč?

Když grep nebo sed se používají s volbou --extended-regexp a vzor {1,9999} je součástí regulárního výrazu, který se používá, výkon těchto příkazů se sníží. Aby to bylo jasnější, níže je aplikováno několik testů.

• Relativní výkon grep -E , egrep a sed -E je téměř stejný, takže pouze test, který byl proveden s grep -E jsou poskytovány.

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       

Jaký je důvod tohoto významného rozdílu ve výkonu?

Přijatá odpověď:

Všimněte si, že čas nezabere párování, ale budování RE. Zjistíte, že také využívá poměrně hodně paměti RAM:

$ 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

Počet alokací se zdá být zhruba úměrný počtu iterací, ale zdá se, že alokovaná paměť roste exponenciálně.

To závisí na tom, jak jsou implementovány regulární výrazy GNU. Pokud zkompilujete GNU grep pomocí CPPFLAGS=-DDEBUG ./configure && make a spusťte tyto příkazy, uvidíte exponenciální efekt v akci. Jít hlouběji by znamenalo projít spoustu teorie o DFA a ponořit se do implementace regulárních výrazů gnulib.

Zde můžete místo toho použít PCRE, které zřejmě nemají stejný problém:grep -Po '[0-9]{1,65535}' (maximálně, i když vždy můžete dělat věci jako [0-9](?:[0-9]{0,10000}){100} pro 1 až 1 000 001 opakování) nezabere více času ani paměti než grep -Po '[0-9]{1,2}' .