modificar - ¿La forma más rápida de leer cada 30 bytes de un archivo binario grande?

manejo de archivos en c++ (7)

¿Cuál es la forma más rápida de leer cada 30 bytes de un archivo binario grande (2-3 GB)? He leído que hay problemas de rendimiento con Fseek debido a los buffers de E / S, pero tampoco quiero leer 2-3 GB de datos en la memoria antes de capturar cada 30 bytes.

Bueno, puedes leer un byte y luego buscar 29 bytes en un bucle. Pero el subsistema IO tiene que leer el archivo por sectores, que normalmente tienen un tamaño de 512 bytes, por lo que aún terminará leyendo todo el archivo.

A la larga, será más rápido leer todo el archivo en fragmentos que son un múltiplo de su tamaño de paso y luego solo mirar en el búfer. Hará que su vida sea un poco más simple si se asegura de que el tamaño del búfer sea un múltiplo de 30, y que la vida del subsistema de archivos sea más fácil si es un múltiplo de 512.

while (still more file to read) { char buf[30 * 512]; int cread = fread (buf, sizeof(buf), 1, fd); for (int ii = 0; ii < cread; ii += 30) { } }

Esto puede parecer ineficiente, pero resultará ser más rápido que intentar leer en fragmentos de 30 bytes.

Por cierto. Si está ejecutando en Windows y está dispuesto a ser específico del sistema operativo, realmente no puede superar el rendimiento de los archivos asignados a la memoria. ¿Cómo escanear archivos realmente enormes en el disco?

El propósito principal de una biblioteca de E / S almacenada en búfer es liberarlo de tales preocupaciones. Si tiene que leer cada 30 bytes, el sistema operativo terminará leyendo todo el archivo, ya que el sistema operativo lee fragmentos más grandes. Aquí están sus opciones, desde el más alto rendimiento hasta el más bajo:

Si tiene un espacio de direcciones grande (es decir, está ejecutando un sistema operativo de 64 bits en un hardware de 64 bits), el uso de IO asignada en memoria ( mmap en sistemas POSIX) le ahorrará el costo de tener los datos de copia del sistema operativo desde Espacio del kernel al espacio del usuario. Este ahorro podría ser significativo.
Como se muestra en las notas detalladas a continuación (y gracias a Steve Jessop por el punto de referencia), si le preocupa el rendimiento de E / S, debe descargar la biblioteca sfio de Phong Vo del grupo de Tecnología avanzada de software de AT&T. Es más seguro, está mejor diseñado y es más rápido que la biblioteca de E / S estándar de C. En los programas que usan mucho fseek , es mucho más rápido: hasta siete veces más rápido en un microbicarcidor simple.
Simplemente relájese y use fseek y fgetc , que están diseñados e implementados exactamente para resolver su problema.

Si toma este problema en serio, debe medir las tres alternativas . Steve Jessop y yo demostramos que el uso de fseek es más lento, y si está utilizando la biblioteca GNU C, fseek es mucho más lento. Usted debe medir mmap ; Puede ser el más rápido de todos.

Addendum: desea examinar su sistema de archivos y asegurarse de que pueda extraer de 2 a 3 GB del disco rápidamente. XFS puede vencer a ext2, por ejemplo. Por supuesto, si estás atascado con NTFS o HFS +, solo será lento.

Resultados impactantes solo en

Repetí las medidas de Steve Jessop en Linux. La biblioteca GNU C hace una llamada al sistema en cada fseek . A menos que POSIX lo requiera por alguna razón, es una locura. Podría masticar un montón de unos y ceros y vomitar una biblioteca de E / S mejorada que eso. De todos modos, los costos aumentan alrededor de un factor de 20, gran parte de los cuales se gastan en el núcleo. Si usa fgetc lugar de fread para leer bytes individuales, puede ahorrar aproximadamente un 20% en pequeños puntos de referencia.

Resultados menos impactantes con una biblioteca de E / S decente

Hice el experimento nuevamente, esta vez utilizando la biblioteca sfio Phong Vo. Lectura de 200MB toma

0.15s sin usar fseek ( BUFSZ es 30k)
0.57s usando fseek

Las mediciones repetidas muestran que sin fseek , el uso de sfio todavía reduce aproximadamente el 10% del tiempo de ejecución, pero los tiempos de ejecución son muy ruidosos (casi todo el tiempo se pasa en el sistema operativo).

En esta máquina (computadora portátil) no tengo suficiente espacio libre en disco para ejecutarme con un archivo que no cabe en el caché de disco, pero estoy dispuesto a sacar estas conclusiones:

