c++ - tutorial - variable google tag manager




Le remplacement d'une variable de comptage de boucle 32 bits par 64 bits introduit des écarts de performance fous (6)

Avez-vous essayé de déplacer l'étape de réduction en dehors de la boucle? En ce moment vous avez une dépendance de 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 bizarre, que je ne suis pas sûr est conforme aux règles strictes d'aliasing.

https://code.i-harness.com

Je cherchais le moyen le plus rapide de popcount grandes baies de données. J'ai rencontré un effet très étrange : Changer la variable loop de unsigned à uint64_t fait uint64_t les performances de 50% sur mon PC.

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

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

Les résultats (absolument dingues)

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 du test 1 (donc 1 Mo de données aléatoires):

  • non signé 41959360000 0.401554 sec 26.113 Go / s
  • uint64_t 41959360000 0,759822 sec 13,8003 Go / s

Comme vous le voyez, le débit de la version uint64_t n'est que la moitié de la version unsigned ! Le problème semble être que l'assemblage différent est généré, mais pourquoi? D'abord, j'ai pensé à un bug de compilateur, donc j'ai 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 sec 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 tampon qui a été lue de l'entrée par une constante 1 , donc je change:

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

à

uint64_t size = 1 << 20;

Ainsi, le compilateur connaît maintenant la taille de la mémoire tampon au moment de la compilation. Peut-être qu'il peut ajouter quelques optimisations! Voici les chiffres pour g++ :

  • non signé 41959360000 0.509156 sec 20.5944 Go / s
  • uint64_t 41959360000 0.508673 sec 20.6139 Go / s

Maintenant, les deux versions sont également rapides. Cependant, le unsigned est encore plus lent ! Il est passé de 26 à 20 GB/s , remplaçant ainsi une 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, pour clang++ avec la nouvelle version:

  • non signé 41959360000 0,677009 sec 15,4884 Go / s
  • uint64_t 41959360000 0.676909 sec 15.4906 Go / s

Attends quoi? Maintenant, les deux versions ont chuté au nombre lent de 15 Go / s. Ainsi, remplacer une 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 CPU Ivy Bridge de compiler mon benchmark. Il a obtenu des résultats similaires, donc ça ne semble pas être Haswell. Parce que deux compilateurs produisent des résultats étranges ici, il ne semble pas non plus être un bogue de compilateur. Nous n'avons pas de CPU AMD ici, donc nous n'avons pu tester qu'avec Intel.

Plus de folie, s'il te plait!

Prenons le premier exemple (celui avec atol(argv[1]) ) et mettons un static devant la variable, ie:

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

Voici mes résultats en g ++:

  • non signé 41959360000 0,396728 sec 26,4306 Go / s
  • uint64_t 41959360000 0.509484 sec 20.5811 Go / s

Yay, encore une autre alternative . Nous avons toujours les 26 Go / s u32 avec u32 , mais nous avons réussi à obtenir u64 au moins de la version 13 Go / s à la version 20 Go / s! Sur le PC de mon u64 , la version u64 est devenue encore plus rapide que la version u32 , donnant le résultat le plus rapide de tous. Malheureusement, cela ne fonctionne que pour g++ , clang++ ne semble pas se soucier de static .

Ma question

Pouvez-vous expliquer ces résultats? Notamment:

  • Comment peut-il y avoir une telle différence entre u32 et u64 ?
  • Comment remplacer un non-constant par une taille de buffer constante déclenche un code moins optimal ?
  • Comment l'insertion du mot-clé static -elle rendre la boucle u64 plus rapide? Encore plus rapide que le code original sur l'ordinateur de mon collègue!

Je sais que l'optimisation est un domaine délicat, cependant, je n'ai jamais pensé que de tels petits changements peuvent entraîner une différence de temps d'exécution de 100% et que de petits facteurs comme une taille de tampon constante peuvent à nouveau mélanger les résultats. Bien sûr, je veux toujours avoir la version capable de générer 26 Go / s. Le seul moyen fiable que je peux penser est de copier coller l'ensemble pour ce cas et utiliser l'assemblage en ligne. C'est la seule façon de 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 le plus de performances?

Le démontage

Voici le démontage pour les différents résultats:

26 Go / s version de 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

13 Go / s version de 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

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

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 aussi la plus longue! Il semble être la seule solution qui utilise lea . Certaines versions utilisent jb pour sauter, d'autres utilisent jne . Mais en dehors de cela, toutes les versions semblent être comparables. Je ne vois pas d'où un écart de performance de 100% pourrait provenir, mais je ne suis pas trop habile à 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

