c++ La sostituzione di un contatore di loop a 32 bit con 64 bit introduce scostamenti di prestazioni pazzi




performance optimization (8)

Stavo cercando il modo più veloce per popcount grandi matrici di dati. Ho riscontrato un effetto molto strano : la modifica della variabile del ciclo da unsigned a uint64_t ha uint64_t le prestazioni del 50% sul mio PC.

Il punto di riferimento

#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);
}

Come vedete, creiamo un buffer di dati casuali, con la dimensione di x megabyte dove x viene letto dalla riga di comando. Successivamente, iteriamo sul buffer e usiamo una versione srotolata del popcount x86 intrinseco per eseguire il popcount. Per ottenere un risultato più preciso, facciamo il popcount 10.000 volte. Misuriamo i tempi per il popcount. In lettere maiuscole, la variabile del ciclo interno è unsigned , nel caso in cui la variabile del ciclo interno è uint64_t . Ho pensato che questo non dovrebbe fare alcuna differenza, ma è vero il contrario.

I risultati (assolutamente pazzi)

Lo compilo in questo modo (versione g ++: Ubuntu 4.8.2-19ubuntu1):

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

Ecco i risultati sulla mia CPU Haswell Core i7-4770K a 3.50 GHz, eseguendo il test 1 (quindi 1 MB di dati casuali):

  • unsigned 41959360000 0.401554 sec 26.113 GB / s
  • uint64_t 41959360000 0,759822 sec 13,8003 GB / s

Come vedi, il throughput della versione uint64_t è solo la metà della versione unsigned ! Il problema sembra essere che viene generato un assembly diverso, ma perché? Per prima cosa ho pensato a un bug del compilatore, quindi ho provato clang++ (Ubuntu Clang versione 3.4-1ubuntu3):

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

Risultato: test 1

  • unsigned 41959360000 0.398293 sec 26.3267 GB / s
  • uint64_t 41959360000 0.680954 sec 15.3986 GB / s

Quindi, è quasi lo stesso risultato ed è ancora strano. Ma ora diventa super strano. Sostituisco la dimensione del buffer letto dall'input con una costante 1 , quindi cambio:

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

a

uint64_t size = 1 << 20;

Pertanto, il compilatore ora conosce la dimensione del buffer in fase di compilazione. Forse può aggiungere alcune ottimizzazioni! Ecco i numeri per g++ :

  • unsigned 41959360000 0.509156 sec 20.5944 GB / s
  • uint64_t 41959360000 0.508673 sec 20.6139 GB / s

Ora, entrambe le versioni sono ugualmente veloci. Tuttavia, i unsigned diventati ancora più lenti ! È sceso da 26 a 20 GB/s , sostituendo così una non costante con un valore costante che porta a una deoptimizzazione . Seriamente, non ho idea di cosa sta succedendo qui! Ma ora clang++ con la nuova versione:

  • unsigned 41959360000 0.677009 sec 15.4884 GB / s
  • uint64_t 41959360000 0.676909 sec 15.4906 GB / s

Aspetta cosa? Ora, entrambe le versioni sono passate al numero lento di 15 GB / s. Pertanto, la sostituzione di una non costante con un valore costante porta addirittura a un codice lento in entrambi i casi per Clang!

Ho chiesto a un collega con una CPU Ivy Bridge di compilare il mio benchmark. Ha ottenuto risultati simili, quindi non sembra essere Haswell. Poiché due compilatori producono risultati strani qui, anche questo non sembra essere un bug del compilatore. Non abbiamo una CPU AMD qui, quindi abbiamo potuto testare solo con Intel.

Più follia, per favore!

Prendi il primo esempio (quello con atol(argv[1]) ) e metti una static prima della variabile, cioè:

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

Ecco i miei risultati in g ++:

  • unsigned 41959360000 0.396728 sec 26.4306 GB / s
  • uint64_t 41959360000 0.509484 sec 20.5811 GB / s

Yay, ancora un'altra alternativa . Abbiamo ancora 26 GB / s u32 con u32 , ma siamo riusciti a ottenere u64 almeno dai 13 GB / s alla versione da 20 GB / s! Sul PC del mio collega, la versione u64 è diventata ancora più veloce della versione u32 , ottenendo il risultato più veloce di tutti. Purtroppo, questo funziona solo per g++ , clang++ non sembra interessarsi di static .

La mia domanda

Puoi spiegare questi risultati? Particolarmente:

  • Come può esserci una tale differenza tra u32 e u64 ?
  • In che modo la sostituzione di una non costante con una dimensione del buffer costante innesca un codice meno ottimale ?
  • In che modo l'inserimento della parola chiave static rende più veloce il loop di u64 ? Ancora più veloce del codice originale sul computer della mia collega!

So che l'ottimizzazione è un territorio difficile, tuttavia, non ho mai pensato che tali piccoli cambiamenti possano portare a una differenza del 100% nei tempi di esecuzione e che piccoli fattori come una dimensione del buffer costante possano nuovamente miscelare i risultati totalmente. Certo, voglio sempre avere la versione che è in grado di popcount 26 GB / s. L'unico modo affidabile che riesco a pensare è copiare l'assembly per questo caso e utilizzare l'assembly inline. Questo è l'unico modo per liberarmi di compilatori che sembrano impazzire con piccole modifiche. Cosa pensi? C'è un altro modo per ottenere il codice in modo affidabile con la maggior parte delle prestazioni?

Il disassemblaggio

Ecco lo smontaggio per i vari risultati:

26 GB / s versione da g ++ / u32 / non-const bufsize :

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

Versione da 13 GB / s da g ++ / u64 / non-const bufsize :

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

Versione da 15 GB / s da 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

Versione da 20 GB / s da 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

Versione da 15 GB / s da clang ++ / u32 & 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

È interessante notare che la versione più veloce (26 GB / s) è anche la più lunga! Sembra essere l'unica soluzione che usa la lea . Alcune versioni usano jb per saltare, altre usano jne . Ma a parte questo, tutte le versioni sembrano essere comparabili. Non vedo da dove potrebbe derivare un gap di prestazioni del 100%, ma non sono troppo esperto nel decifrare il montaggio. La versione più lenta (13 GB / s) sembra anche molto breve e buona. Qualcuno può spiegarlo?

Lezioni imparate

Non importa quale sarà la risposta a questa domanda; Ho imparato che nei loop molto caldi ogni dettaglio può avere importanza, anche i dettagli che non sembrano avere alcuna associazione con il codice di attivazione . Non ho mai pensato a quale tipo utilizzare per una variabile di loop, ma come vedi una modifica così piccola può fare una differenza del 100% ! Anche il tipo di archiviazione di un buffer può fare una grande differenza, come abbiamo visto con l'inserimento della parola chiave static davanti alla variabile di dimensione! In futuro, cercherò sempre varie alternative su vari compilatori quando scriverò loop davvero stretti e caldi che sono cruciali per le prestazioni del sistema.

La cosa interessante è anche che la differenza di prestazioni è ancora così alta anche se ho già srotolato il loop quattro volte. Quindi, anche se ti srotoli, puoi comunque essere colpito dalle principali deviazioni delle prestazioni. Abbastanza interessante.


Answer #1

Hai provato a spostare la fase di riduzione al di fuori del ciclo? In questo momento hai una dipendenza dai dati che non è davvero necessaria.

Provare:

  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];

Hai anche qualche strano aliasing in corso, che non sono sicuro sia conforme alle rigide regole di aliasing.


Answer #2

Non posso dare una risposta autorevole, ma fornire una panoramica di una probabile causa. Questo riferimento mostra chiaramente che per le istruzioni nel corpo del loop esiste un rapporto 3: 1 tra latenza e velocità effettiva. Mostra anche gli effetti della spedizione multipla. Dato che ci sono (dare o prendere) tre unità di interi nei moderni processori x86, è generalmente possibile inviare tre istruzioni per ciclo.

Quindi tra la pipeline di picco e le prestazioni di dispatch multipli e il fallimento di questi meccanismi, abbiamo un fattore di sei in termini di prestazioni. È abbastanza risaputo che la complessità del set di istruzioni x86 rende abbastanza facile il verificarsi di stravaganti rotture. Il documento sopra ha un grande esempio:

Le prestazioni di Pentium 4 per i turni a 64 bit sono davvero scarse. Lo spostamento a sinistra a 64 bit e tutti gli spostamenti a 32 bit hanno prestazioni accettabili. Sembra che il percorso dei dati dai 32 bit superiori ai 32 bit inferiori dell'ALU non sia ben progettato.

Personalmente mi sono imbattuto in uno strano caso in cui un hot loop funzionava molto più lentamente su un core specifico di un chip a quattro core (AMD se ricordo). In realtà, abbiamo ottenuto prestazioni migliori su una mappa: riduciamo i calcoli disattivando il core.

Qui la mia ipotesi è la contesa per le unità intere: che i popcnt , loop counter e indirizzi possono funzionare a malapena a pieno regime con il contatore ampio a 32 bit, ma il contatore a 64 bit causa stallo di contesa e pipeline. Dato che ci sono solo circa 12 cicli in totale, potenzialmente 4 cicli con dispacciamento multiplo, per esecuzione del corpo del loop, un singolo stallo potrebbe influenzare ragionevolmente il tempo di esecuzione di un fattore 2.

Il cambiamento indotto dall'uso di una variabile statica, che presumo causi solo un piccolo riordino delle istruzioni, è un altro indizio del fatto che il codice a 32 bit si trova in un punto critico per la contesa.

So che questa non è un'analisi rigorosa, ma è una spiegazione plausibile.


Answer #3

Ho provato questo con Visual Studio 2013 Express , utilizzando un puntatore invece di un indice, che ha velocizzato il processo un po '. Sospetto che questo sia dovuto al fatto che l'indirizzamento è offset + registro, invece di offset + registro + (registro << 3). Codice 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;
   }

codice assembly: r10 = bfrptr, r15 = bfrend, rsi = count, rdi = buffer, r13 = k:

[email protected]:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT [email protected]
        npad    4
[email protected]:
        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 [email protected]
[email protected]:
        dec     r13
        jne     SHORT [email protected]

Answer #4

Colpevole: dipendenza dai dati falsi (e il compilatore non ne è nemmeno a conoscenza)

Sui processori Sandy / Ivy Bridge e Haswell, l'istruzione:

popcnt  src, dest

sembra avere una falsa dipendenza dalla destinazione del registro di dest . Anche se l'istruzione scrive solo su di esso, l'istruzione attenderà che dest sia pronto prima dell'esecuzione.

Questa dipendenza non si limita a contenere i 4 popcnt da una singola iterazione del ciclo. Può sopportare iterazioni di loop rendendo impossibile per il processore di parallelizzare diverse iterazioni di loop.

Il unsigned contro uint64_t e altre modifiche non influiscono direttamente sul problema. Ma influenzano l'allocatore di registri che assegna i registri alle variabili.

Nel tuo caso, le velocità sono il risultato diretto di ciò che è bloccato alla (falsa) catena di dipendenze a seconda di ciò che l'allocatore di registri ha deciso di fare.

  • 13 GB / s ha una catena: popcnt - add - popcnt - popcnt → iterazione successiva
  • 15 GB / s ha una catena: popcnt - add - popcnt - add → iterazione successiva
  • 20 GB / s ha una catena: popcnt - popcnt → prossima iterazione
  • 26 GB / s ha una catena: popcnt - popcnt → prossima iterazione

La differenza tra 20 GB / se 26 GB / s sembra essere un artefatto secondario dell'indirizzamento indiretto. In entrambi i casi, il processore inizia a colpire altri colli di bottiglia una volta raggiunta questa velocità.

Per verificare ciò, ho utilizzato l'assembly inline per ignorare il compilatore e ottenere esattamente l'assembly che desidero. Ho anche diviso la variabile count per rompere tutte le altre dipendenze che potrebbero compromettere i benchmark.

Ecco i risultati:

Sandy Bridge Xeon @ 3,5 GHz: (codice di prova completo può essere trovato in fondo)

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

Registri diversi: 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

Stesso 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

Stesso registro con catena spezzata: 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

Quindi cosa è andato storto nel compilatore?

Sembra che né GCC né Visual Studio siano consapevoli del fatto che popcnt ha una dipendenza così falsa. Tuttavia, queste false dipendenze non sono rare. È solo questione di sapere se il compilatore ne è a conoscenza.

popcnt non è esattamente l'istruzione più usata. Quindi non è davvero una sorpresa che un compilatore importante possa perdere qualcosa del genere. Sembra anche che non ci sia documentazione da nessuna parte che menziona questo problema. Se Intel non lo rivela, allora nessuno al di fuori saprà fino a quando qualcuno vi si imbatterà per caso.

( Aggiornamento: A partire dalla versione 4.9.2 , GCC è a conoscenza di questa falsa dipendenza e genera codice per compensarlo quando vengono abilitate le ottimizzazioni. I principali compilatori di altri fornitori, inclusi Clang, MSVC e persino il proprio ICC di Intel non sono ancora a conoscenza di questo errore microarchitetturale e non emetterà codice che lo compensi).

