Concevoir des algorithmes SIMD depuis zéro

 (mcyoung.xyz)
2 points par GN⁺ 2023-11-29 | 1 commentaires | Partager sur WhatsApp
  • Le codec base64 vb64 créé avec std::simd de Rust devient un code SIMD rapide et portable non pas en vectorisant tel quel une boucle procédurale, mais en repensant la disposition des données et le flux d’opérations comme un circuit
  • L’optimisation clé consiste à réduire les stalls dus aux branchements et aux accès mémoire, en construisant une structure branchless qui exécute les mêmes opérations indépendamment de l’entrée grâce à des comparaisons, masques, select et shuffle
  • Pour le décodage base64, on construit un perfect hash qui convertit les caractères ASCII en sextets à l’aide de byte >> 4 et d’une correction pour /, puis on trouve l’offset avec une table de lookup dans le vecteur SIMD et un shuffle
  • Lors du compactage de quatre sextets de 6 bits en trois octets, on élargit les lanes en u16 avant de faire le shift, puis on sépare les octets low/high et on combine les fragments d’octets de lanes adjacentes avec rotate_lanes_left et OR
  • Dans les benchmarks, après la combinaison -Zbuild-std, -Ctarget-cpu=native, N = 32 et l’optimisation du chargement du remainder, les performances atteignent environ 2x celles de l’implémentation base64 de référence sur crates.io sur presque toute la plage

Contexte physique qui rend le SIMD nécessaire

  • L’amélioration des performances informatiques est liée directement non seulement à l’informatique théorique, mais aussi aux contraintes physiques
  • La loi de Moore semble toujours tenir en 2023, mais au cours des 15 dernières années, l’effet du Dennard scaling s’est effondré, si bien qu’une plus forte densité de transistors entraîne une hausse de la densité de consommation électrique
  • Après qu’il est devenu difficile d’augmenter continuellement la fréquence d’horloge, la principale voie d’amélioration des performances s’est déplacée au début des années 2000 vers l’utilisation d’un plus grand nombre de cœurs
  • Le multithreading exige une coopération entre les cœurs, ce qui introduit des coûts de synchronisation, et les flux de contrôle comme les sauts, les appels virtuels et la synchronisation provoquent des stalls
  • Il existe deux causes principales de stall
    • Branchements : flux de contrôle comme if, boucles, appels de fonction, retours de fonction ou switch en C
    • Opérations mémoire : load/store, en particulier les accès peu favorables au cache

Code procédural et parallélisme au niveau des instructions

  • Les cœurs CPU modernes n’exécutent pas le code ligne par ligne, mais émettent simultanément les opérations qui ne dépendent pas les unes des autres
  • Des opérations indépendantes comme a = x + y et b = x ^ y peuvent utiliser en même temps les circuits d’addition et de xor
  • Cette approche correspond au parallélisme au niveau des instructions, et les dépendances qui l’entravent sont appelées data hazards
  • Plus le CPU parvient à saturer ses functional units, plus il traite d’opérations par unité de temps
  • Les branchements provoquent des stalls parce qu’il faut attendre le calcul de la condition avant d’aller chercher l’instruction suivante, et les opérations mémoire parce que les données doivent physiquement parvenir jusqu’au CPU
  • Comme les GPU traitent les images sous forme de pixels vectoriels et effectuent beaucoup d’opérations à forte localité, ils sont plus proches de machines SIMD conçues pour les traitements par lots et un flux de contrôle limité
  • SIMD signifie single instruction, multiple data : une seule instruction exécute des opérations en parallèle sur plusieurs lanes de données

Raisonner à l’échelle des lanes

  • SIMD et vector sont souvent employés dans le même sens, et l’unité de base d’une instruction SIMD est un vector, c’est-à-dire un tableau de nombres de taille fixe
  • Chaque composant d’un vector est appelé une lane
  • Les vecteurs SIMD doivent tenir dans des registres, ils sont donc généralement petits
    • Dans l’environnement d’exemple, la largeur vectorielle maximale est de 256 bits
    • Cela correspond à 32 octets de u8x32 ou à 4 doubles de f64x8
  • Même un petit vecteur peut améliorer la latence s’il réduit d’un facteur 4 la charge nécessaire pour saturer le pipeline

Divide and conquer vu à travers popcnt

  • L’opération vectorielle la plus simple est le bitwise and/or/xor
  • Même un entier ordinaire peut être vu, du point de vue des opérations bitwise, comme un vecteur de lanes de 1 bit
    • i32 équivaut dans cette perspective à i1x32
  • popcnt est l’opération qui compte le nombre de bits à 1 dans un entier, et si l’on considère i32 comme i1x32, c’est une opération de réduction
  • Une implémentation naïve qui extrait les 32 bits dans un tableau pour les additionner peut produire un mauvais code
  • Une meilleure méthode consiste à additionner d’abord les paires de bits adjacents, puis les paires de paires, en augmentant progressivement la largeur des lanes
    • séparation des bits pairs/impairs avec les masques 0x55555555 et 0xaaaaaaaa
    • alignement des lanes par shift, puis addition
    • répétition ensuite à l’échelle de 2 bits, 4 bits, 8 bits et 16 bits
  • Cette implémentation n’est pas optimisée en instruction popcnt, mais elle produit un code compact et rapide sur les systèmes qui ne disposent pas de cette instruction
  • Elle s’applique aussi à u64 en ajoutant simplement une étape de réduction supplémentaire, sans nécessiter une addition u64 globale
  • Cette approche de divide and conquer est un motif central de la programmation SIMD

Principaux outils des jeux d’instructions SIMD

  • Les vrais vecteurs SIMD offrent une sémantique plus complexe que les scalaires, et les fonctions destinées à remplacer les flux de contrôle lents sont particulièrement importantes
  • Les instructions disponibles dépendent fortement de l’architecture
    • De nombreux cœurs hautes performances x86 implémentent AVX2
    • AVX2 fournit des vecteurs ymm de 256 bits
    • Le registre lui-même n’a pas de nombre de lanes ; c’est l’instruction qui détermine comment les interpréter
    • Par exemple, vpaddb interprète ymm comme i8x32
  • Les opérations généralement disponibles sont les suivantes
    • opérations bitwise : la largeur de lane est implicitement toujours de 1 bit
    • arithmétique lane par lane : addition, soustraction, multiplication, division, shift entier, min/max, etc.
    • comparaison lane par lane : produit un vecteur de masque du type m[i] = a[i] < b[i]
    • select : choisit lane par lane une valeur entre deux vecteurs à l’aide d’un masque
    • shuffle/swizzle : considère un vecteur comme une table de lookup et réorganise les lanes avec un vecteur d’index
  • Les valeurs true/false d’un vecteur de masque utilisent généralement des motifs de bits all-ones ou all-zeros
  • La comparaison et select sont des outils essentiels pour permettre au code SIMD de rester branchless
  • Un code branchless effectue les mêmes opérations quelle que soit l’entrée, puis élimine les résultats inutiles grâce à des propriétés comme x * 0 = 0 ou a ^ b ^ a = b

Aligner les données avec shuffle

  • shuffle est un outil essentiel en SIMD pour mettre les données à la « bonne position »
  • Broadcast ou splat crée un vecteur dont toutes les lanes contiennent le même scalaire, ce qui peut s’exprimer par un shuffle d’index [0, 0, ...]
  • Interleave ou zip/pack alterne les lanes de deux vecteurs a et b
    • c = [a[0], b[0], a[1], b[1], ...]
    • peut être implémenté avec shuffle2
  • Deinterleave ou unzip/unpack est l’opération inverse de l’interleave
  • Rotate fait tourner les lanes sous la forme b[i] = a[(i + j) % n], ce qui est aussi un shuffle
  • En programmation SIMD, il est fréquent de réinterpréter et de réagencer des blocs de données plus grands que des entiers en petits blocs de tailles variées

