Dicas de otimização de baixo nível em C ++ [fechadas]

Supondo que você já tenha o algoritmo de melhor escolha, que soluções de baixo nível você pode oferecer para extrair as últimas gotas de taxa de quadros de código doce do código C ++?

Escusado será dizer que essas dicas se aplicam apenas à seção de código crítico que você já destacou em seu criador de perfil, mas devem ser melhorias não estruturais de baixo nível. Eu semeei um exemplo.

Otimize seu layout de dados! (Isso se aplica a mais idiomas do que apenas C ++)

Você pode ir muito fundo, ajustando isso especificamente para seus dados, seu processador, lidando bem com vários núcleos etc. Mas o conceito básico é este:

Ao processar as coisas em um loop restrito, você deseja tornar os dados para cada iteração o mais pequenos possível e o mais próximos possível da memória. Isso significa que o ideal é uma matriz ou vetor de objetos (não ponteiros) que contêm apenas os dados necessários para o cálculo.

Dessa forma, quando a CPU buscar os dados para a primeira iteração do seu loop, as próximas várias iterações no valor de dados serão carregadas no cache com ele.

Realmente a CPU é rápida e o compilador é bom. Não há muito o que fazer com instruções menos e mais rápidas. A coerência do cache é onde está (esse é um artigo aleatório que pesquisei no Google - ele contém um bom exemplo de como obter coerência de cache para um algoritmo que não simplesmente executa os dados de maneira linear).

Uma dica de nível muito, muito baixo, mas que pode ser útil:

A maioria dos compiladores suporta alguma forma de dica condicional explícita. O GCC possui uma função chamada __builtin_expect, que permite informar ao compilador qual é provavelmente o valor de um resultado. O GCC pode usar esses dados para otimizar condicionais para executar o mais rápido possível no caso esperado, com uma execução um pouco mais lenta no caso inesperado.

if(__builtin_expect(entity->extremely_unlikely_flag, 0)) {
  // code that is rarely run
}

Eu vi uma aceleração de 10 a 20% com o uso adequado disso.

A primeira coisa que você precisa entender é o hardware em que está executando. Como ele lida com ramificação? E o cache? Possui um conjunto de instruções SIMD? Quantos processadores ele pode usar? Ele precisa compartilhar o tempo do processador com mais alguma coisa?

Você pode resolver o mesmo problema de maneiras muito diferentes - mesmo a sua escolha de algoritmo deve depender do hardware. Em alguns casos, O (N) pode ser executado mais lentamente que O (NlogN) (dependendo da implementação).

Como uma visão geral grosseira da otimização, a primeira coisa que faço é analisar exatamente quais problemas e quais dados você está tentando solucionar. Então otimize para isso. Se você deseja um desempenho extremo, esqueça as soluções genéricas - você pode incluir casos especiais em tudo que não corresponde ao seu caso mais usado.

Então perfil. Perfil, perfil, perfil. Observe o uso da memória, observe as penalidades de ramificação, veja as despesas gerais das chamadas de função, veja a utilização do pipeline. Descubra o que está deixando seu código mais lento. Provavelmente é o acesso a dados (escrevi um artigo chamado "The Latency Elephant" sobre a sobrecarga do acesso a dados - pesquise no Google. Não posso postar 2 links aqui porque não tenho "reputação" suficiente); otimize seu layout de dados ( ótimas matrizes planas e homogêneas são impressionantes ) e acesso a dados (pré-busca sempre que possível).

Depois de minimizar a sobrecarga do subsistema de memória, tente determinar se as instruções agora são o gargalo (espero que sejam) e observe as implementações SIMD do seu algoritmo - as implementações de estruturas de matrizes (SoA) podem ser muito dados e cache de instruções eficiente. Se o SIMD não corresponder ao seu problema, poderá ser necessária a codificação intrínseca e no nível do assembler.

Se você ainda precisar de mais velocidade, vá em paralelo. Se você tem o benefício de rodar em um PS3, as SPUs são seus amigos. Use-os, ame-os. Se você já escreveu uma solução SIMD, obterá um enorme benefício migrando para o SPU.

E então, perfil um pouco mais. Teste em cenários de jogos - esse código ainda é o gargalo? Você pode alterar a maneira como esse código é usado em um nível superior para minimizar seu uso (na verdade, esse deve ser seu primeiro passo)? Você pode adiar cálculos em vários quadros?

Qualquer que seja a plataforma em que esteja, aprenda o máximo possível sobre o hardware e os criadores de perfil disponíveis. Não presuma que você saiba qual é o gargalo - encontre-o com seu criador de perfil. E certifique-se de ter uma heurística para determinar se você realmente fez o seu jogo ir mais rápido.

E depois faça o perfil novamente.

Primeiro passo: pense com cuidado nos seus dados em relação aos seus algoritmos. O (log n) nem sempre é mais rápido que O (n). Exemplo simples: uma tabela de hash com apenas algumas chaves geralmente é melhor substituída por uma pesquisa linear.

Segunda etapa: veja a montagem gerada. O C ++ traz muita geração implícita de código para a tabela. Às vezes, ele se infiltra em você sem você saber.

Mas supondo que seja realmente a hora do pedal do metal: perfil. A sério. A aplicação aleatória de "truques de desempenho" tem tanta probabilidade de doer quanto de ajudar.

Então, tudo depende de quais são seus gargalos.

falta de cache de dados => otimizar seu layout de dados. Aqui está um bom ponto de partida: http://gamesfromwithin.com/data-oriented-design

falta de cache de código => Veja chamadas de funções virtuais, profundidade excessiva de pilhas de chamadas, etc. Uma causa comum de mau desempenho é a crença errônea de que as classes base devem ser virtuais.

Outros sumidouros comuns de desempenho em C ++:

• Alocação / desalocação excessiva. Se for crítico para o desempenho, não ligue para o tempo de execução. Sempre.
• Copie a construção. Evite onde puder. Se puder ser uma referência const, faça uma.

Todas as opções acima são imediatamente óbvias quando você olha para a montagem, então veja acima;)

Remova galhos desnecessários

Em algumas plataformas e com alguns compiladores, as ramificações podem jogar fora todo o pipeline, portanto, mesmo insignificantes, se os blocos () puderem ser caros.

A arquitetura PowerPC (PS3 / x360) oferece a instrução de seleção de ponto flutuante fsel. Isso pode ser usado no lugar de uma ramificação se os blocos forem tarefas simples:

float result = 0;
if (foo > bar) { result = 2.0f; }
else { result = 1.0f; }

Torna-se:

float result = fsel(foo-bar, 2.0f, 1.0f);

Quando o primeiro parâmetro é maior ou igual a 0, o segundo parâmetro é retornado, e o terceiro.

O preço da perda da ramificação é que o bloco if {} e o else {} serão executados; portanto, se uma operação for cara ou derereferenciar um ponteiro NULL, essa otimização não é adequada.

Às vezes, seu compilador já fez esse trabalho; portanto, verifique primeiro sua montagem.

Aqui estão mais informações sobre ramificação e fsel:

http://assemblyrequired.crashworks.org/tag/intrinsics/

Evite acessos à memória e especialmente aleatórios a todo custo.

Essa é a coisa mais importante a ser otimizada nas CPUs modernas. Você pode fazer uma merda de aritmética e até mesmo de muitas ramificações previstas erradas no tempo que espera pelos dados da RAM.

Você também pode ler esta regra ao contrário: faça o máximo de cálculos possível entre os acessos à memória.

Use Intrinsics do compilador.

Assegure-se de que o compilador esteja gerando a montagem mais eficiente para determinadas operações usando intrínsecas - construções que se parecem com chamadas de função que o compilador transforma em montagem otimizada:

Aqui está uma referência para o Visual Studio e outra para o GCC

Remova chamadas desnecessárias de função virtual

O envio de uma função virtual pode ser muito lento. Este artigo fornece uma boa explicação do porquê. Se possível, para funções chamadas muitas e muitas vezes por quadro, evite-as.

Você pode fazer isso de duas maneiras. Às vezes, você pode simplesmente reescrever as classes para não precisar de herança - talvez a MachineGun seja a única subclasse de Arma, e você possa amálgama-las.

Você pode usar modelos para substituir o polimorfismo em tempo de execução pelo polimorfismo em tempo de compilação. Isso funciona apenas se você conhece o subtipo de seus objetos em tempo de execução e pode ser uma grande reescrita.

