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

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  #include  #include  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(buffer); for (unsigned i=0; i<size; ++i) charbuffer[i] = rand()%256; uint64_t count,duration; chrono::time_point 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(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(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 randoms, com o tamanho sendo x megabytes, onde x é lido na linha de comando. Posteriormente, iteramos sobre 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 randoms 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 assembly 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

  • 41959360000 sem assinatura 0,39293 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 input com uma constante 1 , então eu mudo:

 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 compilation. 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, replace 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 a velocidade de 26 GB / s com o u32 , mas conseguimos obter o u64 pelo menos da u64 de 13 GB / s para a versão 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 desassembly

Aqui está a desassembly 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 assembly. 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.

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 aguardará 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 variables.

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: popcntaddpopcntpopcnt → próxima iteração
  • 15 GB / s tem uma cadeia: popcntaddpopcntadd → próxima iteração
  • 20 GB / s tem uma cadeia: popcntpopcnt → próxima iteração
  • 26 GB / s tem uma cadeia: popcntpopcnt → 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 desejado. Eu também divido a variável count para quebrar todas as outras dependencies 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 dependencies 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 inputs. 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  #include  #include  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(buffer); for (unsigned i=0;i 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(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(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(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 

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 assembly:
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 assembly, poderia ter quebrado algo sem perceber. Eu não penso assim.)

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 compilation é 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 compilation 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.

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 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.

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 

Eu tentei isso com o Visual Studio 2013 Express , usando um ponteiro em vez de um índice, que acelerou um pouco o processo. Eu suspeito que isso é porque o endereçamento é offset + register, ao invés de offset + register + (register << 3). Código C ++.

  uint64_t* bfrend = buffer+(size/8); uint64_t* bfrptr; // ... { startP = chrono::system_clock::now(); count = 0; for (unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with uint64_t for (bfrptr = buffer; bfrptr < bfrend;){ count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); } } endP = chrono::system_clock::now(); duration = chrono::duration_cast(endP-startP).count(); cout << "uint64_t\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } 

código de assembly: r10 = bfrptr, r15 = bfrend, rsi = contagem, rdi = buffer, r13 = k:

 $LL5@main: mov r10, rdi cmp rdi, r15 jae SHORT $LN4@main npad 4 $LL2@main: mov rax, QWORD PTR [r10+24] mov rcx, QWORD PTR [r10+16] mov r8, QWORD PTR [r10+8] mov r9, QWORD PTR [r10] popcnt rdx, rax popcnt rax, rcx add rdx, rax popcnt rax, r8 add r10, 32 add rdx, rax popcnt rax, r9 add rsi, rax add rsi, rdx cmp r10, r15 jb SHORT $LL2@main $LN4@main: dec r13 jne SHORT $LL5@main 

Você tentou mover a etapa de redução para fora do loop? Agora você tem uma dependência de dados que realmente não é necessária.

Experimentar:

  uint64_t subset_counts[4] = {}; for( unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with unsigned unsigned i=0; while (i < size/8) { subset_counts[0] += _mm_popcnt_u64(buffer[i]); subset_counts[1] += _mm_popcnt_u64(buffer[i+1]); subset_counts[2] += _mm_popcnt_u64(buffer[i+2]); subset_counts[3] += _mm_popcnt_u64(buffer[i+3]); i += 4; } } count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3]; 

Você também tem algum aliasing estranho acontecendo, que eu não tenho certeza se está em conformidade com as regras de aliasing estritas.

TL; DR: Use __builtin intrinsics.

Eu consegui fazer o gcc 4.8.4 (e até o 4.7.3 no gcc.godbolt.org) gerar um código ótimo para isso usando __builtin_popcountll que usa a mesma instrução de assembly, mas não tem esse bug de dependência falso.

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

Resultados:

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

Código de benchmarking:

 #include  #include  #include  #include  #include  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 \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 compilation:

 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 colors : 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: