Grep -E, Sed -E - baixo desempenho quando '[x] {1,9999}' é usado, mas por quê?

Question

Quando grep ou sed são usados com a opção --extended-regexp e o padrão {1,9999} é uma parte do regexp usado, o desempenho desses comandos fica baixo. Para ser mais claro, abaixo são aplicados alguns testes. ^{[1] [2 ]}

• O desempenho relativo de grep -E , egrep e sed -E é quase igual, por isso apenas os testes que foram feitos com grep -E são fornecidos.

Teste 1

$ time grep -E '[0-9]{1,99}' < /dev/null

real    0m0.002s

Teste 2

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

> real    0m0.494s

Teste 3

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

> real    21m43.947s

Teste 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 é o motivo dessa diferença significativa no desempenho?

    

Answer 1

Note que não é a correspondência que leva tempo, mas a construção do RE. Você verá que ele usa bastante RAM também:

$ 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

O número de alocações parece aproximadamente proporcional ao número de iterações, mas a memória alocada parece crescer exponencialmente.

Isso se resume a como as expressões regulares do GNU são implementadas. Se você compilar o GNU grep com CPPFLAGS=-DDEBUG ./configure && make e executar esses comandos, verá o efeito exponencial em ação. Ir mais fundo do que isso significaria passar por muitas teorias sobre o DFA e mergulhar na implementação do regexp do gnulib.

Aqui, você pode usar PCREs em vez disso, não parece ter o mesmo problema: grep -Po '[0-9]{1,65535}' (o máximo, embora você sempre possa fazer coisas como [0-9](?:[0-9]{0,10000}){100} para 1 a 1.000.001 repetições) não leva mais tempo nem memória que grep -Po '[0-9]{1,2}' .