Meu princípio básico é: não faça nada que não seja necessário .

Se você descobriu que uma função específica é um gargalo, pode otimizar a função - ou tentar impedir que ela seja chamada em primeiro lugar.

Isso não significa necessariamente que você está usando um algoritmo incorreto. Pode significar que você está executando cálculos a cada quadro que pode ser armazenado em cache por um curto período de tempo (ou totalmente pré-calculado), por exemplo.

Eu sempre tento essa abordagem antes de qualquer tentativa de otimização de nível realmente baixo.

Use SIMD (por SSE), se ainda não o fizer. Gamasutra tem um bom artigo sobre isso . Você pode baixar o código-fonte da biblioteca apresentada no final do artigo.

Minimize as cadeias de dependência para fazer melhor uso da linha dupla da CPU.

Em casos simples, o compilador pode fazer isso por você, se você habilitar o desenrolar do loop. No entanto, muitas vezes isso não acontece, especialmente quando há carros alegóricos envolvidos, pois a reordenação das expressões altera o resultado.

Exemplo:

float *data = ...;
int length = ...;

// Slow version
float total = 0.0f;
int i;
for (i=0; i < length; i++)
{
  total += data[i]
}

// Fast version
float total1, total2, total3, total4;
for (i=0; i < length-3; i += 4)
{
  total1 += data[i];
  total2 += data[i+1];
  total3 += data[i+2];
  total4 += data[i+3];
}
for (; i < length; i++)
{
  total += data[i]
}
total += (total1 + total2) + (total3 + total4);

Não negligencie seu compilador - se você estiver usando o gcc na Intel, poderá obter facilmente um ganho de desempenho alternando para o compilador Intel C / C ++, por exemplo. Se você estiver direcionando uma plataforma ARM, consulte o compilador comercial do ARM. Se você estiver no iPhone, a Apple permitirá que o Clang seja usado a partir do iOS 4.0 SDK.

Um problema que você provavelmente encontrará com a otimização, especialmente no x86, é que muitas coisas intuitivas acabam trabalhando contra você nas implementações modernas de CPU. Infelizmente para a maioria de nós, a capacidade de otimizar o compilador desapareceu há muito tempo. O compilador pode agendar instruções no fluxo com base em seu próprio conhecimento interno da CPU. Além disso, a CPU também pode reprogramar instruções com base em suas próprias necessidades. Mesmo se você pensar em uma maneira ideal de organizar um método, é provável que o compilador ou a CPU já tenha inventado isso por conta própria e já tenha realizado essa otimização.

Meu melhor conselho seria ignorar as otimizações de baixo nível e focar nas otimizações de nível superior. O compilador e a CPU não podem alterar seu algoritmo de um algoritmo O (n ^ 2) para O (1), não importa quão bons eles sejam. Isso exigirá que você observe exatamente o que está tentando fazer e encontre uma maneira melhor de fazê-lo. Deixe o compilador e a CPU se preocupar com o nível baixo e você se concentra nos níveis médio e alto.

A palavra-chave restringir é potencialmente útil, especialmente nos casos em que você precisa manipular objetos com ponteiros. Ele permite que o compilador assuma que o objeto apontado não será modificado de nenhuma outra maneira, o que, por sua vez, permite uma otimização mais agressiva, como manter partes do objeto em registros ou reordenar leituras e gravações com mais eficiência.

Uma coisa boa da palavra-chave é que é uma dica que você pode aplicar uma vez e aproveitar os benefícios sem reorganizar seu algoritmo. O lado ruim é que, se você usá-lo no lugar errado, poderá ver corrupção de dados. Mas geralmente é muito fácil identificar onde é legítimo usá-lo - é um dos poucos exemplos em que se espera que o programador saiba mais do que o compilador pode assumir com segurança, e é por isso que a palavra-chave foi introduzida.

Tecnicamente, 'restringir' não existe no C ++ padrão, mas equivalentes específicos de plataforma estão disponíveis para a maioria dos compiladores C ++, portanto vale a pena considerar.

Consulte também: http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

Const tudo!

Quanto mais informações você fornecer ao compilador sobre os dados, melhores serão as otimizações (pelo menos na minha experiência).

