¿Cómo es ksh93 tan rápido?

9

Por lo tanto, en general, tiendo a buscar el sedprocesamiento de texto, especialmente para archivos grandes, y generalmente evito hacer ese tipo de cosas en el shell.

Sin embargo, creo que eso puede cambiar. Estaba hurgando man kshy noté esto:

<#pattern     Seeks forward to the beginning of the
              next line containing pattern.

<##pattern    The same as <# except that  the  por
              tion  of  the file that is skipped is
              copied to standard output.

Escéptico de la utilidad del mundo real, decidí probarlo. Yo hice:

seq -s'foo bar
' 1000000 >file

... para un millón de líneas de datos que se parecen a:

1foo bar
...
999999foo bar
1000000

... y lo enfrenté sedcomo:

p='^[^0-8]99999.*bar'
for c in "sed '/$p/q'" "ksh -c ':<##@(~(E)$p)'"    
do </tmp/file eval "time ( $c )"
done | wc -l

Por lo tanto, ambos comandos deben llegar hasta 999999foo bar y su implementación de coincidencia de patrones debe evaluar al menos el comienzo y el final de cada línea para hacerlo. También tienen que verificar el primer carácter contra un patrón negado. Esto es algo simple, pero ... Los resultados no fueron lo que esperaba:

( sed '/^[^0-8]99999.*bar/q' ) \
    0.40s user 0.01s system 99% cpu 0.419 total
( ksh -c ':<##@(~(E)^[^0-8]99999.*bar)' ) \
    0.02s user 0.01s system 91% cpu 0.033 total
1999997

kshusa ERE aquí y sedun BRE. Hice lo mismo con kshun patrón de shell antes, pero los resultados no fueron diferentes.

De todos modos, esa es una discrepancia bastante significativa: kshsupera sed10 veces más. He leído antes que David Korn escribió su propia io lib y la implementa, ksh¿posiblemente esto esté relacionado? - Pero no sé casi nada al respecto. ¿Cómo es que el shell hace esto tan bien?

Aún más sorprendente para mí es que kshrealmente deja su desplazamiento justo donde lo preguntas. Para obtener (casi) lo mismo de (GNU) sed tiene que usar -u, muy lento .

Aquí hay una prueba grepv.ksh

1000000         #grep + head
( grep -qm1 '^[^0-8]99999.*bar'; head -n1; ) \
    0.02s user 0.00s system 90% cpu 0.026 total
999999foo bar   #ksh + head
( ksh -c ':<#@(~(E)^[^0-8]99999.*bar)'; head -n1; )  \
    0.02s user 0.00s system 73% cpu 0.023 total

kshlate grepaquí, pero no siempre, están bastante empatados. Aún así, eso es bastante excelente y ksh proporciona información anticipada: headla entrada comienza antes de su coincidencia.

Parece demasiado bueno para ser verdad, supongo. ¿Qué hacen estos comandos de manera diferente bajo el capó?

Ah, y al parecer, ni siquiera hay una subshell aquí:

ksh -c 'printf %.5s "${<file;}"'
mikeserv
fuente
¿Es patternuna expresión regular o un patrón de shell más simple?
muru
@muru: puede ser cualquiera de los dos, pero no soy muy bueno para cambiarlos. En el ejemplo, es un patrón de shell, el valor predeterminado.
mikeserv
@muru: agregué uno con una expresión regular.
mikeserv

Respuestas:

8

Ksh no solo usa sfio sino que también usa su propio asignador de memoria personalizado.

Sin embargo, supongo que sfio hace la diferencia en este caso. Acabo de intentar ejecutar su ejemplo bajo strace y puedo ver que ksh llama lectura / escritura ~ 200 veces (bloques de 65 KB) mientras sed lo hace ~ 3400 veces (bloques de 4 KB). Con sed -u mi computadora portátil casi derretida, las lecturas se realizan por byte y las escrituras por línea. Ksh simple usa lseek. Grep usa lectura ~ 400 veces (bloques de 32 KB).

Miroslav Franc
fuente
Sí, sin búfer no es para los débiles de corazón. Me pregunto si kshel motor regex es eficiente como su io? De todos modos, muchas gracias por la respuesta. Mis disculpas por tu laptop. Sin embargo, ¿qué pasa con el asignador de memoria personalizado? ¿Tienes más sobre eso?
mikeserv
1
Tristemente no. Por supuesto, puede descargar el código fuente del sitio web de at & t, pero eso es todo. La biblioteca se llama AST y contiene asignador, motor de expresiones regulares y muchas otras cosas. Por lo tanto, es completamente posible que la combinación de todas esas cosas haga que ksh sea mucho más rápido.
Miroslav Franc
Gracias, esto también parece prometedor: algunos de los componentes disponibles en la colección de software AST son: comandos POSIX La mayoría de los comandos POSIX estándar están disponibles en la colección AST. Muchos están codificados como funciones de biblioteca que se pueden agregar a ksh como comando incorporado que mejora drásticamente el rendimiento. - Ahora tengo que descubrir cómo construirlo,
mikeserv
1
@mikeserv ksh se puede construir para usar el asignador vmalloc de Phong Vo . Artículos de revistas disponibles en ese enlace.
Mark Plotnick