intrinsics, target feature, portable SIMD

  • Les opérations disponibles en SIMD varient selon l’architecture et les extensions du jeu d’instructions
  • x86 peut proposer des opérations absentes sur ARM, et même chez un même fournisseur il existe des extensions réservées aux puces serveur haut de gamme, comme Intel AVX-512
  • Les toolchains généralisent ces extensions sous la forme de target features
    • Sur Linux, lscpu affiche les features reconnues par le CPU
    • LLVM sélectionne les instructions différemment selon les features activées
    • Il faut +avx2 pour que LLVM génère du code utilisant ymm
  • -march=native ou -Ctarget-cpu=native peuvent produire un bon code pour la machine de build, mais la portabilité vers d’autres processeurs peut en pâtir
  • La détection des features à l’exécution consiste à vérifier ce que le CPU prend en charge afin de décider quelle version d’une fonction appeler ; on l’utilise dans du code distribué sur des appareils variés, comme les bibliothèques de chiffrement
  • Le code SIMD en C++ utilise généralement des intrinsics comme _mm256_cvtps_epu32
    • Elles représentent des opérations de bas niveau propres à un jeu d’instructions donné
    • Elles ne se traduisent pas forcément par une seule instruction
    • Le compilateur peut fusionner, éliminer les doublons et optimiser le choix des instructions
  • Si l’on finit par réécrire un code similaire pour plusieurs jeux d’instructions, l’avantage de maintenance par rapport à l’assembly peut devenir limité
  • Les bibliothèques de portable SIMD adoptent une approche où une partie de la sélection d’instructions est gérée au niveau de la bibliothèque, le reste étant laissé au compilateur
  • L’implémentation de vb64 est une expérience destinée à vérifier si le portable SIMD de Rust génère un code compétitif

transformer le décodage base64 en SIMD

  • base64 est une méthode d’encodage de données binaires arbitraires en ASCII
  • La séquence d’octets d’entrée est vue comme un vecteur de bits, puis divisée en morceaux de 6 bits appelés sextets
  • Les valeurs des sextets sont mappées vers les caractères suivants
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • Il existe plusieurs variantes de base64, mais l’essentiel de la complexité est commun
  • Il faut garder deux points en tête
    • base64 est un format où les bits à l’intérieur d’un octet sont en big endian
    • La longueur de l’entrée peut ne pas être divisible par 4 ; en principe on utilise un padding = pour compléter jusqu’à un multiple de 4, mais on peut aussi traiter des messages dont le padding est incorrect
  • La longueur décodée se calcule comme input / 4 * 3, à laquelle on ajoute une longueur résiduelle selon input % 4

refactorisation de base vers du branchless

  • Un décodeur base64 simple contient plusieurs branches
    • une boucle qui parcourt l’entrée par chunks
    • une boucle sur les octets à l’intérieur de chaque chunk
    • un match par caractère ASCII
    • un return Err en cas d’erreur
    • un match dans decoded_len
    • Vec::extend_from_slice et la possibilité d’un appel à l’allocator
  • La consigne d’optimisation consiste à supprimer toutes les branches
  • Le match de decoded_len mappe les valeurs 0, 1, 2, 3 de input % 4 vers 0, 1, 1, 2
  • Le remplacer par mod4 - mod4 / 2 donne une version branchless
  • LLVM peut certes replier le match d’origine en table de saut, mais dans cette zone des accès mémoire inutiles dégradent les performances

