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

1424

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.

gexicida
fonte
8
Tantos comentários! Você pode vê-los no chat e até deixar o seu lá, se quiser, mas por favor não adicione mais aqui!
precisa
3
Consulte também a Edição 62011 do GCC, Dependência de dados falsos na instrução popcnt . Alguém o forneceu, mas parece ter sido perdido durante as limpezas.
JWW
Não sei dizer, mas é uma das desmontagens da versão com a estática? Caso contrário, você pode editar a postagem e adicioná-la?
62719 Kelly S. French

Respostas:

1552

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
Mysticial
fonte
3
Oi pessoal! Muitos comentários anteriores aqui; Antes de deixar um novo, revise o arquivo .
precisa
1
@ JustinL.it parece com esta questão em particular é fixa em Clang a partir de 7,0
Dan M.
@ PeterCordes Eu não acho que seja tanto a unidade de execução quanto o agendador. É o agendador que rastreia dependências. E para fazer isso, as instruções são agrupadas em um número de "classes de instruções", cada uma das quais é tratada de forma idêntica pelo planejador. Assim, todas as instruções de 3 ciclos "slow-int" foram lançadas na mesma "classe" para fins de programação de instruções.
Mysticial 27/11/19
@Mysticial: Você ainda acha isso agora? Isso é plausível, mas imul dst, src, immnão tem dependência de saída e nem lento lea. Nem isso pdep, mas é codificado em VEX com 2 operandos de entrada. Concordou que não é a própria unidade de execução que causa o dep falso; isso depende do estágio RAT e emitir / renomear, pois renomeia os operandos de registro arquitetural em registros físicos. Presumivelmente, ele precisa de uma tabela de código de opção uop -> padrão de dependência e opções de porta, e agrupar todos os uops para a mesma unidade de execução simplifica essa tabela. Foi isso que eu quis dizer com mais detalhes.
Peter Cordes
Deixe-me saber se você deseja que eu edite isso em sua resposta ou se deseja voltar a dizer algo como o que você disse originalmente sobre o agendador. O fato de a SKL ter eliminado o dep falso para lzcnt / tzcnt, mas não popcnt, deve nos dizer algo, mas IDK o quê. Outro sinal possível de que ele seja renomeado / relacionado ao RAT é que o SKL lamina um modo de endereçamento indexado como fonte de memória para lzcnt / tzcnt, mas não popcnt. Obviamente, a unidade de renomeação precisa criar uops que o back-end pode representar.
Peter Cordes
50

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

EOF
fonte
1
“Além disso, o gcc acredita que o número inteiro de 64 bits […] seja melhor, pois o uso de uint_fast32_t faz com que o gcc use um uint de 64 bits.” Infelizmente, e para meu pesar, não há mágica nem introspecção profunda de código por trás desses tipos. Ainda estou para vê-los de outra maneira que não como typedefs únicos para todos os locais possíveis e todos os programas em toda a plataforma. Provavelmente, já se pensou bastante sobre a escolha exata dos tipos, mas a definição única para cada um deles não pode se encaixar em todos os aplicativos que já existirão. Algumas leituras adicionais: stackoverflow.com/q/4116297 .
Keno
2
@ Keno Isso porque sizeof(uint_fast32_t)tem que ser definido. Se você permitir que não seja, poderá fazer esse truque, mas isso só pode ser conseguido com uma extensão do compilador.
wizzwizz4
25

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.

Interrupção não mascarável
fonte
4
Interessante, você pode adicionar versão e sinalizadores do compilador? O melhor é que, na sua máquina, os resultados são invertidos, ou seja, o uso do u64 é mais rápido . Até agora, nunca pensei em qual tipo minha variável de loop possui, mas parece que tenho que pensar duas vezes na próxima vez :).
Gexicide
2
@gexicide: Eu não chamaria um salto de 16.8201 para 16.8126, tornando-o "mais rápido".
user541686
2
@ Mehrdad: O salto que eu quero dizer é aquele entre 12.9e 16.8, portanto, unsignedé mais rápido aqui. Na minha referência, o oposto foi o caso, ou seja, 26 para unsigned, 15 parauint64_t
gexicide
@gexicide Você notou a diferença no endereçamento do buffer [i]?
Interrupção não mascarável
@Calvin: Não, o que você quer dizer?
Gexicide
10

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.

