Je cherchais le moyen le plus rapide de popcount de grands tableaux de données. J'ai rencontré un très bizarre effet : Changer la variable de la boucle de unsigned à uint64_t a fait chuter les performances de 50% sur mon PC.
Le repère
#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 une taille de x mégaoctets où x est lu à partir de la ligne de commande. Ensuite, nous itérons sur le tampon et utilisons une version non laminée de l'algorithme x86 popcount intrinsèque 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. Dans le cas supérieur, la variable de la boucle interne est unsigned en minuscule, la variable de la boucle interne est uint64_t . Je pensais que cela ne devait faire aucune différence, mais c'est le contraire qui se produit.
Les résultats (absolument fous)
Je le compile comme ceci (version de g++ : Ubuntu 4.8.2-19ubuntu1) :
g++ -O3 -march=native -std=c++11 test.cpp -o testVoici les résultats sur mon Haswell Core i7-4770K CPU @ 3.50 GHz, fonctionnant 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 uint64_t version est seulement la moitié celui de la unsigned version ! Le problème semble être que des assemblages différents sont générés, mais pourquoi ? Tout d'abord, j'ai pensé à un bug du compilateur, donc j'ai essayé clang++ (Ubuntu Clang version 3.4-1ubuntu3) :
clang++ -O3 -march=native -std=c++11 teest.cpp -o testRésultat : test 1
- non signé 41959360000 0.398293 sec 26,3267 Go/s
- uint64_t 41959360000 0.680954 sec 15,3986 Go/s
Le résultat est donc presque le même et reste étrange. Mais maintenant ça devient super étrange. Je remplace la taille du tampon qui a été lu à partir de l'entrée par une constante 1 alors je me change :
uint64_t size = atol(argv[1]) << 20;à
uint64_t size = 1 << 20;Ainsi, le compilateur connaît désormais la taille du tampon au moment de la compilation. Il peut peut-être 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
Aujourd'hui, les deux versions sont aussi rapides l'une que l'autre. Cependant, la unsigned est devenu encore plus lent ! Il est passé de 26 à 20 GB/s Ainsi, le remplacement d'une valeur non constante par une valeur constante conduit à une valeur de 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 sont tombées au lent de 15 GB/s. Ainsi, le remplacement d'une valeur non constante par une valeur constante conduit même à un code lent en les deux cas pour Clang !
J'ai demandé à un collègue avec un Ivy Bridge CPU pour compiler mon benchmark. Il a obtenu des résultats similaires, donc il ne semble pas que ce soit Haswell. Comme deux compilateurs produisent des résultats étranges ici, il ne semble pas non plus qu'il s'agisse d'un bogue de compilateur. Nous n'avons pas de CPU AMD ici, donc nous ne pouvions tester qu'avec Intel.
Plus de folie, s'il vous plaît !
Prenons le premier exemple (celui avec atol(argv[1]) ) et mettre un static avant la variable, c'est-à-dire
static uint64_t size=atol(argv[1])<<20;Voici mes résultats dans g++ :
- non signé 41959360000 0.396728 sec 26.4306 GB/s
- uint64_t 41959360000 0.509484 sec 20,5811 Go/s
Yay, encore une autre alternative . Nous avons toujours le rapide 26 GB/s avec u32 mais nous avons réussi à obtenir u64 au moins de la version 13 GB/s à la version 20 GB/s ! Sur le PC de mon collègue, le u64 est devenue encore plus rapide que la version u32 qui donne 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 ? Surtout :
- Comment peut-il y avoir une telle différence entre
u32etu64? - Comment le remplacement d'une taille de mémoire tampon non constante par une taille constante peut-il déclencher l'opération suivante code moins optimal ?
- Comment l'insertion de la
staticle mot-clé fait de lau64boucle plus rapidement ? Même plus rapide que le code original sur l'ordinateur de mon collègue !
Je sais que l'optimisation est un domaine délicat, mais je n'ai jamais pensé que de si petits changements pouvaient conduire à une amélioration de la qualité de vie. 100% de différence 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 qui est capable de compter 26 Go/s en popcount. Le seul moyen fiable auquel je pense est de copier-coller l'assemblage pour ce cas et d'utiliser l'assemblage en ligne. C'est la seule façon de se débarrasser des compilateurs qui semblent devenir fous pour de petits changements. Qu'en pensez-vous ? Existe-t-il un autre moyen d'obtenir de manière fiable le code le plus performant ?
Le démontage
Voici le démontage pour les différents résultats :
Version 26 GB/s 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 0x400af8Version 13 GB/s 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 0x400c00Version 15 GB/s 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 0x400e50Version 20 GB/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 0x400a68Version 15 GB/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 0x400dd0Il est intéressant de noter que la version la plus rapide (26 Go/s) est aussi la plus longue ! Il semble que ce soit la seule solution qui utilise lea . Certaines versions utilisent jb pour 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 très doué 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 ?
Les leçons apprises
Peu importe la réponse à cette question, j'ai appris que dans les boucles vraiment chaudes chaque Les détails peuvent avoir de l'importance, même des détails qui ne semblent pas avoir de lien avec le code chaud. . Je n'ai jamais réfléchi au type de variable à utiliser pour une boucle, mais comme vous le voyez, un changement aussi mineur peut faire toute la différence. 100% différence ! Même le type de stockage d'un tampon peut faire une énorme différence, comme nous l'avons vu avec l'insertion de l'élément static devant la variable de taille ! À l'avenir, je testerai toujours différentes alternatives sur différents compilateurs lorsque j'écrirai des boucles vraiment serrées et chaudes qui sont cruciales pour les performances du système.
Ce qui est intéressant, c'est que la différence de performance est toujours aussi importante alors que j'ai déjà déroulé la boucle quatre fois. Donc, même si vous déroulez la boucle, vous pouvez toujours être frappé par des écarts de performance importants. Assez intéressant.
