Necesita algo que sea más rápido que "wc -l"

12

Para un archivo realmente grande como 1GB wc -lresulta ser lento. ¿Tenemos una forma más rápida de calcular el número de líneas nuevas para un archivo en particular?

prosti
fuente
25
¿Comprar discos más rápidos? Dado que cada byte de la entrada debe inspeccionarse por su entrada 0x0A, la E / S es sin duda el cuello de botella.
thrig
2
Si sospecha que wctiene demasiada sobrecarga, puede intentar implementar la suya foreach byte in file: if byte == '\n': linecount++. Si se implementa en C o ensamblador, no creo que sea más rápido, excepto tal vez en el espacio del kernel en un RTOS con la máxima prioridad (o incluso usar una interrupción para eso; simplemente no puede hacer nada más con el sistema). .. de acuerdo, estoy divagando ;-))
Murphy
3
Y solo para tener una idea de la escala, hice un rápido time wc -l some_movie.avien un archivo sin caché, lo que resultó en 5172672 some_movie.avi -- real 0m57.768s -- user 0m0.255s -- sys 0m0.863s. Lo que básicamente demuestra que @thrig es correcto, la E / S destruye su rendimiento en este caso.
Murphy
10
La mejor manera de mostrar que se trata de un disco IO bottlneck, hacer time wc -l some_large_file_smaller_than_cachedos veces seguidas y ver qué tan rápida es la segunda operación, time wc -l some_large_file_larger_than_cachey ver cómo el tiempo no cambia entre las ejecuciones. Para un archivo de ~ 280MB aquí, el tiempo va de 1.7 segundos a 0.2 segundos, pero para un archivo de 2GB son 14 segundos las dos veces.
EightBitTony
1
¿Qué tan lento es demasiado lento para ti? ¿Qué /usr/bin/time wc -l <file>dice? ¿Cuál es tu hardware? ¿Es más rápido si ejecuta el comando repetidamente? Realmente necesitamos más información;)
marcelm

Respuestas:

21

Puedes intentar escribir en C:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(){
  char buf[BUFSIZ];
  int nread;
  size_t nfound=0;
  while((nread=read(0, buf, BUFSIZ))>0){
    char const* p;
    for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
  }
  if(nread<0) { perror("Error"); return 1; }
  printf("%lu\n", nfound);
  return 0;
}

Guardar en, por ejemplo, wcl.ccompilar, por ejemplo, con gcc wcl.c -O2 -o wcly ejecutar con

<yourFile ./wcl

Esto encuentra nuevas líneas esparcidas en un archivo de 1 GB en mi sistema en aproximadamente 370 ms ( ejecuciones repetidas). (Aumentar el tamaño del búfer aumenta ligeramente el tiempo, lo cual es de esperar; BUFSIZ debería estar cerca de lo óptimo). Esto es muy comparable a los ~ 380 ms que estoy obteniendo wc -l.

Mmaping me da un mejor tiempo de aproximadamente 280 ms , pero por supuesto tiene la limitación de estar limitado a archivos reales (sin FIFOS, sin entrada de terminal, etc.):

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
int main(){
  struct stat sbuf;
  if(fstat(0, &sbuf)<0){ perror("Can't stat stdin"); return 1; }

  char* buf = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, 0/*stdin*/, 0/*offset*/);
  if(buf == MAP_FAILED){ perror("Mmap error"); return 1; } 

  size_t nread = sbuf.st_size, nfound=0;
  char const* p;
  for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}

  printf("%lu\n", nfound);
  return 0;
}

Creé mi archivo de prueba con:

 $ dd if=/dev/zero of=file bs=1M count=1042 

y agregó algunas nuevas líneas de prueba con:

 $ echo >> 1GB 

y un editor hexadecimal.

PSkocik
fuente
Me sorprendió el resultado de mmap TBH. Solía ​​pensar que mmaping era más rápido que leer / escribir, pero luego vi algunos puntos de referencia de Linux que mostraban lo contrario. Parece que es muy cierto en este caso.
PSkocik
44
mmap obtendrá resultados mucho mejores en Linux porque se asignará a páginas enormes en estos días, y los errores de TLB son sloooowwwwwww.
jthill
Puede haber algún beneficio al leer diferentes partes del archivo en subprocesos separados (por ejemplo, con un forbucle OpenMP ) para que se pueda avanzar mientras se detiene un subproceso en espera de entrada. Pero, por otro lado, puede dificultar la programación de E / S, por lo que todo lo que puedo recomendar es probarlo y medir.
Toby Speight
La read()versión puede beneficiarse de la lectura anticipada.
Barmar
1
@TobySpeight Sí, el subprocesamiento múltiple podría acelerarlo. También mirar escanear dos bytes a la vez a través de tablas de búsqueda 2 ^ 16 proporcionó una velocidad bastante buena la última vez que jugué con él.
PSkocik
18

Puede mejorar la solución sugerida por @pskocik reduciendo el número de llamadas a read. Hay muchas llamadas para leer BUFSIZfragmentos de un archivo de 1 Gb. El enfoque habitual para hacerlo es aumentar el tamaño del búfer:

  • solo por diversión, intente aumentar el tamaño del búfer en un factor de 10. O 100. En mi Debian 7, BUFSIZes 8192. Con el programa original, eso es 120 mil operaciones de lectura. Probablemente pueda permitirse un búfer de entrada de 1Mb para reducir eso en un factor de 100.
  • Para un enfoque más óptimo, las aplicaciones pueden asignar un búfer tan grande como el archivo, lo que requiere una sola operación de lectura. Eso funciona lo suficientemente bien para archivos "pequeños" (aunque algunos lectores tienen más de 1 Gb en su máquina).
  • finalmente, podría experimentar con E / S mapeadas en memoria, que maneja la asignación como tal.

Al realizar una evaluación comparativa de los diversos enfoques, debe tener en cuenta que algunos sistemas (como Linux) utilizan la mayor parte de la memoria no utilizada de su máquina como caché de disco. Hace un tiempo (hace casi 20 años, mencionado en las preguntas frecuentes viles ), me sorprendieron los resultados inesperadamente buenos de un algoritmo de paginación (no muy bueno) que había desarrollado para manejar condiciones de poca memoria en un editor de texto. Me explicaron que funcionaba rápido porque el programa funcionaba desde las memorias intermedias utilizadas para leer el archivo, y que solo si el archivo se volvía a leer o escribir, habría una diferencia en la velocidad.

Lo mismo se aplica a mmap(en otro caso aún en mi lista de tareas pendientes para incorporar a un FAQ, un desarrollador reportó muy buenos resultados en un escenario donde la memoria caché del disco fue la razón real para mejorar). El desarrollo de puntos de referencia requiere tiempo y cuidado para analizar las razones del buen (o mal) desempeño.

Otras lecturas:

Thomas Dickey
fuente
2
Está sobreestimando la influencia de los tamaños de búfer por encima de un cierto umbral. Por lo general, aumentar el tamaño del búfer más allá de 4KB-ish no ayuda mucho, y de hecho puede ser perjudicial porque puede expulsar el búfer del caché L1. En mi máquina, las pruebas con ddbuffers de 1 MB son más lentas que 8 KB. El valor predeterminado de 8 KB para wc en realidad se elige bastante bien, será casi óptimo para una amplia gama de sistemas.
marcelm