Al usar una biblioteca de E / S sensible, fseek es más caro, pero no lo suficientemente caro como para hacer una gran diferencia (4 segundos si todo lo que haces es la E / S).
El proyecto GNU no proporciona una biblioteca de E / S sensible. Como suele ser el caso, el software GNU apesta.

Conclusión: si desea una E / S rápida, su primer movimiento debe ser reemplazar la biblioteca de E / S de GNU por la biblioteca sfio de AT&T . Es probable que otros efectos sean pequeños en comparación.

Es casi seguro que no tienes que preocuparte por eso. El tiempo de ejecución puede almacenar el último bloque que leyó para cada identificador de archivo. Incluso si no lo hace, el sistema operativo está almacenando en caché los accesos de archivos para usted.

Dicho esto, si lee un bloque a la vez, ahorra en gastos generales de llamadas a las funciones fseek y fread. Cuanto más grande sea el bloque que lee a la vez, más ahorrará en gastos generales de llamadas, aunque, obviamente, otros costos comienzan a hacerse sentir más allá de cierto punto.

Lo que sugeriría es que cree un búfer de unos pocos miles de bytes, lea cada 30º byte, vuelva a cargar el búfer con los siguientes miles de bytes y continúe hasta que llegue a la eof. De esa manera, la cantidad de datos que se leen en la memoria es limitada, y tampoco tiene que leer el archivo con tanta frecuencia. Encontrarás que cuanto mayor sea el búfer que creas, más rápido será.

Edición: En realidad, como se sugiere a continuación, probablemente querrá hacer que su búfer sea de unos pocos cientos de kb, no unos pocos miles de bytes (como dije, un búfer más grande = lectura de un archivo más rápido).

Si está dispuesto a salir de ANSI-C y utilizar llamadas específicas del sistema operativo, le recomiendo que utilice archivos asignados en la memoria. Esta es la versión de Posix (Windows tiene sus propias llamadas específicas del sistema operativo):

#define MAPSIZE 4096 int fd = open(file, O_RDONLY); struct stat stbuf; fstat(fd, &stbuf); char *addr = 0; off_t last_mapped_offset = -1; off_t idx = 0; while (idx < stbuf.st_size) { if (last_mapped_offset != (idx / MAPSIZE)) { if (addr) munmap(addr, MAPSIZE); last_mapped_offset = idx / MAPSIZE; addr = mmmap(0, MAPSIZE, PROT_READ, MAP_FILE, fd, idx, last_mapped_offset); } *(addr + (idx % MAPSIZE)); idx += 30; } munmap(addr, MAPSIZE); close(fd);

Si está leyendo datos de un disco duro con una fuente giratoria, la respuesta es leer todo el archivo de forma secuencial utilizando un búfer grande y descartar las partes de la memoria que no desea.

La unidad de acceso más pequeña posible a una unidad de disco duro estándar es el sector. Los tamaños de sector para todas las unidades de disco giratorias comunes son muchas veces más de 30 bytes. Esto significa que el controlador del disco duro debe acceder a todos y cada uno de los sectores, independientemente de cómo se vea la solicitud del host. No hay magia de bajo nivel posible para cambiar esto.

Incluso si este no fuera el caso y usted pudiera leer bytes individuales, hay una gran prima para las operaciones de lectura secuencial versus de búsqueda. El mejor caso posible sigue siendo el mismo que la lectura secuencial. En el mundo real, no me sorprendería que la sobrecarga de señalización impida que tales esquemas funcionen incluso con un búfer de comando masivo.

Prueba de rendimiento Si desea usarlo usted mismo, tenga en cuenta que la verificación de integridad (impresión total) solo funciona si el "paso" divide BUFSZ, y MEGS es lo suficientemente pequeño como para que no lea el final del archivo. Esto se debe a (a) la pereza, (b) el deseo de no ocultar el código real. rand1.data es unos pocos GB copiados de / dev / urandom usando dd .

#include <stdio.h> #include <stdlib.h> const long long size = 1024LL*1024*MEGS; const int step = 32; int main() { FILE *in = fopen("/cygdrive/c/rand1.data", "rb"); int total = 0; #if SEEK long long i = 0; char buf[1]; while (i < size) { fread(buf, 1, 1, in); total += (unsigned char) buf[0]; fseek(in, step - 1, SEEK_CUR); i += step; } #endif #ifdef BUFSZ long long i = 0; char buf[BUFSZ]; while (i < size) { fread(buf, BUFSZ, 1, in); i += BUFSZ; for (int j = 0; j < BUFSZ; j += step) total += (unsigned char) buf[j]; } #endif printf("%d/n", total); }

Resultados:

$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=20 && time ./buff2 83595817 real 0m1.391s user 0m0.030s sys 0m0.030s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=20 && time ./buff2 83595817 real 0m0.172s user 0m0.108s sys 0m0.046s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=20 && time ./buff2 83595817 real 0m0.031s user 0m0.030s sys 0m0.015s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=20 && time ./buff2 83595817 real 0m0.141s user 0m0.140s sys 0m0.015s $ gcc -std=c99 buff2.c -obuff2 -O3 -DSEEK -DMEGS=20 && time ./buff2 83595817 real 0m20.797s user 0m1.733s sys 0m9.140s

Resumen:

Estoy usando 20 MB de datos inicialmente, lo que por supuesto cabe en la memoria caché. La primera vez que lo leí (usando un búfer de 32KB) toma 1.4s, llevándolo a la memoria caché. La segunda vez (usando un búfer de 32 bytes) toma 0.17s. La tercera vez (nuevamente con el búfer de 32KB) toma 0.03s, lo cual es demasiado cercano a la granularidad de mi temporizador para que sea significativo. fseek toma más de 20 s, aunque los datos ya están en el caché de disco .

En este punto, estoy sacando a Fseek del ring para que los otros dos puedan continuar:

$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=1000 && time ./buff2 -117681741 real 0m33.437s user 0m0.749s sys 0m1.562s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=1000 && time ./buff2 -117681741 real 0m6.078s user 0m5.030s sys 0m0.484s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=1000 && time ./buff2 -117681741 real 0m1.141s user 0m0.280s sys 0m0.500s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=1000 && time ./buff2 -117681741 real 0m6.094s user 0m4.968s sys 0m0.640s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=1000 && time ./buff2 -117681741 real 0m1.140s user 0m0.171s sys 0m0.640s

1000 MB de datos también parece estar sustancialmente almacenado en caché. Un búfer de 32KB es 6 veces más rápido que un búfer de 32 bytes. Pero la diferencia es todo el tiempo del usuario, no el tiempo pasado bloqueado en la E / S del disco. Ahora, 8000MB es mucho más de lo que tengo RAM, así que puedo evitar el almacenamiento en caché:

$ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=8000 && time ./buff2 -938074821 real 3m25.515s user 0m5.155s sys 0m12.640s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32 -DMEGS=8000 && time ./buff2 -938074821 real 3m59.015s user 1m11.061s sys 0m10.999s $ gcc -std=c99 buff2.c -obuff2 -O3 -DBUFSZ=32*1024 -DMEGS=8000 && time ./buff2 -938074821 real 3m42.423s user 0m5.577s sys 0m14.484s

Ignore el primero de esos tres, se benefició de los primeros 1000 MB del archivo que ya se encontraba en la memoria RAM.

Ahora, la versión con 32KB es solo un poco más rápida en tiempo de reloj de pared (y no puedo molestarme en volver a ejecutar, así que ignorémosla por ahora), pero observe la diferencia en la hora de usuario + sistema: 20s vs. 82s. Creo que el almacenamiento en caché especulativo del disco de lectura anticipada de mi sistema operativo ha ahorrado el tocino del búfer de 32 bytes aquí: mientras el búfer de 32 bytes se está rellenando lentamente, el sistema operativo está cargando los siguientes sectores de disco aunque nadie los haya pedido. Sin eso, sospecho que hubiera sido un minuto (20%) más lento que el búfer de 32KB, que pasa menos tiempo en el usuario antes de solicitar la próxima lectura.

La moraleja de la historia: el almacenamiento en búfer de E / S estándar no lo corta en mi implementación, el desempeño de fseek es atroz como dice el interrogador. Cuando el archivo se almacena en caché en el sistema operativo, el tamaño del búfer es un gran problema. Cuando el archivo no se almacena en caché en el sistema operativo, el tamaño del búfer no hace mucha diferencia en el tiempo del reloj de pared, pero mi CPU estaba más ocupada.

La sugerencia fundamental de incrediman de usar un búfer de lectura es vital, ya que fseek es atroz. Discutir sobre si el búfer debe ser de unos pocos KB o unos cientos de KB es probablemente inútil en mi máquina, probablemente porque el sistema operativo ha hecho un trabajo para garantizar que la operación esté estrechamente vinculada a la E / S. Pero estoy bastante seguro de que esto se debe a la lectura anticipada del disco del sistema operativo, no al búfer de E / S estándar, porque si fuera lo último, entonces fseek sería mejor de lo que es. En realidad, podría ser que la E / S estándar esté haciendo la lectura anticipada, pero una implementación demasiado simple de fseek está descartando el búfer cada vez. No he investigado la implementación (y no pude seguirla a través del límite hacia el sistema operativo y los controladores del sistema de archivos, si lo hice).