isoler la boucle la plus chaude

  • La force du SIMD est de traiter beaucoup de données à la fois afin de dérouler fortement la boucle et de se rapprocher d’un fonctionnement sans branchement
  • L’objectif de la hot loop est de lire jusqu’à 4 octets, de produire jusqu’à 3 octets décodés, et d’indiquer aussi s’il y a une erreur de syntaxe
  • Trois faits peuvent être exploités
    • La longueur de sortie peut être calculée avec un decoded_len() branchless
    • Une base64 invalide peut être considérée comme un chemin très rare, et si l’on a besoin de la position d’erreur on peut refaire un scan après coup
    • En base64, A vaut 0, donc compléter un chunk tronqué avec des A ne change pas la valeur
  • decode_hot() est isolée sous la forme d’une fonction qui traite quatre octets d’entrée et renvoie le résultat décodé avec un booléen de succès
  • Renvoyer séparément un booléen plutôt qu’utiliser Option<[u8; 3]> facilite ensuite la suppression de la branche if !ok
  • Dans la version SIMD, l’entrée est un Simd<u8, 4>, et la sortie reste aussi un Simd<u8, 4> pour correspondre à un nombre de lanes puissance de deux
    • La sortie réellement nécessaire est de 3 octets
    • La dernière lane n’est pas utilisée

comment convertir l’ASCII en sextets

  • L’essentiel du match qui convertit un caractère ASCII en sextet peut s’exprimer sous la forme byte - C
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • Il suffit de construire un vecteur d’offsets par lane puis d’effectuer ascii - offsets
  • La première approche est compare-and-select
    • on crée des masques pour A-Z, a-z, 0-9, +, /
    • une lane pour laquelle aucun masque n’est sélectionné est considérée comme invalide
    • on splat l’offset correspondant à chaque masque puis on combine le tout avec des OR
  • Cette approche est élégante et peut produire un code compétitif, mais elle nécessite 8 comparaisons au total et le nombre de valeurs vivantes peut créer de la pression sur les registres

table de hachage SIMD et perfect hash

  • Les plages d’octets de A-Z, a-z, 0-9 sont respectivement 0x41..0x5b, 0x61..0x7b, 0x30..0x3a, et leurs high nibbles diffèrent
  • + et / valent 0x2b et 0x2f, donc byte >> 4 suffit à les distinguer dans la plupart des cas
  • Dans le cas de /, soustraire 1 donne un perfect hash sur les plages visées
  • Le mapping de (byte >> 4) - (byte == '/') est le suivant
    • A-Z → 4 ou 5
    • a-z → 6 ou 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • Cette valeur est petite, donc on peut placer une table de lookup d’offsets dans un vecteur SIMD et faire le lookup avec un shuffle
  • Cette idée de perfect hash a été proposée par un utilisateur anonyme dans une GitHub issue
  • Simd::swizzle_dyn() impose que le tableau d’index et la longueur de la table de lookup aient la même taille
  • Avec l’approche perfect hash, la validation n’est plus obtenue comme effet de bord pendant le calcul des sextets ; on utilise donc un exact bloom filter pour vérifier la validité des octets, comme dans la même GitHub issue
  • Un exemple d’implémentation est disponible dans le fichier simd.rs de vb64

empaqueter quatre sextets en trois octets

  • L’étape qui consiste à fusionner quatre sextets de 6 bits en trois octets est plus délicate
  • En fixant un sextet d’entrée particulier à all-ones puis en observant où ses bits se déplacent dans la sortie, on peut suivre la logique d’agencement
  • Un simple shuffle au niveau des octets ne suffit pas
    • la cible du déplacement est un fragment d’octet
    • de simples décalages ne suffisent pas non plus
    • les bits décalés au-delà de la limite doivent se propager vers la lane voisine
  • La solution consiste à élargir les lanes
  • On caste sextets en vecteur de u16, puis on applique des décalages lane par lane
    • input[0] est décalé de 2 bits
    • input[1] est décalé de 4 bits
    • input[2] est décalé de 6 bits
    • input[3] est ajusté avec un décalage de 8 bits
  • On sépare ensuite le résultat des décalages en vecteurs d’octets bas et d’octets hauts
  • Avec hi.rotate_lanes_left::<1>(), on aligne la partie en octets hauts sur la lane voisine, puis on combine avec lo | hi_rotated
  • Cette méthode exploite fortement les primitives matérielles, ce qui donne un code compact et efficace

Extension du nombre de lanes et suppression des garbage lanes

  • Simd<u8, 4> est plus petit que le registre vectoriel x86 minimal de 128 bits, donc decode_hot() a été rendu générique sur le nombre de lanes N
  • La contrainte LaneCount<N>: SupportedLaneCount garantit un petit nombre de lanes en puissance de deux
  • La table de lookup et la table de décalage construisent des vecteurs à motif répété avec le helper tiled()
  • Avec N = 4, il suffisait d’ignorer la valeur garbage de la dernière lane, mais quand N augmente, des garbage values se mélangent à chaque quatrième lane
  • Un shuffle est utilisé pour les supprimer
    • La relation voulue est shuffled[i] = output[i + i / 3]
    • On saute chaque quatrième index pour supprimer la garbage lane
    • La partie qui déborde correspond au quart supérieur du vecteur de sortie final, donc elle est ignorée
  • De cette façon, decode_hot::<32>() peut décoder en parallèle 32 octets base64

Optimisation de la boucle externe

  • decode() est lui aussi rendu générique sur le nombre interne de lanes N
  • Les coûts restants sont les suivants
    • la branche de comparaison de longueur dans for chunks in ...
    • le memcpy à longueur variable de [T]::copy_from_slice
    • la branche ok à chaque itération de boucle
    • l’appel potentiel à l’allocateur dans Vec::extend_from_slice et un autre memcpy
  • Comme la longueur de sortie est connue, l’espace est préalloué avec out.reserve(final_len + N / 4)
  • Un espace de slop est ajouté en plus afin d’effectuer un store SIMD complet au lieu d’un memcpy à longueur variable
  • Chaque itération écrit le vecteur SIMD complet, et l’écriture suivante se déplace de 3/4 * N pour écraser les précédents garbage bytes
  • Les derniers garbage bytes ne sont pas inclus dans le Vec::set_len() final, ils sont donc traités comme supprimés
  • Même si if !ok provoque un retour anticipé, set_len() n’a pas validé l’écriture, donc out reste inchangé

Reporter la gestion des erreurs hors de la hot loop

  • Au lieu de retourner à chaque itération avec if !ok, l’erreur est accumulée avec error |= !ok
  • L’état d’erreur n’est vérifié qu’une seule fois, juste avant le set_len() final
  • En partant du principe que la plupart des blobs base64 sont valides, le chemin d’erreur est déplacé hors de la hot loop
  • Même en cas d’erreur de syntaxe, les opérations SIMD suivantes ne se comportent pas arbitrairement de travers, donc les garbage writes ne sont pas validées et disparaissent
  • Un appel ultérieur comme Vec::push() peut écraser cette même zone du buffer

Unroll and jam et gestion du remainder

  • Unroll and jam est appliqué pour réduire le memcpy à longueur variable de copy_from_slice
  • La boucle est divisée en deux parties
    • hot vectorized loop : traite toujours une entrée de longueur N
    • cold remainder part : traite au plus une fois une entrée i < N
  • Iterator::chunks_exact() de Rust est utilisé pour implémenter un unroll-and-jam écrit à la main
  • Dans la hot loop, Simd::from_slice() est appelé pour effectuer un unique chargement de taille vectorielle
  • Les bounds checks prennent alors une forme que le compilateur élimine plus facilement