void foo(Bar * x) {...;}

torna-se;

void foo(const Bar * const x) {...;}

O compilador agora sabe que o ponteiro x não será alterado e que os dados para os quais está apontando também não serão alterados.

O outro benefício adicional é que você pode reduzir o número de bugs acidentais, impedindo-se (ou outros) de modificar as coisas que não deveriam.

Na maioria das vezes, a melhor maneira de obter desempenho é alterar seu algoritmo. Quanto menos geral a implementação, mais perto você fica do metal.

Supondo que isso tenha sido feito ...

Se realmente é um código crítico, tente evitar leituras de memória, evite calcular coisas que podem ser pré-calculadas (embora nenhuma tabela de pesquisa viole a regra número 1). Saiba o que o seu algoritmo faz e escreva de uma maneira que o compilador também saiba. Verifique a montagem para ter certeza de que sim.

Evite falhas de cache. Processo em lote, tanto quanto você puder. Evite funções virtuais e outros indiretos.

Por fim, meça tudo. As regras mudam o tempo todo. O que costumava acelerar o código há 3 anos agora o retarda. Um bom exemplo é 'use funções matemáticas duplas em vez de versões flutuantes'. Eu não teria percebido isso se não tivesse lido.

Eu esqueci - não tem construtores padrão para inicializar suas variáveis, ou se você insiste, pelo menos também cria construtores que não. Esteja ciente das coisas que não aparecem nos perfis. Quando você perde um ciclo desnecessário por linha de código, nada será exibido em seu criador de perfil, mas você perderá muitos ciclos em geral. Novamente, saiba o que seu código está fazendo. Faça com que sua função principal seja enxuta em vez de infalível. Versões infalíveis podem ser chamadas, se necessário, mas nem sempre são necessárias. A versatilidade tem um preço - o desempenho é um.

Editado para explicar por que não há inicialização padrão: Muitos códigos dizem: Vector3 bla; bla = DoSomething ();

A inicialização no construtor é perda de tempo. Além disso, nesse caso, o tempo perdido é pequeno (provavelmente limpando o vetor); no entanto, se os programadores fizerem isso habitualmente, isso aumentará. Além disso, muitas funções criam um temporário (pense em operadores sobrecarregados), que é inicializado como zero e atribuído depois imediatamente. Ciclos perdidos ocultos que são muito pequenos para ver um pico no seu criador de perfil, mas os ciclos de sangria por toda a sua base de código. Além disso, algumas pessoas fazem muito mais em construtores (o que é obviamente um não-não). Vi ganhos de vários milissegundos de uma variável não utilizada, na qual o construtor estava um pouco pesado. Assim que o construtor causar efeitos colaterais, o compilador não poderá otimizá-lo; portanto, a menos que você nunca use o código acima, prefiro um construtor não inicializador ou, como eu disse,

Vector3 bla (noInit); bla = doSomething ();

Reduzir a avaliação da expressão booleana

Este é realmente desesperado, pois é uma mudança muito sutil, mas perigosa, no seu código. No entanto, se você tiver uma condicional avaliada um número excessivo de vezes, poderá reduzir a sobrecarga da avaliação booleana usando operadores bit a bit. Assim:

if ((foo && bar) || blah) { ... } 

Torna-se:

if ((foo & bar) | blah) { ... }

Usando aritmética inteira. Se seus foos e barras são constantes ou avaliadas antes do if (), isso pode ser mais rápido que a versão booleana normal.

Como bônus, a versão aritmética possui menos ramificações que a versão booleana normal. Qual é outra maneira de otimizar .

A grande desvantagem é que você perde a avaliação preguiçosa - todo o bloco é avaliado, então você não pode fazer foo != NULL & foo->dereference(). Por causa disso, é discutível que isso seja difícil de manter e, portanto, o trade-off pode ser muito grande.

Fique de olho no uso da pilha

Tudo o que você adiciona à pilha é um empurrão e construção extra quando uma função é chamada. Quando é necessária uma grande quantidade de espaço de pilha, às vezes pode ser benéfico alocar memória de trabalho com antecedência e se a plataforma em que você está trabalhando tem RAM rápida disponível para uso - tanto melhor!