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

9

Quando grepou sedsão usados ​​com a opção --extended-regexpe o padrão {1,9999}faz parte do regexp usado, o desempenho desses comandos se torna baixo. Para ser mais claro, abaixo são aplicados alguns testes. [1] [2]

  • O desempenho relativo grep -E, egrepe sed -Eé quase igual, portanto, apenas o teste que foram feitas com grep -Esã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 de desempenho?

command-line grep regex pa4080
fonte
3
Essa é uma observação interessante - meu palpite é que você precisa para cavar fundo para internos do grep para encontrar exatamente como ele está construindo a árvore de análise (que seria interessante comparar [0-9]+também)
steeldriver
3
A entrada não importa. Como o @steeldriver sugere, a desaceleração precede a correspondência. Um teste simples é time grep -E '[0-9]{1,99}' </dev/nullvs. time grep -E '[0-9]{1,9999}' </dev/null. Mesmo sem entrada , o segundo comando é lento (em 16.04). Como esperado, omitir -Ee escapar {e }se comporta da mesma maneira e a substituição -Epor -Pnão é lenta (PCRE é um mecanismo diferente). O mais interessante é o quanto mais rápido [0-9] é que ., xe mesmo [0123456789]. Com qualquer um desses {1,9999}, grepconsome uma quantidade enorme de RAM; Não ousei deixá-lo funcionar por mais de ~ 10min.
Eliah Kagan 29/09
3
@ αғsнιη Não, { }estão entre ' 'aspas ; a concha os passa inalterados grep. Enfim, {1,9999}seria uma expansão de chave muito rápida e simples . O shell iria apenas expandi-lo para 1 9999.
Eliah Kagan 29/09
4
@ αғsнιη Não sei bem o que você quer dizer, mas isso definitivamente não tem nada a ver com o shell. Durante um comando de execução demorada, usei pse toppara verificar se grepforam transmitidos os argumentos esperados e se ele não bashconsome muita RAM e CPU. Eu espero grepe sedambos usam as funções de regex POSIX implementadas em libc para correspondência BRE / ERE; Eu realmente não deveria ter falado sobre grepdesign especificamente, exceto na medida em que os grepdesenvolvedores optaram por usar essa biblioteca.
Eliah Kagan 29/09
3
Sugiro que você substitua os testes por time grep ... < /dev/null, para que as pessoas não confundam o problema real com os dados alimentados grepe outras coisas estranhas.
muru 29/09/17

Respostas:

10

Observe que não é a correspondência que leva tempo, mas a construção do ER. 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 deve à maneira como os regexps GNU são implementados. Se você compilar GNU grepcom CPPFLAGS=-DDEBUG ./configure && make, e executar os comandos, você verá o efeito exponencial em ação. Aprofundar isso significaria passar por muita teoria sobre o DFA e mergulhar na implementação do gnulib regexp.

Aqui, você pode usar PCREs que parecem não 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}1 a 1.000.001 repetições) não leva mais tempo nem memória do que grep -Po '[0-9]{1,2}'.

Stéphane Chazelas
fonte
Existe alguma maneira de contornar isso ?
Sergiy Kolodyazhnyy 29/09
3
@SergiyKolodyazhnyy, você pode usar o grep -Po '[0-9]{1,9999}que parece não ter o problema.
Stéphane Chazelas
1
Não é só em sed -Eou grep -E, mas em awktambém tem esse baixo desempenho (cerca último comando awk). talvez awktambém não possa usar o PCRE?
αғsнιη