Quais códigos de operação são mais rápidos no nível da CPU? [fechadas]

Em toda linguagem de programação, existem conjuntos de códigos de operação recomendados em detrimento de outros. Eu tentei listá-los aqui, em ordem de velocidade.

1. Bit a bit
2. Adição / Subtração Inteira
3. Multiplicação / Divisão Inteira
4. Comparação
5. Controle de fluxo
6. Adição / Subtração de Bóia
7. Multiplicação / Divisão de Bóia

Onde você precisa de código de alto desempenho, o C ++ pode ser otimizado manualmente na montagem, para usar instruções SIMD ou fluxo de controle mais eficiente, tipos de dados, etc. Então, estou tentando entender se o tipo de dados (int32 / float32 / float64) ou a operação utilizado ( *, +, &) afeta o desempenho no nível do CPU.

1. Uma única multiplicação é mais lenta na CPU do que uma adição?
2. Na teoria do MCU, você aprende que a velocidade dos códigos de operação é determinada pelo número de ciclos de CPU necessários para executar. Então, isso significa que multiplicar leva 4 ciclos e adicionar leva 2?
3. Exatamente quais são as características de velocidade dos códigos de operação básicos de matemática e controle?
4. Se dois opcodes levam o mesmo número de ciclos para serem executados, então ambos podem ser usados ​​alternadamente sem nenhum ganho / perda de desempenho?
5. Quaisquer outros detalhes técnicos que você possa compartilhar sobre o desempenho da CPU x86 são apreciados

Os guias de otimização da Agner Fog são excelentes. Ele tem guias, tabelas de tempos de instrução e documentos sobre a microarquitetura de todos os projetos recentes de CPU x86 (desde o Intel Pentium). Consulte também alguns outros recursos vinculados em /programming//tags/x86/info

Apenas por diversão, responderei algumas das perguntas (números de CPUs Intel recentes). A escolha de operações não é o principal fator na otimização do código (a menos que você possa evitar a divisão).

Uma única multiplicação é mais lenta na CPU do que uma adição?

Sim (a menos que seja por uma potência de 2). (3-4x da latência, com apenas uma taxa de transferência por clock na Intel.) Não se esforce muito para evitá-la, pois ela é tão rápida quanto 2 ou 3 adiciona.

Exatamente quais são as características de velocidade dos códigos de operação básicos de matemática e controle?

Consulte as tabelas de instruções e o guia de microarquitetura da Agner Fog para saber exatamente : P. Tenha cuidado com saltos condicionais. Saltos incondicionais (como chamadas de função) têm uma pequena sobrecarga, mas não muito.

Se dois opcodes levam o mesmo número de ciclos para serem executados, então ambos podem ser usados ​​alternadamente sem nenhum ganho / perda de desempenho?

Não, eles podem competir pela mesma porta de execução que outra coisa, ou não. Depende de quais outras cadeias de dependência a CPU pode estar trabalhando em paralelo. (Na prática, geralmente não há nenhuma decisão útil a ser tomada. Ocasionalmente, é possível usar um deslocamento de vetor ou um embaralhamento de vetor, que são executados em portas diferentes nas CPUs Intel. Porém, deslocamento por bytes de todo o registro ( PSLLDQetc.) é executado na unidade aleatória.)

Quaisquer outros detalhes técnicos que você possa compartilhar sobre o desempenho da CPU x86 são apreciados

Os documentos de microarquitetura da Agner Fog descrevem os pipelines das CPUs Intel e AMD com detalhes suficientes para determinar exatamente quantos ciclos um loop deve levar por iteração e se o gargalo é a taxa de transferência, a cadeia de dependência ou a contenção de uma porta de execução. Veja algumas das minhas respostas no StackOverflow, como esta ou esta .

Além disso, http://www.realworldtech.com/haswell-cpu/ (e similar para projetos anteriores) é uma leitura divertida se você gosta de design de CPU.

