mmap()vs.bloques de lectura

https://stackoverflow.com/questions/45972

09-06-2019
|

Pregunta

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 para realizar E/S de manera más eficiente, ya que el archivo de entrada se escanea muchas veces.

¿Existe una regla general para utilizar mmap() versus lectura en bloques a través de C++ fstream ¿biblioteca?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 mmap() El código podría potencialmente volverse muy complicado ya que mmapLos bloques 'd deben ubicarse en los límites del tamaño de la página (según tengo entendido) y los registros podrían cruzar los límites de la página.Con fstreams, puedo simplemente 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 del tamaño de una página.

¿Cómo puedo decidir entre estas dos opciones sin redactar primero una implementación completa?Cualquier regla general (por ejemplo, mmap() es 2 veces más rápido) o pruebas simples?

Solución

Estaba tratando de encontrar la última palabra sobre el rendimiento de lectura/mmap en Linux y encontré una buena publicación (enlace) en la lista de correo del kernel de Linux.Es del año 2000, por lo que ha habido muchas mejoras en IO y memoria virtual en el kernel desde entonces, pero explica muy bien el motivo. mmap o read puede ser más rápido o más lento.

una llamada a mmap tiene más gastos generales que read (al igual que epoll tiene más gastos generales que poll, que tiene más gastos generales que read).Cambiar las asignaciones de memoria virtual es una operación bastante costosa en algunos procesadores por las mismas razones que cambiar entre diferentes procesos es costoso.
El sistema IO ya puede usar el caché del disco, por lo que si lees un archivo, accederás al caché o lo perderás sin importar el método que uses.

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 mantener usando páginas del caché hasta que haya terminado.Esto significa que si utiliza mucho un archivo durante un largo período de tiempo, lo cierra y lo vuelve a abrir, las páginas seguirán almacenadas en caché.Con read, es posible que su archivo haya sido eliminado del caché hace años.Esto no se aplica si utiliza un archivo y lo descarta inmediatamente.(Si intentas mlock páginas sólo para mantenerlas en caché, está intentando burlar el caché del disco y este tipo de tontería rara vez ayuda al rendimiento del sistema).
Leer un archivo directamente es muy sencillo y rápido.

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

Algunos programadores de Java se sorprendieron al descubrir que las E/S sin bloqueo suelen ser más lentas que las E/S con bloqueo, lo cual tenía mucho sentido si se sabía que las E/S sin bloqueo requieren realizar más llamadas al sistema.
Algunos otros programadores de redes se sorprendieron al saber que epoll suele ser más lento que poll, lo cual tiene mucho sentido si sabes que gestionar epoll requiere hacer más llamadas al sistema.

Conclusión: Utilice mapas de memoria si accede a los datos de forma aleatoria, los conserva durante mucho tiempo o si sabe que puede compartirlos con otros procesos (MAP_SHARED no es muy interesante si no se comparte).Lea los archivos normalmente si accede a los datos de forma secuencial o los descarta después de leerlos.Y si alguno de los métodos hace que su programa sea menos complejo, hágalo eso.En muchos casos del mundo real, no existe una forma segura de demostrar que uno es más rápido sin probar su aplicación real y NO un punto de referencia.

(Perdón por ignorar esta pregunta, pero estaba buscando una respuesta y esta pregunta seguía apareciendo en la parte superior de los resultados de Google).

Otros consejos

El principal costo de rendimiento será la E/S del disco."mmap()" es ciertamente más rápido que istream, pero la diferencia puede no ser notable porque la E/S del disco dominará los 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 forma más rápido" y no encontró ninguna diferencia mensurable.Vea mis comentarios sobre su respuesta.

ciertamente lo haría no recomiendo mapear por separado cada registro por turno, a menos que sus "registros" sean enormes; eso 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 open()/read() de bajo nivel serán todas iguales.Recomendaría mmap() en estos casos:

Hay acceso aleatorio (no secuencial) dentro del archivo, Y
todo cabe cómodamente en la memoria O hay una localidad de referencia dentro del archivo para que ciertas páginas se puedan mapear y otras páginas se puedan mapear.De esta manera, el sistema operativo aprovecha al máximo la RAM disponible.
O si varios 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()).

mmap es forma más rápido.Podrías escribir un punto de referencia simple para demostrártelo a ti 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 (como cómo determinar cuándo llega al final del archivo en caso de que su archivo no sea un múltiplo de page_size, por ejemplo), pero en realidad no debería ser mucho más complicado que esto.

