Como alguém escreve código que melhor utiliza o cache da CPU para melhorar o desempenho?

Isso pode parecer uma pergunta subjetiva, mas o que estou procurando são instâncias específicas, que você pode ter encontrado relacionadas a isso.

1. Como tornar o código eficaz e compatível com o cache (mais acessos ao cache, o mínimo possível de erros no cache)? De ambas as perspectivas, cache de dados e cache de programa (cache de instruções), ou seja, quais itens do código de alguém, relacionados a estruturas de dados e construções de código, devem ser tomados em consideração para torná-lo eficaz em cache.

2. Existe alguma estrutura de dados específica que se deve usar / evitar ou existe uma maneira específica de acessar os membros dessa estrutura, etc ... para tornar o cache de código eficaz.

3. Existe alguma construção de programa (if, para, switch, break, goto, ...), fluxo de código (para dentro de um if, se dentro de um for, etc ...) deve-se seguir / evitar nesse assunto?

Estou ansioso para ouvir experiências individuais relacionadas a tornar o código eficiente do cache em geral. Pode ser qualquer linguagem de programação (C, C ++, Assembly, ...), qualquer destino de hardware (ARM, Intel, PowerPC, ...), qualquer sistema operacional (Windows, Linux, Symbian, ...), etc. .

A variedade ajudará a melhor entendê-la profundamente.

O cache existe para reduzir o número de vezes que a CPU seria interrompida, aguardando que uma solicitação de memória fosse atendida (evitando a latência da memória ) e, como segundo efeito, possivelmente para reduzir a quantidade geral de dados que precisam ser transferidos (preservando largura de banda da memória ).

Técnicas para evitar sofrer com a latência de busca de memória geralmente são a primeira coisa a considerar e, às vezes, ajudam bastante. A largura de banda de memória limitada também é um fator limitante, principalmente para aplicativos multicores e multithread, nos quais muitos threads desejam usar o barramento de memória. Um conjunto diferente de técnicas ajuda a resolver o último problema.

Melhorar a localidade espacial significa que você garante que cada linha de cache seja usada completamente depois de mapeada para um cache. Quando analisamos vários benchmarks padrão, vimos que uma fração grande e surpreendente desses falha em usar 100% das linhas de cache buscadas antes que as linhas de cache sejam despejadas.

Melhorar a utilização da linha de cache ajuda em três aspectos:

• Ele tende a ajustar dados mais úteis no cache, aumentando essencialmente o tamanho efetivo do cache.
• Ele tende a ajustar dados mais úteis na mesma linha de cache, aumentando a probabilidade de que os dados solicitados possam ser encontrados no cache.
• Reduz os requisitos de largura de banda da memória, pois haverá menos buscas.

Técnicas comuns são:

• Use tipos de dados menores
• Organize seus dados para evitar falhas de alinhamento (classificar os membros da estrutura diminuindo o tamanho é uma maneira)
• Cuidado com o alocador de memória dinâmica padrão, que pode apresentar falhas e espalhar seus dados na memória à medida que aquece.
• Verifique se todos os dados adjacentes são realmente usados ​​nos hot loops. Caso contrário, considere dividir estruturas de dados em componentes quentes e frios, para que os loops quentes usem dados quentes.
• evitar algoritmos e estruturas de dados que exibam padrões de acesso irregulares e favorecer estruturas de dados lineares.

Também devemos observar que existem outras maneiras de ocultar a latência da memória além do uso de caches.

CPU moderna: s costumam ter um ou mais pré-buscadores de hardware . Eles treinam as falhas em um cache e tentam detectar regularidades. Por exemplo, após algumas falhas nas linhas de cache subsequentes, o pré-buscador hw começará a buscar as linhas de cache no cache, antecipando as necessidades do aplicativo. Se você tem um padrão de acesso regular, o pré-buscador de hardware geralmente está fazendo um trabalho muito bom. E se o seu programa não exibir padrões de acesso regulares, você poderá melhorar as coisas adicionando instruções de pré-busca .

Reagrupando as instruções de forma que as que sempre faltam no cache ocorram próximas umas das outras, às vezes a CPU pode sobrepor essas buscas, de modo que o aplicativo sustente apenas uma ocorrência de latência ( paralelismo no nível de memória ).

Para reduzir a pressão geral do barramento de memória, você deve começar a abordar o que é chamado localidade temporal . Isso significa que você precisa reutilizar os dados enquanto eles ainda não foram removidos do cache.

A mesclagem de loops que tocam os mesmos dados ( fusão de loop ) e o emprego de técnicas de reescrita conhecidas como ladrilhos ou bloqueios se esforçam para evitar essas buscas de memória extras.