Benchmarks et optimisation du chargement manuel

  • Les benchmarks décodent des messages de longueur 0 jusqu’à environ 200 ou 500 octets, et les comparent à l’implémentation base64 de référence sur crates.io
  • Les options de compilation utilisées sont -Zbuild-std et -Ctarget-cpu=native
  • Après tuning, N = 32 s’est révélé optimal, en utilisant un registre YMM par itération de la hot loop
  • Au départ, le baseline était battu, mais une variation de performances en forme de heartbeat, fortement corrélée à data.len() % 32, est apparue
  • Après inspection de l’assembly, il a été estimé que copy_from_slice était inline/unrolled en boucle de chargement octet par octet
  • Simd::gather_or() a aussi été essayé, mais produisait un assembly plus mauvais et n’a pas été retenu
  • À la place, une fonction de chargement manuel a été écrite pour les données de longueur variable
    • la hot part effectue dans une boucle des chargements u128, le plus grand chargement scalaire possible
    • LLVM abaisse les chunks de 16 octets en chargements XMM
    • le remainder utilise des chargements qui se chevauchent en u64, u32 et u8
  • Pour lire 15 octets, on lit un u64 depuis p et un u64 depuis p + 7, ce qui fait chevaucher 1 octet, puis on combine le tout avec un OR
  • Pour 4 à 7 octets, des chargements u32 qui se chevauchent sont utilisés
  • Pour 1 à 3 octets, on lit depuis p, p + len/2 et p + len - 1, ce qui peut recharger certains octets, mais réduit le nombre de branches
  • Après application du nouveau code de chargement, la variance est devenue très faible et les performances ont atteint presque 2x le baseline sur quasiment toute la plage

Encodage et base64 web-safe

  • Pour la fonction d’encodage, il suffit d’implémenter encode_hot() en inversant les opérations de decode_hot()
  • Le perfect hash utilisé pour le décodage ne convient pas à l’encodage, donc un nouveau hash est nécessaire
  • Le code de chargement/stockage autour de l’encoder diffère aussi légèrement de celui du decoder
  • vb64 implémente également une routine d’encodage efficace
  • Le base64 web-safe est une variante qui remplace + et / par - et _
  • La construction d’un perfect hash pour le base64 web-safe est plus délicate ; par exemple, une approche comme (byte >> 4) - (byte == '_' ? '_' : 0) peut être nécessaire
  • vb64 ne prend pas encore en charge le base64 web-safe

Conclusion

  • vb64 n’est pas présenté comme une bibliothèque destinée à résoudre un goulot d’étranglement majeur, et l’auteur précise ne pas savoir où le décodage base64 constitue réellement un bottleneck
  • Le code branchless est souvent excessif, mais il aide à comprendre ce que le compilateur peut et ne peut pas faire
  • std::simd de Rust est globalement bon et génère un excellent code
  • Il existe encore quelques rough edges qui mériteraient d’être corrigés pour simplifier davantage le code SIMD, mais le résultat actuel est jugé satisfaisant
  • Le SIMD et l’optimisation des performances sont des sujets complexes qui exigent beaucoup d’astuces et de connaissances matérielles, dont une grande partie n’est pas documentée

À lire aussi