Gene
fonte
2
Infelizmente, desde (Core 2?) Praticamente não há diferenças de desempenho entre operações inteiras de 32 e 64 bits, exceto para multiplicar / dividir - que não estão presentes neste código.
Mysticial
@Gene: Observe que todas as versões armazenam o tamanho em um registro e nunca o leem da pilha no loop. Assim, o cálculo do endereço não pode estar na mistura, pelo menos não dentro do loop.
Gexicide
@ Gene: explicação interessante de fato! Mas isso não explica os principais pontos do WTF: que 64 bits é mais lento que 32 bits devido a paradas no pipeline é uma coisa. Mas, se esse for o caso, a versão de 64 bits não deve ser confiável mais lenta que a de 32 bits? Em vez disso, três compiladores diferentes emitem código lento mesmo para a versão de 32 bits ao usar o tamanho do buffer constante em tempo de compilação; alterar o tamanho do buffer para estático novamente muda completamente as coisas. Houve até um caso na máquina de meus colegas (e na resposta de Calvin) em que a versão de 64 bits é consideravelmente mais rápida! Parece ser absolutamente imprevisível ..
gexicide
@Mysticial Esse é o meu ponto. Não há diferença de pico de desempenho quando não há contenção de IU, tempo de barramento, etc. A referência mostra isso claramente. A disputa faz tudo diferente. Aqui está um exemplo da literatura do Intel Core: "Uma nova tecnologia incluída no design é o Macro-Ops Fusion, que combina duas instruções x86 em uma única micro-operação. Por exemplo, uma sequência de código comum como uma comparação seguida por um salto condicional se tornaria uma única microoperação. Infelizmente, essa tecnologia não funciona no modo de 64 bits ". Portanto, temos uma proporção de 2: 1 na velocidade de execução.
Gene
@gexicide Entendo o que você está dizendo, mas está deduzindo mais do que eu quis dizer. Estou dizendo que o código que está executando o mais rápido é manter o pipeline e as filas de despacho cheias. Esta condição é frágil. Pequenas alterações, como adicionar 32 bits ao fluxo total de dados e reordenar as instruções, são suficientes para quebrá-lo. Em suma, a afirmação do OP de que brincar e testar é o único caminho a seguir está correta.
Gene
10

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
rcgldr
fonte
9

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
Dangelov
fonte
3
Mas, ainda assim, seus resultados são totalmente estranhos (primeiro não assinados mais rapidamente, depois uint64_t mais rápido), pois o desenrolar não corrige o principal problema da falsa dependência.
Gexicide
7

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.

