Substituir um contador de loop de 32 bits por 64 bits introduz desvios de desempenho malucos com _mm_popcnt_u64 em CPUs Intel

Eu estava procurando o caminho mais rápido para popcountgrandes matrizes de dados. Eu encontrei um efeito muito estranho : alterar a variável de loop de unsignedpara uint64_treduzir o desempenho em 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ê vê, criamos um buffer de dados aleatórios, com o tamanho em xmegabytes, onde xé lido na linha de comando. Depois, iteramos sobre o buffer e usamos uma versão desenrolada do x86 popcountintrínseco para executar o popcount. Para obter um resultado mais preciso, fazemos a contagem 10.000 vezes. Medimos os tempos da contagem pop-up. Na maiúscula, a variável do loop interno é unsigned, na minúscula, a variável do loop interno é uint64_t. Eu pensei que isso não faria diferença, mas o oposto é o caso.

Os resultados (absolutamente loucos)

Eu compilei 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 da minha CPU Haswell Core i7-4770K a 3,50 GHz, executando test 1(portanto, 1 MB de dados aleatórios):

• não assinado 41959360000 0,401554 seg 26,113 GB / s
• uint64_t 41959360000 0,759822 seg 13,8003 GB / s

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

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

Resultado: test 1

• não assinado 41959360000 0,398293 seg 26,3267 GB / s
• uint64_t 41959360000 0.680954 seg 15.3986 GB / s

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

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

para

uint64_t size = 1 << 20;

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

• não assinado 41959360000 0,509156 seg 20,5944 GB / s
• uint64_t 41959360000 0.508673 seg 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 26para 20 GB/s, substituindo assim um não-constante por um valor constante, levando a uma desoptimização . Sério, eu não tenho idéia do que está acontecendo aqui! Mas agora clang++com a nova versão:

• não assinado 41959360000 0,677009 seg 15,4884 GB / s
• uint64_t 41959360000 0.676909 seg 15.4906 GB / s

Espere o que? Agora, as duas versões caíram para o número lento de 15 GB / s. Assim, a substituição de uma não-constante por um valor constante pode levar a um código lento nos dois casos para o Clang!

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, também não parece ser um bug do compilador. Não temos uma CPU AMD aqui, portanto só poderíamos testar com a Intel.

Mais loucura, por favor!

Pegue o primeiro exemplo (aquele com atol(argv[1])) e coloque a staticantes da variável, ou seja:

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

Aqui estão meus resultados em g ++:

• não assinado 41959360000 0,396728 seg 26,4306 GB / s
• uint64_t 41959360000 0.509484 seg 20.5811 GB / s

Sim, mais uma alternativa . Ainda temos os rápidos 26 GB / s u32, mas conseguimos passar u64pelo menos da versão de 13 GB / s para 20 GB / s! No PC do meu colega, a u64versão se tornou ainda mais rápida que a u32versão, produzindo o resultado mais rápido de todos. Infelizmente, isso só funciona g++, clang++não parece se importar static.

Minha pergunta

Você pode explicar esses resultados? Especialmente:

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

Sei que a otimização é um território complicado, no entanto, nunca pensei que essas pequenas mudanças possam levar a uma diferença de 100% no tempo de execução e que pequenos fatores, como um tamanho constante do buffer, podem novamente misturar totalmente os resultados. Claro, eu sempre quero ter a versão capaz de contabilizar 26 GB / s. A única maneira confiável de pensar é copiar e colar o assembly para este caso e usar o assembly embutido. 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 o código com mais desempenho de maneira confiável?

A desmontagem

Aqui está a desmontagem dos vários resultados:

Versão de 26 GB / s do bu ++ tamanho 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 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 clang ++ / u64 / non-const bufsize :

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 do g ++ / u32 e 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 dos clang ++ / u32 e u64 / const bufsize :

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 jbpara pular, outras usam jne. Além disso, todas as versões parecem comparáveis. Não vejo de onde se origina uma lacuna de desempenho de 100%, mas não sou muito hábil em decifrar montagem. A versão mais lenta (13 GB / s) parece muito curta e boa. Alguém pode explicar isso?

