Quais são algumas boas estratégias para melhorar o desempenho serial do meu código?

Trabalho em ciência da computação e, como resultado, passo uma quantidade não trivial do meu tempo tentando aumentar a taxa de transferência científica de muitos códigos, além de entender a eficiência desses códigos.

Vamos supor que eu avaliei a troca desempenho versus legibilidade / reutilização / manutenibilidade do software em que estou trabalhando e decidi que é hora de buscar o desempenho. Vamos supor também que eu sei que não tenho um algoritmo melhor para o meu problema (em termos de flop / se largura de banda de memória). Você também pode assumir que minha base de código está em uma linguagem de baixo nível como C, C ++ ou Fortran. Por fim, vamos supor que não haja paralelismo no código ou que apenas estamos interessados ​​no desempenho em um único núcleo.

Quais são as coisas mais importantes para experimentar primeiro? Como sei quanto desempenho posso obter?

Antes de tudo, como o especialista e Dan apontaram, a criação de perfil é essencial. Eu pessoalmente uso o amplificador VTune da Intel no Linux, pois me fornece uma visão geral muito detalhada de onde o tempo foi gasto fazendo o que.

Se você não quiser alterar o algoritmo (por exemplo, se não houver grandes alterações que tornem obsoletas todas as suas otimizações), sugiro procurar alguns detalhes comuns de implementação que possam fazer uma grande diferença:

• Localidade da memória : os dados que são lidos / usados ​​juntos também são armazenados juntos, ou você está pegando pedaços aqui e ali?

• Alinhamento da memória : suas duplas estão realmente alinhadas com 4 bytes? Como você embalou o seu structs? Para ser pedante, use em posix_memalignvez de malloc.

• Eficiência de cache : a localidade cuida da maioria dos problemas de eficiência de cache, mas se você tem algumas estruturas de dados pequenas que lê / grava com frequência, ajuda se elas forem um múltiplo inteiro ou uma fração de uma linha de cache (geralmente 64 bytes). Também ajuda se seus dados estiverem alinhados ao tamanho de uma linha de cache. Isso pode reduzir drasticamente o número de leituras necessárias para carregar um dado.

• Vetorização : Não, não se preocupe com o montador codificado manualmente. gccoferece tipos de vetor que são traduzidos para SSE / AltiVec / quaisquer instruções automagicamente.

• Paralelismo em nível de instrução : O filho bastardo da vetorização. Se algum cálculo repetido com frequência não for bem vetorizado, tente acumular valores de entrada e calcular vários valores ao mesmo tempo. É como um desenrolar de loop. O que você está explorando aqui é que sua CPU geralmente possui mais de uma unidade de ponto flutuante por núcleo.

• Precisão aritmética : Você realmente precisa de aritmética de precisão dupla em tudo que faz? Por exemplo, se você está computando uma correção em uma iteração de Newton, normalmente não precisa de todos os dígitos que está computando. Para uma discussão mais aprofundada, consulte este documento.

Alguns desses truques são usados daxpy_cvec neste tópico. Dito isto, se você estiver usando o Fortran (não é um idioma de baixo nível nos meus livros), terá muito pouco controle sobre a maioria desses "truques".

Se você estiver executando em algum hardware dedicado, por exemplo, um cluster usado para todas as suas execuções de produção, também poderá ler as especificações das CPUs usadas. Não que você deva escrever coisas no assembler diretamente para essa arquitetura, mas pode inspirá-lo a encontrar outras otimizações que você pode ter perdido. Saber sobre um recurso é um primeiro passo necessário para escrever código que possa explorá-lo.

Atualizar

Já faz um tempo desde que escrevi isso e não havia notado que se tornara uma resposta tão popular. Por esse motivo, gostaria de acrescentar um ponto importante:

• Fale com o seu cientista da computação local : não seria legal se houvesse uma disciplina que tratasse exclusivamente de tornar algoritmos e / ou cálculos mais eficientes / elegantes / paralelos, e todos nós poderíamos pedir conselhos a eles? Bem, boas notícias, essa disciplina existe: Ciência da Computação. As chances são de que sua instituição tenha um departamento inteiro dedicado a ela. Converse com esses caras.

Tenho certeza de que para vários cientistas que não são da computação, isso trará de volta memórias de discussões frustrantes com a referida disciplina que não resultou em nada, ou memórias de anedotas de outras pessoas. Não desanime. A colaboração interdisciplinar é uma coisa complicada e exige um pouco de trabalho, mas as recompensas podem ser enormes.

Na minha experiência, como cientista da computação (CS), o truque está em acertar tanto as expectativas quanto a comunicação.

Expectativa - caso contrário, um CS só o ajudará se achar que seu problema é interessante. Isso praticamente exclui a tentativa de otimizar / vetorizar / paralelizar um pedaço de código que você escreveu, mas não comentou realmente, por um problema que eles não entendem. Os CSs geralmente estão mais interessados ​​no problema subjacente, por exemplo, os algoritmos usados ​​para resolvê-lo. Não dê a eles sua solução , dê a eles seu problema .

Além disso, esteja preparado para o CS dizer " esse problema já foi resolvido " e apenas fornecer uma referência a um artigo. Um conselho: Leia esse documento e, se ele realmente se aplicar ao seu problema, implemente o algoritmo que ele sugerir. Este não é um CS sendo presunçoso, é um CS que apenas o ajudou. Não se ofenda, lembre-se: se o problema não for computacionalmente interessante, ou seja, ele já foi resolvido e a solução mostrou-se ótima, eles não funcionarão, muito menos o codificará para você.

Comunicação - lembre-se de que a maioria dos CSs não é especialista em seu campo e explique o problema em termos do que você está fazendo, em vez de como e por quê . Normalmente, não nos importamos com o porquê e como é, bem, o que fazemos melhor.

Por exemplo, atualmente estou trabalhando com um grupo de cosmologistas computacionais na criação de uma versão melhor de seu código de simulação, com base no SPH e multipoles . Foram necessárias três reuniões para parar de falar em termos de matéria escura e halos de galáxias (hein?) E detalhar o núcleo da computação, ou seja, que eles precisam encontrar todos os vizinhos dentro de um determinado raio de cada partícula, calcular alguns quantidade sobre eles e, em seguida, atropele todos os vizinhos mencionados novamente e aplique essa quantidade em algum outro cálculo. Em seguida, mova as partículas, ou pelo menos algumas delas, e faça tudo de novo. Veja bem, enquanto o primeiro pode ser incrivelmente interessante (é!), O último é o que eu preciso entender para começar a pensar em algoritmos.

Mas estou divergindo do ponto principal: se você está realmente interessado em acelerar sua computação e não é um cientista da computação, fale com um deles.

O software científico não é muito diferente de outro software, na medida em que sabe o que precisa de ajuste.

O método que eu uso é uma pausa aleatória . Aqui estão algumas das acelerações que ele encontrou para mim:

Se uma grande fração do tempo é gasta em funções como loge exp, posso ver quais são os argumentos para essas funções, em função dos pontos dos quais eles estão sendo chamados. Muitas vezes, eles são chamados repetidamente com o mesmo argumento. Nesse caso, a memorização produz um enorme fator de aceleração.

Se eu estiver usando as funções BLAS ou LAPACK, posso achar que uma grande fração do tempo é gasta em rotinas para copiar matrizes, multiplicar matrizes, transformar choleski, etc.

• A rotina para copiar matrizes não existe para velocidade, mas para conveniência. Você pode achar que há uma maneira menos conveniente, mas mais rápida, de fazer isso.

• Rotinas para multiplicar ou inverter matrizes ou realizar transformações de choleski tendem a ter argumentos de caracteres que especificam opções, como 'U' ou 'L' para o triângulo superior ou inferior. Mais uma vez, existem por conveniência. O que descobri foi que, como minhas matrizes não eram muito grandes, as rotinas passavam mais da metade do tempo chamando a sub-rotina para comparar caracteres apenas para decifrar as opções. Escrever versões especiais das rotinas matemáticas mais caras produziu aceleração maciça.

Se eu puder apenas expandir o último: a rotina de multiplicação de matriz DGEMM chama LSAME para decodificar seus argumentos de caractere. A análise de perfis de tempo percentual inclusivo (a única estatística que vale a pena considerar) considerada "boa" poderia mostrar o DGEMM usando alguma porcentagem do tempo total, como 80%, e o LSAME usando alguma porcentagem do tempo total, como 50%. Olhando para o primeiro, você seria tentado a dizer "bem, ele deve ser fortemente otimizado, para que eu não possa fazer muito a respeito". Olhando para o último, você seria tentado a dizer "Huh? O que é isso tudo? Isso é apenas uma pequena rotina. Esse criador de perfil deve estar errado!"

Não está errado, apenas não está dizendo o que você precisa saber. O que a pausa aleatória mostra é que o DGEMM está em 80% das amostras de pilha e o LSAME está em 50%. (Você não precisa de muitas amostras para detectar isso. 10 é geralmente suficiente.) Além disso, em muitas dessas amostras, o DGEMM está no processo de chamar o LSAME de algumas linhas de código diferentes.

Então agora você sabe por que as duas rotinas estão demorando tanto. Você também sabe de onde eles estão sendo chamados no código para gastar todo esse tempo. É por isso que uso uma pausa aleatória e tomo uma visão icterícia dos criadores de perfil, não importa quão bem feitos eles sejam. Eles estão mais interessados ​​em obter medições do que em dizer o que está acontecendo.

É fácil supor que as rotinas da biblioteca matemática tenham sido otimizadas até o enésimo grau, mas na verdade elas foram otimizadas para serem usadas para uma ampla variedade de propósitos. Você precisa ver o que realmente está acontecendo, não o que é fácil de assumir.

ADICIONADO: para responder às suas duas últimas perguntas:

Quais são as coisas mais importantes para experimentar primeiro?

Colete amostras de 10 a 20 pilhas e não apenas as resuma, entenda o que cada uma delas está lhe dizendo. Faça isso primeiro, último e intermediário. (Não há "tentativa", jovem Skywalker.)

Como sei quanto desempenho posso obter?

As amostras de pilha fornecerão uma estimativa muito aproximada de qual fração de tempo será salva. (Segue uma distribuição , onde é o número de amostras que exibiram o que você vai corrigir e é o número total de amostras. Isso não conta o custo do código que você usou para substituí-lo, o que provavelmente será pequeno.) Então a taxa de aceleração é de que pode ser grande. Observe como isso se comporta matematicamente. Se e , a média e o modo de são 0,5, para uma taxa de aceleração de 2. Aqui está a distribuição: Se você é avesso ao risco, sim, há uma pequena probabilidade (0,03%) este$x$$\beta(s+1,(n-s)+1)$$s$$n$$1/(1-x)$$n=10$$s=5$$x$

$x$ é menor que 0,1, para uma aceleração menor que 11%. Mas o balanceamento é uma probabilidade igual de que é maior que 0,9, para uma taxa de aceleração maior que 10! Se você está recebendo dinheiro proporcionalmente à velocidade do programa, não há chances ruins.$x$

Como já mencionei antes, você pode repetir todo o procedimento até não poder mais, e a taxa de aceleração composta pode ser bastante grande.

ADICIONADO: Em resposta à preocupação de Pedro sobre falsos positivos, deixe-me tentar construir um exemplo onde eles podem ocorrer. Como nunca agimos sobre um problema em potencial, a menos que o vejamos duas ou mais vezes, esperamos que ocorram falsos positivos quando vemos um problema o menor número possível de vezes, especialmente quando o número total de amostras é grande. Suponha que tomemos 20 amostras e a vejamos duas vezes. Isso estima que seu custo seja 10% do tempo total de execução, o modo de sua distribuição. (A média da distribuição é mais alta - é .) A curva mais baixa no gráfico a seguir é sua distribuição:$(s+1)/(n+2)=3/22=13.6\%$

Considere se pegamos até 40 amostras (mais do que eu já tive ao mesmo tempo) e só vi um problema em duas delas. O custo estimado (modo) desse problema é de 5%, conforme mostrado na curva mais alta.

O que é um "falso positivo"? É que, se você corrige um problema, obtém um ganho tão menor que o esperado, que se arrepende de ter corrigido. As curvas mostram (se o problema for "pequeno") que, embora o ganho possa ser menor que a fração das amostras que o mostram, em média será maior.

Existe um risco muito mais sério - um "falso negativo". É quando há um problema, mas não é encontrado. (Contribuir para isso é o "viés de confirmação", onde a ausência de evidência tende a ser tratada como evidência de ausência.)

O que você obtém com um criador de perfil (bom) é que você obtém uma medição muito mais precisa (portanto, menos chance de falsos positivos), à custa de informações muito menos precisas sobre qual é realmente o problema (menos chance de encontrá-lo e obtê-lo) qualquer ganho). Isso limita a aceleração geral que pode ser alcançada.

Eu encorajaria os usuários de criadores de perfil a relatar os fatores de aceleração que eles realmente praticam.

Há outro ponto a ser ressaltado. A pergunta de Pedro sobre falsos positivos.

Ele mencionou que pode haver uma dificuldade ao se resolver pequenos problemas no código altamente otimizado. (Para mim, um pequeno problema é responsável por 5% ou menos do tempo total.)

Como é perfeitamente possível construir um programa totalmente ideal, exceto 5%, esse ponto só pode ser abordado empiricamente, como nesta resposta . Para generalizar a partir da experiência empírica, é assim:

Um programa, como escrito, normalmente contém várias oportunidades de otimização. (Podemos chamá-los de "problemas", mas geralmente são um código perfeitamente bom, simplesmente capaz de melhorar consideravelmente.) Este diagrama ilustra um programa artificial que leva algum tempo (100s, digamos) e contém os problemas A, B, C, ... que, quando encontrados e corrigidos, economizem 30%, 21% etc. dos 100s originais.

Observe que o problema F custa 5% do tempo original, portanto é "pequeno" e difícil de encontrar sem 40 ou mais amostras.

No entanto, as 10 primeiras amostras encontram facilmente o problema A. ** Quando isso é corrigido, o programa leva apenas 70s, para uma aceleração de 100/70 = 1,43x. Isso não apenas torna o programa mais rápido, como também amplia, nessa proporção, as porcentagens tomadas pelos problemas restantes. Por exemplo, o problema B originalmente levou 21s, o que representava 21% do total, mas após a remoção de A, B tirou 21s dos 70s ou 30%, portanto, é mais fácil encontrar quando todo o processo é repetido.

Depois que o processo é repetido cinco vezes, agora o tempo de execução é de 16,8 segundos, dos quais o problema F é 30%, e não 5%, então 10 amostras o encontram facilmente.

Então esse é o ponto. Empiricamente, os programas contêm uma série de problemas com uma distribuição de tamanhos, e qualquer problema encontrado e corrigido facilita a localização dos demais. Para conseguir isso, nenhum dos problemas pode ser ignorado porque, se houver, eles ficam lá, demorando um tempo, limitando a aceleração total e deixando de ampliar os problemas restantes. É por isso que é muito importante encontrar os problemas que estão ocultos .

Se os problemas de A a F forem encontrados e corrigidos, a aceleração é de 100 / 11,8 = 8,5x. Se um deles faltar, por exemplo D, a aceleração é de apenas 100 / (11,8 + 10,3) = 4,5x. Esse é o preço pago por falsos negativos.

Portanto, quando o criador de perfil diz "não parece haver nenhum problema significativo aqui" (ou seja, bom codificador, esse é praticamente o código ideal), talvez esteja certo e talvez não. (Um falso negativo .) Você não sabe ao certo se há mais problemas a serem corrigidos, para maior velocidade, a menos que tente outro método de criação de perfil e descubra que existem. Na minha experiência, o método de criação de perfil não precisa de um grande número de amostras, resumido, mas de um pequeno número de amostras, em que cada amostra é compreendida completamente o suficiente para reconhecer qualquer oportunidade de otimização.

** São necessários no mínimo 2 acertos em um problema para encontrá-lo, a menos que se tenha conhecimento prévio de que existe um loop infinito (quase). (As marcas vermelhas representam 10 amostras aleatórias); O número médio de amostras necessárias para obter 2 ou mais ocorrências, quando o problema é de 30%, é ( distribuição binomial negativa ). 10 amostras o acham com 85% de probabilidade, 20 amostras - 99,2% ( distribuição binomial ). Para obter a probabilidade de encontrar o problema, em R, avaliar , por exemplo: .$2/0.3=6.67$1 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627

ADICIONADO: A fração de tempo economizada, , segue uma distribuição Beta , em que é o número de amostras e é o número que exibe o problema. No entanto, a taxa de aceleração é igual a (assumindo que é salvo), e seria interessante entender a distribuição de . Acontece que segue uma distribuição BetaPrime . Simulei-o com 2 milhões de amostras, chegando a este comportamento:β ( s + 1 , ( n - s ) + 1 ) n s y 1 / ( 1 - x ) x y y - $x$$\beta(s+1,(n-s)+1)$$n$$s$$y$$1/(1-x)$$x$$y$$y-1$

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

As duas primeiras colunas fornecem o intervalo de confiança de 90% para a taxa de aceleração. A taxa média de aceleração é igual a exceto no caso em que . Nesse caso, é indefinido e, de fato, à medida que aumenta o número de valores simulados , a média empírica aumenta.s = n $(n+1)/(n-s)$$s=n$$y$

Este é um gráfico da distribuição dos fatores de aceleração e suas médias para 2 ocorrências em 5, 4, 3 e 2 amostras. Por exemplo, se três amostras forem coletadas e duas delas forem encontradas em um problema, e esse problema puder ser removido, o fator de aceleração médio seria 4x. Se os 2 hits forem vistos em apenas 2 amostras, a aceleração média é indefinida - conceitualmente porque existem programas com loops infinitos com probabilidade diferente de zero!

Você não apenas precisa ter um conhecimento profundo de seu compilador , mas também de sua arquitetura de destino e sistema operacional .

O que pode afetar o desempenho?

Se você deseja reduzir toda a última gota de desempenho, sempre que alterar sua arquitetura de destino, precisará ajustar e otimizar novamente seu código. Algo que foi uma otimização com uma CPU pode ficar abaixo do ideal na próxima revisão da mesma CPU.

Um excelente exemplo disso seria o cache da CPU. Mova seu programa de uma CPU com um cache pequeno e rápido para outro com um cache um pouco mais lento e um pouco maior e sua criação de perfil pode mudar significativamente.

Mesmo que a arquitetura de destino não seja alterada, alterações de baixo nível em um sistema operacional também podem afetar o desempenho. Os patches de mitigação Spectre e Meltdown tiveram um enorme impacto em algumas cargas de trabalho, portanto, isso pode forçar uma reavaliação de suas otimizações.

Como posso manter meu código otimizado?

Ao desenvolver código altamente otimizado, você precisa mantê-lo modular e facilitar a troca e retirada de diferentes versões do mesmo algoritmo, possivelmente até mesmo selecionando a versão específica usada no tempo de execução, dependendo dos recursos disponíveis e do tamanho / complexidade do código. dados a serem processados.

