mmap () vs. blocos de leitura

Estou trabalhando em um programa que processará arquivos que podem ter 100 GB ou mais de tamanho. Os arquivos contêm conjuntos de registros de tamanho variável. Eu tenho uma primeira implementação em funcionamento e agora estou olhando para melhorar o desempenho, particularmente em fazer I / O com mais eficiência, pois o arquivo de input é varrido várias vezes.

Existe uma regra geral para usar mmap() versus leitura em blocos via biblioteca de fstream C ++? O que eu gostaria de fazer é ler blocos grandes do disco em um buffer, processar registros completos do buffer e ler mais.

O código mmap() poderia ficar muito confuso, já que os blocos do mmap ‘precisam ficar em limites de tamanho de página (minha compreensão) e os registros poderiam gostar dos limites da página. Com o fstream , posso apenas procurar o início de um registro e começar a ler novamente, já que não estamos limitados a ler blocos que estão em limites de tamanho de página.

Como posso decidir entre essas duas opções sem realmente criar uma implementação completa primeiro? Quaisquer regras básicas (por exemplo, mmap() é 2x mais rápido) ou testes simples?

Eu estava tentando encontrar a palavra final sobre o desempenho mmap / read no Linux e me deparei com um bom post ( link ) na lista de discussão do kernel Linux. É de 2000, então tem havido muitas melhorias para IO e memory virtual no kernel desde então, mas explica bem o motivo pelo qual o mmap ou read pode ser mais rápido ou mais lento.

  • Uma chamada para mmap tem mais overhead do que read (assim como epoll tem mais overhead do que poll , que tem mais overhead do que read ). Alterar os mapeamentos de memory virtual é uma operação bastante cara em alguns processadores pelas mesmas razões que a troca entre diferentes processos é cara.
  • O sistema de E / S já pode usar o cache de disco, portanto, se você ler um arquivo, acessará o cache ou não o usará, independentemente do método usado.

Contudo,

  • Os mapas de memory geralmente são mais rápidos para access random, especialmente se seus padrões de access forem esparsos e imprevisíveis.
  • Os mapas de memory permitem que você continue usando páginas do cache até terminar. Isso significa que, se você usar um arquivo intensamente por um longo período de tempo, feche-o e reabra-o, as páginas ainda serão armazenadas em cache. Com a read , seu arquivo pode ter sido liberado do cache há muitos anos. Isso não se aplica se você usar um arquivo e imediatamente descartá-lo. (Se você tentar criar páginas apenas para mantê-las no cache, você está tentando enganar o cache de disco e esse tipo de tolice raramente ajuda o desempenho do sistema).
  • Ler um arquivo diretamente é muito simples e rápido.

A discussão do mmap / read me lembra duas outras discussões sobre desempenho:

  • Alguns programadores de Java ficaram chocados ao descobrir que a E / S sem bloqueio é mais lenta que bloquear E / S, o que fazia todo o sentido se você sabe que E / S não bloqueantes requer mais syscalls.

  • Alguns outros programadores de rede ficaram chocados ao saber que epoll é geralmente mais lento que o poll , o que faz muito sentido se você sabe que gerenciar o epoll requer mais syscalls.

Conclusão: Use mapas de memory se você acessar dados aleatoriamente, mantê-los por um longo período, ou se você souber que pode compartilhá-los com outros processos ( MAP_SHARED não é muito interessante se não houver compartilhamento real). Leia os arquivos normalmente se você acessar os dados sequencialmente ou descartá-los após a leitura. E se um dos methods tornar o seu programa menos complexo, faça isso . Para muitos casos do mundo real, não há uma maneira segura de mostrar que um é mais rápido sem testar seu aplicativo real e NÃO um benchmark.

(Desculpe por necro’ing esta questão, mas eu estava procurando por uma resposta e esta questão continuava chegando no topo dos resultados do Google.)

O principal custo de desempenho será o disco i / o. “mmap ()” é certamente mais rápido que o istream, mas a diferença pode não ser perceptível porque o disco de i / o dominará seus tempos de execução.

Eu tentei o fragment de código de Ben Collins (veja acima / abaixo) para testar sua afirmação de que “mmap () é muito mais rápido” e não encontrou nenhuma diferença mensurável. Veja meus comentários sobre sua resposta.

Eu certamente não recomendaria separadamente o registro de cada registro a menos que seus “registros” sejam enormes – isso seria terrivelmente lento, exigindo 2 chamadas de sistema para cada registro e possivelmente perdendo a página do cache de memory de disco …. .

No seu caso, eu acho que mmap (), istream e as chamadas open () / read () de baixo nível serão todas iguais. Eu recomendaria mmap () nestes casos:

  1. Há access random (não sequencial) dentro do arquivo E
  2. a coisa toda se encheckbox confortavelmente na memory OU há localidade de referência dentro do arquivo para que determinadas páginas possam ser mapeadas e outras páginas mapeadas. Dessa forma, o sistema operacional usa a RAM disponível para o máximo benefício.
  3. OU se vários processos estão lendo / trabalhando no mesmo arquivo, então mmap () é fantástico porque todos os processos compartilham as mesmas páginas físicas.

(btw – Eu amo mmap () / MapViewOfFile ()).

O mmap é bem mais rápido. Você pode escrever um simples referencial para provar isso a si mesmo:

 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; } 

Obviamente, estou deixando de fora detalhes (como determinar quando você alcança o final do arquivo no caso de o arquivo não ser um múltiplo de page_size , por exemplo), mas não deve ser muito mais complicado do que esta.

Se você puder, você pode tentar dividir seus dados em vários arquivos que podem ser mmap () - ed no todo em vez de em parte (muito mais simples).

Um par de meses atrás eu tive uma implementação semi-assada de uma class de stream mmap () de janela deslizante para boost_iostreams, mas ninguém se importava e eu fiquei ocupado com outras coisas. Infelizmente, eu deletei um arquivo de projetos antigos inacabados há algumas semanas, e essa foi uma das vítimas 🙁

Atualização : Eu também devo adicionar a ressalva de que este benchmark pareceria bem diferente no Windows porque a Microsoft implementou um cache de arquivos bacana que faz a maior parte do que você faria com o mmap em primeiro lugar. Ou seja, para arquivos acessados ​​com freqüência, você poderia fazer std :: ifstream.read () e seria tão rápido quanto mmap, porque o cache de arquivos já teria feito um mapeamento de memory para você, e é transparente.

Atualização final : Veja, pessoas: através de várias combinações diferentes de plataformas e bibliotecas padrão e hierarquias de discos e memory, não posso dizer com certeza que o mmap do sistema, visto como uma checkbox preta, sempre será sempre substancialmente mais rápido que read . Essa não era exatamente a minha intenção, mesmo que minhas palavras pudessem ser interpretadas dessa maneira. Por fim, meu ponto é que a E / S mapeada por memory é geralmente mais rápida do que a E / S baseada em byte; isso ainda é verdade . Se você descobrir experimentalmente que não há diferença entre os dois, então a única explicação que parece razoável para mim é que sua plataforma implementa mapeamento de memory sob as capas de uma maneira que é vantajosa para o desempenho das chamadas para read . A única maneira de ter certeza absoluta de que você está usando a E / S mapeada na memory de maneira portátil é usar o mmap . Se você não se importa com a portabilidade e puder confiar nas características específicas de suas plataformas de destino, o uso de read pode ser adequado sem sacrificar qualquer desempenho mensurável.

Editar para limpar a lista de respostas: @jbl:

a janela deslizante mmap parece interessante. Você pode falar um pouco mais sobre isso?

Claro - eu estava escrevendo uma biblioteca C ++ para o Git (um libgit ++, se você quiser), e me deparei com um problema semelhante a este: eu precisava ser capaz de abrir arquivos grandes (muito grandes) e não ter um cão total (como seria com std::fstream ).

Boost::Iostreams já tem um mapped_file Source, mas o problema é que era mmap ping de arquivos inteiros, o que te limita a 2 ^ (wordsize). Em máquinas de 32 bits, 4 GB não são grandes o suficiente. Não é razoável esperar ter arquivos .pack no Git que se tornem muito maiores do que isso, então eu precisei ler o arquivo em partes sem recorrer a i / o de arquivo regular. Sob as coberturas do Boost::Iostreams , eu implementei um Source, que é mais ou menos uma outra visão da interação entre std::streambuf e std::istream . Você também pode tentar uma abordagem semelhante simplesmente herdando std::filebuf em um mapped_filebuf e da mesma forma, herdando std::fstream em a mapped_fstream . É a interação entre os dois que é difícil acertar. Boost::Iostreams tem um pouco do trabalho feito para você, e também fornece ganchos para filtros e cadeias, então eu pensei que seria mais útil implementá-lo dessa maneira.

Existem muitas boas respostas aqui que cobrem muitos dos pontos mais importantes, então vou apenas adicionar alguns problemas que não vi diretamente acima. Ou seja, essa resposta não deve ser considerada uma abrangente dos prós e contras, mas sim um adendo a outras respostas aqui.

mmap parece mágica

Tomando o caso em que o arquivo já está totalmente armazenado em cache 1 como a linha de base 2 , o mmap pode parecer muito com mágica :

  1. mmap requer apenas 1 chamada de sistema para (potencialmente) mapear o arquivo inteiro, após o qual não são necessárias mais chamadas do sistema.
  2. mmap não requer uma cópia dos dados do arquivo do kernel para o espaço do usuário.
  3. mmap permite que você acesse o arquivo “como memory”, incluindo processá-lo com qualquer truque avançado que você possa fazer contra a memory, como autovetorização do compilador, intrínsecos SIMD , pré-busca, rotinas de análise na memory otimizada, OpenMP, etc.

No caso em que o arquivo já está no cache, parece impossível de bater: você acessa diretamente o cache da página do kernel como memory e não pode ficar mais rápido do que isso.

Bem, isso pode.

mmap não é realmente mágico porque …

O mmap ainda faz o trabalho por página

Um custo oculto primário de mmap vs read(2) (que é realmente o syscall de nível de SO comparável para blocos de leitura ) é que com o mmap você precisará fazer “algum trabalho” para cada página 4K no espaço do usuário, mesmo que ele pode estar oculto pelo mecanismo de falha de página.

Por exemplo, uma implementação típica que apenas mmap o arquivo inteiro precisará fazer uma falha de 100 GB / 4K = 25 milhões de falhas para ler um arquivo de 100 GB. Agora, estas serão pequenas falhas , mas 25 bilhões de falhas de página ainda não serão super rápidas. O custo de uma falha menor provavelmente está nos 100s de nanos no melhor dos casos.

mmap depende muito do desempenho do TLB

Agora, você pode passar o MAP_POPULATE para o mmap para dizer a ele para configurar todas as tabelas da página antes de retornar, portanto, não deve haver falhas de página ao acessá-lo. Agora, isso tem o pequeno problema que também lê todo o arquivo na RAM, que vai explodir se você tentar mapear um arquivo de 100GB – mas vamos ignorar isso por enquanto 3 . O kernel precisa fazer o trabalho por página para configurar essas tabelas de páginas (aparece como hora do kernel). Isso acaba sendo um grande custo na abordagem mmap , e é proporcional ao tamanho do arquivo (ou seja, ele não fica relativamente menos importante à medida que o tamanho do arquivo aumenta) 4 .

Finalmente, mesmo no espaço de usuário acessando tal mapeamento não é exatamente livre (comparado a grandes buffers de memory não originários de um mmap baseado em arquivo) – mesmo quando as tabelas de páginas são configuradas, cada access a uma nova página vai , conceitualmente, incorrer em uma falta de TLB. Como mmap um arquivo significa usar o cache de páginas e suas páginas de 4K, você novamente incorre em 25 milhões de vezes para um arquivo de 100 GB.

Agora, o custo real dessas falhas de TLB depende muito dos seguintes aspectos do seu hardware: (a) quantos 4K TLB você tem e como o restante do cache de tradução funciona (b) como a pré-busca de hardware lida com com o TLB – por exemplo, a pré-busca pode acionar uma page walk? (c) quão rápido e paralelo é o hardware de page walking. Em processadores Intel x86 high-end modernos, o hardware de leitura de páginas é em geral muito forte: há pelo menos 2 walkers de páginas paralelas, uma page walk pode ocorrer simultaneamente com a execução continuada e a pré-busca de hardware pode acionar uma page walk. Portanto, o impacto de TLB em uma carga de leitura de stream contínuo é bastante baixo – e essa carga geralmente terá um desempenho similar, independentemente do tamanho da página. Outro hardware é geralmente muito pior, no entanto!

read () evita essas armadilhas

O syscall read() , que é o que geralmente serve de base para as chamadas do tipo “block read” oferecidas, por exemplo, em C, C ++ e outras linguagens, tem uma desvantagem principal que todos estão bem cientes:

  • Toda chamada read() de N bytes deve copiar N bytes do kernel para o espaço do usuário.

Por outro lado, evita a maioria dos custos acima – você não precisa mapear em 25 milhões de páginas 4K em espaço de uso. Você pode geralmente malloc um pequeno buffer buffer no espaço do usuário, e reutilizá-lo repetidamente para todas as suas chamadas de read . No lado do kernel, não há praticamente nenhum problema com páginas 4K ou erros de TLB, pois toda a RAM é geralmente mapeada linearmente usando algumas páginas muito grandes (por exemplo, 1 GB em x86), para que as páginas subjacentes no cache da página sejam cobertas muito eficientemente no espaço do kernel.

Então basicamente você tem a seguinte comparação para determinar qual é mais rápido para uma única leitura de um arquivo grande:

O trabalho extra por página implícito na abordagem mmap é mais caro do que o trabalho por byte de copiar o conteúdo do arquivo do kernel para o espaço do usuário implícito usando read() ?

Em muitos sistemas, eles são, na verdade, aproximadamente balanceados. Observe que cada um é dimensionado com atributos completamente diferentes do hardware e da pilha do sistema operacional.

Em particular, a abordagem mmap se torna relativamente mais rápida quando:

  • O sistema operacional tem um tratamento rápido de falhas leves e, especialmente, otimizações de volume menores, como falhas.
  • O sistema operacional tem uma boa implementação de MAP_POPULATE que pode processar eficientemente mapas grandes nos casos em que, por exemplo, as páginas subjacentes são contíguas na memory física.
  • O hardware tem um forte desempenho de tradução de páginas, como grandes TLBs, TLBs rápidos de segundo nível, page-walkers rápidos e paralelos, boa interação de pré-busca com tradução e assim por diante.

… enquanto a abordagem read() se torna relativamente mais rápida quando:

  • O syscall read() tem um bom desempenho de cópia. Por exemplo, bom desempenho copy_to_user no lado do kernel.
  • O kernel tem uma maneira eficiente (relativa à terra do usuário) de mapear a memory, por exemplo, usando apenas algumas páginas grandes com suporte de hardware.
  • O kernel tem syscalls rápidos e uma maneira de manter as inputs do TLB do kernel por meio de syscalls.

Os fatores de hardware acima variam muito em diferentes plataformas, mesmo dentro da mesma família (por exemplo, em x86 gerações e especialmente segmentos de mercado) e definitivamente em arquiteturas (por exemplo, ARM vs x86 vs PPC).

Os fatores OS continuam mudando também, com várias melhorias em ambos os lados causando um grande salto na velocidade relativa de uma abordagem ou outra. Uma lista recente inclui:

  • Adição de falha, descrita acima, que realmente ajuda o caso do mmap sem o MAP_POPULATE .
  • Adição de methods copy_to_user caminho copy_to_user em arch/x86/lib/copy_user_64.S , por exemplo, usando REP MOVQ quando estiver rápido, o que realmente ajuda o caso read() .

1 Este mais-ou-menos também inclui o caso onde o arquivo não foi totalmente armazenado em cache para começar, mas onde a leitura antecipada do SO é boa o suficiente para fazê-lo parecer (ou seja, a página geralmente é armazenada em cache no momento em que você eu quero isso). Essa é uma questão sutil, porque a maneira como a leitura antecipada funciona é muitas vezes bem diferente entre as chamadas mmap e de read , e pode ser ajustada de acordo com as chamadas “advise”, conforme descrito em 2 .

2 … porque se o arquivo não estiver em cache, seu comportamento será completamente dominado por preocupações de IO, incluindo o quão simpático é seu padrão de access ao hardware subjacente – e todo o seu esforço deve ser garantir que esse access seja tão simpático quanto possível, por exemplo, através do uso de madvise de madvise ou fadvise (e quaisquer mudanças de nível de aplicação que você possa fazer para melhorar os padrões de access).

3 Você poderia contornar isso, por exemplo, mmap sequencialmente em janelas de tamanho menor, digamos 100 MB.

4 Na verdade, a abordagem MAP_POPULATE é (pelo menos uma combinação hardware / sistema operacional) apenas um pouco mais rápida do que não usá-la, provavelmente porque o kernel está usando faulto – então o número real de pequenas falhas é reduzido por um fator de 16 ou mais.

Me desculpe, Ben Collins perdeu seu código fonte mmap windows deslizante. Isso seria bom ter no Boost.

Sim, mapear o arquivo é muito mais rápido. Você está essencialmente usando o subsistema de memory virtual do SO para associar memory a disco e vice-versa. Pense nisso desta maneira: se os desenvolvedores do kernel do sistema operacional pudessem torná-lo mais rápido, eles o fariam. Porque isso torna tudo mais rápido: bancos de dados, tempos de boot, tempos de carregamento de programas, etc.

A abordagem da janela deslizante não é tão difícil, pois várias páginas contíguas podem ser mapeadas de uma só vez. Portanto, o tamanho do registro não importa, desde que o maior de qualquer registro individual caiba na memory. O importante é administrar a contabilidade.

Se um registro não começar em um limite getpagesize (), seu mapeamento deve começar na página anterior. O comprimento da região mapeada se estende do primeiro byte do registro (arredondado para baixo, se necessário, até o múltiplo de getpagesize () mais próximo do último byte do registro (arredondado para o múltiplo de getpagesize () mais próximo). Quando terminar de processar um registro, você poderá desmapear () e passar para o próximo.

Isso tudo funciona muito bem no Windows também usando CreateFileMapping () e MapViewOfFile () (e GetSystemInfo () para obter SYSTEM_INFO.dwAllocationGranularity — não SYSTEM_INFO.dwPageSize).

O mmap deve ser mais rápido, mas não sei quanto. Depende muito do seu código. Se você usar o mmap, é melhor mapear o arquivo inteiro de uma só vez, o que tornará sua vida muito mais fácil. Um problema em potencial é que, se o arquivo for maior que 4 GB (ou, na prática, o limite é menor, geralmente 2 GB), você precisará de uma arquitetura de 64 bits. Portanto, se você estiver usando um ambiente 32, provavelmente não desejará usá-lo.

Dito isto, pode haver um caminho melhor para melhorar o desempenho. Você disse que o arquivo de input é varrido muitas vezes , se você consegue ler em uma passagem e depois terminar com isso, isso poderia ser muito mais rápido.

Eu concordo que a E / S do arquivo mmap’d será mais rápida, mas enquanto você faz o benchmarking do código, o exemplo contrário não deve ser um pouco otimizado?

Ben Collins escreveu:

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

Eu sugeriria também tentar:

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

E além disso, você também pode tentar fazer o tamanho do buffer o mesmo tamanho de uma página de memory virtual, no caso de 0x1000 não é o tamanho de uma página de memory virtual em sua máquina … IMHO mmap’d arquivo I / O ainda ganha, mas isso deve tornar as coisas mais próximas.

Talvez você deva pré-processar os arquivos, de modo que cada registro esteja em um arquivo separado (ou pelo menos que cada arquivo seja de tamanho mmap).

Você também poderia fazer todas as etapas de processamento de cada registro antes de passar para o próximo? Talvez isso evitasse alguma sobrecarga do IO?

Lembro-me de mapear um enorme arquivo contendo uma estrutura de tree na memory anos atrás. Fiquei impressionado com a velocidade em comparação com a desserialização normal, que envolve muito trabalho na memory, como alocação de nós de trees e configuração de pointers. Então, na verdade, eu estava comparando uma única chamada ao mmap (ou sua contraparte no Windows) contra muitas chamadas (MANY) para o operador new e chamadas de construtor. Para esse tipo de tarefa, o mmap é imbatível em comparação com a desserialização. É claro que se deve olhar para impulsionar o ponteiro relocável para isso.

Isso soa como um bom caso de uso para multi-threading … Eu acho que você poderia facilmente configurar um thread para ler dados enquanto o outro (s) processa. Essa pode ser uma maneira de aumentar drasticamente o desempenho percebido. Apenas um pensamento.

Na minha opinião, usar o mmap () “apenas” desonera o desenvolvedor de ter que escrever seu próprio código de cache. Em um simples caso de “leitura direta do arquivo uma vez”, isso não será difícil (embora, como aponta o mlbrock, você ainda salve a cópia da memory no espaço do processo), mas se você estiver indo e voltando no arquivo ou saltando bits e assim por diante, eu acredito que os desenvolvedores do kernel provavelmente fizeram um trabalho melhor implementando o cache do que eu posso …

Eu acho que a melhor coisa sobre o mmap é o potencial de leitura assíncrona com:

  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); 

O problema é que não consigo encontrar o MAP_FLAGS correto para dar uma dica de que essa memory deve ser sincronizada do arquivo o mais rápido possível. Espero que o MAP_POPULATE dê a dica certa para o mmap (isto é, ele não tentará carregar todo o conteúdo antes do retorno da chamada, mas fará isso em asynchronous. Com feed_data). Pelo menos, dá melhores resultados com este sinalizador, mesmo que o manual declare que não faz nada sem o MAP_PRIVATE desde 2.6.23.