Lições aprendidas

Não importa qual será a resposta para esta pergunta; Aprendi que em loops realmente quentes todos os detalhes podem importar, mesmo detalhes que parecem não ter nenhuma 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 alteração tão pequena pode fazer uma diferença de 100% ! Até o tipo de armazenamento de um buffer pode fazer uma enorme diferença, como vimos com a inserção da staticpalavra - chave na frente da variável size! No futuro, sempre testarei 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 é também que a diferença de desempenho ainda é tão alta, embora eu já tenha desenrolado o loop quatro vezes. Portanto, mesmo se você desenrolar, ainda poderá sofrer 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 dependência falsa no registro de destino dest. Mesmo que a instrução apenas escreva nela, a instrução aguardará até que destesteja pronta antes de executar. Essa dependência falsa é (agora) documentada pela Intel como errata HSD146 (Haswell) e SKL029 (Skylake)

Skylake corrigiu isso para lzcntetzcnt .
O Lago Cannon (e o Ice Lake) resolveu isso popcnt.
bsf/ bsrtenho uma dependência de saída verdadeira: saída não modificada para input = 0. (Mas não há como tirar proveito disso com intrínsecos - apenas a AMD documenta e os compiladores não o expõem.)

(Sim, todas essas instruções são executadas na mesma unidade de execução ).

Essa dependência não sustenta apenas os 4 popcnts de uma iteração de loop único. Ele pode realizar iterações de loop, impossibilitando que o processador paralelize diferentes iterações de loop.

O unsignedvs. uint64_te outros ajustes não afetam diretamente o problema. Mas eles influenciam o alocador de registros que atribui os registros às variáveis.

No seu caso, as velocidades são um resultado direto do que está preso à cadeia de dependências (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 possui 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 forma, o processador começa a atingir outros gargalos quando você atinge essa velocidade.

Para testar isso, usei o assembly embutido para ignorar o compilador e obter exatamente o assembly que eu quero. Também dividi a countvariável para quebrar todas as outras dependências que podem interferir nos benchmarks.

Aqui estão os resultados:

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

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

Registros 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 sabem que popcntessa dependência é falsa. No entanto, essas dependências falsas não são incomuns. É apenas uma questão de saber se o compilador está ciente disso.

popcntnão é exatamente a instrução mais usada. Portanto, não é realmente uma surpresa que um grande compilador perca algo assim. Também parece não haver documentação em nenhum lugar que mencione esse problema. Se a Intel não divulgar, ninguém lá fora saberá até que alguém o encontre por acaso.

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

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

Podemos especular: ele é executado na mesma unidade de execução como bsf/ bsrque fazer têm uma dependência de saída. ( Como o POPCNT é implementado no hardware? ). Para essas instruções, a Intel documenta o resultado inteiro da entrada = 0 como "indefinido" (com ZF = 1), mas o hardware da Intel realmente oferece uma garantia mais forte para evitar a quebra de software antigo: saída não modificada. A AMD documenta esse comportamento.

Presumivelmente, era de alguma forma inconveniente fazer alguns upgrades para esta unidade de execução dependentes da saída, mas outros não.

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

Codifiquei um programa C equivalente para experimentar e posso confirmar esse comportamento estranho. Além do mais, gccacredita que o número inteiro de 64 bits (que provavelmente deve ser de size_tqualquer maneira ...) seja melhor, pois o uso uint_fast32_tfaz com que o gcc use um uint de 64 bits.

Eu pensei um pouco 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 de contagem interna do programa. Observação: o código é tão rápido quanto a versão de 32 bits!

Obviamente, isso é um truque, já que o tamanho da variável não é realmente de 64 bits, pois outras partes do programa ainda usam a versão de 32 bits, mas enquanto o loop interno de pop-count dominar o desempenho, esse é um bom começo. .

Em seguida, copiei o código do loop interno da versão de 32 bits do programa, cortei-o em 64 bits, mexi nos registros 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 esse é 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: cortei a montagem, poderia ter quebrado alguma coisa sem perceber. Acho que não.)

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

