O que todo programador deve saber sobre memória?

164

Gostaria de saber quanto do que cada programador deve saber sobre memória de Ulrich Drepper de 2007 ainda é válido. Também não consegui encontrar uma versão mais recente que 1.0 ou uma errata.

Framester
fonte
1
alguém sabe se eu posso baixar este artigo no formato mobi em algum lugar para que eu possa lê-lo facilmente no Kindle? "pdf" é muito difícil de ler devido a problemas com zoom / formatação
javapowered
1
Não é mobi, mas o LWN publicou o jornal como um conjunto de artigos que são mais fáceis de ler em um telefone / tablet. O primeiro é em lwn.net/Articles/250967
Nathan

Respostas:

111

Tanto quanto me lembro, o conteúdo de Drepper descreve conceitos fundamentais sobre memória: como o cache da CPU funciona, o que são memória física e virtual e como o kernel do Linux lida com esse zoológico. Provavelmente, existem referências desatualizadas da API em alguns exemplos, mas isso não importa; isso não afetará a relevância dos conceitos fundamentais.

Portanto, qualquer livro ou artigo que descreva algo fundamental não pode ser chamado de desatualizado. Definitivamente vale a pena ler "o que todo programador deve saber sobre memória", mas, bem, eu não acho que seja para "todo programador". É mais adequado para o pessoal do sistema / incorporado / kernel.

Dan Kruchinin
fonte
3
Sim, eu realmente não vejo por que um programador precisa saber como a SRAM e a DRAM funcionam no nível analógico - isso não ajudará muito ao escrever programas. E as pessoas que realmente precisam desse conhecimento passam melhor o tempo lendo os manuais sobre detalhes sobre os horários reais etc. Mas para as pessoas interessadas no material de baixo nível do HW? Talvez não seja útil, mas pelo menos divertido.
Voo
47
Atualmente desempenho == desempenho da memória, portanto, entender a memória é a coisa mais importante em qualquer aplicativo de alto desempenho. Isso torna o documento essencial para qualquer pessoa envolvida em: desenvolvimento de jogos, computação científica, finanças, bancos de dados, compiladores, processamento de grandes conjuntos de dados, visualização, qualquer coisa que precise lidar com muitas solicitações ... Então, sim, se você estiver trabalhando em um aplicativo que fica ocioso na maioria das vezes, como um editor de texto, o artigo é completamente desinteressante até que você precise fazer algo rápido, como encontrar uma palavra, contar as palavras, verificar a ortografia ... oh, espere ... deixa pra lá.
precisa saber é o seguinte
144

O guia em formato PDF está em https://www.akkadia.org/drepper/cpumemory.pdf .

Geralmente, ainda é excelente e altamente recomendado (por mim, e acho que por outros especialistas em ajuste de desempenho). Seria legal se Ulrich (ou qualquer outra pessoa) escrevesse uma atualização de 2017, mas isso daria muito trabalho (por exemplo, reexecutar os benchmarks). Consulte também outros links de otimização de desempenho x86 e de otimização SSE / asm (e C / C ++) no diretório tag wiki . (O artigo de Ulrich não é específico para x86, mas a maioria (todos) de seus benchmarks estão em hardware x86.)

Os detalhes de hardware de baixo nível sobre como funcionam a DRAM e os caches ainda se aplicam . DDR4 usa os mesmos comandos descritos para DDR1 / DDR2 (leitura / gravação burst). As melhorias no DDR3 / 4 não são mudanças fundamentais. AFAIK, todo o material independente de arco ainda se aplica geralmente, por exemplo, ao AArch64 / ARM32.

Consulte também a seção Plataformas associadas à latência desta resposta para obter detalhes importantes sobre o efeito da latência de memória / L3 na largura de banda de thread único: bandwidth <= max_concurrency / latencye este é realmente o principal gargalo da largura de banda de thread único em uma CPU moderna de vários núcleos como um Xeon . Mas um desktop Skylake de quatro núcleos pode chegar perto de maximizar a largura de banda DRAM com um único thread. Esse link tem algumas informações muito boas sobre lojas NT versus lojas normais no x86. Por que Skylake é muito melhor que Broadwell-E para taxa de transferência de memória de thread único? é um resumo.