1 commentaires

 
GN⁺ 2023-11-29
Commentaires sur Hacker News

  • C’était intéressant de voir portable SIMD utilisé en pratique, et en reproduisant le benchmark sur un système Zen 3, j’ai obtenu le même gain de performance
    Sur un MacBook Pro M1, le gain commençait à 1,4x pour une longueur d’entrée de 110 octets puis montait progressivement jusqu’à 2x ; c’est moins que sur x86_64, mais l’objectif semble atteint
    Cela dit, en regardant le code, cela a confirmé mon expérience selon laquelle Rust a une ergonomie assez mauvaise pour le SIMD et le travail avec les pointeurs, et plus largement pour l’ingénierie de la performance

    • En tant qu’ingénieur Rust, je suis assez d’accord, mais le travail avec les pointeurs et la mémoire brute est volontairement très contraint pour des raisons de sécurité, et il y a aussi l’idée de vraiment forcer à réfléchir à ce que fait le langage
      Cela dit, le portable SIMD de Rust n’est pas encore très convaincant par rapport à C++, et pour descendre au niveau des zones d’octets brutes, des pointeurs et de la manipulation de buffers, il faut se familiariser avec Pin, MaybeUninit, etc.
      portable_simd et allocator_api sont instables depuis des années, la barrière à l’entrée reste élevée et l’ensemble est plus maladroit, ce qui est pour l’essentiel intentionnel
      En revanche, rien n’empêche de créer soi-même des abstractions plus agréables à utiliser dans son programme, ou d’employer des crates tierces
    • Je ne suis pas d’accord avec l’idée que l’ergonomie soit mauvaise
      Les intrinsics SSE en C++ sont bien pires, avec leurs underscores hideux et des noms difficiles à mémoriser

  • J’ai déjà implémenté quelque chose du mieux possible en C++ classique, puis vu quelqu’un arriver avec une version SIMD plus de 10 fois plus rapide, et c’est parfois vraiment stupéfiant
    En contrepartie, ce code est moins portable
    J’aimerais que l’auto-vectorisation des compilateurs soit meilleure, et qu’il existe aussi une forme de support au niveau du langage, comme des annotations permettant localement une certaine réorganisation des opérations

    • Un bon code SIMD doit tenir compte avec soin de la manière dont les données sont disposées en mémoire
      En dehors d’un contexte très local, le compilateur ne peut pas réorganiser les données à votre place, ce qui rend l’auto-vectorisation vraiment difficile
    • Même si le compilateur pouvait optimiser parfaitement, il existe beaucoup de garanties sérielles inévitables
      Par exemple, dans for(double v: vec) sum+=v, l’addition en virgule flottante n’est pas associative ; additionner les valeurs dans l’ordre n’est donc pas équivalent à une approche SIMD où l’on additionne par groupes espacés de 8 puis combine les restes
      Du point de vue du compilateur, cela peut sembler être une optimisation évidente, mais à moins d’indiquer explicitement qu’on peut assouplir certaines garanties, il privilégiera la préservation de la sémantique sérielle plutôt que l’optimisation
      Cela devient donc vite compliqué et, comme le disait janwas, il vaut mieux utiliser des bibliothèques sur les chemins critiques, en particulier Google Highway ou quelque chose comme Intel ISPC
    • C’est justement l’un des intérêts d’un langage de programmation système comme C++
      Il cherche à être efficace de la manière la plus portable possible, tout en facilitant la programmation ciblée quand c’est nécessaire
      Les compilateurs FORTRAN sont clairement meilleurs en auto-vectorisation, parce que l’aliasing n’y est pas permis
      C++ est pénalisé par le fait qu’il suit le modèle mémoire du C
    • On peut aussi simplement utiliser CUDA
      CUDA est du C++ conçu pour les GPU, qui sont les machines SIMD ultimes d’aujourd’hui, et ROCm est en pratique assez proche d’un CUDA pour AMD
      Personnellement, j’aimais bien le C++AMP de Microsoft, que je trouvais le plus simple pour débuter
      Dommage qu’il n’ait finalement pas trouvé sa place
    • D’après mon expérience, ce genre de chose arrive souvent
      Et avec une bibliothèque d’encapsulation SIMD, on peut en réalité obtenir quelque chose d’assez portable

  • Petite remarque au passage : le compilateur n’a pas réussi à optimiser cette implémentation de popcount en une seule instruction, mais c’est possible avec d’autres implémentations
    C’est certes assez délicat : https://godbolt.org/z/T69KxWWW8

  • Il a été dit que _mm256_cvtps_epu32 représente une opération bas niveau d’un jeu d’instructions donné, et décrit comme le cast float-vers-int d’AVX2, mais cette instruction fait en fait partie d’AVX-512
    AVX2 n’a pas de cast float-vers-int non signé ; en AVX1, le résultat entier est signed et l’instruction est _mm256_cvtps_epi32

  • Je me demande ce que cela donnerait comparé à fastbase64[0]
    L’article est excellent et je suis ravi de voir ce type de contenu en ligne, mais j’ai plus de mal à partager l’optimisme de l’auteur au sujet des bibliothèques portable SIMD
    [0]: https://github.com/lemire/fastbase64

  • À mon avis, ISPC est tout simplement meilleur que d’ajouter du SIMD à C++ ou à Rust
    Il prend aussi en charge le dispatch dynamique, une fonctionnalité pénible à implémenter soi-même

    • Tout outil qui pousse davantage de gens à utiliser le SIMD est globalement une bonne chose, mais personnellement je préfère quand le SIMD est intégré dans la même toolchain
      On peut ainsi réinjecter des appels inline vers du C++, utiliser templates et classes dans le code SIMD, et même inliner ensemble plusieurs zones de code SIMD
      Je suis d’accord sur le fait que le dispatch dynamique est difficile à implémenter, mais Highway s’en charge
    • Je me demande si, pour de petites sous-routines comme dans l’article, C++ ou Rust appellent facilement ISPC

  • Excellent article, avec cette impression persistante de « je ne serai jamais aussi intelligent »

    • C’est simplement que ce n’est pas votre domaine de travail
      Un peu comme la plupart des gens ne sont ni ingénieurs logiciel ni physiciens
      Avec quelques mois d’étude concentrée, vous pourriez probablement atteindre un niveau comparable
    • Si vous avez l’occasion de rencontrer un employeur ou un projet qui a besoin de ce genre de choses, vous pourriez probablement devenir « aussi intelligent » sur ce point
      Au fond, c’est surtout une question d’intérêt et de nécessité
      Moi aussi je passe de l’optimisation des performances à une ingénierie plus proche du système ou du bare metal dans des projets personnels, et j’aimerais en avoir davantage besoin dans mon travail
      Mais la plupart des emplois du secteur n’exigent pas cela
    • Cela vaut le coup d’essayer AoC '23 avec APL/j/k, BQN, Python/numpy, CUDA et autres
      Pas en Python idiomatique, mais en résolvant tout avec numpy
      C’est amusant, on peut y apprendre cette forme d’ingéniosité, et beaucoup d’éléments de l’article paraissent tout à fait naturels quand on aborde les problèmes avec l’état d’esprit de ces langages
      Avec le temps, on commence à voir les problèmes sous cette forme
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • Article intéressant
    Dès le premier exemple, l’auteur dit que l’implémentation non vectorisée de popcnt produit un code « franchement ridiculement mauvais », mais en mode release avec le CPU cible natif, cette fonction semble en réalité être assez bien vectorisée
    https://godbolt.org/z/WE1Eq65jY

    • Le code ci-dessous devrait produire une sortie équivalente
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      Il est compilé en popcnt eax, edi; ret
      Sur de grands vecteurs de bits, une implémentation AVX2 peut être plus rapide que POPCNT
      Voir « Faster Population Counts Using AVX2 Instructions » : https://academic.oup.com/comjnl/article/61/1/111/3852071
      32 bits n’est pas une taille suffisante, et le code généré par Rust est effectivement ridiculement mauvais
    • Idéalement, cela devrait être abaissé en instruction popcnt
    • L’autovectorisation fonctionne parfois, parfois non
      J’ai récemment écrit du code où il fallait compter le nombre de bits dans un masque résultat d’opérations vectorielles, et là cela est bien transformé en popcnt
      https://godbolt.org/z/zT9Whcnco

  • À cause de passages du genre « ça ressemble à une question piège… ce n’est pas simplement un add ? », on a généralement envie de cibler la représentation vectorielle intermédiaire et de laisser le compilateur décider des détails
    Par exemple, les puces Haswell disposaient de plusieurs unités d’exécution en virgule flottante par cœur, et le CPU pouvait exécuter simultanément plus d’une opération en virgule flottante pipelineée, mais parmi elles une seule instruction add était possible
    S’il y avait beaucoup d’additions ne dépendant pas du résultat précédent, au point d’éviter la latence, on pouvait aussi envoyer des instructions de fused multiply-add avec un terme de multiplication égal à 1 afin de doubler le débit des additions
    Cette instruction pouvait être exécutée en parallèle d’une addition vectorielle classique en virgule flottante