Ben Voigt
fonte
2
Essa foi a primeira coisa que fiz depois de ler a pergunta. Quebrar a cadeia de dependência. Como se viu, a diferença de desempenho não muda (pelo menos no meu computador - Intel Haswell com GCC 4.7.3).
Nils Pipenbrinck
1
@ BenVoigt: É compatível com aliasing estrito. void*e char*são os dois tipos que podem ser alternativos, pois são considerados essencialmente "indicadores de algum pedaço de memória"! Sua ideia sobre a remoção de dependência de dados é boa para otimização, mas não responde à pergunta. E, como diz o @NilsPipenbrinck, isso não parece mudar nada.
Gexicide
@gexicide: A regra estrita de aliasing não é simétrica. Você pode usar char*para acessar a T[]. Você não pode usar com segurança a T*para acessar a char[]e seu código parece fazer isso.
Ben Voigt
@BenVoigt: Então você nunca poderia ter mallocuma variedade de coisas, pois o malloc retorna void*e o interpreta como T[]. E tenho certeza disso void*e char*tinha a mesma semântica em relação a aliasing estrito. No entanto, eu acho que isso é bastante offtopic aqui :)
gexicide
1
Pessoalmente acho que o caminho certo éuint64_t* buffer = new uint64_t[size/8]; /* type is clearly uint64_t[] */ char* charbuffer=reinterpret_cast<char*>(buffer); /* aliasing a uint64_t[] with char* is safe */
Ben Voigt
6

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:
assp1r1n3
fonte
3
É uma sorte que, por -funroll-loopsacaso, crie código que não afunde em uma cadeia de dependências transportada por loop criada pelo popcntdep falso. Usar uma versão antiga do compilador que não conhece a falsa dependência é um risco. Sem -funroll-loops, o loop do gcc 4.8.5 afunilará a latência popcnt em vez da taxa de transferência, porque é importanterdx . O mesmo código, compilado pelo gcc 4.9.3, adiciona um xor edx,edxpara quebrar a cadeia de dependência.
Peter Cordes
3
Com os compiladores antigos, seu código ainda estaria vulnerável à mesma variação de desempenho que o OP experimentava: mudanças aparentemente triviais poderiam tornar o gcc algo lento porque não fazia ideia de que causaria um problema. Encontrar algo que funcione em um caso em um compilador antigo não é a questão.
Peter Cordes
2
Para constar, x86intrin.has _mm_popcnt_*funções do GCC são invólucros forçados à volta do__builtin_popcount* ; o inlining deve fazer um exatamente equivalente ao outro. Duvido muito que você veja alguma diferença que possa ser causada pela alternância entre eles.
ShadowRanger
-2

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;
}
Kovalex
fonte
Se você está cronometrando nos ciclos de clock do núcleo (em vez de segundos), 1 segundo é tempo de sobra para um pequeno loop vinculado à CPU. Até 100ms é bom para encontrar grandes diferenças ou verificar os contadores de desempenho quanto à contagem de uop. Especialmente em um Skylake, onde o gerenciamento do estado P do hardware permite aumentar a velocidade máxima do relógio em microssegundos após o início do carregamento.
22818 Peter Cordes
O clang pode se auto-vetorizar __builtin_popcountlcom o AVX2 vpshufbe não precisa de vários acumuladores na fonte C para fazer isso. Não tenho certeza _mm_popcnt_u64; que só podem se auto-vetorizar com AVX512-VPOPCNT. (Veja Counting bits 1 (contagem da população) em grandes volumes de dados usando AVX-512 ou AVX-2 /)
Peter Cordes
Mas, enfim, olhar o manual de otimização da Intel não ajudará: como mostra a resposta aceita, o problema é uma dependência inesperada da saída popcnt. Isso está documentado nas erratas da Intel para algumas de suas microarquiteturas recentes, mas acho que não estava na época. Sua análise dep-chain falhará se houver inesperadas dependências falsas, portanto, essa resposta é um bom conselho genérico, mas não aplicável aqui.
Peter Cordes
1
Você está brincando comigo? Não preciso "acreditar" em coisas que posso medir experimentalmente com contadores de desempenho em um loop asm escrito à mão. São apenas fatos. Eu testei e o Skylake corrigiu a dependência falsa para lzcnt/ tzcnt, mas não para popcnt. Veja SKL029 errata da Intel em intel.com/content/dam/www/public/us/en/documents/... . Além disso, gcc.gnu.org/bugzilla/show_bug.cgi?id=62011 é "resolvido corrigido", não "inválido". Não há base para sua alegação de que não há dependência de saída no HW.
Peter Cordes
1
Se você criar um loop simples como popcnt eax, edx/ dec ecx / jnz, esperaria que ele fosse executado a 1 por relógio, com gargalo na taxa de transferência popcnt e na taxa de transferência de ramificação obtida. Mas na verdade, ele é executado apenas em 1 por 3 relógios com gargalo na popcntlatência para substituir repetidamente o EAX, mesmo que você esperasse que fosse somente gravação. Você tem um Skylake, então você pode tentar você mesmo.
Peter Cordes
-3

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.

Kelly S. Francês
fonte
2
Parece-me muito mais provável que o uso staticalterasse a alocação do registro para a função de uma maneira que afetasse a falsa dependência de saída das popcntCPUs Intel em que o OP estava testando, com um compilador que não sabia evitá-las. (Como esse buraco de desempenho nas CPUs Intel ainda não havia sido descoberto.) Um compilador pode manter uma staticvariável local em um registro, assim como uma variável de armazenamento automático, mas se elas não otimizarem, assumindo que mainapenas sejam executadas uma vez, isso afetará código-gen (porque o valor é definido por apenas a primeira chamada.)
Peter Cordes
1
De qualquer forma, a diferença de desempenho entre os modos [RIP + rel32]e [rsp + 42]endereçamento é bastante insignificante para a maioria dos casos. cmp dword [RIP+rel32], immediatenão posso micro-fusível em uma única carga + cmp uop, mas não acho que isso seja um fator. Como eu disse, os loops internos provavelmente permanecem em um registro, mas ajustar o C ++ pode significar diferentes opções do compilador.
Peter Cordes