Eu obtenho esses resultados com um Mac Pro ( Westmere 6-Cores Xeon 3.33 GHz). Eu o compilei com clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2 obtém 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 de teste, o resultado é o mesmo e exclui o fator de cache.
2. Ter a fordeclaração em sentido inverso: 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 o esperado).

Aqui está o meu palpite:

O fator de velocidade vem em três partes:

• cache de código: a uint64_tversão possui um 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 utilizadas. Observe não apenas a contagem de loop, mas o buffer é acessado com um índice de 32 e 64 bits nas duas versões. O acesso a um ponteiro com deslocamento de 64 bits solicita um registro e endereçamento dedicados de 64 bits, 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 torna 64 bits mais rápido.

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

Não posso dar uma resposta autorizada, mas forneço uma visão geral de uma causa provável. Essa referência mostra claramente que, para as instruções no corpo do seu loop, há uma proporção de 3: 1 entre latência e taxa de transferência. Também mostra os efeitos do envio múltiplo. Como existem três unidades inteiras nos modernos processadores x86, geralmente é possível enviar três instruções por ciclo.

Portanto, entre o pico do pipeline e o desempenho de múltiplos despachos e a falha desses mecanismos, temos um fator de seis no desempenho. É bem sabido que a complexidade do conjunto de instruções x86 facilita bastante a ocorrência de quebra subtil. O documento acima tem um ótimo exemplo:

O desempenho do Pentium 4 para turnos à direita de 64 bits é realmente ruim. O deslocamento para a esquerda 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 ULA não foi bem projetado.

Pessoalmente, deparei-me com um caso estranho em que um hot loop era consideravelmente mais lento em um núcleo específico de um chip de quatro núcleos (AMD, se bem me lembro). Na verdade, obtivemos melhor desempenho em um cálculo de redução de mapa desativando esse núcleo.

Aqui, meu palpite é a contenção de unidades inteiras: que os popcntcálculos de contador de loop e endereço mal podem ser executados a toda velocidade com o contador de 32 bits de largura, 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 despacho múltiplo, por execução do corpo do loop, uma única paralisação pode afetar razoavelmente o tempo de execução por um fator de 2.

A mudança induzida pelo uso de uma variável estática, que, suponho, causa apenas uma pequena reordenação das instruções, é outra pista de que o código de 32 bits está em algum ponto de inflexão.

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

Eu tentei isso com o Visual Studio 2013 Express , usando um ponteiro em vez de um índice, o que acelerou um pouco o processo. Eu suspeito que isso ocorre porque o endereçamento é deslocamento + registro, em vez de deslocamento + registro + (registro << 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<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

código de montagem: r10 = bfrptr, r15 = bfrend, rsi = count, 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ê já tentou passar -funroll-loops -fprefetch-loop-arrayspara o GCC?

Recebo 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

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

Tentar:

  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 alias estranho, que não tenho certeza de que esteja em conformidade com as regras estritas de alias.

TL; DR: use __builtinintrínsecos; eles podem ajudar.

Consegui fazer com que o gcc4.8.4 (e até o 4.7.3 no gcc.godbolt.org) gerasse um código ideal para isso usando o __builtin_popcountllque usa a mesma instrução de montagem, mas tem sorte e cria um código que não possui um código inesperado dependência longa transportada por loop devido ao erro 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 nenhuma 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ção 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:

Primeiro, tente estimar o desempenho máximo - examine https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf , em particular, apêndice C.

No seu caso, é a tabela C-10 que mostra que a instrução POPCNT tem latência = 3 relógios e taxa de transferência = 1 relógio. A taxa de transferência mostra sua taxa máxima em relógios (multiplique pela freqüência principal e 8 bytes no caso de popcnt64 para obter o melhor número possível de largura de banda).

Agora examine o que o compilador fez e some as taxas de transferência de todas as outras instruções no loop. Isso fornecerá a melhor estimativa possível para o código gerado.

Por fim, observe as dependências de dados entre as instruções no loop, pois elas forçarão um atraso grande na latência em vez da taxa de transferência - portanto, divida as instruções de iteração única nas cadeias de fluxo de dados e calcule a latência entre elas e, ingenuamente, obtenha o máximo delas. fornecerá uma estimativa aproximada levando em consideração as dependências do fluxo de dados.

No entanto, no seu caso, apenas escrever o código da maneira correta eliminaria todas essas complexidades. Em vez de acumular para a mesma variável de contagem, apenas acumule para diferentes (como count0, count1, ... count8) e some-as no final. Ou até mesmo criar uma matriz de contagens [8] e acumular para seus elementos - talvez seja vetorizada mesmo e você obtenha uma taxa de transferência muito melhor.

PS e nunca execute benchmark por um segundo, primeiro aqueça o núcleo e depois execute o loop por pelo menos 10 segundos ou mais 100 segundos. caso contrário, você testará o firmware de gerenciamento de energia e a implementação do DVFS no hardware :)

PPS Eu ouvi debates intermináveis ​​sobre quanto tempo o benchmark realmente deveria ser executado. A maioria das pessoas mais inteligentes está perguntando por que 10 segundos, não 11 ou 12. Devo admitir que isso é engraçado em teoria. Na prática, basta executar o benchmark centenas de vezes seguidas e registrar desvios. Isso é engraçado. A maioria das pessoas muda de fonte e corre depois disso exatamente uma vez para capturar um novo recorde de desempenho. Faça as coisas certas direito.

Ainda não está convencido? Basta usar a versão C do benchmark acima por assp1r1n3 ( https://stackoverflow.com/a/37026212/9706746 ) e tente 100 em vez de 10000 no loop de nova tentativa.

Meus 7960X mostram, com RETRY = 100:

Contagem: 203182300 Decorrido: 0.008385 segundos Velocidade: 12.505379 GB / s

Contagem: 203182300 Decorrido: 0,011063 segundos Velocidade: 9,478225 GB / s

Contagem: 203182300 Decorrido: 0,011188 segundos Velocidade: 9,372327 GB / s

Contagem: 203182300 Decorrido: 0,010393 segundos Velocidade: 10,089252 GB / s

Contagem: 203182300 Decorrido: 0.009076 segundos Velocidade: 11.553283 GB / s

com RETRY = 10000:

Contagem: 20318230000 Decorrido: 0.661791 segundos Velocidade: 15.844519 GB / s

Contagem: 20318230000 Decorrido: 0.665422 segundos Velocidade: 15.758060 GB / s

Contagem: 20318230000 Decorrido: 0.660983 segundos Velocidade: 15.863888 GB / s

Contagem: 20318230000 Decorrido: 0.665337 segundos Velocidade: 15.760073 GB / s

Contagem: 20318230000 Decorrido: 0.662138 segundos Velocidade: 15.836215 GB / s

PPPS Finalmente, em "resposta aceita" e outros mistérios ;-)

Vamos usar a resposta do assp1r1n3 - ele tem um núcleo de 2.5Ghz. O POPCNT possui 1 relógio através da saída, seu código está usando o popcnt de 64 bits. Portanto, a matemática é de 2,5 Ghz * 1 relógio * 8 bytes = 20 GB / s para sua configuração. Ele está vendo 25Gb / s, talvez devido ao aumento do turbo em torno de 3Ghz.

