c++ - guia - qgis manual

mmap() vs. bloques de lectura (12)

Estoy trabajando en un programa que procesará archivos que podrían tener un tamaño de 100 GB o más. Los archivos contienen conjuntos de registros de longitud variable. Tengo una primera implementación en funcionamiento y ahora estoy buscando mejorar el rendimiento, particularmente al hacer E / S de manera más eficiente ya que el archivo de entrada se escanea muchas veces.

¿Existe una regla general para usar mmap() frente a la lectura en bloques a través de la biblioteca fstream C ++? Lo que me gustaría hacer es leer bloques grandes del disco en un búfer, procesar registros completos del búfer y luego leer más.

El código mmap() podría ser potencialmente complicado, ya que los bloques de mmap deben ubicarse en límites de tamaño de página (lo que yo entiendo) y es posible que los registros de los archivos me gusten a través de los límites de la página. Con fstream s, puedo buscar el inicio de un registro y comenzar a leer nuevamente, ya que no estamos limitados a leer bloques que se encuentran en límites de tamaño de página.

¿Cómo puedo decidir entre estas dos opciones sin escribir primero una implementación completa? ¿Alguna regla general (p. Ej., mmap() es 2 veces más rápido) o pruebas simples?

Creo que lo mejor de mmap es su potencial para la lectura asincrónica con:

addr1 = NULL; while( size_left > 0 ) { r = min(MMAP_SIZE, size_left); addr2 = mmap(NULL, r, PROT_READ, MAP_FLAGS, 0, pos); if (addr1 != NULL) { /* process mmap from prev cycle */ feed_data(ctx, addr1, MMAP_SIZE); munmap(addr1, MMAP_SIZE); } addr1 = addr2; size_left -= r; pos += r; } feed_data(ctx, addr1, r); munmap(addr1, r);

El problema es que no puedo encontrar el MAP_FLAGS correcto para dar una pista de que esta memoria debe sincronizarse desde el archivo lo antes posible. Espero que MAP_POPULATE brinde la pista correcta para mmap (es decir, que no intente cargar todo el contenido antes del retorno de la llamada, pero lo hará en modo asíncrono con feed_data). Al menos da mejores resultados con esta bandera, incluso ese manual indica que no hace nada sin MAP_PRIVATE desde 2.6.23.

El costo de rendimiento principal va a ser de disco i / o. "mmap ()" es ciertamente más rápido que istream, pero la diferencia puede no ser notable porque el disco de E / S dominará sus tiempos de ejecución.

Probé el fragmento de código de Ben Collins (ver arriba / abajo) para probar su afirmación de que "mmap () es mucho más rápido" y no encontró ninguna diferencia medible. Vea mis comentarios sobre su respuesta.

Ciertamente, no recomendaría separar el mapa de cada registro a menos que sus "registros" sean enormes, sería terriblemente lento, requeriría 2 llamadas al sistema para cada registro y posiblemente perdería la página de la memoria caché del disco. .

En su caso, creo que mmap (), istream y las llamadas de bajo nivel open () / read () serán todas iguales. Recomendaría mmap () en estos casos:

Hay acceso aleatorio (no secuencial) dentro del archivo, Y
todo encaja cómodamente en la memoria O hay una localidad de referencia dentro del archivo para que se puedan mapear ciertas páginas y otras páginas mapeadas. De esta forma, el sistema operativo usa la RAM disponible para obtener el máximo beneficio.
O si múltiples procesos están leyendo / trabajando en el mismo archivo, entonces mmap () es fantástico porque todos los procesos comparten las mismas páginas físicas.

(Por cierto, me encanta mmap () / MapViewOfFile ()).

En mi opinión, usar mmap () "solo" libera al desarrollador de tener que escribir su propio código de almacenamiento en caché. En un caso simple de "leer archivo exactamente una vez", esto no va a ser difícil (aunque como señala mlbrock aún guarda la copia de memoria en el espacio de proceso), pero si va y viene en el archivo o saltando bits y demás, creo que los desarrolladores del kernel probablemente hayan hecho un mejor trabajo al implementar el almacenamiento en caché que yo ...

Estaba tratando de encontrar la última palabra sobre el rendimiento de mmap / read en Linux y encontré una buena publicación ( link ) en la lista de distribución del kernel de Linux. Es desde 2000, por lo que desde entonces se han realizado muchas mejoras en IO y la memoria virtual en el kernel, pero explica muy bien la razón por la cual mmap o read pueden ser más rápidos o más lentos.

Una llamada a mmap tiene más sobrecarga que read (al igual que epoll tiene más sobrecarga que poll , que tiene más sobrecarga que read ). Cambiar las asignaciones de memoria virtual es una operación bastante costosa en algunos procesadores por las mismas razones por las que el cambio entre diferentes procesos es costoso.
El sistema IO ya puede usar el caché de disco, por lo que si lee un archivo, golpeará el caché o lo omitirá independientemente del método que utilice.

Sin embargo,

Los mapas de memoria son generalmente más rápidos para el acceso aleatorio, especialmente si sus patrones de acceso son escasos e impredecibles.
Los mapas de memoria le permiten seguir usando páginas de la memoria caché hasta que termine. Esto significa que si utiliza un archivo pesadamente durante un período prolongado de tiempo, luego lo cierra y lo vuelve a abrir, las páginas aún se almacenarán en caché. Con la read , es posible que tu archivo haya sido eliminado del caché hace siglos. Esto no se aplica si usa un archivo y lo descarta inmediatamente. (Si intentas mlock páginas para mantenerlas en caché, estás tratando de burlar el caché del disco y este tipo de tonterías rara vez ayuda al rendimiento del sistema).
Leer un archivo directamente es muy simple y rápido.

La discusión de mmap / read me recuerda a otras dos discusiones de rendimiento:

Algunos programadores de Java se sorprendieron al descubrir que la E / S no bloqueada a menudo es más lenta que el bloqueo de E / S, lo cual tiene mucho sentido si se sabe que la E / S sin bloqueo requiere hacer más llamadas de sistema.
Algunos otros programadores de redes se sorprendieron al saber que epoll es a menudo más lento que la poll , lo que tiene mucho sentido si sabes que administrar epoll requiere hacer más llamadas de sistema.

Conclusión: utilice los mapas de memoria si accede a los datos aleatoriamente, manténgalos durante mucho tiempo, o si sabe que puede compartirlos con otros procesos ( MAP_SHARED no es muy interesante si no hay intercambio real). Lea los archivos normalmente si accede a los datos secuencialmente o deséchelos después de leerlos. Y si alguno de los métodos hace que tu programa sea menos complejo, hazlo. Para muchos casos del mundo real, no hay una forma segura de mostrar que uno es más rápido sin probar su aplicación real y NO es un punto de referencia.

(Perdón por necro''ear esta pregunta, pero estaba buscando una respuesta y esta pregunta sigue apareciendo en la parte superior de los resultados de Google).

Esto suena como un buen caso de uso para multi-threading ... Creo que podrías configurar fácilmente un hilo para leer datos mientras el otro (s) lo procesa. Esa puede ser una forma de aumentar drásticamente el rendimiento percibido. Solo un pensamiento.

Estoy de acuerdo en que la E / S de archivo mmap será más rápida, pero mientras se compara el código con el código, ¿no debería optimizarse el ejemplo del contador?

Ben Collins escribió:

char data[0x1000]; std::ifstream in("file.bin"); while (in) { in.read(data, 0x1000); // do something with data }

Sugeriría también intentar:

char data[0x1000]; std::ifstream iifle( "file.bin"); std::istream in( ifile.rdbuf() ); while( in ) { in.read( data, 0x1000); // do something with data }

Y más allá de eso, también podría tratar de hacer que el tamaño del búfer sea del mismo tamaño que una página de memoria virtual, en caso de que 0x1000 no tenga el tamaño de una página de memoria virtual en su máquina ... IMHO mmap''d file I / O still gana, pero esto debería acercar las cosas.

Hay muchas buenas respuestas aquí, así que solo agregaré un par de cuestiones que no vi tratadas directamente arriba.

mmap parece mágico

Tomando el caso donde el archivo ya está completamente en caché ¹ como la línea ^de base ² , mmap puede parecerse a la magia :

mmap solo requiere 1 llamada de sistema para (potencialmente) mapear el archivo completo, después del cual no se necesitan más llamadas al sistema.
mmap no requiere una copia de los datos del archivo desde el kernel al espacio de usuario.
mmap permite acceder al archivo "como memoria", incluido el procesamiento con cualquier truco avanzado que pueda hacer contra la memoria, como la auto-vectorización del compilador, intrínsecos SIMD , captación previa, rutinas de análisis optimizadas en memoria, OpenMP, etc.

En el caso de que el archivo ya esté en la memoria caché, parece imposible de superar: solo tiene acceso directo a la memoria caché de la página del núcleo como memoria y no puede ser más rápido que eso.

Bueno, puede.

mmap no es realmente mágico porque ...

mmap hace el trabajo por página

Un costo oculto principal de mmap vs read(2) (que es realmente el sistema comparable de nivel de sistema operativo syscall para bloques de lectura ) es que con mmap tendrá que hacer "algún trabajo" para cada página 4K en espacio de usuario, aunque podría estar oculto por el mecanismo de falla de página.

Por ejemplo, una implementación típica que solo mmap s todo el archivo necesitará un error, así que 100 GB / 4K = 25 millones de fallas para leer un archivo de 100 GB. Ahora, estas serán fallas menores , pero 25 mil millones de fallas de página aún no serán superrápidas. El costo de una falla menor probablemente esté en los 100s de los nanos en el mejor de los casos.

mmap depende en gran medida del rendimiento de TLB

Ahora, puede pasar MAP_POPULATE a mmap para indicarle que configure todas las tablas de página antes de regresar, por lo que no debería haber fallas de página al acceder a él. Ahora bien, esto tiene el pequeño problema de que también lee todo el archivo en la RAM, que explotará si tratas de mapear un archivo de 100 GB, pero ignorémoslo por el momento ³ . El núcleo necesita hacer un trabajo por página para configurar estas tablas de página (se muestra como tiempo de kernel). Esto termina siendo un costo importante en el enfoque de mmap , y es proporcional al tamaño del archivo (es decir, no se vuelve relativamente menos importante a medida que crece el tamaño del archivo) ⁴ .

Finalmente, incluso en el acceso de espacio de usuario, una asignación de este tipo no es exactamente gratuita (en comparación con los búferes de memoria grandes que no se originan en un mmap basado en archivos): incluso una vez configuradas las tablas de páginas, cada acceso a una nueva página , conceptualmente, incurrir en una falla TLB. Dado que mmap un archivo significa usar la memoria caché de la página y sus páginas de 4K, nuevamente incurre en este costo 25 millones de veces para un archivo de 100 GB.

Ahora, el costo real de estas fallas TLB depende en gran medida de al menos los siguientes aspectos de su hardware: (a) cuántas entidades 4K TLB tiene y cómo funciona el resto de la traducción en caché (b) qué tan bien trata la captación previa de hardware con el TLB, por ejemplo, ¿se puede precapturar el inicio de una página? (c) qué tan rápido y qué tan paralelo es el hardware para caminar de página. En los modernos procesadores Intel de gama alta x86, el hardware para caminar de página es en general muy fuerte: hay al menos 2 andadores de página paralelos, una caminata de página simultánea con la ejecución continua y la recuperación previa de hardware puede desencadenar una caminata de página. Por lo tanto, el impacto de TLB en una carga de lectura de transmisión es bastante bajo, y dicha carga a menudo funcionará de manera similar independientemente del tamaño de la página. ¡Sin embargo, otro hardware es mucho peor!

read () evita estas trampas

El syscall de read() , que es lo que generalmente subyace a las llamadas de tipo "lectura en bloque" ofrecidas, por ejemplo, en C, C ++ y en otros idiomas, tiene una desventaja principal de la que todos son conscientes:

Cada llamada de read() de N bytes debe copiar N bytes del kernel al espacio del usuario.

Por otro lado, evita la mayoría de los costos anteriores: no necesita asignar en 25 millones de páginas 4K al espacio de uso. Por lo general, puede malloc un buffer pequeño de un solo buffer en el espacio de usuario y reutilizarlo repetidamente para todas sus llamadas de read . Del lado del kernel, casi no hay problemas con páginas 4K o errores TLB porque toda la RAM se mapea linealmente usando algunas páginas muy grandes (por ejemplo, páginas de 1 GB en x86), por lo que las páginas subyacentes en el caché de páginas están cubiertas muy eficientemente en el espacio del kernel.

Así que, básicamente, tiene la siguiente comparación para determinar cuál es más rápido para una sola lectura de un archivo grande:

¿El trabajo extra por página implicado por el enfoque de mmap más costoso que el trabajo por bytes de copiar el contenido del kernel al espacio de usuario implícito al usar read() ?

En muchos sistemas, en realidad son aproximadamente equilibrados. Tenga en cuenta que cada uno se escala con atributos completamente diferentes del hardware y la pila del sistema operativo.

En particular, el enfoque mmap se vuelve relativamente más rápido cuando:

El sistema operativo tiene un manejo rápido de fallas menores y especialmente optimizaciones de volcado de fallas menores tales como fallas.
El sistema operativo tiene una buena implementación MAP_POPULATE que puede procesar eficientemente mapas grandes en casos donde, por ejemplo, las páginas subyacentes son contiguas en la memoria física.
El hardware tiene un rendimiento de traducción de página fuerte, como grandes TLB, TLB de segundo nivel rápidos, buscadores de páginas rápidos y paralelos, buena interacción de captación previa con traducción, etc.

... mientras que el enfoque de read() se vuelve relativamente más rápido cuando:

El syscall de read() tiene un buen rendimiento de copia. Por ejemplo, buen rendimiento de copy_to_user en el lado kernel.
El kernel tiene una forma eficiente (relativa a la tierra de usuario) de mapear la memoria, por ejemplo, usando solo unas pocas páginas grandes con soporte de hardware.
El kernel tiene llamadas de sistema rápidas y una forma de mantener las entradas de TLB del núcleo en todas las llamadas de sistema.

Los factores de hardware anteriores varían enormemente en diferentes plataformas, incluso dentro de la misma familia (por ejemplo, dentro de generaciones x86 y especialmente segmentos de mercado) y definitivamente a través de arquitecturas (por ejemplo, ARM vs x86 vs PPC).

Los factores del sistema operativo también cambian, con varias mejoras en ambos lados que causan un gran salto en la velocidad relativa para un enfoque u otro. Una lista reciente incluye:

Adición de fault-around, descrito anteriormente, que realmente ayuda al caso de mmap sin MAP_POPULATE .
Adición de métodos copy_to_user -path copy_to_user en arch/x86/lib/copy_user_64.S , por ejemplo, utilizando REP MOVQ cuando es rápido, lo que realmente ayuda al caso de read() .

¹ Esto más o menos también incluye el caso en el que el archivo no se almacenó en caché completo para comenzar, pero donde la lectura anticipada del sistema operativo es lo suficientemente buena para que parezca así (es decir, la página generalmente se almacena en caché cuando usted lo quiero). Sin embargo, este es un tema sutil porque la manera en que la lectura anticipada funciona a menudo es bastante diferente entre mmap y las llamadas de read , y puede ajustarse aún más mediante llamadas de "aviso" como se describe en ² .

² ... porque si el archivo no está almacenado en la memoria caché, su comportamiento estará completamente dominado por las preocupaciones de IO, incluyendo qué tan comprensivo es su patrón de acceso para el hardware subyacente, y todo su esfuerzo debe ser para garantizar que dicho acceso sea tan simpático como posible, por ejemplo, mediante el uso de llamadas madvise o fadvise (y cualquier cambio de nivel de aplicación que pueda realizar para mejorar los patrones de acceso).

³ Puede solucionarlo, por ejemplo, creando mmap secuenciales en ventanas de un tamaño más pequeño, digamos 100 MB.

⁴ De hecho, resulta que el enfoque MAP_POPULATE es (al menos una combinación de hardware / OS) solo ligeramente más rápido que no usarlo, probablemente porque el núcleo está usando faultaround , por lo que el número real de fallas menores se reduce por un factor de 16 o así.

Lamento que Ben Collins haya perdido su código fuente de ventanas correctas de mmap. Sería bueno tenerlo en Boost.

Sí, mapear el archivo es mucho más rápido. Básicamente está utilizando el subsistema de memoria virtual del sistema operativo para asociar la memoria al disco y viceversa. Piénselo de esta manera: si los desarrolladores del kernel del sistema operativo pudieran hacerlo más rápido, lo harían. Porque hacerlo hace que todo sea más rápido: bases de datos, tiempos de arranque, tiempos de carga del programa, etcétera.

El enfoque de la ventana deslizante realmente no es tan difícil ya que se pueden mapear múltiples páginas contiguas a la vez. Por lo tanto, el tamaño del registro no importa siempre que el más grande de un solo registro se ajuste a la memoria. Lo importante es administrar la contabilidad.

Si un registro no comienza en un límite getpagesize (), su asignación debe comenzar en la página anterior. La longitud de la región mapeada se extiende desde el primer byte del registro (redondeado hacia abajo si es necesario al múltiplo más cercano de getpagesize ()) hasta el último byte del registro (redondeado al múltiplo más cercano de getpagesize ()). Cuando haya terminado de procesar un registro, puede desasignarlo () y pasar al siguiente.

Todo esto funciona bien en Windows también usando CreateFileMapping () y MapViewOfFile () (y GetSystemInfo () para obtener SYSTEM_INFO.dwAllocationGranularity --- not SYSTEM_INFO.dwPageSize).

Quizás deba preprocesar los archivos, de modo que cada registro esté en un archivo separado (o al menos que cada archivo tenga un tamaño de mmap).

¿También podría hacer todos los pasos de procesamiento para cada registro, antes de pasar al siguiente? Tal vez eso evitaría algunos de los gastos indirectos de IO?

Recuerdo haber mapeado un gran archivo que contenía una estructura de árbol en la memoria hace años. Me sorprendió la velocidad en comparación con la deserialización normal que implica mucho trabajo en la memoria, como la asignación de nodos de árbol y la configuración de punteros. De hecho, estaba comparando una sola llamada a mmap (o su contraparte en Windows) con muchas (MUCHAS) llamadas al operador nuevas y llamadas al constructor. Para ese tipo de tarea, mmap es inmejorable en comparación con la deserialización. Por supuesto, uno debe buscar impulsa el puntero reubicable para esto.

mmap debería ser más rápido, pero no sé cuánto. Depende mucho de tu código. Si usa mmap, es mejor mapear todo el archivo a la vez, eso hará que su vida sea mucho más fácil. Un posible problema es que si su archivo es más grande que 4 GB (o en la práctica el límite es más bajo, a menudo 2 GB), necesitará una arquitectura de 64 bits. Entonces, si está usando un entorno 32, probablemente no quiera usarlo.

Habiendo dicho eso, puede haber una mejor ruta para mejorar el rendimiento. Dijiste que el archivo de entrada se escanea muchas veces , si puedes leerlo en una pasada y luego terminarlo, eso podría ser mucho más rápido.

mmap es mucho más rápido. Puede escribir un punto de referencia simple para demostrarlo a usted mismo:

char data[0x1000]; std::ifstream in("file.bin"); while (in) { in.read(data, 0x1000); // do something with data }

versus:

const int file_size=something; const int page_size=0x1000; int off=0; void *data; int fd = open("filename.bin", O_RDONLY); while (off < file_size) { data = mmap(NULL, page_size, PROT_READ, 0, fd, off); // do stuff with data munmap(data, page_size); off += page_size; }

Claramente, estoy omitiendo detalles (por ejemplo, cómo determinar cuándo se llega al final del archivo en caso de que el archivo no sea un múltiplo de page_size , por ejemplo), pero realmente no debería ser mucho más complicado que esta.

Si puede, puede tratar de dividir sus datos en varios archivos que pueden ser mmap () - ed en su totalidad en lugar de en parte (mucho más simple).

Hace un par de meses tuve una implementación a medias de una clase de flujo m_map () de ventanas deslizantes para boost_iostreams, pero a nadie le importó y me puse ocupado con otras cosas. Lamentablemente, eliminé un archivo de proyectos inacabados antiguos hace unas semanas, y esa fue una de las víctimas :-(

Actualización : también debería agregar la advertencia de que este punto de referencia se vería bastante diferente en Windows porque Microsoft implementó una caché de archivos ingeniosa que hace la mayor parte de lo que haría con mmap en primer lugar. Es decir, para los archivos de acceso frecuente, puede hacer std :: ifstream.read () y sería tan rápido como mmap, porque la memoria caché de archivos ya habría hecho una asignación de memoria para usted, y es transparente.

Actualización final : Miren, gente: en una gran cantidad de diferentes combinaciones de plataformas de sistemas operativos y bibliotecas y discos estándar y jerarquías de memoria, no puedo decir con certeza que la llamada al sistema mmap , vista como una caja negra, siempre siempre será sustancialmente más rápido que read . Esa no era exactamente mi intención, incluso si mis palabras pudieran interpretarse de esa manera. En última instancia, mi punto era que la E / S asignada por memoria es generalmente más rápida que la E / S basada en bytes; esto sigue siendo cierto Si encuentra experimentalmente que no hay diferencia entre los dos, entonces la única explicación que me parece razonable es que su plataforma implemente la asignación de memoria debajo de las cubiertas de una manera que sea ventajosa para la realización de llamadas para read . La única manera de estar absolutamente seguro de que está utilizando E / S con asignación de memoria de forma portátil es usar mmap . Si no le importa la portabilidad y puede confiar en las características particulares de sus plataformas de destino, entonces el uso de la read puede ser adecuado sin sacrificar de forma medible ningún rendimiento.

Editar para limpiar la lista de respuestas: @jbl:

la ventana deslizante mmap suena interesante. ¿Puedes decir un poco más al respecto?

Claro, estaba escribiendo una biblioteca C ++ para Git (una libgit ++, si lo desea), y me encontré con un problema similar a esto: necesitaba poder abrir archivos grandes (muy grandes) y no tener el rendimiento ser un perro total (como lo sería con std::fstream ).

Boost::Iostreams ya tiene una fuente mapped_file, pero el problema fue que se trataba de archivos completos de mmap ping, lo que te limita a 2 ^ (wordsize). En máquinas de 32 bits, 4 GB no es lo suficientemente grande. No es irrazonable esperar tener archivos .pack en Git que se vuelven mucho más grandes que eso, así que necesitaba leer el archivo en fragmentos sin recurrir a archivos regulares de .pack Bajo las tapas de Boost::Iostreams , implementé una fuente, que es más o menos otra vista de la interacción entre std::streambuf y std::istream . También podría intentar un enfoque similar simplemente heredando std::filebuf en mapped_filebuf y de manera similar, heredando std::fstream en a mapped_fstream . Es la interacción entre los dos que es difícil acertar. Boost::Iostreams ha hecho parte del trabajo por usted, y también proporciona ganchos para filtros y cadenas, por lo que pensé que sería más útil implementarlo de esa manera.