Si puede, puede intentar dividir sus datos en varios archivos que puedan editarse con mmap() 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 transmisión mmap()-ed de ventana deslizante para boost_iostreams, pero a nadie le importó y me puse a trabajar con otras cosas.Desafortunadamente, hace unas semanas eliminé un archivo de viejos proyectos sin terminar, y esa fue una de las víctimas :-(

Actualizar:También debo agregar la advertencia de que este punto de referencia se vería bastante diferente en Windows porque Microsoft implementó un ingenioso caché de archivos que hace la mayor parte de lo que haría con mmap en primer lugar.Es decir, para los archivos a los que se accede con frecuencia, podría simplemente hacer std::ifstream.read() y sería tan rápido como mmap, porque el caché del archivo ya habría realizado un mapeo de memoria por usted, y es transparente.

Actualización final:Miren gente:en muchas combinaciones de plataformas diferentes de sistema operativo y bibliotecas estándar, discos y jerarquías de memoria, no puedo decir con certeza que la llamada al sistema mmap, visto como una caja negra, 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 fue que la E/S asignada en memoria es generalmente más rápida que la E/S basada en bytes;esto sigue siendo cierto.Si descubre experimentalmente que no hay diferencia entre los dos, entonces la única explicación que me parece razonable es que su plataforma implementa un mapeo de memoria en secreto de una manera que resulta ventajosa para el rendimiento de las llamadas a read.La única forma de estar absolutamente seguro de que está utilizando E/S asignadas en memoria de forma portátil es utilizar mmap.Si no le importa la portabilidad y puede confiar en las características particulares de sus plataformas de destino, entonces use read puede ser adecuado sin sacrificar de manera mensurable ningún rendimiento.

Edite 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++, por así decirlo) y me encontré con un problema similar a este:Necesitaba poder abrir archivos grandes (muy grandes) y que el rendimiento no fuera un perro total (como sería con std::fstream).

Boost::Iostreams ya tiene una fuente mapped_file, pero el problema era que era mmaphaga ping a archivos completos, lo que lo limita a 2 ^ (tamaño de palabra).En máquinas de 32 bits, 4 GB no es suficiente.No es descabellado esperar tener .pack archivos en Git que se vuelven mucho más grandes que eso, por lo que necesitaba leer el archivo en fragmentos sin recurrir a la E/S de archivos normal.Bajo las sábanas 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 puedes probar un enfoque similar simplemente heredando std::filebuf en un mapped_filebuf y de la misma manera, heredar std::fstream en a mapped_fstream.Es la interacción entre los dos lo que es difícil de lograr. Boost::Iostreams tiene parte del trabajo hecho 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.

Ya hay muchas buenas respuestas aquí que cubren muchos de los puntos destacados, por lo que solo agregaré un par de cuestiones que no vi abordadas directamente arriba.Es decir, esta respuesta no debe considerarse una descripción completa de los pros y los contras, sino más bien un complemento a otras respuestas aquí.

mmap parece magia

Tomando el caso donde el archivo ya está completamente almacenado en caché¹ como base², mmap podría parecer bastante parecido magia:

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

En el caso de que el archivo ya esté en el caché, parece imposible de superar:simplemente accede directamente al caché de la página del kernel como memoria y no puede ser más rápido que eso.

Bueno, puede.

mmap no es realmente mágico porque...

mmap todavía funciona por página

Un costo oculto primario de mmap vs read(2) (que es realmente la llamada al sistema comparable a nivel de sistema operativo para bloques de lectura) es que con mmap Tendrás que hacer "algo de trabajo" para cada página 4K en el espacio de usuario, aunque pueda estar oculta por el mecanismo de error de página.

Por ejemplo, una implementación típica que simplemente mmapPero será necesario corregir el archivo completo, por lo que 100 GB/4K = 25 millones de errores para leer un archivo de 100 GB.Ahora, estos serán fallas menores, pero 25 mil millones de errores de página todavía no serán muy rápidos.El costo de una falla menor probablemente sea de cientos de nanos en el mejor de los casos.

mmap depende en gran medida del rendimiento de TLB