Portanto, a sugestão de Ulrich no 6.5.8 Utilizando toda a largura de banda sobre o uso de memória remota em outros nós da NUMA e na sua própria é contraproducente em hardware moderno, onde os controladores de memória têm mais largura de banda do que um único núcleo pode usar. Bem, possivelmente você pode imaginar uma situação em que há um benefício líquido em executar vários threads com fome de memória no mesmo nó NUMA para comunicação entre threads de baixa latência, mas fazer com que eles usem memória remota para coisas com grande largura de banda e não sensíveis à latência. Mas isso é bastante obscuro, normalmente apenas divida os threads entre os nós NUMA e faça com que eles usem a memória local. A largura de banda por núcleo é sensível à latência devido aos limites de simultaneidade máxima (veja abaixo), mas todos os núcleos em um soquete geralmente podem mais do que saturar os controladores de memória nesse soquete.


(geralmente) Não use pré-busca de software

Uma coisa importante que mudou foi que a pré-busca de hardware é muito melhor do que no Pentium 4 e pode reconhecer padrões de acesso estridificado até um passo bastante grande e vários fluxos de uma só vez (por exemplo, um avanço / retrocesso por página de 4k). O manual de otimização da Intel descreve alguns detalhes dos pré-buscadores de HW em vários níveis de cache para sua microarquitetura da família Sandybridge. Ivybridge e mais tarde têm pré-busca de hardware na próxima página, em vez de aguardar uma falha de cache na nova página para iniciar rapidamente. Presumo que a AMD tenha algumas coisas semelhantes em seu manual de otimização. Cuidado que o manual da Intel também está cheio de conselhos antigos, alguns dos quais só são bons para o P4. As seções específicas de Sandybridge são obviamente precisas para SnB, mas, por exemplo,a laminação de micro-fusíveis mudou no HSW e o manual não menciona .

O conselho usual hoje em dia é remover todas as pré-buscas SW do código antigo e considere colocá-lo novamente novamente se a criação de perfil mostrar falhas no cache (e você não estiver saturando a largura de banda da memória). A pré-busca de ambos os lados da próxima etapa de uma pesquisa binária ainda pode ajudar. por exemplo, depois de decidir qual elemento examinar a seguir, pré-busque os elementos 1/4 e 3/4 para que eles possam carregar em paralelo com o carregamento / verificação do meio.

A sugestão de usar um thread de pré-busca separado (6.3.4) é totalmente obsoleta , eu acho, e só foi boa no Pentium 4. O P4 tinha hyperthreading (2 núcleos lógicos compartilhando um núcleo físico), mas não havia cache de rastreamento suficiente (e / ou recursos de execução fora de ordem) para obter rendimento executando dois threads de computação completos no mesmo núcleo. Porém, as CPUs modernas (família Sandybridge e Ryzen) são muito mais robustas e devem executar um encadeamento real ou não usar hyperthreading (deixar o outro núcleo lógico ocioso para que o encadeamento solo tenha todos os recursos em vez de particionar o ROB).

A pré-busca do software sempre foi "quebradiça" : os números de sintonia mágica certos para obter uma aceleração dependem dos detalhes do hardware e, talvez, da carga do sistema. Muito cedo e é despejado antes do carregamento da demanda. Tarde demais e isso não ajuda. Este artigo do blog mostra códigos + gráficos para uma experiência interessante no uso da pré-busca SW no Haswell para pré-buscar a parte não sequencial de um problema. Consulte também Como usar corretamente as instruções de pré-busca? . A pré-busca do NT é interessante, mas ainda mais frágil porque um despejo precoce de L1 significa que você precisa percorrer todo o caminho para L3 ou DRAM, não apenas para L2. Se você precisar de toda a última gota de desempenho e puder ajustar para uma máquina específica, vale a pena procurar o acesso sequencial de pré-busca do SW, masainda pode ser uma lentidão se você tiver trabalho suficiente na ULA para fazer enquanto estiver perto do gargalo na memória.