Perché la CPU ha una dipendenza così falsa?

Possiamo solo ipotizzare, ma è probabile che Intel abbia la stessa gestione per molte istruzioni a due operandi. Istruzioni comuni come add , sub prendono due operandi che sono entrambi input. Quindi Intel probabilmente ha spinto popcnt nella stessa categoria per mantenere il design del processore semplice.

I processori AMD non sembrano avere questa falsa dipendenza.

Il codice di prova completo è sotto per riferimento:

#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);
}

Un benchmark altrettanto interessante può essere trovato qui: http://pastebin.com/kbzgL8si
Questo benchmark varia il numero di popcnt che si trovano nella catena di dipendenze (false).

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

Answer #5

TL; DR: usa invece __builtin intrinsics.

Sono stato in grado di generare gcc 4.8.4 (e anche 4.7.3 su gcc.godbolt.org) generare codice ottimale per questo usando __builtin_popcountll che usa la stessa istruzione di assemblaggio, ma non ha quel bug di falsa dipendenza.

Non sono sicuro al 100% del mio codice di benchmark, ma objdump uscita objdump sembra condividere le mie opinioni. Uso altri trucchi ( ++i vs i++ ) per fare in modo che il compilatore srotoli il ciclo per me senza alcuna istruzione movl (comportamento strano, devo dire).

risultati:

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

Codice di 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;
}

Opzioni di compilazione:

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

Versione GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Versione del kernel Linux:

3.19.0-58-generic

Informazioni sulla 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:

Answer #6

Questa non è una risposta, ma è difficile da leggere se inserisco i risultati nel commento.

Ottengo questi risultati con un Mac Pro ( Westmere 6-Core Xeon 3.33 GHz). L'ho compilato con clang -O3 -msse4 -lstdc++ a.cpp -oa (-O2 ottiene lo stesso risultato).

clang con 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 con uint64_t size=1<<20;

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

Ho anche provato a:

  1. Invertire l'ordine di test, il risultato è lo stesso in modo da escludere il fattore di cache.
  2. Avere l'istruzione for al contrario: for (uint64_t i=size/8;i>0;i-=4) . Questo dà lo stesso risultato e dimostra che la compilazione è abbastanza intelligente da non dividere la dimensione per 8 ogni iterazione (come previsto).

Ecco la mia ipotesi selvaggia:

Il fattore di velocità si compone di tre parti:

  • cache del codice: la versione di uint64_t ha dimensioni maggiori del codice, ma questo non ha effetto sulla mia CPU Xeon. Ciò rende la versione a 64 bit più lenta.

  • Istruzioni usate Si noti non solo il conteggio dei cicli, ma si accede al buffer con un indice a 32 e 64 bit sulle due versioni. L'accesso a un puntatore con un offset a 64 bit richiede un registro e un indirizzamento dedicati a 64 bit, mentre è possibile utilizzare immediatamente un offset a 32 bit. Ciò potrebbe rendere la versione a 32 bit più veloce.

  • Le istruzioni vengono emesse solo nella compilazione a 64 bit (ovvero, prefetch). Questo rende 64-bit più veloce.

I tre fattori coincidono con i risultati apparentemente contrastanti osservati.


Answer #7

Prima di tutto, prova a stimare il rendimento massimo - esamina https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf , in particolare, Appendice C.

Nel tuo caso, è la tabella C-10 che mostra che l'istruzione POPCNT ha latenza = 3 orologi e velocità effettiva = 1 orologio. La velocità effettiva mostra la velocità massima in clock (moltiplicata per frequenza core e 8 byte in caso di popcnt64 per ottenere il miglior numero possibile di larghezza di banda).

Ora esaminate cosa ha fatto il compilatore e sommate il throughput di tutte le altre istruzioni nel ciclo. Ciò fornirà la migliore stima possibile per il codice generato.

Infine, esaminate le dipendenze dei dati tra le istruzioni nel ciclo poiché imporranno un ritardo di latenza elevato anziché il throughput, quindi suddividete le istruzioni di singola iterazione sulle catene di flusso di dati e calcolate la latenza su di esse, quindi ingenuamente ricavate il massimo da esse. fornirà stime approssimative tenendo conto delle dipendenze del flusso di dati.