Aqui está sua lista, classificada para uma CPU Haswell, com base nos meus melhores hóspedes. Esta não é realmente uma maneira útil de pensar sobre as coisas, mas para ajustar um loop asm. Os efeitos de previsão de cache / ramificação geralmente dominam; portanto, escreva seu código para ter bons padrões. Os números são muito ondulatórios e tentam explicar a alta latência, mesmo que a taxa de transferência não seja um problema, ou a geração de mais uops que entopem o tubo para que outras coisas aconteçam em paralelo. Esp. os números de cache / filial são muito inventados. A latência importa para dependências transportadas por loop, a taxa de transferência importa quando cada iteração é independente.

TL: DR esses números são criados com base no que estou visualizando para um caso de uso "típico", tanto quanto trocas entre latência, gargalos na porta de execução e taxa de transferência de front-end (ou paralisações para coisas como falhas de ramificação) ) Por favor, não use esses números para qualquer tipo de análise de desempenho séria .

• 0,5 a 1 adição / subtração bit a bit / número inteiro /
  shift and rotate (contagem de const em tempo de compilação) /
  versões vetoriais de tudo isso (1 a 4 por taxa de transferência de ciclo, latência de 1 ciclo)
• 1 vetor mínimo, máximo, comparação igual, comparação maior (para criar uma máscara)
• 1,5 vector embaralha. Haswell e os mais novos têm apenas uma porta de reprodução aleatória, e me parece que é comum precisar de muito embaralhamento, se você precisar, por isso estou ponderando um pouco mais para incentivar o pensamento de usar menos embaralhamento. Eles não são livres, esp. se você precisar de uma máscara de controle pshufb da memória.
• 1,5 carregamento / armazenamento (acerto do cache L1. Taxa de transferência melhor que a latência)
• 1,75 Multiplicação Inteira (latência 3c / uma por 1c tput na Intel, 4c lat na AMD e apenas uma por 2c tput) Constantes pequenas são ainda mais baratas usando LEA e / ou ADD / SUB / shift . Mas é claro que as constantes em tempo de compilação são sempre boas e geralmente podem se otimizar em outras coisas. (E multiplicar em um loop geralmente pode ser reduzido pelo compilador para tmp += 7um loop em vez de tmp = i*7)
• 1,75 alguns embaralham vetor 256b (latência extra em insns que podem mover dados entre faixas 128b de um vetor AVX). (Ou 3 a 7 em Ryzen, onde as travessias de travessia de faixa precisam de muito mais uops)
• 2 fp add / sub (e versões vetoriais do mesmo) (1 ou 2 por taxa de transferência de ciclo, latência de 3 a 5 ciclos). Pode ser lento se você estrangular a latência, por exemplo, somar uma matriz com apenas 1 sumvariável. (Eu poderia ponderar isso e fp mul tão baixo quanto 1 ou tão alto quanto 5, dependendo do caso de uso).
• 2 vetores fp mul ou FMA. (x * y + z é tão barato quanto um mul ou um add se você compilar com o suporte a FMA ativado).
• 2 inserção / extração de registros de uso geral em elementos vetoriais ( _mm_insert_epi8, etc.)
• 2,25 vector int mul (elementos de 16 bits ou pmaddubsw executando 8 * 8 -> 16 bits). Mais barato em Skylake, com melhor rendimento do que mul escalar
• 2,25 deslocamento / rotação por contagem variável (latência 2c, uma taxa de transferência 2c na Intel, mais rápida na AMD ou com IMC2)
• 2.5 Comparação sem ramificação ( y = x ? a : b, ou y = x >= 0) ( test / setccou cmov)
• 3 int-> conversão flutuante
• 3 Fluxo de controle perfeitamente previsto (ramificação prevista, chamada, retorno).
• 4 vetores int mul (elementos de 32 bits) (2 uops, latência 10c em Haswell)
• 4 divisão inteira ou %por uma constante em tempo de compilação (não potência de 2).
• 7 operações horizontais de vetor (por exemplo, PHADDadicionando valores em um vetor)
• 11 Divisão FP (vetorial) (latência 10-13c, uma por 7c de taxa de transferência ou pior). (Pode ser barato se usado raramente, mas o rendimento é 6 a 40x pior que o FP mul)
• 13? Fluxo de controle (ramo mal previsto, talvez 75% previsível)
• 13 divisão int ( sim , na verdade , é mais lento que a divisão FP e não pode vetorizar). (observe que os compiladores se dividem por uma constante usando mul / shift / add com uma constante mágica e div / mod por potências de 2 é muito barato.)
• 16 sqrt FP (vetorial)
• 25? carga (acerto do cache L3). (as lojas com cache-miss são mais baratas que as cargas.)
• 50? FP trig / exp / log. Se você precisar de muitos exp / log e não precisar de precisão total, poderá trocar precisão por velocidade com um polinômio mais curto e / ou uma tabela. Você também pode vetorizar o SIMD.
• 50-80? ramo sempre imprevisível, custando 15 a 20 ciclos
• 200-400? carregar / armazenar (falta de cache)
• 3000 ??? leia a página do arquivo (clique no cache do disco do SO) (componha os números aqui)
• 20000 ??? página de leitura de disco (falta de cache de disco do SO, SSD rápido) (número totalmente inventado)

