Le remplacement d'un compteur de boucles 32 bits par 64 bits introduit des écarts de performances fous avec _mm_popcnt_u64 sur les processeurs Intel

Je cherchais le moyen le plus rapide d'accéder à de popcountgrands tableaux de données. J'ai rencontré un effet très étrange : changer la variable de boucle de unsignedà a uint64_tfait chuter les performances de 50% sur mon PC.

La référence

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

Comme vous le voyez, nous créons un tampon de données aléatoires, avec la taille étant xmégaoctets où xest lu à partir de la ligne de commande. Ensuite, nous parcourons le tampon et utilisons une version déroulée de l' popcountintrinsèque x86 pour effectuer le popcount. Pour obtenir un résultat plus précis, nous faisons le popcount 10 000 fois. Nous mesurons les temps pour le popcount. En majuscule, la variable de boucle interne est unsigned, en minuscule, la variable de boucle interne est uint64_t. Je pensais que cela ne devrait pas faire de différence, mais le contraire est le cas.

Les résultats (absolument fous)

Je le compile comme ceci (version g ++: Ubuntu 4.8.2-19ubuntu1):

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

Voici les résultats sur mon processeur Haswell Core i7-4770K à 3,50 GHz, en cours d'exécution test 1(donc 1 Mo de données aléatoires):

• non signé 41959360000 0,401554 s 26,113 Go / s
• uint64_t 41959360000 0,759822 sec 13,8003 Go / s

Comme vous le voyez, le débit de la uint64_tversion n'est que la moitié de celui de la unsignedversion! Le problème semble être que différents assemblages sont générés, mais pourquoi? J'ai d'abord pensé à un bug du compilateur, j'ai donc essayé clang++(Ubuntu Clang version 3.4-1ubuntu3):

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

Résultat: test 1

• non signé 41959360000 0,398293 sec 26,3267 Go / s
• uint64_t 41959360000 0,680954 s 15,3986 Go / s

Donc, c'est presque le même résultat et c'est toujours étrange. Mais maintenant, ça devient super étrange. Je remplace la taille de la mémoire tampon qui a été lue depuis l'entrée par une constante 1, je change donc:

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

à

uint64_t size = 1 << 20;

Ainsi, le compilateur connaît maintenant la taille du tampon au moment de la compilation. Peut-être que cela peut ajouter des optimisations! Voici les chiffres pour g++:

• non signé 41959360000 0,509156 s 20,5944 Go / s
• uint64_t 41959360000 0,508673 sec 20,6139 Go / s

Maintenant, les deux versions sont également rapides. Cependant, cela est unsigned devenu encore plus lent ! Elle est passée de 26à 20 GB/s, remplaçant ainsi une valeur non constante par une valeur constante conduisant à une désoptimisation . Sérieusement, je n'ai aucune idée de ce qui se passe ici! Mais maintenant, clang++avec la nouvelle version:

• non signé 41959360000 0,677009 s 15,4884 Go / s
• uint64_t 41959360000 0,676909 sec 15,4906 Go / s

Attends quoi? Maintenant, les deux versions ont chuté au lent nombre de 15 Go / s. Ainsi, remplacer une non constante par une valeur constante conduit même à un code lent dans les deux cas pour Clang!

J'ai demandé à un collègue avec un processeur Ivy Bridge de compiler mon benchmark. Il a obtenu des résultats similaires, il ne semble donc pas s'agir de Haswell. Parce que deux compilateurs produisent des résultats étranges ici, il ne semble pas non plus être un bogue du compilateur. Nous n'avons pas de processeur AMD ici, nous ne pouvions donc tester qu'avec Intel.

Plus de folie, s'il vous plaît!

Prenez le premier exemple (celui avec atol(argv[1])) et mettez un staticavant la variable, c'est-à-dire:

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

Voici mes résultats en g ++:

• non signé 41959360000 0,396728 s 26,4306 Go / s
• uint64_t 41959360000 0,509484 sec 20,5811 Go / s

Oui, encore une autre alternative . Nous avons encore le rapide 26 Go / s avec u32, mais nous avons réussi à passer u64au moins de la version 13 Go / s à la version 20 Go / s! Sur le PC de mon collègue, la u64version est devenue encore plus rapide que la u32version, donnant le résultat le plus rapide de tous. Malheureusement, cela ne fonctionne que pour g++, clang++ne semble pas se soucier static.

Ma question

Pouvez-vous expliquer ces résultats? Surtout:

• Comment peut-il y avoir une telle différence entre u32et u64?
• Comment le remplacement d'un non constant par une taille de tampon constante peut-il déclencher un code moins optimal ?
• Comment l'insertion du staticmot - clé peut-elle u64accélérer la boucle? Encore plus rapide que le code d'origine sur l'ordinateur de mon collègue!

Je sais que l'optimisation est un territoire délicat, cependant, je n'ai jamais pensé que de si petits changements peuvent entraîner une différence de 100% dans le temps d'exécution et que de petits facteurs comme une taille de tampon constante peuvent à nouveau mélanger totalement les résultats. Bien sûr, je veux toujours avoir la version capable de popcount 26 Go / s. Le seul moyen fiable auquel je peux penser est de copier-coller l'assemblage pour ce cas et d'utiliser l'assemblage en ligne. C'est la seule façon dont je peux me débarrasser des compilateurs qui semblent devenir fous de petits changements. Qu'est-ce que tu penses? Existe-t-il un autre moyen d'obtenir de manière fiable le code avec la plupart des performances?

Le démontage

Voici le démontage des différents résultats:

Version 26 Go / s de g ++ / u32 / non const 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

Version 13 Go / s de g ++ / u64 / bufsize 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

Version 15 Go / s à partir de bufsize clang ++ / u64 / non const :

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

Version 20 Go / s de g ++ / u32 & u64 / const bufsize :

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

Version 15 Go / s de 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

Fait intéressant, la version la plus rapide (26 Go / s) est également la plus longue! Il semble que ce soit la seule solution qui utilise lea. Certaines versions utilisent jbpour sauter, d'autres utilisent jne. Mais à part cela, toutes les versions semblent être comparables. Je ne vois pas d'où pourrait provenir un écart de performance de 100%, mais je ne suis pas trop habile pour déchiffrer l'assemblage. La version la plus lente (13 Go / s) semble même très courte et bonne. Quelqu'un peut-il expliquer cela?

Leçons apprises

Quelle que soit la réponse à cette question, J'ai appris que dans les boucles vraiment chaudes, chaque détail peut être important, même les détails qui ne semblent pas avoir d'association avec le code chaud . Je n'ai jamais pensé au type à utiliser pour une variable de boucle, mais comme vous le voyez, un changement aussi mineur peut faire une différence de 100% ! Même le type de stockage d'un tampon peut faire une énorme différence, comme nous l'avons vu avec l'insertion du staticmot - clé devant la variable de taille! À l'avenir, je testerai toujours différentes alternatives sur différents compilateurs lors de l'écriture de boucles vraiment serrées et chaudes qui sont cruciales pour les performances du système.

La chose intéressante est aussi que la différence de performance est toujours aussi élevée même si j'ai déjà déroulé la boucle quatre fois. Ainsi, même si vous vous déroulez, vous pouvez toujours être frappé par des écarts de performances majeurs. Plutôt interessant.

