¿Por qué iterar sobre un archivo dos veces más rápido que leerlo en la memoria y calcular dos veces?

26

Estoy comparando lo siguiente

tail -n 1000000 stdout.log | grep -c '"success": true'
tail -n 1000000 stdout.log | grep -c '"success": false'

con lo siguiente

log=$(tail -n 1000000 stdout.log)
echo "$log" | grep -c '"success": true'
echo "$log" | grep -c '"success": false'

y sorprendentemente, el segundo tarda casi 3 veces más que el primero. Debería ser más rápido, ¿no?

phunehehe
fuente
¿Podría ser porque la segunda solución, el contenido del archivo se lee 3 veces, y solo dos veces en el primer ejemplo?
Laurent C.
44
Al menos en el segundo ejemplo, sus $( command substitution )es decir , no se transmiten. Todo lo demás sucede a través de tuberías al mismo tiempo, pero en el segundo ejemplo, debe esperar a log=que se complete. Pruébelo con << AQUÍ \ n $ {log = $ (comando)} \ nAQUÍ: vea lo que obtiene.
mikeserv
En el caso de archivos extremadamente grandes, máquinas con memoria limitada o más elementos greppara, es posible que vea un poco de aceleración teepara que el archivo definitivamente solo se lea una vez. cat stdout.log | tee >/dev/null >(grep -c 'true'>true.cnt) >(grep -c 'false'>false.cnt); cat true.cnt; cat false.cnt
Matt
@LaurentC., No, solo se lee una vez en el segundo ejemplo. Solo hay una llamada a la cola.
psusi
Ahora compare esto con tail -n 10000 | fgrep -c '"success": true'falso.
kojiro

Respuestas:

11

Por un lado, el primer método llama taildos veces, por lo que tiene que hacer más trabajo que el segundo método que solo hace esto una vez. Por otro lado, el segundo método tiene que copiar los datos en el shell y luego retroceder, por lo que tiene que hacer más trabajo que la primera versión donde tailse canaliza directamente grep. El primer método tiene una ventaja adicional en una máquina multiprocesador: greppuede funcionar en paralelo con tail, mientras que el segundo método es estrictamente serializado, primero taily luego grep.

Por lo tanto, no hay una razón obvia por la cual una sea más rápida que la otra.

Si quieres ver qué está pasando, mira qué llamadas al sistema hace el shell. Prueba con diferentes conchas también.

strace -t -f -o 1.strace sh -c '
  tail -n 1000000 stdout.log | grep "\"success\": true" | wc -l;
  tail -n 1000000 stdout.log | grep "\"success\": false" | wc -l'

strace -t -f -o 2-bash.strace bash -c '
  log=$(tail -n 1000000 stdout.log);
  echo "$log" | grep "\"success\": true" | wc -l;
  echo "$log" | grep "\"success\": true" | wc -l'

strace -t -f -o 2-zsh.strace zsh -c '
  log=$(tail -n 1000000 stdout.log);
  echo "$log" | grep "\"success\": true" | wc -l;
  echo "$log" | grep "\"success\": true" | wc -l'

Con el método 1, las etapas principales son:

  1. tail lee y busca encontrar su punto de partida.
  2. tailescribe fragmentos de 4096 bytes que se grepleen tan rápido como se producen.
  3. Repita el paso anterior para la segunda cadena de búsqueda.

Con el método 2, las etapas principales son:

  1. tail lee y busca encontrar su punto de partida.
  2. tail escribe fragmentos de 4096 bytes que bash lee 128 bytes a la vez y zsh lee 4096 bytes a la vez.
  3. Bash o zsh escribe fragmentos de 4096 bytes que se grepleen tan rápido como se producen.
  4. Repita el paso anterior para la segunda cadena de búsqueda.

Los fragmentos de 128 bytes de Bash al leer el resultado de la sustitución del comando lo ralentiza significativamente; zsh sale casi tan rápido como el método 1 para mí. Su kilometraje puede variar según el tipo y número de CPU, la configuración del planificador, las versiones de las herramientas involucradas y el tamaño de los datos.

Gilles 'SO- deja de ser malvado'
fuente
¿Depende el tamaño de página de la figura de 4k? Quiero decir, ¿cola y zsh son solo llamadas de sistema? (Posiblemente sea una terminología incorrecta, aunque espero que no ...) ¿Qué hace bash de manera diferente?
mikeserv
Este es el lugar en Gilles! Con zsh, el segundo método es un poco más rápido en mi máquina.
phunehehe
Gran trabajo Gilles, tks.
X Tian
@mikeserv No he mirado la fuente para ver cómo estos programas eligen el tamaño. Las razones más probables para ver 4096 serían una constante incorporada o el st_blksizevalor de una tubería, que es 4096 en esta máquina (y no sé si es porque es el tamaño de página de MMU). Los 128 de Bash tendrían que ser una constante incorporada.
Gilles 'SO- deja de ser malvado'
@Gilles, gracias por la atenta respuesta. He tenido curiosidad por los tamaños de página últimamente.
mikeserv
26

Hice la siguiente prueba y en mi sistema la diferencia resultante es aproximadamente 100 veces más larga para el segundo script.

Mi archivo es una salida extraña llamada bigfile

$ wc -l bigfile.log 
1617000 bigfile.log

Guiones

xtian@clafujiu:~/tmp$ cat p1.sh
tail -n 1000000 bigfile.log | grep '"success": true' | wc -l
tail -n 1000000 bigfile.log | grep '"success": false' | wc -l

xtian@clafujiu:~/tmp$ cat p2.sh
log=$(tail -n 1000000 bigfile.log)
echo "$log" | grep '"success": true' | wc -l
echo "$log" | grep '"success": true' | wc -l

En realidad no tengo coincidencias para el grep, por lo que no se escribe nada en la última tubería hasta wc -l

Aquí están los horarios:

xtian@clafujiu:~/tmp$ time bash p1.sh
0
0

real    0m0.381s
user    0m0.248s
sys 0m0.280s
xtian@clafujiu:~/tmp$ time bash p2.sh
0
0

real    0m46.060s
user    0m43.903s
sys 0m2.176s

Así que ejecuté los dos scripts nuevamente a través del comando strace

strace -cfo p1.strace bash p1.sh
strace -cfo p2.strace bash p2.sh

Aquí están los resultados de las huellas:

$ cat p1.strace 
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 97.24    0.508109       63514         8         2 waitpid
  1.61    0.008388           0     84569           read
  1.08    0.005659           0     42448           write
  0.06    0.000328           0     21233           _llseek
  0.00    0.000024           0       204       146 stat64
  0.00    0.000017           0       137           fstat64
  0.00    0.000000           0       283       149 open
  0.00    0.000000           0       180         8 close
...
  0.00    0.000000           0       162           mmap2
  0.00    0.000000           0        29           getuid32
  0.00    0.000000           0        29           getgid32
  0.00    0.000000           0        29           geteuid32
  0.00    0.000000           0        29           getegid32
  0.00    0.000000           0         3         1 fcntl64
  0.00    0.000000           0         7           set_thread_area
------ ----------- ----------- --------- --------- ----------------
100.00    0.522525                149618       332 total

Y p2.strace

$ cat p2.strace 
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 75.27    1.336886      133689        10         3 waitpid
 13.36    0.237266          11     21231           write
  4.65    0.082527        1115        74           brk
  2.48    0.044000        7333         6           execve
  2.31    0.040998        5857         7           clone
  1.91    0.033965           0    705681           read
  0.02    0.000376           0     10619           _llseek
  0.00    0.000000           0       248       132 open
...
  0.00    0.000000           0       141           mmap2
  0.00    0.000000           0       176       126 stat64
  0.00    0.000000           0       118           fstat64
  0.00    0.000000           0        25           getuid32
  0.00    0.000000           0        25           getgid32
  0.00    0.000000           0        25           geteuid32
  0.00    0.000000           0        25           getegid32
  0.00    0.000000           0         3         1 fcntl64
  0.00    0.000000           0         6           set_thread_area
------ ----------- ----------- --------- --------- ----------------
100.00    1.776018                738827       293 total

Análisis

No es sorprendente que, en ambos casos, la mayor parte del tiempo se pase esperando a que se complete un proceso, pero p2 espera 2,63 veces más que p1, y como otros han mencionado, está comenzando tarde en p2.sh.

Así que ahora olvídate de waitpid, ignora la %columna y mira la columna de segundos en ambas trazas.

El tiempo más largo que p1 pasa la mayor parte de su tiempo en lectura probablemente sea comprensible, porque hay un archivo grande para leer, pero p2 pasa 28.82 veces más tiempo en lectura que p1. - bashno espera leer un archivo tan grande en una variable y probablemente esté leyendo el búfer a la vez, dividiéndolo en líneas y luego obteniendo otro.

El recuento de lectura p2 es 705k vs 84k para p1, cada lectura requiere un cambio de contexto en el espacio del kernel y de nuevo. Casi 10 veces el número de lecturas y cambios de contexto.

El tiempo en escritura p2 pasa 41.93 veces más en escritura que p1

el recuento de escritura p1 realiza más escrituras que p2, 42k frente a 21k, sin embargo, son mucho más rápidos.

Probablemente debido a las echolíneas en los grepbuffers de escritura de cola.

Además , p2 pasa más tiempo en escritura que en lectura, ¡p1 es al revés!

Otro factor Observe la cantidad de brkllamadas al sistema: ¡p2 gasta 2.42 veces más tiempo de interrupción de lo que lee! En p1 (ni siquiera se registra). brkes cuando el programa necesita expandir su espacio de direcciones porque inicialmente no se asignó suficiente, esto probablemente se deba a que bash tiene que leer ese archivo en la variable, y no esperar que sea tan grande, y como mencionó @scai, si el el archivo se hace demasiado grande, incluso eso no funcionaría.

tailes probablemente un lector de archivos bastante eficiente, porque para esto fue diseñado, probablemente mapee el archivo y escanee en busca de saltos de línea, permitiendo así que el núcleo optimice la E / S. bash no es tan bueno tanto en el tiempo dedicado a leer como a escribir.

p2 gasta 44ms y 41ms cloney execvno es una cantidad medible para p1. Probablemente bash leyendo y creando la variable desde la cola.

Finalmente, Totals p1 ejecuta ~ 150k llamadas al sistema frente a p2 740k (4.93 veces mayor).

Eliminando waitpid, p1 gasta 0.014416 segundos ejecutando llamadas al sistema, p2 0.439132 segundos (30 veces más).

Por lo tanto, parece que p2 pasa la mayor parte del tiempo en el espacio del usuario sin hacer nada excepto esperar a que se completen las llamadas del sistema y que el kernel reorganice la memoria, p1 realiza más escrituras, pero es más eficiente y causa una carga de sistema significativamente menor, y por lo tanto es más rápido.

Conclusión

Nunca trataría de preocuparme por la codificación a través de la memoria al escribir un script bash, eso no significa que no intentes ser eficiente.

tailestá diseñado para hacer lo que hace, probablemente sea memory mapsel archivo para que sea eficiente de leer y permita que el núcleo optimice la E / S.

Una mejor manera de optimizar su problema podría ser primero greppara '' éxito '': líneas y luego contar las verdades y falsos, greptiene una opción de conteo que nuevamente evita wc -l, o incluso mejor, canalizar la cola awky contar las verdades y falsos al mismo tiempo. p2 no solo lleva mucho tiempo, sino que agrega carga al sistema mientras la memoria se baraja con brks.

X Tian
fuente
2
TL; DR: malloc (); si pudiera decirle a $ log qué tan grande debía ser y escribirlo rápidamente en una operación sin reasignaciones, probablemente sería igual de rápido.
Chris K
5

En realidad, la primera solución también lee el archivo en la memoria. Esto se llama almacenamiento en caché y el sistema operativo lo hace automáticamente.

Y como ya explica correctamente mikeserv, la primera solución se ejecuta grep mientras se lee el archivo, mientras que la segunda solución lo ejecuta después de que el archivo haya sido leído tail.

Entonces, la primera solución es más rápida debido a varias optimizaciones. Pero esto no siempre tiene que ser cierto. Para archivos realmente grandes que el sistema operativo decide no almacenar en caché, la segunda solución podría ser más rápida. Pero tenga en cuenta que para archivos aún más grandes que no caben en su memoria, la segunda solución no funcionará en absoluto.

scai
fuente
3

Creo que la principal diferencia es muy simple, que echoes lenta. Considera esto:

$ time (tail -n 1000000 foo | grep 'true' | wc -l; 
        tail -n 1000000 foo | grep 'false' | wc -l;)
666666
333333

real    0m0.999s
user    0m1.056s
sys     0m0.136s

$ time (log=$(tail -n 1000000 foo); echo "$log" | grep 'true' | wc -l; 
                                    echo "$log" | grep 'false' | wc -l)
666666
333333

real    0m4.132s
user    0m3.876s
sys     0m0.468s

$ time (tail -n 1000000 foo > bb;  grep 'true' bb | wc -l; 
                                   grep 'false' bb | wc -l)
666666
333333

real    0m0.568s
user    0m0.512s
sys     0m0.092s

Como puede ver arriba, el paso que lleva mucho tiempo es imprimir los datos. Si simplemente redirige a un nuevo archivo y lo revisa, es mucho más rápido cuando solo lee el archivo una vez.


Y según lo solicitado, con una cadena aquí:

 $ time (log=$(tail -n 1000000 foo); grep 'true' <<< $log | wc -l; 
                                     grep 'false' <<< $log | wc -l  )
1
1

real    0m7.574s
user    0m7.092s
sys     0m0.516s

Este es aún más lento, presumiblemente porque la cadena here está concatenando todos los datos en una línea larga y eso ralentizará grep:

$ tail -n 1000000 foo | (time grep -c 'true')
666666

real    0m0.500s
user    0m0.472s
sys     0m0.000s

$ tail -n 1000000 foo | perl -pe 's/\n/ /' | (time grep -c 'true')
1

real    0m1.053s
user    0m0.048s
sys     0m0.068s

Si la variable se cita para que no ocurra división, las cosas son un poco más rápidas:

 $ time (log=$(tail -n 1000000 foo); grep 'true' <<< "$log" | wc -l; 
                                     grep 'false' <<< "$log" | wc -l  )
666666
333333

real    0m6.545s
user    0m6.060s
sys     0m0.548s

Pero sigue siendo lento porque el paso de limitación de velocidad es imprimir los datos.

terdon
fuente
¿Por qué no lo intentas? <<<Sería interesante ver si eso marca la diferencia.
Graeme
3

También probé esto ... Primero, construí el archivo:

printf '"success": "true"
        "success": "true"
        "success": "false"
        %.0b' `seq 1 500000` >|/tmp/log

Si ejecuta lo anterior usted mismo, debería obtener 1,5 millones de líneas /tmp/logcon una proporción de 2: 1 de "success": "true"líneas a "success": "false"líneas.

Lo siguiente que hice fue ejecutar algunas pruebas. Ejecuté todas las pruebas a través de un proxy, shpor timelo que solo tendría que ver un solo proceso y, por lo tanto, podría mostrar un solo resultado para todo el trabajo.

Este parece ser el más rápido, aunque agrega un segundo descriptor de archivos y tee,creo que puedo explicar por qué:

    time sh <<-\CMD
        . <<HD /dev/stdin | grep '"success": "true"' | wc -l
            tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
                grep '"success": "false"' |\
                    wc -l 1>&2 & } 3>&1 &
        HD
    CMD
666666
333334
sh <<<''  0.11s user 0.08s system 84% cpu 0.224 total

Aquí está tu primero:

    time sh <<\CMD
        tail -n 1000000 /tmp/log | grep '"success": "true"' | wc -l
        tail -n 1000000 /tmp/log | grep '"success": "false"' | wc -l
    CMD

666666
333334
sh <<<''  0.31s user 0.17s system 148% cpu 0.323 total

Y tu segundo:

    time sh <<\CMD
        log=$(tail -n 1000000 /tmp/log)
        echo "$log" | grep '"success": "true"' | wc -l
        echo "$log" | grep '"success": "false"' | wc -l
    CMD
666666
333334
sh <<<''  2.12s user 0.46s system 108% cpu 2.381 total

Puede ver que en mis pruebas hubo una diferencia de velocidad de más de 3 * al leerla en una variable como lo hizo.

Creo que parte de eso es que una variable de shell debe ser dividida y manejada por el shell cuando se lee, no es un archivo.

A, here-documentpor otro lado, para todos los efectos, es a file- a defile descriptor, todos modos. Y como todos sabemos, Unix funciona con archivos.

Lo que es más interesante para mí here-docses que puedes manipularlos file-descriptors, como una escalera |pipe, y ejecutarlos. Esto es muy útil ya que te permite un poco más de libertad para apuntar hacia |pipedonde quieras.

Tenía que teeel taildebido a que los primeros grepcome las here-doc |pipey de allí no queda nada para el segundo para leer. Pero ya que |pipedlo metí /dev/fd/3y lo recogí nuevamente para pasarlo >&1 stdout,, no importó demasiado. Si usa grep -ccomo muchos otros, recomiende:

    time sh <<-\CMD
        . <<HD /dev/stdin | grep -c '"success": "true"'
            tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
                grep -c '"success": "false"' 1>&2 & } 3>&1 &
        HD
    CMD
666666
333334
sh <<<''  0.07s user 0.04s system 62% cpu 0.175 total

Es incluso más rápido

Pero cuando lo ejecuto sin . sourcingel heredocno puedo ejecutar con éxito el primer proceso para ejecutarlos completamente al mismo tiempo. Aquí está sin fondo completo:

    time sh <<\CMD
        tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
            grep -c '"success": "true"' 1>&2 & } 3>&1 |\
                grep -c '"success": "false"'
    CMD
666666
333334
sh <<<''  0.10s user 0.08s system 109% cpu 0.165 total

Pero cuando agrego el &:

    time sh <<\CMD
        tail -n 1000000 /tmp/log | { tee /dev/fd/3 |\
            grep -c '"success": "true"' 1>&2 & } 3>&1 & |\
                grep -c '"success": "false"'
    CMD
sh: line 2: syntax error near unexpected token `|'

Aún así, la diferencia parece ser solo unas pocas centésimas de segundo, al menos para mí, así que tómalo como quieras.

De todos modos, la razón por la que se ejecuta más rápido teees porque ambos se grepsejecutan al mismo tiempo con solo una invocación de tail. teeduplicados del archivo para nosotros y lo divide en el segundo grepproceso todo en flujo: todo se ejecuta a la vez de principio a fin, por lo que todos terminan al mismo tiempo también.

Volviendo a tu primer ejemplo:

    tail | grep | wc #wait til finished
    tail | grep | wc #now we're done

Y tu segundo:

    var=$( tail ) ; #wait til finished
    echo | grep | wc #wait til finished
    echo | grep | wc #now we're done

Pero cuando dividimos nuestra entrada y ejecutamos nuestros procesos simultáneamente:

          3>&1  | grep #now we're done
              /        
    tail | tee  #both process together
              \  
          >&1   | grep #now we're done
revs mikeserv
fuente
1
+1 pero su última prueba murió con un error de sintaxis, no creo que los tiempos sean correctos allí :)
terdon
@terdon Podrían estar equivocados: estaba señalando que murió. Mostré la diferencia entre el & y el no & - cuando lo agrega, el shell se molesta. Pero hice muchas copias / pegados, así que podría haber estropeado uno o dos, pero creo que están bien ...
mikeserv
sh: línea 2: error de sintaxis cerca del token inesperado `| '
terdon
@terdon Sí, eso: "No puedo ejecutar con éxito el primer proceso para ejecutarlos de forma simultánea. ¿Ves?" El primero no está en segundo plano, pero cuando agrego & en un intento de hacerlo "token inesperado". Cuando yo . fuente el heredoc puedo usar el &.
mikeserv