Peu importe ce que la réponse à cette question sera; J'ai appris que dans les boucles très chaudes, chaque détail peut être important, même les détails qui ne semblent pas avoir d'association avec le code hot . Je n'ai jamais pensé à quel type utiliser pour une variable de boucle, mais comme vous voyez un tel changement mineur peut faire une différence de 100% ! Même le type de stockage d'un buffer peut faire une énorme différence, comme nous l'avons vu avec l'insertion du mot-clé static devant la variable size! À l'avenir, je testerai toujours différentes alternatives sur différents compilateurs lorsque j'écris des boucles vraiment serrées et chaudes qui sont cruciales pour la performance du système.

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


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

J'ai codé un programme C équivalent à expérimenter, et je peux confirmer ce comportement étrange. De plus, gcc croit que l'entier de 64 bits (qui devrait probablement être de size_t toute façon ...) sera meilleur, car l'utilisation de uint_fast32_t oblige gcc à utiliser un uint 64 bits.

Je me suis un peu amusé avec l'assemblée:
Prenez simplement la version 32 bits, remplacez toutes les instructions / registres 32 bits par la version 64 bits dans la boucle popcount interne du programme. Observation: le code est tout aussi rapide que la version 32 bits!

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

J'ai ensuite copié le code de boucle interne de la version 32 bits du programme, l'ai piraté en 64 bits, manipulé avec les registres pour en faire un remplacement de la boucle interne de la version 64 bits. Ce code fonctionne aussi vite que la version 32 bits.

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

(Attention: j'ai piraté l'assemblage, je pourrais avoir cassé quelque chose sans m'en rendre compte.) Je ne le pense pas.


J'ai essayé ceci 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 suppose que c'est parce que l'adressage est offset + register, au lieu de offset + register + (register << 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 = compte, rdi = tampon, 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]

TL; DR: Utilisez __builtin intrinsics à la place.

J'ai réussi à faire gcc 4.8.4 (et même 4.7.3 sur gcc.godbolt.org) générer un code optimal pour cela en utilisant __builtin_popcountll qui utilise la même instruction d'assemblage, mais qui n'a pas ce bug de fausse dépendance.

Je ne suis pas sûr à 100% de mon code de benchmarking, mais la sortie d' objdump semble partager mon point de vue. J'utilise d'autres astuces ( ++i vs i++ ) pour que le compilateur déroule la boucle sans aucune instruction movl (comportement étrange, je dois dire).

Résultats:

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

Code d'analyse comparative:

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

Compiler les options:

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 sur le processeur:

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:

Culprit: False Data Dependency (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'écrit que, l'instruction attendra que dest soit prêt avant l'exécution.

Cette dépendance ne tient pas seulement les 4 popcnt partir d'une seule itération de boucle. Il peut effectuer des itérations de boucle, ce qui empêche le processeur de paralléliser différentes itérations de boucle.

Le unsigned vs uint64_t et d'autres tweaks n'affectent pas directement le problème. Mais ils influencent l'allocateur de registre qui affecte les registres aux variables.

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

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

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'assemblage en ligne pour contourner le compilateur et obtenir exactement l'assemblage que je veux. Je divise également la variable de count pour casser toutes les autres dépendances qui pourraient déranger les repères.

Voici les résultats:

Sandy Bridge Xeon @ 3.5 GHz: (code de test complet peut être trouvé 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 brisé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 a mal tourné avec le compilateur?

Il semble que ni GCC ni Visual Studio ne sont conscients que popcnt a une fausse dépendance. Néanmoins, ces fausses dépendances ne sont pas rares. C'est juste une question de savoir si le compilateur est conscient de cela.

popcnt n'est pas exactement l'instruction la plus utilisée. Ce n'est donc pas vraiment une surprise qu'un grand compilateur puisse manquer quelque chose comme ça. Il semble également n'y avoir aucune documentation nulle part qui mentionne ce problème. Si Intel ne le divulgue pas, personne ne le saura à l'extérieur jusqu'à ce que quelqu'un le rencontre par hasard.

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

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

Nous ne pouvons que spéculer, mais il est probable qu'Intel ait la même manipulation pour beaucoup d'instructions à deux opérandes. Les instructions communes comme add , sub prennent deux opérandes dont les deux sont des entrées. Intel a donc probablement popcnt dans la même catégorie pour simplifier la conception du processeur.

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 varie le nombre de popcnt qui sont dans la chaîne de dépendance (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




compiler-optimization