Ahora puedes pasar MAP_POPULATE a mmap para decirle que configure todas las tablas de páginas antes de regresar, para que no haya fallas de página al acceder a ella.Ahora, esto tiene el pequeño problema de que también lee el archivo completo en la RAM, lo que explotará si intentas asignar un archivo de 100 GB, pero ignoremos eso por ahora.³.El núcleo necesita hacer trabajo por página para configurar estas tablas de páginas (aparece como tiempo del kernel).Esto termina siendo un costo importante en el mmap enfoque, 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 espacio de usuario, acceder a dicha asignación no es exactamente gratuito (en comparación con grandes buffers de memoria que no se originan en un archivo basado en archivos). mmap) - incluso una vez que las tablas de páginas están configuradas, cada acceso a una nueva página, conceptualmente, incurrirá en una pérdida de TLB.Desde mmapLeer un archivo significa utilizar el caché de páginas y sus páginas 4K; nuevamente, incurre en este costo 25 millones de veces por un archivo de 100 GB.

Ahora bien, el coste real de estos errores de TLB depende en gran medida de al menos los siguientes aspectos de su hardware:(a) cuántas entidades TLB 4K tiene y cómo funciona el resto del almacenamiento en caché de traducción (b) qué tan bien la captación previa de hardware trata con el TLB; por ejemplo, ¿puede la captación previa desencadenar un recorrido de página?(c) qué tan rápido y paralelo es el hardware de desplazamiento de páginas.En los procesadores Intel x86 modernos de gama alta, el hardware de desplazamiento de páginas es, en general, muy potente:Hay al menos dos recorridos de página paralelos, un recorrido de página puede ocurrir simultáneamente con la ejecución continua y la captación previa de hardware puede desencadenar un recorrido de página.Entonces el impacto del TLB en un transmisión La carga de lectura es bastante baja y dicha carga a menudo funcionará de manera similar independientemente del tamaño de la página.¡Sin embargo, otro hardware suele ser mucho peor!

read() evita estos errores

El read() syscall, que es lo que generalmente subyace a las llamadas de tipo "lectura en bloque" que se ofrecen, por ejemplo, en C, C++ y otros lenguajes, tiene una desventaja principal que todos conocen:

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

Por otro lado, evita la mayoría de los costos anteriores: no es necesario mapear 25 millones de páginas 4K en el espacio del usuario.normalmente puedes malloc un único búfer pequeño en el espacio del usuario y reutilícelo repetidamente para todos sus read llamadas.En el lado del kernel, casi no hay problemas con las páginas 4K o los errores de TLB porque toda la RAM generalmente se asigna linealmente usando unas pocas 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.

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 que implica el mmap enfoque es más costoso que el trabajo por byte de copiar el contenido del archivo desde el kernel al espacio de usuario que implica el uso read()?

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

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

El sistema operativo tiene un manejo rápido de fallas menores y, especialmente, optimizaciones de agrupación de fallas menores, como la solución de fallas.
El sistema operativo tiene una buena MAP_POPULATE Implementación 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 sólido rendimiento de traducción de páginas, como TLB grandes, TLB rápidos de segundo nivel, recorridos de página rápidos y paralelos, buena interacción de captación previa con la traducción, etc.

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

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

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

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

Además de la corrección de errores, descrita anteriormente, que realmente ayuda al mmap caso sin MAP_POPULATE.
Adición de vía rápida copy_to_user métodos en arch/x86/lib/copy_user_64.S, por ejemplo, usando REP MOVQ cuando es rápido, lo que realmente ayuda al read() caso.

Actualización después de Spectre y Meltdown

Las mitigaciones de las vulnerabilidades Spectre y Meltdown aumentaron considerablemente el costo de una llamada al sistema.En los sistemas que he medido, el costo de una llamada al sistema "no hacer nada" (que es una estimación de la sobrecarga pura de la llamada al sistema, aparte de cualquier trabajo real realizado por la llamada) pasó de aproximadamente 100 ns en un tiempo típico sistema Linux moderno a aproximadamente 700 ns.Además, dependiendo de su sistema, el aislamiento de tabla de páginas La solución específica para Meltdown puede tener efectos posteriores adicionales además del costo directo de la llamada al sistema debido a la necesidad de recargar las entradas TLB.

Todo esto es una desventaja relativa para read() métodos basados en comparación con mmap métodos basados, ya que read() Los métodos deben realizar una llamada al sistema para cada "tamaño de búfer" de datos.No puede aumentar arbitrariamente el tamaño del búfer para amortizar este costo, ya que el uso de búferes grandes generalmente funciona peor ya que excede el tamaño L1 y, por lo tanto, sufre constantemente errores de caché.