Tuttavia, nel tuo caso, solo scrivere codice nel modo giusto eliminerebbe tutte queste complessità. Invece di accumulare nella stessa variabile di conteggio, basta accumularne di diversi (come count0, count1, ... count8) e sommarli alla fine. O anche creare una serie di conteggi [8] e accumularsi ai suoi elementi - forse, sarà vettorizzato anche e otterrete un rendimento molto migliore.

PS e non eseguire mai il benchmark per un secondo, prima riscaldare il core quindi eseguire il ciclo per almeno 10 secondi o meglio 100 secondi. in caso contrario, testare il firmware di gestione dell'alimentazione e l'implementazione DVFS nell'hardware :)

PPS Ho ascoltato interminabili dibattiti su quanto tempo il benchmark dovrebbe davvero funzionare. Le persone più intelligenti chiedono addirittura perché 10 secondi non 11 o 12. Devo ammettere che in teoria è divertente. In pratica, devi solo eseguire il benchmark centinaia di volte di seguito e registrare le deviazioni. Quel IS divertente. La maggior parte delle persone cambia sorgente e si mette in panchina esattamente dopo UNA VOLTA per acquisire un nuovo record di prestazioni. Fai le cose giuste.

Non sei ancora convinto? Basta usare sopra la versione C del benchmark di assp1r1n3 ( https://.com/a/37026212/9706746 ) e provare 100 anziché 10000 nel ciclo di tentativi.

Il mio 7960X mostra, con RETRY = 100:

Conteggio: 203182300 Trascorso: 0,008385 secondi Velocità: 12,505379 GB / s

Conteggio: 203182300 Trascorso: 0,011063 secondi Velocità: 9,478225 GB / s

Conteggio: 203182300 Trascorso: 0,011188 secondi Velocità: 9.372327 GB / s

Conteggio: 203182300 Trascorso: 0.010393 secondi Velocità: 10.089252 GB / s

Conteggio: 203182300 Trascorso: 0,009076 secondi Velocità: 11,553283 GB / s

con RETRY = 10000:

Conteggio: 20318230000 Trascorso: 0,661791 secondi Velocità: 15,844519 GB / s

Conteggio: 20318230000 Trascorso: 0.665422 secondi Velocità: 15.758060 GB / s

Conteggio: 20318230000 Trascorso: 0.660983 secondi Velocità: 15.863888 GB / s

Conteggio: 20318230000 Trascorso: 0.665337 secondi Velocità: 15.760073 GB / s

Conteggio: 20318230000 Trascorso: 0.662138 secondi Velocità: 15.836215 GB / s

PPPS, infine, su "risposta accettata" e altro mistero ;-)

Usiamo la risposta di assp1r1n3 - ha core 2.5Ghz. POPCNT ha 1 clock throuhgput, il suo codice usa 64 bit popcnt. Quindi la matematica è 2.5 Ghz * 1 orologio * 8 byte = 20 GB / s per la sua configurazione. Sta vedendo 25Gb / s, forse a causa del turbo boost a circa 3Ghz.

Quindi vai su ark.intel.com e cerca i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70-GHz-?q=i7-4870HQ

Quel core potrebbe arrivare a 3.7 Ghz e la velocità massima reale è di 29.6 GB / s per il suo hardware. Allora, dov'è un altro 4GB / s? Forse, è speso per la logica del loop e altro codice circostante all'interno di ogni iterazione.

Ora dov'è questa falsa dipendenza? l'hardware funziona a velocità quasi massime. Forse la mia matematica è brutta, succede a volte :)

PPPPPS Le persone che suggeriscono HW errata è colpevole, quindi seguo il suggerimento e ho creato l'esempio in linea asm, vedi sotto.

Sulla mia 7960X, la prima versione (con uscita singola in cnt0) funziona a 11 MB / s, la seconda versione (con output in cnt0, cnt1, cnt2 e cnt3) funziona a 33 MB / s. E si potrebbe dire - voilà! è dipendenza di uscita.

OK, forse, il punto che ho fatto è che non ha senso scrivere codice come questo e non è un problema di dipendenza da output ma una generazione di codice stupida. Non stiamo testando l'hardware, stiamo scrivendo il codice per liberare le massime prestazioni. Potresti aspettarti che HW OOO debba rinominare e nascondere quelle "dipendenze di output" ma, squarcio, fai semplicemente le cose giuste e non troverai mai nessun mistero.

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;
}

Answer #8

Hai provato a passare -funroll-loops -fprefetch-loop-arrays a GCC?

Ottengo i seguenti risultati con queste ottimizzazioni aggiuntive:

[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






compiler-optimization