O tamanho da linha de cache ainda é de 64 bytes. (A largura de banda de leitura / gravação L1D é muito alta, e as CPUs modernas podem realizar 2 cargas vetoriais por relógio + 1 armazenamento vetorial se tudo ocorrer no L1D. Consulte Como o cache pode ser tão rápido?. ) Com o AVX512, tamanho da linha = largura do vetor, para que você possa carregar / armazenar uma linha de cache inteira em uma instrução. Portanto, todo carregamento / armazenamento desalinhado cruza um limite da linha de cache, em vez de outro para o 256b AVX1 / AVX2, que geralmente não diminui a velocidade do loop sobre uma matriz que não estava no L1D.

Instruções de carregamento desalinhadas têm zero de penalidade se o endereço estiver alinhado em tempo de execução, mas os compiladores (especialmente o gcc) criam um código melhor ao se autovectorizar, se souberem de alguma garantia de alinhamento. Na verdade, operações desalinhadas geralmente são rápidas, mas as divisões de páginas ainda prejudicam (muito menos no Skylake; porém, apenas ~ 11 ciclos de latência extra vs. 100, mas ainda uma penalidade na taxa de transferência).


Como Ulrich previu, todos os sistemas com vários soquetes são NUMA atualmente: controladores de memória integrados são padrão, ou seja, não há Northbridge externo. Mas SMP não significa mais multi-soquete, porque as CPUs com vários núcleos são generalizadas. As CPUs da Intel, de Nehalem a Skylake, usaram um cache L3 amplo e inclusivo como pano de fundo para coerência entre os núcleos. Os processadores AMD são diferentes, mas não sou tão claro quanto aos detalhes.

O Skylake-X (AVX512) não tem mais um L3 inclusivo, mas acho que ainda existe um diretório de tags que permite verificar o que é armazenado em cache em qualquer lugar do chip (e, se for o caso, onde) sem realmente transmitir bisbilhoteiros para todos os núcleos. Infelizmente, a SKX usa uma malha em vez de um barramento em anel , com latência geralmente ainda pior que os Xeons com muitos núcleos anteriores.

Basicamente, todos os conselhos sobre como otimizar o posicionamento da memória ainda se aplicam, apenas os detalhes exatamente do que acontece quando você não pode evitar falhas no cache ou a contenção varia.


6.4.2 Operações atômicas : o benchmark que mostra um loop de repetição de CAS como 4x pior que o arbitrado por hardware lock addprovavelmente ainda reflete um caso de contenção máxima . Mas em programas reais multithread, a sincronização é mantida no mínimo (porque é cara), portanto a contenção é baixa e um loop de repetição de CAS geralmente é bem-sucedido sem ter que tentar novamente.

O C ++ 11 std::atomic fetch_addserá compilado para um lock add(ou lock xaddse o valor de retorno for usado), mas um algoritmo usando o CAS para fazer algo que não pode ser feito com uma lockinstrução ed geralmente não é um desastre. Use C ++ 11std::atomic ou C11 em stdatomicvez dos __syncincorporados herdados do gcc ou dos __atomicincorporados mais novos , a menos que você queira misturar acesso atômico e não atômico ao mesmo local ...

8.1 DWCAS ( cmpxchg16b) : Você pode convencer o gcc a emiti-lo, mas se você deseja cargas eficientes de apenas metade do objeto, precisará de unionhacks feios : Como implementar o contador ABA com o c ++ 11 CAS? . (Não confunda DWCAS com DCAS de 2 locais de memória separados . Emulação atômica sem bloqueio de DCAS não é possível com DWCAS, mas a memória transacional (como x86 TSX) torna isso possível.)