Por otra parte, con mmap, puedes mapear en una gran región de memoria con MAP_POPULATE y acceder a él de manera eficiente, al costo de una sola llamada al sistema.

¹ Esto más o menos también incluye el caso en el que el archivo no estaba completamente almacenado en caché para empezar, pero donde la lectura anticipada del sistema operativo es lo suficientemente buena como para que así parezca (es decir, la página generalmente está almacenada en caché en el momento que desee). él).Sin embargo, se trata de un problema sutil porque la forma en que funciona la lectura anticipada suele ser bastante diferente entre mmap y read llamadas, y se puede ajustar aún más mediante llamadas de "aviso" como se describe en ².

² ...porque si el archivo es no almacenado en caché, su comportamiento estará completamente dominado por preocupaciones de IO, incluido qué tan comprensivo es su patrón de acceso al hardware subyacente, y todo su esfuerzo debe centrarse en garantizar que dicho acceso sea lo más comprensivo posible, por ejemplo.mediante el uso de madvise o fadvise llamadas (y cualquier cambio a nivel de aplicación que pueda realizar para mejorar los patrones de acceso).

³ Podrías evitar eso, por ejemplo, secuencialmente mmaping en ventanas de un tamaño más pequeño, digamos 100 MB.

⁴ De hecho, resulta que MAP_POPULATE El enfoque es (al menos una combinación de hardware/OS) sólo un poco más rápido que no usarlo, probablemente porque el kernel está usando falla - por lo que el número real de fallos menores se reduce en un factor de 16 aproximadamente.

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

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

El enfoque de 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 cualquier registro quepa en la memoria.Lo importante es llevar la contabilidad.

Si un registro no comienza en un límite getpagesize(), su mapeo debe comenzar en la página anterior.La longitud de la región asignada 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 hacia arriba al múltiplo más cercano de getpagesize()).Cuando haya terminado de procesar un registro, puede desasignarlo() y pasar al siguiente.

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

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 le hará la vida mucho más fácil.Un problema potencial es que si su archivo tiene más de 4 GB (o en la práctica el límite es inferior, a menudo 2 GB), necesitará una arquitectura de 64 bits.Entonces, si estás usando un entorno 32, probablemente no quieras usarlo.

Dicho esto, puede haber una mejor ruta para mejorar el rendimiento.Usted dijo el archivo de entrada se escanea muchas veces, si puede leerlo de una sola vez y luego terminarlo, podría ser mucho más rápido.

Estoy de acuerdo en que la E/S de archivos mmap será más rápida, pero mientras comparas el código, ¿no debería ser el contraejemplo? un poco optimizado?

Ben Collins escribió:

char data[0x1000];
std::ifstream in("file.bin");

while (in)
{
    in.read(data, 0x1000);
    // do something with data 
}

Sugeriría probar también:

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 puede intentar 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 sea el tamaño de una página de memoria virtual en su máquina...En mi humilde opinión, la E/S de archivos mmap todavía gana, pero esto debería acercar las cosas.

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

¿También podría realizar todos los pasos de procesamiento para cada registro antes de pasar al siguiente?¿Quizás eso evitaría algunos de los gastos generales de IO?

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

Recuerdo haber mapeado en la memoria un archivo enorme que contenía una estructura de árbol hace años.Me sorprendió la velocidad en comparación con la deserialización normal, que implica mucho trabajo en la memoria, como asignar nodos de árbol y configurar punteros.De hecho, estaba comparando una sola llamada a MMAP (o su contraparte en Windows) con muchas (muchas) llamadas al operador de nuevas y llamadas de constructor.Para este tipo de tareas, mmap es inmejorable en comparación con la deserialización.Por supuesto, uno debería considerar los impulsos del puntero reubicable para esto.

Esto suena como un buen caso de uso para subprocesos múltiples...Creo que podrías configurar con bastante facilidad un hilo para que lea datos mientras los demás los procesan.Ésa puede ser una forma de aumentar drásticamente el rendimiento percibido.Solo un pensamiento.

Creo que lo mejor de mmap es su potencial para 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 dé la pista correcta para mmap (es decir,No intentará cargar todo el contenido antes de regresar de la llamada, pero lo hará de forma asíncrona.con feed_data).Al menos da mejores resultados con este indicador, incluso ese manual indica que no hace nada sin MAP_PRIVATE desde 2.6.23.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow