Le remplacement d'un compteur de boucle de 32 bits par un compteur de boucle de 64 bits introduit des déviations de performance folles

j'ai codé un programme C équivalent à expérimenter, et je peux confirmer ce comportement étrange. De plus, gcc croit que l'entier 64 bits (qui devrait probablement être un size_t de toute façon...) afin d'être mieux, que l'utilisation de uint_fast32_t les causes de gcc pour utiliser une version 64 bits de uint.



J'ai fait un peu de mucking autour de l'Assemblée:

Il suffit de prendre la version 32 bits, remplacer toutes les instructions/registres 32 bits par le Version 64 bits dans la boucle popcount interne du programme. Observation: 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 encore la version 32 bits, mais aussi longtemps que la boucle popcount interne domine la performance, c'est un bon début.



J'ai ensuite copié la boucle intérieure code à partir de la version 32 bits du programme, a piraté jusqu'à 64 bits, jouait avec les registres pour 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 qu'il s'agit d'une mauvaise planification d'instruction par le compilateur, et non d'un avantage réel de vitesse/latence des instructions 32 bits.



(Mise En Garde: I montage piraté, il aurait pu casser quelque chose sans s'en apercevoir. Je ne le pense pas.)

ce n'est pas une réponse, mais il est difficile de lire si je mets les résultats dans le commentaire.

j'obtiens ces résultats avec un Mac Pro ( Westmere 6-Core Xeon 3.33 GHz). Je l'ai compilé avec clang -O3 -msse4 -lstdc++ a.cpp -o a (-O2 obtenir le même résultat).

clang 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

clang 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. Inverser l'ordre de test, le résultat est le même donc il exclut le facteur de cache.
2. ont le for au verso: for (uint64_t i=size/8;i>0;i-=4) . Cela donne le même résultat et prouve que la compilation est assez intelligente pour ne pas diviser la taille par 8 à chaque itération (comme prévu).

voici ma supposition sauvage:

le facteur de vitesse est en trois parties:

• code cache: uint64_t version a une plus grande taille de code, mais cela n'a pas d'effet sur mon CPU 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 de 32 bits et 64 bits sur les deux versions. L'accès à un pointeur avec un offset 64 bits demande un registre et une adresse 64 bits dédiés, alors que vous pouvez utiliser immediate for a 32-bits de décalage. Cela pourrait rendre la version 32 bits plus rapide.

Les Instructions

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

les trois facteurs ensemble concordent avec les résultats apparemment contradictoires observés.

Je ne peux pas donner une réponse qui fasse autorité, mais donner 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 y a un rapport 3:1 entre la latence et le débit. Il montre également les effets d'une expédition 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.

donc entre le pic les performances de pipeline et de répartition multiple et la défaillance de ces mécanismes, nous avons un facteur de six dans la performance. Il est assez bien connu que la complexité du jeu d'instructions x86 le rend assez facile pour cassure bizarre de se produire. Le document ci-dessus a un grand exemple:

la performance du Pentium 4 pour les équipes de droite 64 bits est vraiment médiocre. Le poste de gauche de 64 bits ainsi que tous les postes de 32 bits ont des performances acceptables. Il semble que le chemin de données les 32 bits supérieurs aux 32 bits inférieurs de L'ALU ne sont pas bien conçus.

j'ai personnellement rencontré un cas étrange où une boucle chaude courait considérablement plus lentement sur un noyau spécifique d'une puce à quatre noyaux (AMD si je me souviens). Nous avons en fait obtenu de meilleures performances sur une carte-réduire le calcul en éteignant ce noyau.

voici ma supposition est la prétention pour les unités entières: que le popcnt , compteur de boucle, et les calculs d'adresse peuvent juste exécuter à pleine vitesse avec le compteur 32 bits large, mais le compteur 64 bits provoque des conflits et des décrochages de pipeline. Comme il n'y a qu'environ 12 cycles au total, potentiellement 4 cycles avec régulation multiple, par exécution de corps de boucle, un seul décrochage pourrait raisonnablement affecter le temps d'exécution d'un facteur de 2.

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

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

j'ai essayé avec Visual Studio 2013 Express , en utilisant un pointeur au lieu d'un index, ce qui a accéléré le processus un peu. Je soupçonne que c'est parce que l'adressage est compensée + registre, au lieu de décalage + registre + (inscrire<<3). Le 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 en dehors de la boucle? Maintenant vous avez une dépendance de données, ce n'est pas vraiment nécessaire.

, Essayez:

  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 aussi quelques aliasing bizarres en cours, que je ne suis pas sûr de respecter les règles d'aliasing strictes.

TL; DR: utiliser __builtin intrinsics à la place.

I was able to make gcc 4.8.4 (and even 4.7.3 on gcc.godbolt.org) générez le code optimal pour cela en utilisant __builtin_popcountll qui utilise la même instruction d'assemblage, mais n'a pas ce bug de fausse dépendance.

Je ne suis pas sûr à 100% de mon code de benchmarking, mais la sortie objdump semble partager mes vues. J'utilise quelques autres trucs ( ++i vs i++ ) pour faire le compilateur déroulez boucle pour moi sans aucune instruction movl (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;
}

Compiler 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

le noyau Linux version:

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: