Grep -e, Sed -e – Prestazioni basse quando viene utilizzato "[x]{1,9999}", ma perché?

Quando grep o sed vengono utilizzati con l'opzione --extended-regexp e il modello {1,9999} è una parte dell'espressione regolare utilizzata, le prestazioni di questi comandi diventano basse. Per essere più chiari, di seguito vengono applicati alcuni test.

• Il rendimento relativo di grep -E , egrep e sed -E è quasi uguale, quindi solo il test eseguito con grep -E sono forniti.

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       

Qual ​​è il motivo di questa significativa differenza di rendimento?

Risposta accettata:

Nota che non è l'abbinamento che richiede tempo, ma la costruzione della RE. Scoprirai che utilizza anche parecchia 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

Il numero di alloc sembra più o meno proporzionale al numero di iterazioni, ma la memoria allocata sembra crescere in modo esponenziale.

Dipende da come vengono implementate le espressioni regolari GNU. Se compili GNU grep con CPPFLAGS=-DDEBUG ./configure && make ed esegui quei comandi, vedrai l'effetto esponenziale in azione. Andare più in profondità significherebbe esaminare molte teorie su DFA e immergersi nell'implementazione dell'espressione regolare di gnulib.

Qui puoi invece utilizzare PCRE che non sembrano avere lo stesso problema:grep -Po '[0-9]{1,65535}' (il massimo, anche se puoi sempre fare cose come [0-9](?:[0-9]{0,10000}){100} da 1 a 1.000.001 di ripetizioni) non richiede più tempo né memoria di grep -Po '[0-9]{1,2}' .