Portanto, acesse ark.intel.com e procure o i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-? Q = i7-4870HQ

Esse núcleo pode rodar até 3,7 Ghz e a taxa máxima real é de 29,6 GB / s para seu hardware. Então, onde estão outros 4 GB / s? Talvez seja gasto com lógica de loop e outro código circundante em cada iteração.

Agora, onde está essa falsa dependência? o hardware é executado quase na taxa de pico. Talvez minha matemática esteja ruim, às vezes acontece :)

PPPPPS Ainda as pessoas que sugerem erratas de HW são as culpadas, por isso sigo as sugestões e criei o exemplo inline asm, veja abaixo.

No meu 7960X, a primeira versão (com saída única para cnt0) é executada em 11MB / s, a segunda versão (com saída para cnt0, cnt1, cnt2 e cnt3) é executada em 33MB / s. E pode-se dizer - voila! é dependência de saída.

OK, talvez, o argumento que afirmei é que não faz sentido escrever código como este e não é problema de dependência de saída, mas geração de código estúpido. Não estamos testando hardware, estamos escrevendo código para liberar o desempenho máximo. Você pode esperar que o HW OOO renomeie e oculte essas "dependências de saída", mas, corte, faça as coisas certas corretamente e você nunca enfrentará nenhum mistério.

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) 
{
    uint64_t cnt0, cnt1, cnt2, cnt3;
    cnt0 = cnt1 = cnt2 = cnt3 = 0;
    uint64_t val = buf[0];
    #if 0
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0)
        : "q" (val)
        :
        );
    #else
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %5, %1\n\t"
            "popcnt %5, %2\n\t"
            "popcnt %5, %3\n\t"
            "popcnt %5, %4\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
        : "q" (val)
        :
        );
    #endif
    return cnt0;
}

Ok, quero fornecer uma pequena resposta para uma das sub-perguntas que o OP fez e que não parecem ser abordadas nas perguntas existentes. Advertência, eu não fiz nenhum teste, geração ou desmontagem de código, só queria compartilhar um pensamento para que outros possam expor.

Por que isso staticaltera o desempenho?

A linha em questão: uint64_t size = atol(argv[1])<<20;

Resposta curta

Eu examinaria o assembly gerado para acessar sizee veria se há etapas extras de indireto de ponteiro envolvidas para a versão não estática.

Resposta longa

Como existe apenas uma cópia da variável, declarada staticou não, e o tamanho não muda, teorizo ​​que a diferença é o local da memória usada para fazer backup da variável e o local em que ela é usada no código. baixa.

Ok, para começar com o óbvio, lembre-se de que todas as variáveis ​​locais (junto com os parâmetros) de uma função recebem espaço na pilha para uso como armazenamento. Agora, obviamente, o quadro de pilha para main () nunca limpa e é gerado apenas uma vez. Ok, que tal fazer isso static? Bem, nesse caso, o compilador sabe reservar espaço no espaço de dados global do processo para que o local não possa ser limpo com a remoção de um quadro de pilha. Mas ainda assim, temos apenas um local, então qual é a diferença? Suspeito que tenha a ver com a referência de locais de memória na pilha.

Quando o compilador está gerando a tabela de símbolos, ele apenas faz uma entrada para um rótulo junto com atributos relevantes, como tamanho, etc. Ele sabe que deve reservar o espaço apropriado na memória, mas na verdade não escolhe esse local até um pouco mais tarde. depois de fazer uma análise de vivacidade e possivelmente registrar a alocação. Como, então, o vinculador sabe qual endereço fornecer ao código de máquina para o código de montagem final? Ele conhece o local final ou sabe como chegar ao local. Com uma pilha, é bastante simples se referir a um local com base em dois elementos, o ponteiro para o quadro da pilha e depois um deslocamento no quadro. Isso ocorre basicamente porque o vinculador não pode saber a localização do stackframe antes do tempo de execução.