sjub a écrit 28 commentaires

Dans le cas du find, on peut raisonnablement se dire que la performance est limitée par la bande passante mémoire, on est dans un scénario memory-bound, car le processeur doit charger beaucoup de données et ne fait que peu de calcul dessus, en tout cas pas suffisamment pour recouvrir le temps d'attente de la donnée. Du coup est-ce qu'on pourrait avoir des infos sur la mémoire utilisée sur la machine pour déterminer une bande passante max ?

D'après les données, le tableau fait 16M de int donc 64Mo, l'élément à trouver est en dernière position donc on traverse tout, et le temps pour la version optimisée SSE est d'environ 5ms, ce qui donne environ un débit de 12,8Go/s. Le i5-3210M ça doit être du Sandy Bridge avec de la DDR3 12800, donc on attendrait la perf max ! mais c'est en simple canal et il faudrait vérifier la config mémoire pour voir si c'est pas du double canal.

Il est possible de faire de la vecto sans unité vectorielle ! En manipulant des types de taille inférieure à 64 bits, par exemple des int, on peut "caster" le tableau en (int64_t*) donc charger deux int à la fois et faire une seule instruction de comparaison avec un registre contenant deux fois l'int recherché. Cela permet de diviser par deux le nombre d'instructions de comparaison et de chargement, même si on charge finalement la même quantité de données. Pour des opérations simples on doit pouvoir gagner, par contre j'avais testé il y a longtemps pour des instructions arithmétiques pour du traitement d'images, donc en manipulant 8 octets dans un registre 64-bit, mais il faut gérer les risques de dépassement en évitant la propagation des retenues entre les octets et c'était finalement pas efficace. En plus le code était illisible, mais ça peut être bien pour de l'obfuscation !

Bonjour,
Merci pour cette petite expérience. Je travaille pas mal sur l'optimisation de codes/parallélisation et je me méfie toujours de ce que fait le compilateur suite à de nombreuses déconvenues. Mes conclusions (en partie suite aux résultats dans ce papier https://hal.archives-ouvertes.fr/hal-01915529, je recommande le tableau page 8!) :

1. le compilateur n'apporte aucune garantie sur les optimisations : parfois avec -O2 c'est plus rapide qu'avec -O3, parfois c'est avec -Ofast, parfois avec un -march qui ne correspond pas à l'archi de la machine sur laquelle tourne le code, …
2. le compilateur casse parfois les optimisations qu'on essaie de mettre en place -> assembleur…
3. l'autovectorisation ne vectorise pas des cas triviaux mais vectorise des cas complexes sans doute par identification de motifs et remplacement par du code optimisé (un peu comme la boucle for pour copier qui est remplacée par un memcpy), mais dès qu'on modifie un peu le motif, plus personne…
4. l'autovectorisation quand elle produit du code vectorisé ne garantit pas que le code vectorisé soit plus efficace, par exemple sur un traitement d'image, le code "vectorisé" va passer son temps à faire des instructions shuffle/unpack/permute pour réorganiser les données avant de faire quelques calculs puis refaire tout le chemin inverse et parfois c'est plus lent que du code scalaire… mais si on le fait correctement à la main avec des intrinsics on va 3x plus vite ! C'est ce qui a motivé la désactivation de la vecto pour AVX-512, le gain de perf dans de nombreux cas n'était pas suffisant pour contrecarrer la baisse de fréquence.
5. l'autovectorisation n'est pas portable entre architectures (je sais que ce ne sont pas les mêmes instructions mais le processus devrait être un peu indépendant de l'archi), le même compilo va arriver à vectoriser sur x86 en SSE, mais pas en NEON sur Arm, sans utiliser des instructions spécifiques.
6. sur Arm 32-bit j'ai eu une surprise avec une ancienne version de GCC : mes intrinsics étaient convertis en code scalaire mais ça allait 20-30% plus vite que le code scalaire parce que du coup la boucle était déroulée de 4 !
7. parfois l'ajout d'une directive #pragma omp simd bloque l'autovectorisation qui est pourtant faite avec juste -O3.
8. il y a des optimisations qui cassent si on ajoute une petite couche de templates, même juste en utilisant std::vector à la place d'un tableau à la C.
9. j'ai vu des personnes passer énormément de temps à modifier leur code et à espérer que le compilo daigne enfin vectoriser tout seul. Le code ne ressemble plus à rien, on peut espérer gagner 20%, alors qu'en passant par des intrinsics et avec la surcharge des opérateurs on peut vectoriser sans modifier la structure du code et on a un x2 à x5 suivant les archis.

Vivement que Facebook vienne révolutionner tout ça… ou pas ! https://ai.facebook.com/blog/compilergym-making-compiler-optimizations-accessible-to-all/