Grep -E, Sed -E - faible performance lorsque '[x] {1,9999}' est utilisé, mais pourquoi?

9

Lorsque grepou sedsont utilisés avec l'option --extended-regexpet que le modèle {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. [1] [2]

  • La performance relative des grep -E, egrepet sed -Eest à peu près égale, de sorte que le test qui ont été faites avec grep -Esont 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

Test 3

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

> vrai 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

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

command-line grep regex pa4080
la source
3
C'est une observation intéressante - je suppose que vous auriez besoin de creuser profondément dans les internes de grep pour trouver exactement comment il construit l'arbre d'analyse (il serait également intéressant de comparer [0-9]+)
steeldriver
3
L'entrée n'a pas d'importance. Comme le suggère @steeldriver, le ralentissement précède la correspondance. Un test simple est time grep -E '[0-9]{1,99}' </dev/nullcontre time grep -E '[0-9]{1,9999}' </dev/null. Même sans entrée , la deuxième commande est lente (le 16.04). Comme prévu, omettre -Eet s'échapper {et }se comporte de la même manière et le remplacer -Epar -Pn'est pas lent (PCRE est un moteur différent). Le plus intéressant est combien plus rapide [0-9] est que ., xet même [0123456789]. Avec l'un de ceux-ci et {1,9999}, grepconsomme une énorme quantité de RAM; Je n'ai pas osé le laisser fonctionner pendant plus de ~ 10min.
Eliah Kagan
3
@ αғsнιη Non, les { }sont ' 'cités ; l'obus les passe inchangés grep. Quoi qu'il en soit, ce {1,9999}serait une expansion d'accolade très rapide et simple . Le shell ne ferait que l'étendre 1 9999.
Eliah Kagan
4
@ αғsнιη Je ne sais pas très bien ce que vous voulez dire, mais cela n'a certainement rien à voir avec le shell. Au cours d'une commande de longue durée, j'ai utilisé pset toppour vérifier que greples arguments attendus étaient passés et que cela ne bashconsommait pas beaucoup de RAM et de CPU. J'attends grepet les seddeux utilisent les fonctions d'expression régulière POSIX implémentées dans libc pour la correspondance BRE / ERE; Je n'aurais pas vraiment dû parler de grepdesign spécifiquement, sauf dans la mesure où les grepdéveloppeurs ont choisi d'utiliser cette bibliothèque.
Eliah Kagan
3
Je vous suggère de remplacer les tests par time grep ... < /dev/null, afin que les gens ne confondent pas le problème réel avec les données alimentées grepet d'autres choses étrangères.
muru

Réponses:

10

Notez que ce n'est pas l'appariement qui prend du temps, mais la construction du RE. 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 grepavec CPPFLAGS=-DDEBUG ./configure && makeet exécutez ces commandes, vous verrez l'effet exponentiel en action. Aller plus loin que cela signifierait passer en revue beaucoup de théorie sur DFA et plonger dans l'implémentation de l'expression rationnelle de 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, bien que vous puissiez 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}'.

Stéphane Chazelas
la source
Y a-t-il un moyen de contourner cela?
Sergiy Kolodyazhnyy
3
@SergiyKolodyazhnyy, vous pouvez utiliser grep -Po '[0-9]{1,9999}ce qui ne semble pas avoir le problème.
Stéphane Chazelas
1
Il est non seulement dans sed -Eou grep -E, mais en awka aussi ce faible rendement (environ la dernière commande awk). peut-être awkne peut-il pas non plus utiliser PCRE?
αғsнιη