Embora existam algumas regras práticas para este exercício de reescrita, você normalmente deve considerar cuidadosamente as dependências de dados transportados por loop, para garantir que você não afete a semântica do programa.

Essas são as coisas que realmente valem a pena no mundo multicore, onde você normalmente não verá muitas melhorias na taxa de transferência após adicionar o segundo segmento.

Não acredito que não há mais respostas para isso. Enfim, um exemplo clássico é iterar uma matriz multidimensional "de dentro para fora":

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

A razão pela qual esse cache é ineficiente é porque as CPUs modernas carregam a linha de cache com endereços de memória "próximos" da memória principal quando você acessa um único endereço de memória. Estamos iterando pelas linhas "j" (externas) da matriz no loop interno, portanto, para cada viagem pelo loop interno, a linha de cache fará com que seja liberada e carregada com uma linha de endereços próximos ao [ j] [i] entrada. Se isso for alterado para o equivalente:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Vai correr muito mais rápido.

As regras básicas são realmente bastante simples. O problema é como eles se aplicam ao seu código.

O cache funciona em dois princípios: localidade temporal e local espacial. A primeira é a ideia de que, se você usou recentemente um determinado pedaço de dados, provavelmente precisará deles novamente em breve. O último significa que, se você usou recentemente os dados no endereço X, provavelmente precisará em breve do endereço X + 1.

O cache tenta acomodar isso lembrando os pedaços de dados usados ​​mais recentemente. Ele opera com linhas de cache, geralmente com tamanho de 128 bytes, aproximadamente, portanto, mesmo que você precise apenas de um byte, toda a linha de cache que a contém é puxada para o cache. Portanto, se você precisar do seguinte byte depois, ele já estará no cache.

E isso significa que você sempre desejará que seu próprio código explore essas duas formas de localidade o máximo possível. Não pule toda a memória. Faça o máximo de trabalho possível em uma pequena área e, em seguida, passe para a próxima, e faça o máximo de trabalho possível.

Um exemplo simples é o percurso da matriz 2D que a resposta de 1800 mostrou. Se você percorrer uma linha de cada vez, estará lendo a memória sequencialmente. Se você fizer isso em colunas, lerá uma entrada e depois pulará para um local completamente diferente (o início da próxima linha), lerá uma entrada e pulará novamente. E quando você finalmente voltar à primeira linha, ela não estará mais no cache.

O mesmo se aplica ao código. Saltos ou ramificações significam um uso menos eficiente do cache (porque você não está lendo as instruções sequencialmente, mas pulando para um endereço diferente). É claro que pequenas instruções if provavelmente não mudarão nada (você está pulando apenas alguns bytes, portanto ainda vai acabar dentro da região em cache), mas as chamadas de função normalmente implicam que você está pulando para uma posição completamente diferente. endereço que não pode ser armazenado em cache. A menos que tenha sido chamado recentemente.

O uso do cache de instruções geralmente é bem menos problemático. Em geral, você precisa se preocupar com o cache de dados.

Em uma estrutura ou classe, todos os membros são dispostos de forma contígua, o que é bom. Em uma matriz, todas as entradas também são dispostas de forma contígua. Nas listas vinculadas, cada nó é alocado em um local completamente diferente, o que é ruim. Os ponteiros em geral tendem a apontar para endereços não relacionados, o que provavelmente resultará em uma falta de cache se você o derereçar.

E se você quiser explorar vários núcleos, pode ser realmente interessante, como normalmente, apenas uma CPU pode ter um endereço específico no cache L1 de cada vez. Portanto, se os dois núcleos acessarem constantemente o mesmo endereço, isso resultará em constantes falhas de cache, pois eles estão brigando pelo endereço.

Eu recomendo a leitura do artigo de 9 partes O que todo programador deve saber sobre memória por Ulrich Drepper se você estiver interessado em como a memória e o software interagem. Também está disponível como um PDF de 104 páginas .

Seções especialmente relevantes para esta questão podem ser a Parte 2 (caches da CPU) e a Parte 5 (O que os programadores podem fazer - otimização do cache).

Além dos padrões de acesso a dados, um fator importante no código compatível com o cache é o tamanho dos dados . Menos dados significa que mais deles se encaixa no cache.

Isso é principalmente um fator com estruturas de dados alinhadas à memória. A sabedoria "convencional" diz que as estruturas de dados devem ser alinhadas nos limites das palavras, porque a CPU pode acessar apenas palavras inteiras e, se uma palavra contiver mais de um valor, você precisará fazer um trabalho extra (ler, modificar, escrever em vez de uma gravação simples) . Mas caches podem invalidar completamente esse argumento.

