Ce post a été publié sur LinuxFr.org. Vous pouvez le lire là bas, ainsi que les commentaires associés
Bonjour ’nal,
GCC, Clang, MSVC, sont tous des compilateurs très performants, ayant de nombreuses heuristiques pour émettre des instructions terriblement efficaces, à défaut d’être optimales. De même pour ICC, le compilateur d’Intel, réputé pour enterrer tous les autres en termes de performance du code généré. On en parle pas beaucoup mais il est là. (Tiens, d’ailleurs, savais-tu qu’Intel migrait son compilateur vers LLVM ? Le nouveau compilateur se nomme ICX pour le C, et ICPX pour le C++.)
Il est de plus en plus difficile d’écrire de l’assembleur plus efficace que celui généré par un de ces compilateurs. Pour illustrer leurs performances, prenons par exemple cet algorithme qui cherche un entier dans un tableau, demi-finaliste dans la catégorie « Algorithme Le Plus Bête Qui Soit » aux championnat du monde d’algorithmes de Limoges en 2019 :
// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_c(int k, const int* v, size_t n)
{
for (size_t i = 0; i != n; ++i)
if (v[i] == k)
return i;
return n;
}
Simple et direct, un bon vieil algorithme en C. Voyons un peu comment les compilateurs s’en sortent. Pour les comparer j’utilise Google Benchmark et je mesure la recherche du dernier élément d’un tableau de valeurs distinctes (i.e. je mesure le pire cas) pour des tailles jusqu’à 16 millions d’éléments. La machine qui fait tourner cela est un MacBook pro de 2014, avec un CPU 4 cœurs i5-3210M à 2.5 GHz. Le système est Ubuntu 21.04, GCC version 11.1, Clang version 12, ICC et ICPX version 2021.3.0. Les tests sont compilés avec -O3 -DNDEBUG bien entendu.
Sans surprise, les compilateurs sont tous aussi efficaces les uns que les autres. Il faut dire que l’algo n’est pas compliqué, ça doit fuser au niveau des heuristiques d’optimisation. Mais bon, nous sommes en 2021 et tu vas me dire : « qu’est-ce qui te prend d’écrire une boucle, tu te prends pour un programmeur oh ? » Allez, essayons de cacher cette boucle avec un algo idiomatique du C++ :
// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_cpp(int k, const int* v, size_t n)
{
return std::find(v, v + n, k) - v;
}
Je t’épargne la version ranges de even more moderner C++20 parce ça ne change rien aux performances. Observons juste que le fait de passer --std=c++20 au compilateur a multiplié le temps de compilation par 1,55 (sur une base de 1,35 secondes), contre un facteur de 1,17 pour C++17 et de 1,02 pour C++14. D’autre part, ICPC et ICPX 2021 ne gèrent pas le C++20.
Je relance le benchmark histoire de dire, mais bon on se doute bien que ça ne va rien changer.
Euh… bon, ben… C’est inattendu.
On voit deux choses ici : d’une part tout est beaucoup plus rapide qu’avec la boucle en C (note que l’axe des ordonnées est le même que sur le graphique précédent), d’autre part la version d’ICC se démarque en étant encore plus rapide que les autres. On parle d’une réduction du temps d’exécution de 35-40% pour les premiers, et 70-75% pour ICC.
Sur une bête boucle comme ici, nous pouvons facilement imaginer que le compilateur applique un bon vieux déroulage de boucle. Confirmons par exemple en testant huit entrées par itération :
// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_c_unrolled_8(int k, const int* v, size_t n)
{
size_t i = 0;
for (; n - i >= 8; i += 8)
{
if (v[i] == k)
return i;
if (v[i + 1] == k)
return i + 1;
if (v[i + 2] == k)
return i + 2;
if (v[i + 3] == k)
return i + 3;
if (v[i + 4] == k)
return i + 4;
if (v[i + 5] == k)
return i + 5;
if (v[i + 6] == k)
return i + 6;
if (v[i + 7] == k)
return i + 7;
}
for (; i != n; ++i)
if (v[i] == k)
return i;
return n;
}
Ça a l’air de se valoir, mais bizarrement c’est quand même plus rapide que l’implémentation de std::find(). En fait on peut directement aller voir le code de libstdc++ pour constater qu’ils traitent quatre entrées du tableau à chaque itération. Observons aussi que ICPC est revenu au niveau des autres compilateurs, ce qui signifie qu’il y a quelque chose de particulier derrière std::find() chez lui.
As-tu une idée de ce que pourrait être cette particularité ? Retourne ton écran pour vérifier ta réponse : sǝןןǝı̣ɹoʇɔǝʌ suoı̣ʇɔnɹʇsuı̣,p ǝƃɐsn ʇı̣ɐɟ ƆԀƆI,p ()puı̣ɟ::pʇs uoı̣ʇɔuoɟ ɐן. Évidemment je n’ai pas accès au code de la bibliothèque standard utilisée par ICPC, alors je te propose cette implémentation qui fait usage du jeu d’instructions SSE2 :
// Retourne la position de la première occurrence de k dans les n entiers
// pointés par v, ou n si la valeur n'y est pas.
size_t find_int_sse2(int k, const int* v, size_t n)
{
// Nous allons tester les valeurs de v quatre par quatre.
// Cette instruction copie la valeur recherchée k dans chaque segment
// de 32-bits d'un un registre de 128 bits. Si k…k représente les 32 bits
// de k, le registre ressemble à ce qui suit:
//
// [ k…k | k…k | k…k | k…k ]
//
const __m128i needle = _mm_set1_epi32(k);
// Là on réinterprète juste le pointeur v comme un pointeur vers des
// vecteurs de 128 bits, comme ça on prendra les entiers quatre par
// quatre. Et ouais, je caste à la C comme une brute.
const __m128i* p = (const __m128i*)v;
// Une division ! Est-ce que le compilateur émettra un décalage à la place ?
const size_t iterations = n / 4;
const size_t tail = n % 4;
for (size_t i(0); i != iterations; ++i, ++p)
{
const __m128i haystack = *p;
// Ceci compare les quatre valeurs 32 bits de needle (donc
// quatre fois la valeur recherchée) avec quatre entiers pointés
// par p, en un seul cycle. Tous les bits d'un segment de 32 bits
// sont mis à un si les valeurs sur celui-ci sont égales.
// L'opération ressemble à ceci :
//
// [ k…k | k…k | k…k | k…k ]
// cmpeq [ a…a | b…b | k…k | c…c ]
// = [ 0…0 | 0…0 | 1…1 | 0…0 ]
//
const __m128i mask = _mm_cmpeq_epi32(needle, haystack);
// On ne peut pas directement comparer la valeur mask avec zéro
// mais il existe une instruction qui va nous aider à tester les
// bits de mask.
// Cette instruction prend les bits de poids fort de chaque
// segment de 8 bits d'un registre 128 bits et les copie dans les
// bits de poids faible d'un entier (32-bits).
//
// Par conséquent, puisqu'il y a quatre fois 8 bits dans un
// entier, si k a été trouvé dans haystack, nous devrions avoir un
// 0b1111 dans eq. Autrement eq sera zéro. Autrement dit (les 16
// bits de poids forts sont toujours nuls) :
//
// movemask [ 0…0 | 0…0 | 1…1 | 0…0 ]
// = 0000 0000 0000 0000 0000 0000 1111 0000
//
const uint32_t eq = _mm_movemask_epi8(mask);
// Puisque nous avons de nouveau affaire à un scalaire, nous
// pouvons le tester directement.
if (eq == 0)
continue;
// Il ne reste plus qu'à trouver l'offset du premier bit de
// poids faible égal à 1. Mon ordinateur ne gère pas l'instruction
// tzcnt donc j'utilise l'équivalent des fonctions de GCC.
const unsigned zero_bits_count = __builtin_ctz(eq);
// Chaque groupe de 4 bits dans eq correspond à une valeur 32
// bits dans mask, donc on divise par 4.
return i * 4 + zero_bits_count / 4;
}
// On teste quand même les dernières valeurs du tableau à l'ancienne
// au cas où le nombre d'éléments n'est pas un multiple de 4.
for (size_t i(iterations * 4); i != n; ++i)
if (v[i] == k)
return i;
return n;
}
Mesurons ça:
Et voilà, maintenant tous les compilateurs génèrent un code équivalent à l’implémentation de std::find() utilisée par ICC.
Conclusion
Cette aventure a été assez surprenante finalement. Tout à commencé alors que je m’entraînais à utiliser des intrinsics, et que je tentais de valider mon implémentation — tant du point de vue résultats que de perfs — avec le binaire produit par GCC pour la boucle C. Quelle surprise de voir mon code sortir le résultat quatre fois plus rapidement !
Au fond ce résultat me déçoit un peu. Cela fait plus de vingt ans que j’entends que le temps d’ingénierie coûte cher, qu’il vaut mieux acheter du CPU et de la mémoire, et que la loi de Moore fera le taf’ ; et quasiment aussi longtemps que j’entends que les compilateurs « d’aujourd’hui » sont performants, etc. Pour au final constater que seul un compilateur sur les quatre me sort du code optimisé. Et encore, si je prends la version la plus moderne de ce compilateur, ICPX versus ICPC donc, je perds cette optimisation ! Juste pour le fun, je te mets un extrait de l’annonce d’Intel :
The latest Intel C/C++ compilers, using LLVM, deliver faster compiler times, better optimizations, enhanced standards support, and support for GPU and FPGA offloading.
Better.
Optimizations.
Du coup j’ai tendance à penser maintenant que ceux qui tiennent ce discours (« les compilateurs d’aujourd’hui sont performants etc. ») ont surtout la flemme de regarder comment leur code est traduit et répètent cette doctrine pour éviter d’avoir à se poser la question.
Évidemment il n’est pas question de tout optimiser, mais la vraie raison pour laquelle nous écrivons du code de haut niveau n’est pas que les compilateurs sont très performants ; c’est plutôt un compromis du temps de mise en œuvre. En d’autres termes, nous acceptons du code sous optimal au profit d’une écriture et d’une maintenance simplifiée.
Au passage, je suis aussi un peu déçu de voir toute la variété des compilateurs doucement s’éteindre au profit d’une seule implémentation, LLVM. J’ai l’impression de revoir l’effet Chrome : au début c’est tout frais, tout jeune et performant, ça met un coup de fouet à l’ancêtre (Firefox/GCC) et puis au final ça grossit, ça bouffe tout et il n’y a plus de choix (Internet Explorer est mort au profit de Edge, toute appli récente est codée en Electron, tout compilateur récent est basé sur LLVM).
Je ne dis pas que LLVM est aussi problématique que Chrome, il y a plein de chouettes outils qui viennent de LLVM (clang-format, clang-tidy, FileCheck…), mais de là à abandonner toute variété, personnalité, créativité, au profit d’un seul et unique modèle, c’est déprimant.
Pour lutter contre tout cela et garder le moral, je t’invite à mettre à l’épreuve les outils que tu utilises, à les confronter à d’autres outils et à ce que tu saurais faire de toi-même. Au final la décision sera probablement toujours « bah on va prendre X, c’est moins bien mais tout le monde l’utilise et ça sera vite intégré », parce quand il y a des sous ou de la popularité en jeu, c’est l’efficacité de production qui compte ; mais peut être qu’en s’intéressant aux détails on pourra petit à petit subrepticement pousser une culture de curiosité, de défi et d’optimisation même dans les processus les plus « bottom line ». Et puis même si ça ne change rien, on apprendra des choses ; et ça c’est cool :)