Grep -e, Sed -e - Faibles performances lorsque '[x]{1,9999}' est utilisé, mais pourquoi ?

Quand grep ou sed sont utilisés avec l'option --extended-regexp et le motif {1,9999} fait partie de l'expression rationnelle utilisée, les performances de ces commandes deviennent faibles. Pour être plus clair, ci-dessous sont appliqués quelques tests.

• Les performances relatives de grep -E , egrep et sed -E est presque égal, donc seul le test qui a été fait avec grep -E sont fournis.

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

Essai 3

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

> real    21m43.947s

Essai 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       

Quelle est la raison de cette différence significative de performances ?

Réponse acceptée :

Notez que ce n'est pas l'appariement qui prend du temps, mais la construction de l'ER. Vous constaterez qu'il utilise également beaucoup de 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

Le nombre d'allocations semble à peu près proportionnel au nombre d'itérations, mais la mémoire allouée semble croître de façon exponentielle.

Cela dépend de la façon dont les expressions rationnelles GNU sont implémentées. Si vous compilez GNU grep avec CPPFLAGS=-DDEBUG ./configure && make , et exécutez ces commandes, vous verrez l'effet exponentiel en action. Aller plus loin signifierait parcourir beaucoup de théorie sur DFA et se plonger dans l'implémentation de l'expression régulière gnulib.

Ici, vous pouvez utiliser des PCRE à la place qui ne semblent pas avoir le même problème :grep -Po '[0-9]{1,65535}' (le maximum, même si vous pouvez toujours faire des choses comme [0-9](?:[0-9]{0,10000}){100} pour 1 à 1 000 001 répétitions) ne prend pas plus de temps ni de mémoire que grep -Po '[0-9]{1,2}' .