Da mesma forma, uma matriz booleana Java usa um byte inteiro para cada valor, a fim de permitir a operação diretamente em valores individuais. Você pode reduzir o tamanho dos dados em um fator 8 se usar bits reais, mas o acesso a valores individuais se tornará muito mais complexo, exigindo operações de troca de bits e máscara (a BitSetclasse faz isso por você). No entanto, devido aos efeitos do cache, isso ainda pode ser consideravelmente mais rápido do que usar um booleano [] quando a matriz é grande. O IIRC I alcançou uma aceleração por um fator de 2 ou 3 dessa maneira.

A estrutura de dados mais eficaz para um cache é uma matriz. Os caches funcionam melhor, se sua estrutura de dados é organizada em seqüência, à medida que as CPUs lêem linhas inteiras de cache (geralmente 32 bytes ou mais) de uma só vez na memória principal.

Qualquer algoritmo que acessa a memória aleatoriamente elimina os caches porque sempre precisa de novas linhas de cache para acomodar a memória acessada aleatoriamente. Por outro lado, um algoritmo, que é executado seqüencialmente através de uma matriz, é melhor porque:

1. Isso dá à CPU a chance de ler antecipadamente, por exemplo, especulativamente colocar mais memória no cache, que será acessado mais tarde. Essa leitura antecipada oferece um enorme aumento de desempenho.

2. A execução de um loop restrito em uma matriz grande também permite que a CPU armazene em cache o código em execução no loop e, na maioria dos casos, permite executar um algoritmo inteiramente a partir da memória cache, sem ter que bloquear o acesso à memória externa.

Um exemplo que vi usado em um mecanismo de jogo foi mover dados para fora dos objetos e para suas próprias matrizes. Um objeto de jogo que estava sujeito à física também pode ter muitos outros dados anexados. Porém, durante o ciclo de atualização da física, todo o motor se importava com dados sobre posição, velocidade, massa, caixa delimitadora, etc. Portanto, tudo isso era colocado em suas próprias matrizes e otimizado o máximo possível para o SSE.

Portanto, durante o ciclo da física, os dados da física foram processados ​​em ordem de array usando a matemática vetorial. Os objetos do jogo usavam seu ID de objeto como o índice para as várias matrizes. Não era um ponteiro porque os ponteiros poderiam ser invalidados se as matrizes precisassem ser realocadas.

De muitas maneiras, isso violou os padrões de design orientados a objetos, mas tornou o código muito mais rápido, colocando dados próximos que precisavam ser operados nos mesmos loops.

Este exemplo provavelmente está desatualizado, porque espero que a maioria dos jogos modernos use um mecanismo de física pré-construído como o Havok.

Apenas um post foi abordado, mas um grande problema surge ao compartilhar dados entre processos. Você deseja evitar vários processos tentando modificar a mesma linha de cache simultaneamente. Algo a se observar aqui é o compartilhamento "falso", em que duas estruturas de dados adjacentes compartilham uma linha de cache e modificações em uma invalidam a linha de cache da outra. Isso pode fazer com que as linhas de cache se movam desnecessariamente entre os caches do processador que compartilham os dados em um sistema multiprocessador. Uma maneira de evitá-lo é alinhar e preencher estruturas de dados para colocá-las em linhas diferentes.

Uma observação para o "exemplo clássico" do usuário 1800 INFORMAÇÃO (muito tempo para um comentário)

Queria verificar as diferenças de horário para duas ordens de iteração ("outter" e "inner"), então fiz um experimento simples com uma grande matriz 2D:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

e o segundo caso com o for loops trocados.

A versão mais lenta ("x first") foi de 0,88s e a mais rápida, de 0,06s. Esse é o poder do cache :)

Eu usei gcc -O2e ainda os loops não foram otimizados. O comentário de Ricardo de que "a maioria dos compiladores modernos pode descobrir isso sozinho" não se sustenta

Eu posso responder (2) dizendo que, no mundo C ++, as listas vinculadas podem facilmente matar o cache da CPU. Matrizes são uma solução melhor sempre que possível. Nenhuma experiência sobre se o mesmo se aplica a outros idiomas, mas é fácil imaginar que os mesmos problemas possam surgir.

O cache é organizado em "linhas de cache" e a memória (real) é lida e gravada em pedaços desse tamanho.

As estruturas de dados contidas em uma única linha de cache são, portanto, mais eficientes.

Da mesma forma, algoritmos que acessam blocos de memória contíguos serão mais eficientes do que algoritmos que pulam na memória em uma ordem aleatória.