A modularidade também significa ser capaz de usar o mesmo conjunto de testes em todas as suas versões otimizadas e unoptimised, permitindo-lhe verificar que todos eles se comportam da mesma e perfil de cada um rapidamente em um like-for-like comparação. Entro um pouco mais detalhadamente na minha resposta para Como documentar e ensinar aos outros códigos "intensivos além do reconhecimento" computacionalmente intensivos? .

Leitura adicional

Além disso, eu recomendo dar uma olhada no excelente artigo de Ulrich Drepper O que todo programador deveria saber sobre memória , cujo título é uma homenagem ao igualmente fantástico O que todo cientista da computação deve saber sobre aritmética de ponto flutuante .

Lembre-se de que toda otimização tem potencial para se tornar uma anti-otimização futura ; portanto, deve ser considerado um possível odor de código, a ser mantido no mínimo. Minha resposta para A micro-otimização é importante ao codificar? fornece um exemplo concreto disso a partir da experiência pessoal.

Eu acho que você formulou a pergunta de maneira muito restrita. Na minha opinião, uma atitude útil é viver sob a suposição de que apenas alterações nas estruturas e algoritmos de dados podem gerar ganhos de desempenho significativos em códigos com mais de algumas 100 linhas, e acredito que ainda não encontrei um contra-exemplo para esta reivindicação.

A primeira coisa que você deve fazer é criar um perfil do seu código. Você deseja descobrir quais partes do seu programa estão diminuindo sua velocidade antes de começar a otimizar, caso contrário, você poderá otimizar uma parte do seu código que não está consumindo muito tempo de execução.

Linux

O gprof é muito bom, mas apenas informa quanto tempo leva para cada função e não para cada linha.

Apple OS X

Você pode experimentar o Shark . Está disponível no site da Apple Developer em Downloads> Ferramentas do desenvolvedor> CHUD 4.6.2, a versão mais antiga aqui . O CHUD também contém outras ferramentas de criação de perfil, como o BigTop frontend, a ferramenta de pesquisa de índice PMC, o perfilador de nível de função Saturn e muitos outros comandos. O Shark virá com uma versão em linha de comando.

Quanto ao desempenho que você pode obter, pegue os resultados da criação de perfil do seu código e digamos que você identifique uma parte que leva a fração "p" do tempo. Se você melhorar o desempenho dessa peça apenas por um fator "s", sua velocidade geral será de 1 / ((1-p) + p / s). Portanto, você pode aumentar sua velocidade ao máximo por um fator de 1 / (1-p). Espero que você tenha áreas de alta p! Isso é equivalente à Lei de Amdahl para otimização serial.

A otimização do seu código deve ser feita com cuidado. Vamos supor também que você já depurou o código. Você pode economizar muito tempo se seguir certas prioridades, a saber:

1. Use bibliotecas altamente otimizadas (ou profissionalmente otimizadas) sempre que possível. Alguns exemplos podem incluir bibliotecas FFTW, OpenBlas, Intel MKL, NAG, etc. A menos que você seja altamente talentoso (como o desenvolvedor do GotoBLAS), provavelmente não poderá vencer os profissionais.

2. Use um criador de perfil (alguns na lista a seguir já foram nomeados neste segmento - Intel Tune, valgrind, gprof, gcov etc.) para descobrir quais partes do seu código levam mais tempo. Não adianta perder tempo otimizando partes do código que raramente são chamadas.

3. Nos resultados do criador de perfil, observe a parte do seu código que demorou mais tempo. Determine qual é a natureza do seu algoritmo - ele está ligado à CPU ou à memória? Cada um requer um conjunto diferente de técnicas de otimização. Se você estiver com muitas falhas de cache, a memória pode ser o gargalo - a CPU está desperdiçando ciclos de clock aguardando a disponibilidade da memória. Pense se o loop se encaixa no cache L1 / L2 / L3 do seu sistema. Se você tiver instruções "if" em seu loop, verifique se o criador de perfil diz alguma coisa sobre erros de previsão de ramificação? Qual é a penalidade de desvio de agência do seu sistema? A propósito, você pode obter dados de predição incorreta de ramificações nos Manuais de Referência da Intel Optimization [1]. Observe que a penalidade de desvio de ramificação é específica do processador, como você verá no manual da Intel.

