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

Cuando grep o sed se usan con la opción --extended-regexp y 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 claros, a continuación se aplican algunas pruebas.

• El rendimiento relativo de grep -E , egrep y sed -E es casi igual, solo la prueba que se hizo con grep -E se proporcionan.

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 del rendimiento?

Respuesta aceptada:

Tenga en cuenta que no es el emparejamiento lo que lleva tiempo, sino la construcción del RE. Descubrirá 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 depende de cómo se implementen las expresiones regulares de GNU. Si compila GNU grep con CPPFLAGS=-DDEBUG ./configure && make y ejecute esos comandos, verá el efecto exponencial en acción. Profundizar más que eso significaría analizar mucha teoría sobre DFA y sumergirse en la implementación de expresiones regulares de gnulib.

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