mmap () vs. blocos de leitura

Estou trabalhando em um programa que processará arquivos com tamanho potencial de 100 GB ou mais. Os arquivos contêm conjuntos de registros de comprimento variável. Eu tenho uma primeira implementação em funcionamento e agora estou olhando para melhorar o desempenho, principalmente para fazer E / S com mais eficiência, pois o arquivo de entrada é verificado muitas vezes.

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

O mmap()código pode potencialmente ficar muito confuso, já que mmapos blocos precisam estar no limite do tamanho da página (pelo que entendi) e os registros podem potencialmente gostar nos limites da página. Com fstreams, posso apenas procurar o início de um registro e começar a ler novamente, pois não estamos limitados a blocos de leitura que se encontram nos limites do tamanho da página.

Como posso decidir entre essas duas opções sem antes escrever uma implementação completa? Alguma regra prática (por exemplo, mmap()é 2x mais rápida) ou testes simples?

Eu estava tentando encontrar a palavra final no desempenho do mmap / read no Linux e me deparei com uma boa postagem ( link ) na lista de discussão do kernel do Linux. É a partir de 2000, então houve muitas melhorias no IO e na memória virtual no kernel desde então, mas explica bem o motivo pelo qual mmapou readpode ser mais rápido ou mais lento.

• Uma chamada para mmaptem mais despesas gerais do que read(assim como epollmais despesas indiretas que poll, que têm mais despesas indiretas que read). Alterar os mapeamentos de memória 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 do disco; portanto, se você ler um arquivo, você o atingirá ou perderá, independentemente do método usado.

Contudo,

• Os mapas de memória geralmente são mais rápidos para acesso aleatório, especialmente se seus padrões de acesso forem escassos e imprevisíveis.
• Os mapas de memória permitem que você continue usando as 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 read, seu arquivo pode ter sido liberado do cache há muito tempo. Isso não se aplica se você usar um arquivo e descartá-lo imediatamente. (Se você tentar mlockpáginas apenas para mantê-las em cache, está tentando ser mais esperto que o cache do disco e esse tipo de bobagem raramente ajuda no desempenho do sistema).
• Ler um arquivo diretamente é muito simples e rápido.

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

• Alguns programadores de Java ficaram chocados ao descobrir que a E / S sem bloqueio é geralmente mais lenta que a E / S de bloqueio, o que fazia todo o sentido se você soubesse que a E / S sem bloqueio requer mais chamadas de sys.

• Alguns outros programadores de rede ficaram chocados ao saber que isso epollgeralmente é mais lento do que poll, o que faz todo o sentido se você souber que o gerenciamento epollexige mais chamadas de sistema.

