Grep -E, Sed -E - bajo rendimiento cuando se usa '[x] {1,9999}', pero ¿por qué?

9

Cuando grepo sedse usan con la opción --extended-regexpy el patrón {1,9999}es una parte de la expresión regular que se usa, el rendimiento de estos comandos se vuelve bajo. Para ser más claro, a continuación se aplican algunas pruebas. [1] [2]

  • El rendimiento relativo de grep -E, egrepy sed -Ees casi igual, por lo que solo se proporcionan las pruebas realizadas grep -E.

Prueba 1

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

real    0m0.002s

Prueba 2

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

> real    0m0.494s

Prueba 3

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

> real 21m43.947s

Prueba 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

¿Cuál es la razón de esta diferencia significativa de rendimiento?

command-line grep regex pa4080
fuente
3
Esa es una observación interesante - mi conjetura es que había necesidad de profundizar en partes internas de grep para encontrar exactamente cómo se está construyendo el árbol de análisis sintáctico (sería interesante comparar [0-9]+también)
steeldriver
3
La entrada no importa. Como sugiere @steeldriver, la desaceleración precede a la coincidencia. Una prueba más simple es time grep -E '[0-9]{1,99}' </dev/nullvs time grep -E '[0-9]{1,9999}' </dev/null. Incluso sin entrada , el segundo comando es lento (en 16.04). Como se esperaba, omitir -Ey escapar {y se }comporta igual y reemplazar -Econ -Pno es lento (PCRE es un motor diferente). Lo más interesante es cuánto más rápido [0-9] es que ., xy hasta [0123456789]. Con cualquiera de esos y {1,9999}, grepconsume una gran cantidad de RAM; No me he atrevido a dejarlo correr por más de ~ 10 minutos.
Eliah Kagan
3
@ αғsнιη No, { }se ' 'citan ; el caparazón los pasa sin cambios grep. De todos modos, {1,9999}sería una expansión de llaves muy rápida y simple . El shell simplemente lo expandiría a 1 9999.
Eliah Kagan
44
@ αғsнιη No sé exactamente a qué te refieres, pero esto definitivamente no tiene nada que ver con el shell. Durante un comando de larga ejecución, utilicé psy toppara verificar grepse pasaron los argumentos esperados y que, no bash, consume mucha RAM y CPU. Espero grepy sedambos usan las funciones de expresiones regulares POSIX implementadas en libc para la coincidencia BRE / ERE; Realmente no debería haber hablado grepespecíficamente del diseño, excepto en la medida en que los grepdesarrolladores eligieron usar esa biblioteca.
Eliah Kagan
3
Sugiero que reemplace las pruebas con time grep ... < /dev/null, para que las personas no combinen el problema real con los datos que se envían grepy otras cosas extrañas.
muru

Respuestas:

10

Tenga en cuenta que no es la correspondencia lo que lleva tiempo, sino la construcción del RE. Encontrarás que también usa bastante 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

El número de asignaciones parece aproximadamente proporcional al número de iteraciones, pero la memoria asignada parece crecer exponencialmente.

Eso se debe a cómo se implementan las expresiones regulares GNU. Si compila GNU grepcon CPPFLAGS=-DDEBUG ./configure && makey ejecuta esos comandos, verá el efecto exponencial en acción. Ir más profundo que eso significaría pasar por muchas teorías sobre DFA y sumergirse en la implementación de expresiones regulares de gnulib.

Aquí, puede usar PCRE en su lugar que no parece tener el mismo problema: grep -Po '[0-9]{1,65535}'(el máximo, aunque siempre puede hacer cosas como [0-9](?:[0-9]{0,10000}){100}1 a 1,000,001 repeticiones) no toma más tiempo ni memoria que grep -Po '[0-9]{1,2}'.

Stéphane Chazelas
fuente
¿Hay alguna forma de evitar esto?
Sergiy Kolodyazhnyy
3
@SergiyKolodyazhnyy, puede usar grep -Po '[0-9]{1,9999}lo que no parece tener el problema.
Stéphane Chazelas
1
No se trata sólo de sed -Eo grep -E, pero en la awkque también tiene este bajo rendimiento (alrededor del último comando awk). tal vez awktampoco puede usar PCRE?
αғsнιη