4. Por fim, resolva os problemas identificados pelo criador de perfil. Várias técnicas já foram discutidas aqui. Também estão disponíveis vários recursos bons, confiáveis ​​e abrangentes sobre otimização. Para citar apenas dois, há o Intel Optimization Reference Manual [1] e os cinco manuais de otimização de Agner Fog [2]. Observe que há algumas coisas que você talvez não precise fazer, se o compilador já o fizer - por exemplo, desenrolar o loop, alinhar a memória etc. Leia atentamente a documentação do compilador.

Referências:

[1] Manual de referência da otimização de arquiteturas Intel 64 e IA-32: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf

[2] Agner Fog, "Recursos de otimização de software": http://www.agner.org/optimize/

• "Otimizando o software em C ++: um guia de otimização para plataformas Windows, Linux e Mac"
• "Otimizando sub-rotinas na linguagem assembly: um guia de otimização para plataformas x86"
• "A microarquitetura das CPUs Intel, AMD e VIA: um guia de otimização para programadores de montagem e fabricantes de compiladores"
• "Tabelas de instruções: listas de latências de instrução, taxas de transferência e falhas de micro-operação para CPUs Intel, AMD e VIA"
• "Convenções de chamada para diferentes compiladores C ++ e sistemas operacionais"

Eu não sou um cientista computacional como muitos outros aqui (então eu posso estar errado :)), mas hoje em dia há pouco sentido em gastar muito tempo em desempenho serial, desde que usemos bibliotecas padrão. Talvez valha a pena gastar algum tempo / esforço adicional para tornar o código mais escalável.

De qualquer forma, aqui estão dois exemplos (se você ainda não os leu) sobre como o desempenho foi aprimorado (para problemas não estruturados de EF).

Serial : Veja a segunda metade do texto abstrato e relacionado.

Paralelo : Especialmente a fase de inicialização, na seção 4.2.

Talvez seja mais uma resposta do que uma resposta ...

Você deve desenvolver uma familiaridade íntima com seu compilador. Você pode adquiri-lo com mais eficiência lendo o manual e experimentando as opções.

Muitos dos bons conselhos que o @Pedro distribui podem ser implementados ajustando a compilação em vez do programa.

Uma maneira fácil de criar um perfil de um programa (no Linux) é usar perfno statmodo. A maneira mais simples é apenas executá-lo como

perf stat ./my_program args ...

e fornecerá várias estatísticas de desempenho úteis:

Performance counter stats for './simd_test1':

     3884.559489 task-clock                #    1.000 CPUs utilized
              18 context-switches          #    0.005 K/sec
               0 cpu-migrations            #    0.000 K/sec
             383 page-faults               #    0.099 K/sec
  10,911,904,779 cycles                    #    2.809 GHz
 <not supported> stalled-cycles-frontend
 <not supported> stalled-cycles-backend
  14,346,983,161 instructions              #    1.31  insns per cycle
   2,143,017,630 branches                  #  551.676 M/sec
          28,892 branch-misses             #    0.00% of all branches

     3.885986246 seconds time elapsed

Às vezes, também listará cargas e erros de cache D. Se houver muitas falhas de cache, seu programa consome muita memória e não está tratando bem os caches. Atualmente, as CPUs estão ficando mais rápidas que a largura de banda da memória e, geralmente, o problema é sempre o acesso à memória.

Você também pode tentar perf record ./my_program; perf reportqual é uma maneira fácil de criar um perfil. Leia as páginas de manual para saber mais.