Conclusão: use mapas de memória se você acessar dados aleatoriamente, mantê-los por muito tempo ou se souber que pode compartilhá-los com outros processos ( MAP_SHAREDnã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 qualquer um dos métodos tornar seu programa menos complexo, faça isso . Para muitos casos do mundo real, não há como garantir que um seja mais rápido sem testar seu aplicativo real e NÃO ser uma referência.

(Desculpe por necro'ing esta pergunta, mas eu estava procurando uma resposta e esta pergunta continuava aparecendo no topo dos resultados do Google.)

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

Eu tentei o fragmento 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 diferença mensurável. Veja meus comentários sobre a resposta dele.

Certamente, eu não recomendaria mapear separadamente cada registro por vez, a menos que seus "registros" sejam enormes - isso seria terrivelmente lento, exigindo duas chamadas do sistema para cada registro e possivelmente perdendo a página do cache da memória em disco .... .

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

1. Há acesso aleatório (não sequencial) dentro do arquivo, E
2. a coisa toda cabe confortavelmente na memória OU existe localidade de referência no 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 estiverem lendo / trabalhando no mesmo arquivo, o mmap () é fantástico porque todos os processos compartilham as mesmas páginas físicas.

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

O mmap é muito mais rápido. Você pode escrever uma referência simples para provar 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;
}

Claramente, estou deixando de fora os detalhes (como determinar quando você chega ao final do arquivo, caso seu arquivo não seja múltiplo page_size, por exemplo), mas realmente não deve ser muito mais complicado do que isso .

Se você puder, pode tentar dividir seus dados em vários arquivos que podem ser mmap () - editados por inteiro, em vez de parcialmente (muito mais simples).

Há alguns meses, eu tive uma implementação incompleta de uma classe de fluxo mmap () de janela deslizante para boost_iostreams, mas ninguém se importou e eu fiquei ocupado com outras coisas. Infelizmente, eu apaguei um arquivo de projetos inacabados antigos há algumas semanas, e essa foi uma das vítimas :-(

Atualização : devo acrescentar também que este benchmark seria 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 frequência, você poderia fazer std :: ifstream.read () e seria tão rápido quanto o mmap, porque o cache do arquivo já teria feito um mapeamento de memória para você, e é transparente.

Atualização final : Veja, pessoal: em várias combinações diferentes de plataformas de SO, bibliotecas e discos padrão e hierarquias de memória, não posso ter certeza de que a chamada do sistema mmap, vista como uma caixa preta, sempre será sempre sempre mais rápida que read. Essa não era exatamente minha intenção, mesmo que minhas palavras pudessem ser interpretadas dessa maneira. Por fim, meu argumento foi que a E / S mapeada na memória é geralmente mais rápida que a E / S baseada em bytes; isso ainda é verdade . Se você achar experimentalmente que não há diferença entre os dois, a única explicação que me parece razoável é que sua plataforma implementa o mapeamento de memória sob as cobertas de uma maneira que é vantajosa para o desempenho de chamadas pararead. A única maneira de ter certeza absoluta de que você está usando a E / S mapeada na memória de maneira portátil é usá-la mmap. Se você não se importa com a portabilidade e pode confiar nas características específicas de suas plataformas de destino, o uso readpode ser adequado sem sacrificar qualquer desempenho mensurável.

Edite para limpar a lista de respostas: @jbl:

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

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

Boost::Iostreamsjá possui uma fonte mapped_file, mas o problema era que ele fazia mmapping de arquivos inteiros, o que o limita a 2 ^ (tamanho das palavras). Em máquinas de 32 bits, 4 GB não são grandes o suficiente. Não é irracional esperar ter parte do trabalho feito para você e também fornece ganchos para filtros e correntes, então pensei que seria mais útil implementá-lo dessa maneira..pack arquivos no Git se tornem muito maiores do que isso, então eu precisava ler o arquivo em partes, sem recorrer à E / S regular de arquivos. Nos bastidores de Boost::Iostreams, eu implementei uma Fonte, que é mais ou menos outra visão da interação entre std::streambufe std::istream. Você também pode tentar uma abordagem semelhante, apenas herdando std::filebufum mapped_filebufe da mesma forma, herdando std::fstreamum a mapped_fstream. É a interação entre os dois que é difícil de acertar. Boost::Iostreams

Já existem muitas respostas boas que cobrem muitos dos pontos mais importantes, então adicionarei algumas questões que não vi abordadas diretamente acima. Ou seja, essa resposta não deve ser considerada 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 em cache ¹ como linha de base ^{de 2} , mmappode parecer bastante mágico :

1. mmap requer apenas 1 chamada do 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. mmappermite acessar o arquivo "como memória", inclusive processando-o com quaisquer truques avançados que você possa fazer com relação à memória, como auto-vetorização do compilador, intrínseca do SIMD , pré-busca, rotinas otimizadas de análise na memória, OpenMP, etc.

No caso de o arquivo já estar no cache, parece impossível: basta acessar diretamente o cache da página do kernel como memória e ele não pode ficar mais rápido que isso.

Bem, pode.

mmap não é realmente mágico porque ...

O mmap ainda funciona por página

Um custo oculto primário de mmapvs read(2)(que é realmente o syscall comparável no nível do SO para blocos de leitura ) é o demmap você precisará fazer "algum trabalho" para cada página de 4K no espaço do usuário, mesmo que possa estar oculta pelo mecanismo de falha de página.

Por exemplo, uma implementação típica que apenas mmaps o arquivo inteiro precisará executar uma falha de modo que 100 GB / 4K = 25 milhões de falhas para ler um arquivo de 100 GB. Agora, essas serão falhas menores , mas 25 bilhões de páginas ainda não serão super rápidas. O custo de uma falha menor provavelmente está nos 100s dos nanos, na melhor das hipóteses.

O mmap depende muito do desempenho do TLB

Agora, você pode passar MAP_POPULATEpara o mmapcomando para configurar todas as tabelas de páginas antes de retornar, para que não haja falhas na página ao acessá-lo. Agora, isso tem o pequeno problema de que ele também lê o arquivo inteiro na RAM, que explodirá se você tentar mapear um arquivo de 100 GB - mas vamos ignorá-lo por enquanto ³ . O kernel precisa executar um trabalho por página para configurar essas tabelas de páginas (aparece como hora do kernel). Isso acaba sendo um grande custo na mmapabordagem e é proporcional ao tamanho do arquivo (ou seja, não fica relativamente menos importante à medida que o tamanho do arquivo aumenta) ⁴ .

Por fim, mesmo no acesso ao espaço do usuário, esse mapeamento não é exatamente gratuito (comparado aos grandes buffers de memória que não são originários de um arquivo mmap) - mesmo depois que as tabelas de páginas são configuradas, cada acesso a uma nova página vai, conceitualmente, incorrem em uma falha no TLB. Como mmapincluir um arquivo significa usar o cache da página e suas páginas em 4K, você incorre novamente nesse custo 25 milhões de vezes para um arquivo de 100 GB.

Agora, o custo real dessas falhas de TLB depende muito de pelo menos os seguintes aspectos do seu hardware: (a) quantos TLB de 4K você possui e como o restante do cache de tradução funciona (b) quão bem a pré-busca de hardware lida com com o TLB - por exemplo, a pré-busca pode desencadear uma caminhada de página? (c) quão rápido e quão paralelo é o hardware de deslocamento da página. Nos modernos processadores Intel x86 de ponta, o hardware de deslocamento de página é geralmente muito forte: há pelo menos 2 caminhantes de páginas paralelas, um passeio de página pode ocorrer simultaneamente com a execução contínua e a pré-busca de hardware pode acionar um passeio de página. Portanto, o impacto TLB em um streaming carga de leitura de é bastante baixo - e essa carga geralmente terá desempenho semelhante, independentemente do tamanho da página. Outro hardware é geralmente muito pior, no entanto!

read () evita essas armadilhas

O read()syscall, que é o que geralmente subjaz às chamadas do tipo "leitura de bloco" oferecidas, por exemplo, em C, C ++ e outras linguagens, tem uma desvantagem principal da qual todos estão cientes:

• Cada read() chamada 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 no espaço do usuário. Você pode geralmentemalloc usar um único buffer pequeno no espaço do usuário e reutilizá-lo repetidamente para todos os seusread chamadas. No lado do kernel, quase não há problemas com páginas 4K ou falhas de TLB porque toda a RAM geralmente é mapeada linearmente usando algumas páginas muito grandes (por exemplo, páginas de 1 GB no x86), portanto as páginas subjacentes no cache da página são 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 mmapabordagem mais caro do que o trabalho por byte de copiar o conteúdo do arquivo do kernel para o espaço do usuário implicado pelo uso read()?

Em muitos sistemas, eles são realmente aproximadamente equilibrados. Observe que cada um é dimensionado com atributos completamente diferentes do hardware e da pilha do SO.

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

• O sistema operacional possui manipulação rápida de falhas menores e otimizações de volume especialmente de falhas menores, como falhas ao redor.
• O sistema operacional possui uma boa MAP_POPULATEimplementação que pode processar mapas grandes com eficiência nos casos em que, por exemplo, as páginas subjacentes são contíguas na memória física.
• O hardware tem um forte desempenho de tradução de páginas, como TLBs grandes, TLBs rápidos de segundo nível, caminhantes de páginas rápidos e paralelos, boa interação de pré-busca com tradução e assim por diante.

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

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

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

Os fatores do SO também mudam, com várias melhorias nos dois lados, causando um grande salto na velocidade relativa de uma abordagem ou de outra. Uma lista recente inclui:

• Adição de falha, descrita acima, o que realmente ajuda o mmapcaso sem MAP_POPULATE.
• Adição de copy_to_usermétodos de atalho arch/x86/lib/copy_user_64.S, por exemplo, usando REP MOVQquando é rápido, o que realmente ajuda o read()caso.

Atualização após Spectre e Meltdown

As atenuações para as vulnerabilidades Spectre e Meltdown aumentaram consideravelmente o custo de uma chamada do sistema. Nos sistemas que medi, o custo de uma chamada de sistema "não faça nada" (que é uma estimativa da sobrecarga pura da chamada de sistema, além de qualquer trabalho real realizado pela chamada) passou de cerca de 100 ns em uma configuração típica. sistema Linux moderno para cerca de 700 ns. Além disso, dependendo do seu sistema, a correção de isolamento da tabela de páginas especificamente para o Meltdown pode ter efeitos adicionais a jusante, além do custo direto das chamadas do sistema devido à necessidade de recarregar as entradas TLB.

Tudo isso é uma desvantagem relativa para read()métodos baseados em comparação mmapcom métodos baseados, pois os read()métodos devem fazer uma chamada de sistema para cada valor de "tamanho do buffer" dos dados. Você não pode aumentar arbitrariamente o tamanho do buffer para amortizar esse custo, pois o uso de buffers grandes geralmente apresenta desempenho pior, pois você excede o tamanho L1 e, portanto, sofre constantemente falhas de cache.

Por outro lado, com mmap, você pode mapear em uma grande região da memória MAP_POPULATEe acessá-la com eficiência, ao custo de apenas uma única chamada do sistema.

¹ Isso inclui mais ou menos o caso em que o arquivo não foi totalmente armazenado em cache para começar, mas onde a leitura antecipada do sistema operacional é boa o suficiente para fazer com que pareça assim (ou seja, a página geralmente é armazenada em cache na hora em que você eu quero isso). Esta é uma questão sutil, porque embora o caminho read-ahead obras muitas vezes é bastante diferente entre mmape readchamadas, e pode ser ainda mais modificada chamadas "aconselhar", conforme descrito no ² .

² ... porque se o arquivo não for armazenado em cache, seu comportamento será completamente dominado pelas preocupações de E / S, incluindo a simpatia do seu padrão de acesso ao hardware subjacente - e todo o seu esforço deve ser para garantir que esse acesso seja tão compreensivo quanto possível, por exemplo, através do uso de madviseou fadvisechamadas (e qualquer alteração no nível do aplicativo que você possa fazer para melhorar os padrões de acesso).

³ Você pode contornar isso, por exemplo, sequencialmente mmapem janelas de tamanho menor, digamos 100 MB.

⁴ De fato, verifica-se que a MAP_POPULATEabordagem é (pelo menos uma combinação de hardware / sistema operacional) apenas um pouco mais rápida do que não usá-lo, provavelmente porque o kernel está usando uma falha ao redor - de modo que o número real de falhas menores é reduzido por um fator de 16 ou então.

Sinto muito Ben Collins perdeu seu código-fonte do Windows mmap deslizante. Seria bom ter no Boost.

Sim, o mapeamento do arquivo é muito mais rápido. Você está basicamente usando o subsistema de memória virtual do SO para associar memória a disco e vice-versa. Pense da seguinte maneira: se os desenvolvedores do kernel do sistema operacional pudessem torná-lo mais rápido, eles o fariam. Porque isso faz com que tudo seja mais rápido: bancos de dados, tempos de inicialização, tempos de carregamento do programa etc.

A abordagem da janela deslizante realmente não é tão difícil, pois várias páginas contíguas podem ser mapeadas ao mesmo tempo. Portanto, o tamanho do registro não importa, desde que o maior de um único registro caiba na memória. O importante é gerenciar a contabilidade.

Se um registro não começar no limite de getpagesize (), seu mapeamento deverá 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, ao múltiplo mais próximo de getpagesize ()) até o último byte do registro (arredondado para o múltiplo mais próximo de getpagesize ()). Quando terminar de processar um registro, você pode desmapear () e passar para o próximo.

Isso tudo funciona 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, para facilitar sua vida. Um problema em potencial é que, se seu arquivo for maior que 4 GB (ou, na prática, o limite for menor, geralmente 2 GB), será necessária uma arquitetura de 64 bits. Portanto, se você estiver usando um ambiente 32, provavelmente não deseja usá-lo.

Dito isto, pode haver um caminho melhor para melhorar o desempenho. Você disse que o arquivo de entrada é digitalizado muitas vezes , se você puder lê-lo em uma passagem e terminar com ele, isso pode ser muito mais rápido.

Talvez você deva pré-processar os arquivos, para que cada registro esteja em um arquivo separado (ou pelo menos que cada arquivo tenha um tamanho compatível com mmap).

Além disso, você poderia executar todas as etapas de processamento de cada registro antes de passar para o próximo? Talvez isso evitasse parte da sobrecarga de IO?

Concordo que a E / S do arquivo mmap'd será mais rápida, mas, enquanto você avalia o 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
}