8.2.4 memória transacional : após algumas partidas falsas (liberadas e desativadas por uma atualização de microcódigo devido a um bug raramente acionado), a Intel possui memória transacional em funcionamento no modelo Broadwell e em todas as CPUs Skylake. O design ainda é o que David Kanter descreveu para Haswell . Existe uma maneira de elimina-trava para usá-lo para acelerar o código que usa (e pode retornar a) um bloqueio regular (especialmente com um único bloqueio para todos os elementos de um contêiner, para que vários encadeamentos na mesma seção crítica frequentemente não colidam ) ou escrever um código que saiba diretamente sobre transações.


7.5 Páginas enormes : páginas enormes anônimas transparentes funcionam bem no Linux sem ter que usar manualmente o hugetlbfs. Faça alocações> = 2MiB com alinhamento de 2MiB (por exemplo posix_memalign, ou umaligned_alloc que não imponha o estúpido requisito ISO C ++ 17 de falhar quando size % alignment != 0).

Uma alocação anônima alinhada a 2MiB usará páginas enormes por padrão. Algumas cargas de trabalho (por exemplo, que continuam usando grandes alocações por um tempo depois de criá-las) podem se beneficiar
echo always >/sys/kernel/mm/transparent_hugepage/defragcom o kernel para desfragmentar a memória física sempre que necessário, em vez de retornar às páginas de 4k. (Veja os documentos do kernel ). Como alternativa, use madvise(MADV_HUGEPAGE)depois de fazer grandes alocações (de preferência ainda com alinhamento de 2MiB).


Apêndice B: Oprofile : O Linux perfsubstituiu principalmente oprofile. Para eventos detalhados específicos para determinadas microarquiteturas, use o ocperf.pywrapper . por exemplo

ocperf.py stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,\
branches,branch-misses,instructions,uops_issued.any,\
uops_executed.thread,idq_uops_not_delivered.core -r2 ./a.out

Para alguns exemplos de como usá-lo, consulte O MOV do x86 pode realmente ser "gratuito"? Por que não consigo reproduzir isso? .

Peter Cordes
fonte
3
Resposta muito instrutiva e sugestões! Isso claramente merece mais votos!
CLAF
@ Peter Cordes Há outros guias / documentos que você recomendaria ler? Eu não sou um programador de alto desempenho, mas gostaria de aprender mais sobre isso e, espero, aprender práticas que eu possa incorporar à minha programação diária.
user3927312
4
@ user3927312: agner.org/optimize é um dos melhores e mais coerentes guias para itens de baixo nível para o x86 especificamente, mas algumas das idéias gerais se aplicam a outros ISAs. Além de guias ASM, o Agner possui um PDF C ++ otimizado. Para outros links de desempenho / arquitetura da CPU, consulte stackoverflow.com/tags/x86/info . Também escrevi sobre otimização de C ++, ajudando o compilador a criar melhor asm para loops críticos, quando vale a pena dar uma olhada na saída asm do compilador: código C ++ para testar a conjectura de Collatz mais rapidamente do que asm escrito à mão?
Peter Cordes
74

Pela minha rápida olhada, parece bastante preciso. A única coisa a se notar é a parte da diferença entre controladores de memória "integrados" e "externos". Desde o lançamento dos processadores Intel da linha i7, todos estão integrados, e a AMD usa controladores de memória integrados desde que os chips AMD64 foram lançados.

Desde que este artigo foi escrito, não mudou muito, as velocidades aumentaram, os controladores de memória ficaram muito mais inteligentes (o i7 atrasará as gravações na RAM até que pareça cometer as alterações), mas não mudou muito . Pelo menos não da maneira que um desenvolvedor de software se importaria.

Timothy Baldridge
fonte
5
Eu gostaria de aceitar vocês dois. Mas eu votei em seu post.
Framester
5
Provavelmente a mudança mais importante que é relevante para os desenvolvedores de SW é que os threads de pré-busca são uma má ideia. As CPUs são poderosas o suficiente para executar 2 threads completos com hyperthreading e têm uma pré-busca de HW muito melhor. A pré-busca de SW em geral é muito menos importante, especialmente para acesso seqüencial. Veja minha resposta.
Peter Cordes