Infelizmente, o tamanho da linha de cache varia drasticamente entre os processadores, portanto não há como garantir que uma estrutura de dados ideal para um processador seja eficiente para qualquer outro.

Perguntar como criar um código, armazenar em cache o cache eficaz e a maioria das outras perguntas é geralmente como otimizar um programa, porque o cache tem um impacto tão grande nos desempenhos que qualquer programa otimizado é aquele em cache. cache eficaz.

Sugiro ler sobre otimização, existem algumas boas respostas neste site. Em termos de livros, eu recomendo em Sistemas de Computador: A Perspectiva de um Programador, com algum texto fino sobre o uso adequado do cache.

(btw - por pior que seja uma falta de cache, é pior - se um programa estiver paginando a partir do disco rígido ...)

Existem muitas respostas sobre conselhos gerais, como seleção da estrutura de dados, padrão de acesso, etc. Aqui eu gostaria de adicionar outro padrão de design de código chamado pipeline de software que faz uso do gerenciamento de cache ativo.

A idéia é pedir emprestado de outras técnicas de pipelining, por exemplo, pipelining de instruções da CPU.

Esse tipo de padrão se aplica melhor aos procedimentos que

1. pode ser dividido em várias sub-etapas razoáveis, S [1], S [2], S [3], ... cujo tempo de execução é aproximadamente comparável ao tempo de acesso à RAM (~ 60-70ns).
2. recebe um lote de entrada e executa várias etapas acima para obter resultado.

Vamos considerar um caso simples em que existe apenas um subprocedimento. Normalmente o código gostaria:

def proc(input):
    return sub-step(input))

Para ter um melhor desempenho, convém passar várias entradas para a função em um lote, para amortizar a sobrecarga da chamada de função e também aumentar a localidade do cache de código.

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

No entanto, como dito anteriormente, se a execução da etapa for aproximadamente a mesma do tempo de acesso à RAM, você poderá melhorar ainda mais o código para algo como isto:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

O fluxo de execução seria semelhante a:

1. pré-busca (1) solicita que a CPU pré-busque a entrada [1] no cache, onde as instruções de pré-busca recebem os ciclos P e retornam e, em segundo plano, a entrada [1] chegaria ao cache após os ciclos R.
2. trabalhos_em (0) falta fria no 0 e trabalha nele, o que leva M
3. pré-busca (2) emitir outra busca
4. trabalhos_em (1) se P + R <= M, as entradas [1] já devem estar no cache antes desta etapa, evitando assim um erro no cache de dados
5. trabalhos_em (2) ...

Pode haver mais etapas envolvidas, então você pode projetar um pipeline de vários estágios, desde que o tempo das etapas e a latência de acesso à memória correspondam, você sofreria pouca falta de código / cache de dados. No entanto, esse processo precisa ser ajustado com muitas experiências para descobrir o agrupamento correto de etapas e o tempo de pré-busca. Devido ao seu esforço necessário, ele vê mais adoção no processamento de fluxo de dados / pacotes de alto desempenho. Um bom exemplo de código de produção pode ser encontrado no design do pipeline do DPDK QoS Enqueue: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Capítulo 21.2.4.3. Enfileirar pipeline.

Mais informações podem ser encontradas:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

Escreva seu programa para obter um tamanho mínimo. É por isso que nem sempre é uma boa ideia usar otimizações -O3 para o GCC. Ele ocupa um tamanho maior. Freqüentemente, -Os é tão bom quanto -O2. Tudo depende do processador usado. YMMV.

Trabalhe com pequenos pedaços de dados de cada vez. É por isso que algoritmos de classificação menos eficientes podem executar mais rápido que o quicksort se o conjunto de dados for grande. Encontre maneiras de dividir seus conjuntos de dados maiores em outros menores. Outros sugeriram isso.

Para ajudá-lo a explorar melhor a localidade temporal / espacial da instrução, convém estudar como seu código é convertido em assembly. Por exemplo:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

Os dois loops produzem códigos diferentes, mesmo que estejam apenas analisando através de uma matriz. De qualquer forma, sua pergunta é muito específica da arquitetura. Portanto, sua única maneira de controlar rigidamente o uso do cache é entender como o hardware funciona e otimizar seu código.

Além de alinhar sua estrutura e campos, se sua estrutura for heap alocada, convém usar alocadores que suportam alocações alinhadas; como _alinhado_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); caso contrário, você pode ter um compartilhamento falso aleatório; lembre-se de que no Windows, o heap padrão tem um alinhamento de 16 bytes.