Coupable: Fausse dépendance aux données (et le compilateur n'en est même pas conscient)

Sur les processeurs Sandy / Ivy Bridge et Haswell, l'instruction:

popcnt  src, dest

semble avoir une fausse dépendance sur le registre de destination dest. Même si l'instruction n'y écrit que, l'instruction attendra jusqu'à ce qu'elle destsoit prête avant de s'exécuter. Cette fausse dépendance est (maintenant) documentée par Intel comme erratum HSD146 (Haswell) et SKL029 (Skylake)

Skylake a corrigé cela pour lzcntettzcnt .
Cannon Lake (et Ice Lake) ont corrigé cela popcnt.
bsf/ bsravoir une véritable dépendance de sortie: sortie non modifiée pour entrée = 0. (Mais aucun moyen de profiter de cela avec les intrinsèques - seuls AMD le documente et les compilateurs ne l'exposent pas.)

(Oui, ces instructions s'exécutent toutes sur la même unité d'exécution ).

Cette dépendance ne se contente pas de retarder les 4 popcnts d'une seule itération de boucle. Il peut transporter des itérations de boucle, ce qui empêche le processeur de paralléliser différentes itérations de boucle.

Les ajustements unsignedvs. uint64_tet autres n'affectent pas directement le problème. Mais ils influencent l'allocateur de registres qui assigne les registres aux variables.

Dans votre cas, les vitesses sont le résultat direct de ce qui est collé à la (fausse) chaîne de dépendance en fonction de ce que l'allocateur de registre a décidé de faire.

• 13 Go / s a ​​une chaîne: popcnt- add- popcnt- popcnt→ prochaine itération
• 15 Go / s ont une chaîne: popcnt- add- popcnt- add→ prochaine itération
• 20 Go / s ont une chaîne: popcnt- popcnt→ itération suivante
• 26 Go / s a ​​une chaîne: popcnt- popcnt→ prochaine itération

La différence entre 20 Go / s et 26 Go / s semble être un artefact mineur de l'adressage indirect. De toute façon, le processeur commence à frapper d'autres goulots d'étranglement une fois que vous atteignez cette vitesse.

Pour tester cela, j'ai utilisé l'assembly en ligne pour contourner le compilateur et obtenir exactement l'assembly que je veux. J'ai également divisé la countvariable pour briser toutes les autres dépendances qui pourraient perturber les repères.

Voici les résultats:

Sandy Bridge Xeon @ 3,5 GHz: (le code de test complet se trouve en bas)

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

Différents registres: 18,6195 Go / 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

Même registre: 8.49272 Go / 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

Même registre avec chaîne cassée: 17,8869 Go / 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

Alors, qu'est-ce qui ne va pas avec le compilateur?

Il semble que ni GCC ni Visual Studio ne soient conscients de l'existence d' popcntune telle fausse dépendance. Néanmoins, ces fausses dépendances ne sont pas rares. C'est juste une question de savoir si le compilateur en est conscient.

popcntn'est pas exactement l'instruction la plus utilisée. Ce n'est donc pas vraiment une surprise qu'un compilateur majeur puisse manquer quelque chose comme ça. Il semble également qu'il n'y ait aucune documentation mentionnant ce problème. Si Intel ne le révèle pas, personne à l'extérieur ne le saura jusqu'à ce que quelqu'un le rencontre par hasard.

( Mise à jour: à partir de la version 4.9.2 , GCC est conscient de cette fausse dépendance et génère du code pour la compenser lorsque les optimisations sont activées. Les principaux compilateurs d'autres fournisseurs, y compris Clang, MSVC et même le propre ICC d'Intel, ne sont pas encore au courant cet erratum microarchitectural et n'émettra pas de code qui le compense.)

Pourquoi le CPU a-t-il une telle fausse dépendance?

Nous pouvons spéculer: il fonctionne sur la même unité d'exécution que bsf/ bsrqui n'ont une dépendance de sortie. ( Comment POPCNT est-il implémenté dans le matériel? ). Pour ces instructions, Intel documente le résultat entier pour input = 0 comme "non défini" (avec ZF = 1), mais le matériel Intel donne en fait une garantie plus forte pour éviter de casser les anciens logiciels: sortie non modifiée. AMD documente ce comportement.

Vraisemblablement, il était quelque peu gênant de rendre certains uops pour cette unité d'exécution dépendants de la sortie, mais pas d'autres.

Les processeurs AMD ne semblent pas avoir cette fausse dépendance.

Le code de test complet est ci-dessous pour référence:

#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 tout aussi intéressant peut être trouvé ici: http://pastebin.com/kbzgL8si
Ce benchmark fait varier le nombre de popcnts qui se trouvent dans la (fausse) chaîne de dépendance.

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

J'ai codé un programme C équivalent pour expérimenter, et je peux confirmer ce comportement étrange. De plus, gccestime que l'entier 64 bits (qui devrait probablement être de size_ttoute façon ...) est meilleur, car l'utilisation uint_fast32_toblige gcc à utiliser une uint 64 bits.

J'ai fait un peu de détour avec l'assemblage:
prenez simplement la version 32 bits, remplacez toutes les instructions / registres 32 bits par la version 64 bits dans la boucle de popcount interne du programme. Remarque: le code est aussi rapide que la version 32 bits!

C'est évidemment un hack, car la taille de la variable n'est pas vraiment 64 bits, car d'autres parties du programme utilisent toujours la version 32 bits, mais tant que la boucle popcount intérieure domine les performances, c'est un bon début .

J'ai ensuite copié le code de la boucle interne de la version 32 bits du programme, je l'ai piraté jusqu'à 64 bits, j'ai manipulé les registres pour en faire un remplacement de la boucle interne de la version 64 bits. Ce code s'exécute également aussi rapidement que la version 32 bits.

Ma conclusion est que c'est une mauvaise programmation des instructions par le compilateur, pas un avantage réel de vitesse / latence des instructions 32 bits.

(Avertissement: j'ai piraté l'assemblage, j'aurais pu casser quelque chose sans le remarquer. Je ne pense pas.)

Ce n'est pas une réponse, mais c'est difficile à lire si je mets les résultats en commentaire.

J'obtiens ces résultats avec un Mac Pro ( Westmere 6-Cores Xeon 3,33 GHz). Je l'ai compilé avec clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2 obtient le même résultat).

frapper avec 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

frapper avec uint64_t size=1<<20;

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

J'ai aussi essayé de:

1. Inversez l'ordre de test, le résultat est le même, il exclut donc le facteur de cache.
2. Avoir la fordéclaration en sens inverse: for (uint64_t i=size/8;i>0;i-=4). Cela donne le même résultat et prouve que la compilation est suffisamment intelligente pour ne pas diviser la taille par 8 à chaque itération (comme prévu).

Voici ma conjecture sauvage:

Le facteur de vitesse se décline en trois parties:

• cache de code: la uint64_tversion a une taille de code plus grande, mais cela n'a pas d'effet sur mon processeur Xeon. Cela rend la version 64 bits plus lente.

• Instructions utilisées. Notez non seulement le nombre de boucles, mais le tampon est accessible avec un index 32 bits et 64 bits sur les deux versions. L'accès à un pointeur avec un décalage 64 bits nécessite un registre et un adressage 64 bits dédiés, tandis que vous pouvez utiliser immédiat pour un décalage 32 bits. Cela peut rendre la version 32 bits plus rapide.

• Les instructions ne sont émises que sur la compilation 64 bits (c'est-à-dire la prélecture). Cela rend 64 bits plus rapide.

Les trois facteurs ensemble correspondent aux résultats apparemment contradictoires observés.

Je ne peux pas donner de réponse faisant autorité, mais fournir un aperçu d'une cause probable. Cette référence montre assez clairement que pour les instructions dans le corps de votre boucle, il existe un rapport 3: 1 entre la latence et le débit. Il montre également les effets de l'envoi multiple. Puisqu'il y a (donner ou prendre) trois unités entières dans les processeurs x86 modernes, il est généralement possible d'envoyer trois instructions par cycle.

Ainsi, entre le pic de pipeline et les performances de répartition multiple et l'échec de ces mécanismes, nous avons un facteur de performance de six. Il est assez bien connu que la complexité du jeu d'instructions x86 facilite assez la casse. Le document ci-dessus a un excellent exemple:

Les performances du Pentium 4 pour les décalages à droite 64 bits sont vraiment médiocres. Le décalage gauche 64 bits ainsi que tous les décalages 32 bits ont des performances acceptables. Il apparaît que le chemin de données des 32 bits supérieurs vers les 32 bits inférieurs de l'ALU n'est pas bien conçu.

J'ai personnellement rencontré un cas étrange où une boucle chaude fonctionnait considérablement plus lentement sur un cœur spécifique d'une puce à quatre cœurs (AMD si je me souviens bien). Nous avons en fait obtenu de meilleures performances sur un calcul de réduction de carte en désactivant ce cœur.

Ici, je suppose que la contention pour les unités entières est que le popcntcompteur de boucle et les calculs d'adresse peuvent tous à peine fonctionner à pleine vitesse avec le compteur large 32 bits, mais le compteur 64 bits provoque des conflits et des blocages de pipeline. Puisqu'il n'y a qu'environ 12 cycles au total, potentiellement 4 cycles avec répartition multiple, par exécution de corps de boucle, un décrochage unique pourrait raisonnablement affecter le temps d'exécution par un facteur de 2.

Le changement induit par l'utilisation d'une variable statique, qui, je suppose, ne provoque qu'une réorganisation mineure des instructions, est un autre indice que le code 32 bits est à un certain point de basculement.

Je sais que ce n'est pas une analyse rigoureuse, mais il est une explication plausible.

J'ai essayé cela avec Visual Studio 2013 Express , en utilisant un pointeur au lieu d'un index, ce qui a accéléré un peu le processus. Je soupçonne que c'est parce que l'adressage est offset + registre, au lieu de décalage + registre + (registre << 3). Code 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;
   }

code d'assemblage: 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

Avez-vous essayé de passer -funroll-loops -fprefetch-loop-arraysà GCC?

J'obtiens les résultats suivants avec ces optimisations supplémentaires:

[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

Avez-vous essayé de déplacer l'étape de réduction hors de la boucle? À l'heure actuelle, vous avez une dépendance aux données qui n'est vraiment pas nécessaire.

Essayer:

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

Vous avez également un aliasing étrange, dont je ne suis pas sûr qu'il soit conforme aux règles strictes d'alias.

TL; DR: utilisez __builtinplutôt des éléments intrinsèques; ils pourraient arriver à aider.

J'ai pu faire gcc4.8.4 (et même 4.7.3 sur gcc.godbolt.org) générer du code optimal pour cela en utilisant __builtin_popcountllqui utilise la même instruction d'assemblage, mais j'ai de la chance et arrive de faire du code qui n'a pas de façon inattendue longue dépendance portée par la boucle à cause du faux bogue de dépendance.

Je ne suis pas sûr à 100% de mon code d'analyse comparative, mais la objdumpsortie semble partager mes vues. J'utilise d'autres astuces ( ++ivs i++) pour faire la boucle de déroulement du compilateur pour moi sans aucune movlinstruction (comportement étrange, je dois dire).

Résultats:

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

Code de référence:

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

Options de compilation:

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

Version GCC:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Version du noyau Linux:

3.19.0-58-generic

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

Tout d'abord, essayez d'estimer les performances maximales - examinez https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf en particulier l'annexe C.

Dans votre cas, c'est le tableau C-10 qui montre que l'instruction POPCNT a une latence = 3 horloges et un débit = 1 horloge. Le débit affiche votre taux maximal en horloges (multipliez par la fréquence de base et 8 octets en cas de popcnt64 pour obtenir votre meilleur nombre de bande passante possible).

Examinez maintenant ce qu'a fait le compilateur et résumez les débits de toutes les autres instructions de la boucle. Cela donnera la meilleure estimation possible du code généré.

Enfin, examinez les dépendances des données entre les instructions dans la boucle car elles forceront un délai de latence élevé au lieu du débit - divisez donc les instructions d'une seule itération sur les chaînes de flux de données et calculez la latence à travers elles, puis récupérez naïvement le maximum d'entre elles. il donnera une estimation approximative en tenant compte des dépendances du flux de données.

Cependant, dans votre cas, le simple fait d'écrire du code de la bonne façon éliminerait toutes ces complexités. Au lieu d'accumuler dans la même variable de comptage, il vous suffit de les accumuler dans des variables différentes (comme count0, count1, ... count8) et de les additionner à la fin. Ou même créez un tableau de comptes [8] et accumulez-les dans ses éléments - peut-être, il sera même vectorisé et vous obtiendrez un bien meilleur débit.

PS et ne lancez jamais le benchmark pendant une seconde, commencez par réchauffer le cœur puis exécutez la boucle pendant au moins 10 secondes ou mieux 100 secondes. sinon, vous testerez le firmware de gestion de l'alimentation et l'implémentation DVFS dans le matériel :)

PPS J'ai entendu des débats interminables sur la durée réelle du benchmark. La plupart des gens intelligents demandent même pourquoi 10 secondes et non 11 ou 12. Je dois admettre que c'est drôle en théorie. En pratique, il vous suffit de lancer le benchmark cent fois de suite et d'enregistrer les écarts. C'EST drôle. La plupart des gens changent de source et exécutent le banc après cela exactement UNE FOIS pour capturer un nouveau record de performances. Faites bien les bonnes choses.

Pas encore convaincu? Utilisez simplement la version C ci-dessus du test de référence par assp1r1n3 ( https://stackoverflow.com/a/37026212/9706746 ) et essayez 100 au lieu de 10000 en boucle de nouvelle tentative.

Mon 7960X montre, avec RETRY = 100:

Nombre: 203182300 écoulé: 0,008385 secondes Vitesse: 12,505379 Go / s

Nombre: 203182300 écoulé: 0,011063 secondes Vitesse: 9,478225 Go / s

Nombre: 203182300 écoulé: 0,011188 secondes Vitesse: 9,372327 Go / s

Nombre: 203182300 écoulé: 0,010393 secondes Vitesse: 10,089252 Go / s

Nombre: 203182300 écoulé: 0,009076 secondes Vitesse: 11,553283 Go / s

avec RETRY = 10000:

Nombre: 20318230000 écoulé: 0,661791 seconde Vitesse: 15,844519 Go / s

Nombre: 20318230000 écoulé: 0,665422 seconde Vitesse: 15,758060 Go / s

Nombre: 20318230000 écoulé: 0,660983 secondes Vitesse: 15,863888 Go / s

Nombre: 20318230000 écoulé: 0,665337 seconde Vitesse: 15,760073 Go / s

Nombre: 20318230000 écoulé: 0,662138 seconde Vitesse: 15,836215 Go / s

PPPS Enfin, sur la "réponse acceptée" et autres mystères ;-)

Utilisons la réponse de assp1r1n3 - il a un coeur 2.5Ghz. POPCNT a 1 horloge de sortie, son code utilise popcnt 64 bits. Les mathématiques sont donc de 2,5 GHz * 1 horloge * 8 octets = 20 Go / s pour sa configuration. Il voit 25 Gb / s, peut-être en raison de l'augmentation du turbo à environ 3Ghz.

Allez donc sur ark.intel.com et recherchez i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-? Q = i7-4870HQ

Ce cœur pourrait fonctionner jusqu'à 3,7 GHz et le débit maximal réel est de 29,6 Go / s pour son matériel. Alors, où est un autre 4 Go / s? Peut-être, il est consacré à la logique de boucle et à tout autre code environnant à chaque itération.

Maintenant, où est cette fausse dépendance? le matériel fonctionne à un taux presque maximal. Peut-être que mes maths sont mauvaises, ça arrive parfois :)

PPPPPS Toujours les gens suggérant que les errata HW sont coupables, donc je suis la suggestion et j'ai créé un exemple asm en ligne, voir ci-dessous.

Sur mon 7960X, la première version (avec sortie unique vers cnt0) fonctionne à 11 Mo / s, la deuxième version (avec sortie vers cnt0, cnt1, cnt2 et cnt3) fonctionne à 33 Mo / s. Et on pourrait dire - le tour est joué! c'est la dépendance de sortie.

OK, peut-être, le point que j'ai fait valoir est que cela n'a pas de sens d'écrire du code comme celui-ci et ce n'est pas un problème de dépendance de sortie mais une génération de code stupide. Nous ne testons pas le matériel, nous écrivons du code pour libérer des performances maximales. Vous pourriez vous attendre à ce que HW OOO renomme et masque ces "dépendances de sortie" mais, cran, faites juste les bonnes choses et vous ne serez jamais confronté à aucun mystère.

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

D'accord, je veux apporter une petite réponse à l'une des sous-questions posées par le PO et qui ne semblent pas être abordées dans les questions existantes. Attention, je n'ai fait aucun test ni génération de code, ni désassemblage, je voulais juste partager une pensée pour que d'autres puissent l'exposer.

Pourquoi staticla performance change-t-elle?

La ligne en question: uint64_t size = atol(argv[1])<<20;

Réponse courte

Je regarderais l'assembly généré pour accéder sizeet voir s'il y a des étapes supplémentaires d'indirection de pointeur impliquées pour la version non statique.

Longue réponse

Puisqu'il n'y a qu'une seule copie de la variable, qu'elle ait été déclarée staticou non, et que la taille ne change pas, je théorise que la différence est l'emplacement de la mémoire utilisée pour sauvegarder la variable ainsi que l'endroit où elle est utilisée dans le code. vers le bas.

Ok, pour commencer avec l'évidence, rappelez-vous que toutes les variables locales (ainsi que les paramètres) d'une fonction disposent d'un espace sur la pile pour une utilisation en tant que stockage. Maintenant, évidemment, le cadre de pile de main () ne nettoie jamais et n'est généré qu'une seule fois. Ok, qu'en est-il de le faire static? Eh bien, dans ce cas, le compilateur sait réserver de l'espace dans l'espace de données global du processus afin que l'emplacement ne puisse pas être effacé par la suppression d'un cadre de pile. Mais quand même, nous n'avons qu'un seul emplacement alors quelle est la différence? Je soupçonne que cela a à voir avec la façon dont les emplacements de mémoire sur la pile sont référencés.

Lorsque le compilateur génère la table des symboles, il crée simplement une entrée pour une étiquette avec des attributs pertinents, comme la taille, etc. Il sait qu'il doit réserver l'espace approprié en mémoire mais ne choisit cet emplacement que plus tard dans processus après avoir fait une analyse de la vivacité et éventuellement enregistrer l'allocation Comment l'éditeur de liens sait-il alors quelle adresse fournir au code machine pour le code d'assemblage final? Il connaît l'emplacement final ou sait comment arriver à l'emplacement. Avec une pile, il est assez simple de se référer à un emplacement basé sur deux éléments, le pointeur sur le stackframe, puis un décalage dans le cadre. Ceci est essentiellement dû au fait que l'éditeur de liens ne peut pas connaître l'emplacement du stackframe avant l'exécution.