c++ - usar - repete em c




A substituição de um contador de loops de 32 bits por um de 64 bits apresenta desvios loucos no desempenho (6)

Eu codifiquei um programa C equivalente para experimentar, e posso confirmar esse comportamento estranho. Além do mais, o gcc acredita que o inteiro de 64 bits (que provavelmente deve ser um size_t qualquer maneira ...) seja melhor, já que usar o uint_fast32_t faz com que o gcc use um uint de 64 bits.

Eu fiz um pouco de mexer com a montagem:
Simplesmente pegue a versão de 32 bits, substitua todas as instruções / registros de 32 bits pela versão de 64 bits no loop popcount interno do programa. Observação: o código é tão rápido quanto a versão de 32 bits!

Isso é obviamente um truque, já que o tamanho da variável não é realmente de 64 bits, já que outras partes do programa ainda usam a versão de 32 bits, mas enquanto o loop de contagem interna domina o desempenho, este é um bom começo .

Eu então copiei o código do loop interno da versão de 32 bits do programa, o hackei para ser de 64 bits, mexi nos registradores para substituí-lo pelo loop interno da versão de 64 bits. Esse código também é executado tão rápido quanto a versão de 32 bits.

Minha conclusão é que isso é um mau agendamento de instruções pelo compilador, não a vantagem real de velocidade / latência das instruções de 32 bits.

(Advertência: eu arrastei a montagem, poderia ter quebrado algo sem perceber. Eu não penso assim.)

Eu estava procurando o caminho mais rápido para popcount grandes matrizes de dados. Eu encontrei um efeito muito estranho : Alterar a variável de loop de unsigned para uint64_t fez o desempenho cair 50% no meu PC.

O benchmark

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

Como você pode ver, criamos um buffer de dados aleatórios, com o tamanho sendo x megabytes, onde x é lido na linha de comando. Posteriormente, iteramos o buffer e usamos uma versão desenrolada do intrinseco de popcount x86 para executar o popcount. Para obter um resultado mais preciso, fazemos o número de 10.000 vezes. Nós medimos os tempos para o popcount. Na maiúscula, a variável de loop interno unsigned está unsigned , em letras minúsculas, a variável de loop interno é uint64_t . Eu pensei que isso não deveria fazer diferença, mas o oposto é o caso.

Os resultados (absolutamente loucos)

Eu compilo assim (versão g ++: Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

Aqui estão os resultados na minha CPU Haswell Core i7-4770K a 3,50 GHz, executando o test 1 (então dados aleatórios de 1 MB):

  • sem assinatura 41959360000 0,401554 seg 26,113 GB / s
  • uint64_t 41959360000 0,759822 seg 13,8003 GB / s

Como você pode ver, a taxa de transferência da versão uint64_t é apenas metade da versão unsigned ! O problema parece ser que uma montagem diferente é gerada, mas por quê? Primeiro, eu pensei em um bug do compilador, então eu tentei clang++ (Ubuntu Clang versão 3.4-1ubuntu3):

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

Resultado: test 1

  • sem assinatura 41959360000 0.398293 seg 26.3267 GB / s
  • uint64_t 41959360000 0,680954 seg 15,3986 GB / s

Então, é quase o mesmo resultado e ainda é estranho. Mas agora fica super estranho. Eu substituo o tamanho do buffer que foi lido da entrada com uma constante 1 , então altero:

uint64_t size = atol(argv[1]) << 20;

para

uint64_t size = 1 << 20;

Assim, o compilador agora sabe o tamanho do buffer em tempo de compilação. Talvez possa adicionar algumas otimizações! Aqui estão os números para g++ :

  • sem assinatura 41959360000 0,509156 seg 20,5944 GB / s
  • uint64_t 41959360000 0,508673 segundo 20,6139 GB / s

Agora, ambas as versões são igualmente rápidas. No entanto, o unsigned ficou ainda mais lento ! Ele caiu de 26 para 20 GB/s , substituindo assim uma constante não-constante por um valor constante para uma desotimização . Sério, eu não tenho ideia do que está acontecendo aqui! Mas agora para clang++ com a nova versão:

  • sem assinatura 41959360000 0,677009 seg 15,4884 GB / s
  • uint64_t 41959360000 0,676909 seg 15,4906 GB / s

Espere o que? Agora, ambas as versões caíram para o lento número de 15 GB / s. Assim, substituir uma não constante por um valor constante leva mesmo a um código lento em ambos os casos para o Clang!

Eu pedi a um colega com uma CPU Ivy Bridge para compilar meu benchmark. Ele obteve resultados semelhantes, por isso não parece ser Haswell. Como dois compiladores produzem resultados estranhos aqui, ele também não parece ser um bug do compilador. Nós não temos uma CPU AMD aqui, então só poderíamos testar com a Intel.

Mais loucura, por favor!

Tome o primeiro exemplo (aquele com atol(argv[1]) ) e coloque um static antes da variável, ie:

static uint64_t size=atol(argv[1])<<20;

Aqui estão os meus resultados em g + +:

  • 41959360000 sem assinatura 0,396728 segundo 26,4306 GB / s
  • uint64_t 41959360000 0,509484 seg 20,5811 GB / s

Mais uma alternativa . Ainda temos o rápido 26 GB / s com o u32 , mas conseguimos obter pelo menos o u64 da u64 de 13 GB / s para a de 20 GB / s! No PC do meu colega, a versão do u64 se tornou ainda mais rápida que a versão do u32 , produzindo o resultado mais rápido de todos. Infelizmente, isso só funciona para o g++ , o clang++ não parece se preocupar com static .

Minha pergunta

Você pode explicar esses resultados? Especialmente:

  • Como pode haver uma diferença entre o u32 e o u64 ?
  • Como a substituição de uma não constante por um tamanho de buffer constante pode desencadear menos código ideal ?
  • Como a inserção da palavra-chave static tornar o loop do u64 mais rápido? Ainda mais rápido que o código original no computador do meu colega!

Eu sei que a otimização é um território complicado, no entanto, nunca pensei que mudanças tão pequenas pudessem levar a uma diferença de 100% no tempo de execução e que pequenos fatores como um tamanho de buffer constante podem novamente misturar totalmente os resultados. Claro, eu sempre quero ter a versão que é capaz de aumentar em 26 GB / s. A única maneira confiável que posso pensar é copiar colar o assembly para este caso e usar assembly in-line. Esta é a única maneira de me livrar de compiladores que parecem enlouquecer com pequenas mudanças. O que você acha? Existe outra maneira de obter com segurança o código com mais desempenho?

A desmontagem

Aqui está a desmontagem dos vários resultados:

Versão de 26 GB / s do bufsize g + + / u32 / non-const :

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

Versão de 13 GB / s do bufsize de g ++ / u64 / non-const :

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

Versão de 15 GB / s do bufsize do clang ++ / u64 / non-const :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

Versão de 20 GB / s de g ++ / u32 & u64 / const bufsize :

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

Versão de 15 GB / s do bufsize do clang ++ / u32 & u64 / const :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

Curiosamente, a versão mais rápida (26 GB / s) é também a mais longa! Parece ser a única solução que usa lea . Algumas versões usam jb para pular, outras usam jne . Mas, além disso, todas as versões parecem ser comparáveis. Não vejo de onde uma lacuna de desempenho de 100% poderia se originar, mas não sou muito hábil em decifrar a montagem. A versão mais lenta (13 GB / s) parece mesmo muito curta e boa. Alguém pode explicar isso?

Lições aprendidas

Não importa qual seja a resposta a essa pergunta; Eu aprendi que em loops muito quentes todos os detalhes podem importar, até mesmo detalhes que não parecem ter qualquer associação com o código quente . Eu nunca pensei sobre que tipo usar para uma variável de loop, mas como você vê uma mudança tão pequena pode fazer uma diferença de 100% ! Mesmo o tipo de armazenamento de um buffer pode fazer uma grande diferença, como vimos com a inserção da palavra-chave static na frente da variável size! No futuro, irei sempre testar várias alternativas em vários compiladores ao escrever loops realmente apertados e quentes que são cruciais para o desempenho do sistema.

O interessante é que a diferença de desempenho ainda é tão alta, embora eu já tenha desenrolado o loop quatro vezes. Assim, mesmo se você se desenrolar, você ainda pode ser atingido por grandes desvios de desempenho. Muito interessante.


Eu não posso dar uma resposta autoritária, mas fornecer uma visão geral de uma causa provável. Essa referência mostra claramente que, para as instruções no corpo do loop, há uma proporção de 3: 1 entre a latência e a taxa de transferência. Também mostra os efeitos do envio múltiplo. Como há (dar ou receber) três unidades inteiras em processadores x86 modernos, geralmente é possível enviar três instruções por ciclo.

Portanto, entre o pipeline de pico e o desempenho de vários envios e a falha desses mecanismos, temos um fator de seis no desempenho. É bem sabido que a complexidade do conjunto de instruções x86 facilita a ocorrência de quebras peculiares. O documento acima tem um ótimo exemplo:

O desempenho do Pentium 4 para turnos à direita de 64 bits é muito ruim. O turno esquerdo de 64 bits e todos os turnos de 32 bits têm desempenho aceitável. Parece que o caminho de dados dos 32 bits superiores para os 32 bits inferiores da ALU não está bem desenhado.

Eu pessoalmente encontrei um caso estranho em que um loop quente rodava consideravelmente mais lento em um núcleo específico de um chip de quatro núcleos (AMD, se bem me lembro). Na verdade, obtivemos um desempenho melhor em um cálculo de redução de mapa desativando esse núcleo.

Aqui, meu palpite é a contenção de unidades inteiras: que os popcnt , contador de loops e endereço podem ser executados em velocidade máxima com o contador grande de 32 bits, mas o contador de 64 bits causa contenção e paralisação de pipeline. Como há apenas cerca de 12 ciclos no total, potencialmente 4 ciclos com vários despachos, por execução do corpo do loop, um único bloqueio pode afetar o tempo de execução por um fator de 2.

A mudança induzida usando uma variável estática, que eu estou supondo apenas causa um pequeno reordenamento de instruções, é outro indício de que o código de 32 bits está em algum ponto de inflexão para a contenção.

Eu sei que isso não é uma análise rigorosa, mas é uma explicação plausível.


Isso não é uma resposta, mas é difícil de ler se eu colocar resultados em comentários.

Eu recebo esses resultados com um Mac Pro ( Westmere 6-Cores Xeon 3.33 GHz). Eu compilei com clang -O3 -msse4 -lstdc++ a.cpp -oa (-O2 obter o mesmo resultado).

clang com uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

clang com uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

Eu também tentei:

  1. Inverta a ordem do teste, o resultado é o mesmo, então elimina o fator de cache.
  2. Tenha a instrução for em reverso: for (uint64_t i=size/8;i>0;i-=4) . Isso fornece o mesmo resultado e prova que a compilação é inteligente o suficiente para não dividir o tamanho por 8 a cada iteração (conforme esperado).

Aqui está meu palpite:

O fator de velocidade vem em três partes:

  • cache de código: a versão uint64_t tem tamanho de código maior, mas isso não afeta a minha CPU Xeon. Isso torna a versão de 64 bits mais lenta.

  • Instruções usadas. Observe não apenas a contagem de loop, mas o buffer é acessado com um índice de 32 bits e 64 bits nas duas versões. Acessar um ponteiro com um deslocamento de 64 bits solicita um registro e endereçamento de 64 bits dedicado, enquanto você pode usar imediato para um deslocamento de 32 bits. Isso pode tornar a versão de 32 bits mais rápida.

  • As instruções são emitidas apenas na compilação de 64 bits (ou seja, pré-busca). Isso faz com que 64 bits seja mais rápido.

Os três fatores juntos combinam com os resultados aparentemente conflitantes observados.


TL; DR: Use __builtin intrinsics.

Eu consegui fazer com que o gcc4.8.4 (e mesmo o 4.7.3 no gcc.godbolt.org) gerasse o código ideal para isso usando __builtin_popcountllo mesmo comando assembly, mas ele não tem esse bug de dependência falsa.

Não tenho 100% de certeza do meu código de benchmarking, mas a objdumpsaída parece compartilhar meus pontos de vista. Eu uso alguns outros truques ( ++ivs i++) para fazer o compilador desenrolar o loop para mim sem qualquer movlinstrução (comportamento estranho, devo dizer).

Resultados:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

Código de benchmarking:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

Opções de compilação:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

Versão do GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Versão do kernel do Linux:

3.19.0-58-generic

Informações da CPU:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Você tentou passar -funroll-loops -fprefetch-loop-arrays para o GCC?

Eu obtenho os seguintes resultados com essas otimizações adicionais:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

Culpado: Dependência de Dados Falsos (e o compilador nem está ciente disso)

Nos processadores Sandy / Ivy Bridge e Haswell, a instrução:

popcnt  src, dest

parece ter uma falsa dependência no registro de destino dest . Mesmo que a instrução apenas escreva para ela, a instrução esperará até que o dest esteja pronto antes da execução.

Esta dependência não suporta apenas os 4 popcnt de uma iteração de loop único. Ele pode ser transmitido através de iterações de loop, tornando impossível para o processador paralelizar diferentes iterações de loop.

O unsigned versus uint64_t e outros ajustes não afetam diretamente o problema. Mas eles influenciam o alocador de registros que atribui os registradores às variáveis.

No seu caso, as velocidades são um resultado direto do que está preso à cadeia de dependência (falsa), dependendo do que o alocador de registro decidiu fazer.

  • 13 GB / s tem uma cadeia: popcnt - add - popcnt - popcnt → próxima iteração
  • 15 GB / s tem uma cadeia: popcnt - add - popcnt - add → próxima iteração
  • 20 GB / s tem uma cadeia: popcnt - popcnt → próxima iteração
  • 26 GB / s tem uma cadeia: popcnt - popcnt → próxima iteração

A diferença entre 20 GB / se 26 GB / s parece ser um artefato menor do endereçamento indireto. De qualquer maneira, o processador começa a atingir outros gargalos quando você atinge essa velocidade.

Para testar isso, usei o assembly in-line para ignorar o compilador e obter exatamente o assembly que quero. Eu também divido a variável count para quebrar todas as outras dependências que podem atrapalhar os benchmarks.

Aqui estão os resultados:

Sandy Bridge Xeon @ 3,5 GHz: (código de teste completo pode ser encontrado na parte inferior)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 12

Registradores diferentes: 18,6195 GB / s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

Mesmo registro: 8,49272 GB / s

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

Mesmo registro com corrente quebrada: 17.8869 GB / s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

Então, o que deu errado com o compilador?

Parece que nem o GCC nem o Visual Studio estão cientes de que popcnt tem uma dependência tão falsa. No entanto, essas falsas dependências não são incomuns. É apenas uma questão de saber se o compilador está ciente disso.

popcnt não é exatamente a instrução mais usada. Então não é realmente uma surpresa que um grande compilador possa perder algo assim. Também parece não haver documentação em lugar algum que mencione esse problema. Se a Intel não divulgá-lo, ninguém saberá até que alguém o encontre por acaso.

( Atualização: A partir da versão 4.9.2 , o GCC está ciente dessa falsa dependência e gera código para compensá-lo quando as otimizações são ativadas. Grandes compiladores de outros fornecedores, incluindo o Clang, MSVC e até mesmo o próprio ICC da Intel ainda não estão cientes esta errata microarquitetural e não irá emitir código que a compense.)

Por que a CPU tem uma dependência tão falsa?

Podemos apenas especular, mas é provável que a Intel tenha o mesmo tratamento para muitas instruções de dois operandos. Instruções comuns como add , sub usam dois operandos, ambos entradas. Então, a Intel provavelmente empurrou o popcnt para a mesma categoria para manter o design do processador simples.

Os processadores AMD não parecem ter essa falsa dependência.

O código de teste completo está abaixo para referência:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

Um benchmark igualmente interessante pode ser encontrado aqui: http://pastebin.com/kbzgL8si
Este benchmark varia o número de popcnt que estão na cadeia de dependência (falsa).

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s




compiler-optimization