Além disso, você também pode tentar tornar o tamanho do buffer do mesmo tamanho que uma página de memória virtual, caso 0x1000 não seja o tamanho de uma página de memória virtual na sua máquina ... IMO de arquivo mmap'd IMHO ainda ganha, mas isso deve tornar as coisas mais próximas.

Na minha opinião, o uso de mmap () "apenas" impede o desenvolvedor de escrever seu próprio código de cache. Em um caso simples de "ler o arquivo rapidamente uma vez", isso não será difícil (embora, como o mlbrock ressalte, você ainda salve a cópia da memória no espaço do processo), mas se você estiver indo e voltando no arquivo ou pulando bits e assim por diante, acredito que os desenvolvedores do kernel provavelmente tenham feito um trabalho melhor implementando o cache do que eu ...

Lembro-me de mapear um arquivo enorme contendo uma estrutura de árvore na memória anos atrás. Fiquei impressionado com a velocidade em comparação com a desserialização normal, que envolve muito trabalho na memória, como alocar nós de árvore e definir ponteiros. Então, na verdade, eu estava comparando uma única chamada ao mmap (ou sua contrapartida no Windows) contra muitas (MUITAS) chamadas a novas e construtoras do operador. Para esse tipo de tarefa, o mmap é imbatível comparado à desserialização. Obviamente, deve-se procurar impulsionar o ponteiro realocá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 os outros o processam. Essa pode ser uma maneira de aumentar drasticamente o desempenho percebido. Apenas um pensamento.

Eu acho que a melhor coisa sobre o mmap é o potencial para 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 memória deve ser sincronizada a partir do arquivo o mais rápido possível. Espero que MAP_POPULATE dê a dica correta para o mmap (ou seja, ele não tentará carregar todo o conteúdo antes do retorno da chamada, mas fará isso de forma assíncrona. Com feed_data). Pelo menos, obtém melhores resultados com esse sinalizador, mesmo que o manual afirme que ele não faz nada sem MAP_PRIVATE desde 2.6.23.