Eu totalmente inventei isso com base em suposições . Se algo parece errado, é porque eu estava pensando em um caso de uso diferente ou em um erro de edição.

O custo relativo das coisas nos processadores AMD será semelhante, exceto que eles têm shifters inteiros mais rápidos quando a contagem de turnos é variável. As CPUs da família AMD Bulldozer são obviamente mais lentas na maioria dos códigos, por vários motivos. (Ryzen é muito bom em muitas coisas).

Lembre-se de que é realmente impossível resumir as coisas a um custo unidimensional . Além de erros de cache e erros de ramificação, o gargalo em um bloco de código pode ser latência, taxa de transferência total de uop (front-end) ou taxa de transferência de uma porta específica (porta de execução).

Uma operação "lenta" como a divisão FP pode ser muito barata se o código circundante mantiver a CPU ocupada com outros trabalhos . (a div de vetor FP ou o sqrt são 1 uop cada, eles apenas apresentam baixa latência e taxa de transferência. Eles apenas bloqueiam a unidade de divisão, não toda a porta de execução em que está. Div inteiro é vários uops.) Portanto, se você tiver apenas uma divisão de FP para cada ~ 20 mul e acrescentar, e há outro trabalho para a CPU (por exemplo, uma iteração de loop independente), então o "custo" da divisão FP pode ser aproximadamente o mesmo que uma FP mul. Este é provavelmente o melhor exemplo de algo com baixa taxa de transferência quando tudo o que você está fazendo, mas combina muito bem com outro código (quando a latência não é um fator), por causa do baixo total de uops.

Observe que a divisão inteira não é tão amigável com o código circundante: no Haswell, são 9 uops, com um por taxa de transferência de 8 a 11c e latência de 22 a 29c. (A divisão de 64 bits é muito mais lenta, mesmo na Skylake.) Portanto, os números de latência e taxa de transferência são um pouco semelhantes à divisão FP, mas a divisão FP é apenas um uop.

Para exemplos de análise de uma curta sequência de insns para taxa de transferência, latência e total de Uops, consulte algumas das minhas respostas de SO:

• A seção "análise de desempenho" desta resposta resume as coisas. O restante da resposta é sobre a otimização de um loop,sum += x[i] * y[i]desenrolando-se com vários acumuladores de vetores para ocultar a latência de FMA. É bastante técnico e de baixo nível, mas mostra o tipo de saída em linguagem assembly que você deseja que seu compilador faça e por que isso importa.
• Por que esse código C ++ é mais rápido que meu assembly escrito à mão para testar a conjectura de Collatz? : essa resposta popular que escrevi explica como segurar o compilador manualmente para torná-lo melhor quando possível. Também alguns detalhes de otimização de asm que permitem vencer o compilador para pequenas funções / loops nesse caso. IDK por que tem tantos mais votos positivos do que qualquer uma das minhas outras respostas.
• Qual é a maneira eficiente de contar bits definidos em uma posição ou menos? : Uma análise de desempenho de uma sequência de 6 insns para um problema interessante em que algumas operações manuais na fonte C levaram o gcc a criar um código melhor. Algumas das minhas outras respostas são para sequências de instruções ainda mais curtas.
• Calculadora de valor absoluto mais rápida usando SSE
• Problemas com ADC / SBB e INC / DEC em loops apertados em algumas CPUs
• Rsqrt vetorizado rápido e recíproco com SSE / AVX, dependendo da precisão
• Classificando estruturas de 64 bits usando o AVX?
• /programming//search?q=user%3A224132+throughput+latency+cycles

IDK se outras pessoas escreverem respostas SO, incluindo esse tipo de análise. É muito mais fácil encontrar o meu, porque sei que vou a esse detalhe com frequência e me lembro do que escrevi.

Depende da CPU em questão, mas para uma CPU moderna a lista é algo como isto:

1. Bitwise, adição, subtração, comparação, multiplicação
2. Divisão
3. Controle de fluxo (ver resposta 3)

Dependendo da CPU, pode haver um custo considerável para trabalhar com tipos de dados de 64 bits.

Suas perguntas:

1. De maneira alguma ou não apreciável em uma CPU moderna. Depende da CPU.
2. Essa informação é algo como 20 a 30 anos desatualizado (a escola é péssima, você agora tem provas), as CPUs modernas lidam com um número variável de instruções por relógio, quantas dependem do que o planejador planeja.
3. A divisão é um pouco mais lenta que as demais, o fluxo de controle é muito rápido se a previsão de ramificação estiver correta e muito lento se estiver errado (algo como 20 ciclos, depende da CPU). O resultado é que muito código é limitado principalmente pelo fluxo de controle. Não faça com umif que você pode razoavelmente fazer com aritmética.
4. Não existe um número fixo para quantos ciclos uma instrução leva, mas às vezes duas instruções diferentes podem executar igualmente, colocá-las em outro contexto e talvez não, executá-las em uma CPU diferente e é provável que você veja um terceiro resultado.
5. No topo do fluxo de controle, o outro grande desperdício de tempo está em falta de cache, sempre que você tenta ler dados que não estão em cache, a CPU terá que esperar que ela seja buscada na memória. Em geral, você deve tentar manipular os dados próximos um do outro simultaneamente, em vez de coletar dados de todo o lugar.

E finalmente, se você estiver fazendo um jogo, não se preocupe muito com tudo isso, concentre-se melhor em fazer um bom jogo do que cortar os ciclos da CPU.

Fiz um teste sobre operação inteira que fez um loop um milhão de vezes em x64_64, chegou a uma breve conclusão como abaixo,

adicionar --- 116 microssegundos

sub ---- 116 microssegundos

mul ---- 1036 microssegundos

div ---- 13037 microssegundos

os dados acima já reduziram a sobrecarga induzida pelo loop,

Os manuais do processador intel podem ser baixados gratuitamente em seu site. Eles são bastante grandes, mas tecnicamente podem responder à sua pergunta. O manual de otimização, em particular, é o que você procura, mas o manual de instruções também possui os tempos e latências para a maioria das principais linhas de CPU para obter instruções simd, pois elas variam de chip para chip.

Em geral, eu consideraria ramificações completas, bem como a busca por ponteiros (traverals da lista de links, chamando funções virtuais) como os melhores para os perf killers, mas os cpus x86 / x64 são muito bons em ambos, em comparação com outras arquiteturas. Se você mover para outra plataforma, verá o quanto de um problema pode ser se estiver escrevendo um código de alto desempenho.