Une fonction `tolower()` implémentée avec AVX-512

 (dotat.at)
1 points par GN⁺ 2024-07-30 | 1 commentaires | Partager sur WhatsApp
  • Il s’agit d’une expérimentation visant à exploiter les performances SIMD même sur de petites chaînes, en copiant la chaîne tout en convertissant les majuscules ASCII en minuscules par blocs de 64 octets avec AVX-512-BW
  • Le cœur de l’implémentation consiste à comparer chaque octet pour vérifier s’il est compris entre 'A' et 'Z', puis à appliquer une opération masquée qui n’ajoute ('a' - 'A') qu’aux positions concernées
  • Les courtes chaînes ainsi que la fin résiduelle des longues chaînes sont traitées via des load/store masqués, afin de réduire le coût de traitement des petits fragments, un point souvent problématique pour le code SIMD
  • Mesuré avec Clang 16, Debian 11 et un AMD Ryzen 9 7950X sur environ 1 MiB de copie avec des chunks de 1 octet à 1 KiB, tolower64 fait partie des implémentations constamment les plus rapides du comparatif
  • Sur Zen 4, AVX-512-BW semble particulièrement bien adapté au traitement de chaînes, mais les extensions ARM SVE et RISC-V Vector n’ont pas pu être vérifiées en détail directement

Créer un tolower() 64 octets avec AVX-512-BW

  • L’objectif est d’implémenter en SIMD un noyau tolower() qui copie une chaîne tout en convertissant les caractères ASCII majuscules en minuscules
  • AVX-512-BW est une extension qui prend en charge les opérations sur octets et mots, disponible sur les récents processeurs AMD Zen
    • AVX-512 est découpé en plusieurs extensions, ce qui rend le support complexe
    • Le support côté Intel est jugé particulièrement irrégulier
  • ARM SVE fournit lui aussi des load/store masqués au niveau octet bien adaptés au traitement de chaînes
    • Disponible sur de récents gros cœurs ARM Neoverse, par exemple Amazon Graviton
    • Non disponible sur Apple Silicon
  • L’extension vectorielle RISC-V adopte un style similaire à ARM SVE et se trouve sur plusieurs petits ordinateurs monocartes

Fonctionnement de tolower64()

  • tolower64() est un noyau basé sur AVX-512 qui traite 64 octets à la fois
  • On commence par remplir un registre vectoriel avec les valeurs de référence suivantes
    • 'A'
    • 'Z'
    • 'a' - 'A'
  • Le vecteur d’entrée c est comparé à 'A' et 'Z' pour produire deux masques 64 bits
    • positions où c >= 'A'
    • positions où c <= 'Z'
  • Les deux masques sont combinés avec _kand_mask64() pour former le masque is_upper, qui ne marque que les positions contenant des majuscules
  • Enfin, on applique _mm512_mask_add_epi8()
    • si is_upper vaut false pour un octet, la valeur originale c est conservée
    • si is_upper vaut true, on obtient c + ('a' - 'A')

Traitement des longues et des courtes chaînes

  • La majeure partie des longues chaînes est traitée avec des load/store vectoriels non alignés classiques
    • _mm512_loadu_epi8()
    • tolower64()
    • _mm512_storeu_epi8()
  • Pour les courtes chaînes et le dernier fragment restant des longues chaînes, on utilise des load/store non alignés masqués
  • Le masque est construit avec uniquement les len bits de poids faible activés
    • uint64_t len_bits = (~0ULL) >> (64 - len)
    • chargés dans un registre de masque SIMD via _cvtu64_mask64(len_bits)
  • _mm512_maskz_loadu_epi8() remplit avec 0 les positions du registre destination pour lesquelles le masque est désactivé
  • _mm512_mask_storeu_epi8() n’écrit que les positions où le masque est activé
  • Cette approche est la clé pour traiter rapidement les petits fragments de chaîne

Conditions du benchmark et éléments comparés

  • Le benchmark a été exécuté avec Clang 16, Debian 11 et un AMD Ryzen 9 7950X
  • La mesure porte sur environ 1 MiB de copie, avec des longueurs de chunk variant de 1 octet à 1 KiB
  • Afin de refléter les différences d’alignement entre la chaîne source et la chaîne destination, quelques octets étaient intercalés entre elles, sans être comptabilisés dans le volume mesuré de 1 MiB
  • Le Ryzen 9 7950X disposant de 1 MiB de cache L2 par cœur, chaque exécution de test est supposée déborder jusqu’au cache L3
  • Chaque fonction a été compilée séparément pour éviter les interférences dues à l’inlining et aux déplacements de code
    • Dans du code réel, il est plus probable qu’on cherche à favoriser l’inlining plutôt qu’à l’empêcher

Résultats : les performances régulières de tolower64

  • En rose, tolower64 reste globalement dans le groupe de tête parmi les fonctions testées
    • il y a un léger recul à 65 octets, au moment du passage au deuxième vecteur
    • la courbe remonte vite et ne présente pas de creux marqué, ce qui montre l’efficacité des load/store masqués pour les petits fragments de chaîne
  • En vert, copybytes64 est une version de memcpy qui utilise AVX-512 de façon similaire
    • elle n’est pas beaucoup plus rapide que tolower64
    • les versions récentes de Clang reconnaissent la sémantique de cette fonction et la réécrivent entièrement, donc elle a été compilée avec Clang 11
  • En orange, copybytes1 est une version octet par octet de memcpy
    • compilée avec Clang 11
    • elle montre que les heuristiques d’auto-vectorisation de Clang 11 sont relativement peu performantes sur des fragments de chaîne de moins de 256 octets
  • En rouge, tolower est la référence qui appelle le tolower() standard de <ctype.h>, et elle est très lente
  • En violet, tolower1 est une version octet par octet de tolower() compilée avec Clang 16
    • l’auto-vectorisation de Clang 16 est nettement meilleure que celle de Clang 11
    • elle reste plus lente que la version écrite à la main et génère un code bien plus complexe
    • la gestion des petits fragments de chaîne est moins bonne que dans tolower64, d’où une courbe de performances plus irrégulière et plus pointue
  • En brun, tolower8 est le tolower() SWAR présenté dans un précédent article
    • Clang tente de l’auto-vectoriser, mais la fonction est trop complexe pour produire un bon résultat
    • compilée avec Clang 16, elle présente malgré tout la même falaise de performances autour de 256 octets que le style de code de Clang 11
  • En bleu, memcpy appelle le memcpy de glibc
    • il est rapide au départ, mais connaît une zone où il tombe à environ la moitié de la vitesse de copybytes64
    • la cause n’a pas été identifiée

Conclusion et code

  • AVX-512-BW est très bien adapté au traitement des chaînes, en particulier des chaînes courtes
  • Sur Zen 4, il est très rapide et les fonctions intrinsic restent relativement simples à utiliser
  • Sa caractéristique la plus frappante est la régularité des performances
    • on n’observe presque pas les creux liés au passage au code scalaire sur petits fragments, comme c’est souvent le cas avec l’auto-vectorisation
  • Faute d’un accès pratique à du matériel compatible ARM SVE ou RISC-V Vector extension, ces deux extensions n’ont pas pu être étudiées en détail
  • Le code est disponible dans le dépôt git du site web

À lire aussi

1 commentaires

 
GN⁺ 2024-07-30
Avis sur Hacker News

  • L’astuce de l’« unsafe read beyond of death » est considérée comme un comportement indéfini dans les modèles mémoire de Rust et de LLVM, même si le matériel l’autorise
    Comme pour les autres comportements indéfinis, le compilateur peut supposer pendant l’optimisation que « cela n’arrive pas », ce qui peut produire des résultats inattendus, et il faut utiliser de l’assembleur inline pour contourner cela
    https://github.com/ogxd/gxhash/issues/82

    • Ce serait bien d’avoir une alternative autre que l’assembleur dans ce genre de cas
      Un chargement du type « lire au-delà de la plage allouée comme des éléments non spécifiés, et ne considérer cela comme un comportement indéfini que si le matériel n’aime pas ça » ne semble pas difficile à prendre en charge, même si en interne ce n’est qu’un alias de cet appel assembleur
      Mieux encore, il serait souhaitable que chaque allocation — malloc, pile, constantes, etc. — garantisse au moins 64 octets d’adresses sans fault après sa fin, mais cela demanderait la coopération de plusieurs composants et serait bien plus complexe
      Avec un allocateur personnalisé, c’est trivial, mais dans ce cas il devient difficile d’utiliser du code SIMD sur des données hors du tas personnalisé, et on reste dépendant d’une très faible possibilité de segfault
      Les sanitizer et Valgrind resteraient malgré tout utiles, car ils pourraient suivre les valeurs hors limites comme des valeurs indéterminées et signaler une erreur lors de leur utilisation réelle
    • Je me demande si c’est vraiment vrai même au niveau matériel
      Que se passe-t-il si on lit depuis une page non mappée ou une mémoire protégée ? Je n’ai pas regardé le code, donc je ne sais pas si les garanties d’alignement permettent d’éviter cela
    • L’explication selon laquelle « si c’est un comportement indéfini, le compilateur peut supposer que cela n’arrive pas » est fausse
      Le comportement indéfini est un terme technique du standard C, donc le généraliser ainsi est déjà étrange, et l’ANSI C n’autorise pas explicitement cette hypothèse, tandis que l’ISO C est plus ouvert mais ne justifie pas concrètement cette supposition
      Présenter les choses comme « UB = on suppose que cela ne peut pas arriver » ressemble davantage à une rhétorique alarmiste assez malhonnête

  • Le code propre et performant de l’article donne envie de voir comment l’implémentation AVX512 d’AMD et le futur AVX10 d’Intel vont se mesurer
    L’objectif principal d’AVX10 semble être de résoudre la situation des P-cores/E-cores chez Intel, alors qu’AMD paraît avoir choisi une meilleure approche en conservant une API fluide tout en utilisant soit une implémentation pleine largeur sur Zen5, soit un traitement en deux passes sur 256 bits pour les Zen4 et Zen5 mobiles selon le contexte
    Les gros gains de performance de l’article proviennent tous de cœurs Zen4, et comme AVX512 a de nombreux avantages, il est frustrant qu’Intel l’ait tellement limité par segmentation de marché qu’il en a pratiquement empêché l’adoption dans le code client généraliste

    • Si Intel intègre réellement AVX10/256 dans tous ses futurs CPU, il finira par l’emporter simplement grâce à sa diffusion
      Le marché a toujours rejeté les chemins de code séparés selon les CPU, et en pratique les implémentations SIMD importantes ciblent le plus petit dénominateur commun
      AVX10.1/256 et AVX512VL ont un sous-ensemble commun ; une fois qu’assez de temps aura passé et que la plupart des CPU le prendront en charge, les gens finiront par viser cette partie-là
      AMD continuera sans doute à engranger des victoires faciles dans certains benchs mis à jour pour prendre en charge AVX512, mais si Intel maintient son plan AVX10, AMD finira probablement lui aussi par généraliser des pipelines SIMD en deux passes pour prendre efficacement en charge AVX10/256 tout en conservant la compatibilité AVX512
      Intel a pris beaucoup de mauvaises décisions ces dix dernières années, mais fragmenter le marché par jeu d’instructions a été l’une des pires. Cela a tué l’élan et l’intérêt pour l’innovation récente, et des fonctionnalités comme les opérations de masquage comptent bien plus que la largeur elle-même ; j’espère donc voir AVX10/256 sur toute la gamme
    • L’implémentation AVX512 de Zen 4 n’est pas en double pompage (double-pumped), et les journalistes tech devraient cesser de l’appeler ainsi
      Cette expression a un sens précis, qui ne correspond pas au fonctionnement réel
      Zen 4 décode simplement les opérations sur registres ZMM en plusieurs micro-opérations qu’il planifie sur des unités 256 bits libres, tandis que les shuffle 512 bits pleine largeur sont traités à part par un matériel dédié pour éviter une émulation coûteuse
      Ainsi, le Zen 4, avec ses quatre unités SIMD 256 bits, se comporte comme un solide cœur 2×512 bits, et cette implémentation n’est en rien une solution au rabais ; c’est peut-être même la meilleure forme vue jusqu’ici dans le matériel grand public
    • Je ne comprends pas pourquoi Intel ne résout pas ce problème en mettant de l’AVX512 en deux passes sur ses E-cores. Sinon, ils pourraient simplement produire pour le desktop des CPU avec uniquement des P-cores, comme cela devrait être le cas
      Ils ont déjà eu des années pour corriger cela, et le fait que l’adoption ne suive pas malgré la prise en charge par AMD est agaçant à cause de la part de marché ; AVX10 risque malheureusement surtout de permettre à Intel de garder plus longtemps son emprise sur le monde
      Sur desktop, j’aimerais voir de meilleurs cœurs, davantage de cœurs, et un jeu d’instructions bien standardisé qui ouvre l’accès à des fonctions utiles comme le SIMD large, le float16 et le gather/scatter, et AMD s’en sort plutôt bien sur ce point
      Intel, à l’inverse, colle des cœurs faibles à côté de cœurs corrects, limite les cœurs corrects pour s’aligner sur les plus faibles, sort pendant plusieurs générations des CPU avec le même nombre de cœurs, donne l’impression d’en avoir beaucoup grâce aux cœurs faibles, multiplie les variantes d’instructions au point qu’il devient difficile de définir un ensemble commun utile, et abandonne même des prises en charge d’instructions qu’il semblait avoir promises
      Les préférences des constructeurs desktop ont favorisé Intel dans les années 90, AMD au début des années 2000, Intel à la fin des années 2000 et dans les années 2010, et maintenant à nouveau AMD. Je me demande ce qu’Intel fera pour regagner du terrain autrement qu’en sabotant son concurrent, car la concurrence doit continuer pour éviter qu’un camp ne s’installe trop confortablement

  • Ressource intéressante à consulter pour le plaisir : http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

    • Il y a aussi ce genre de cas : passer le ß allemand en majuscule change la longueur de la chaîne
      Par exemple, "straße".upper() devient 'STRASSE'
      Et si l’on ne précise pas de locale, les conversions aller-retour en majuscule/minuscule du i sans point des langues turques cassent aussi : 'ı'.upper().lower() devient 'i'
    • Heureusement, ce code provient d’un travail sur le DNS, donc il est réservé à l’ASCII et n’a pas besoin de gérer cette complexité
      Il existe plusieurs protocoles ASCII insensibles à la casse, et on les rencontre souvent dans les hot paths de nombreux serveurs
    • Les chaînes utilisées comme ID en interne ne sont pas la même chose que le texte saisi par un humain
      Pour les premières, du pur ASCII en encodage 8 bits suffit généralement, mais pour le second cela devient complexe
      Les adresses DNS sont un exemple simple : techniquement, elles peuvent contenir presque tout Unicode, mais pour la résolution DNS réelle elles sont converties vers un sous-ensemble ASCII très limité, et cette résolution ne distingue pas la casse
      Bien sûr, il existe aussi des langages de programmation dont les identifiants sont insensibles à la casse tout en prenant en charge tous les systèmes d’écriture Unicode. Si vous travaillez là-dessus, toutes mes condoléances
    • À propos de l’exemple où l’allemand maße devient MASSE, l’allemand possède aussi un Eszett majuscule, ẞ
      Il n’est pas encore largement diffusé et les polices qui le prennent en charge sont rares, mais en théorie il existe désormais

  • J’ai l’impression que l’explication de « l’addition du masque » dans l’article est erronée
    Quand is_upper est false, il faudrait ajouter, et quand c’est true, copier tel quel, non ?

    • Ah, je viens seulement de réaliser que le nom de variable to_upper est inversé et qu’il faudrait l’appeler to_lower
      Merci d’avoir pointé ce passage trompeur ; j’ai corrigé l’article et le code
    • Cette opération est un tolower
      La lettre majuscule A vaut 0x40 et la minuscule 0x60, donc ajouter 0x20 doit se produire quand is_upper est true

  • Ce genre d’optimisation SWAR n’est souvent utile que lorsque la chaîne est alignée sur une adresse de 8 octets
    Appliquer un algorithme SWAR à une chaîne non alignée le rend souvent plus lent que l’algorithme d’origine
    Si on découpe en trois étapes — traiter le début jusqu’à l’adresse alignée, traiter le corps aligné, puis traiter la fin de moins de 8 octets — cela ajoute encore plus d’instructions
    Voici un cas similaire avec benchmark concernant l’affirmation erronée selon laquelle utf8.IsValid est plus rapide en Go : https://github.com/sugawarayuuta/charcoal/pull/1

    • Les opérations SIMD masquées d’AVX-512 et d’ARM SVE ont justement été conçues pour résoudre ce problème
      Les opérations mémoire se font toujours alignées et sur la taille complète du vecteur, tout en permettant de n’appliquer le masque qu’aux éléments valides
      Même si une opération mémoire vectorielle masquée n’est pas alignée et chevauche une page non mappée ou protégée, elle ne provoque pas de fault si la lane concernée est désactivée par le masque
      Il existe aussi des instructions de chargement spéciales qui réduisent la longueur du vecteur juste avant le premier élément qui provoquerait un fault, pour des opérations comme strlen() dont on ne connaît pas la longueur à l’avance

  • L’addition de masques a l’air élégante. J’aimerais pouvoir manipuler directement les registres de masque AVX512 dans les intrinsic .NET, mais pour l’instant il faut s’en remettre à des « idiomes reconnus »
    Si on analyse avec uiCA (CQA/MAQAO) la boucle critique écrite par l’auteur et générée par GCC, en prenant Ice Lake comme référence, on obtient environ 32B/cycle, soit presque 96GiB/s à 3GHz si l’on suppose l’absence de goulot d’étranglement mémoire. Bien sûr, sur ce genre d’algorithme, l’accès mémoire est toujours le facteur limitant
    Cela dit, on ne semble pas encore très proche d’une utilisation optimale, et avec Clang on arrive à 42.67B/cycle grâce à un déroulage mieux résolu et à un meilleur choix d’instructions. Le cache L2 aurait sans doute lui aussi du mal à soutenir un tel débit, mais il est intéressant de voir que la conversion majuscules/minuscules de chaînes de longueur intermédiaire se termine à peu près dans le temps qu’il faut pour que la lumière de l’écran atteigne la cornée
    Il y a quelques mois, j’ai implémenté en C# une conversion similaire des majuscules/minuscules ASCII dans l’UTF-8 : https://github.com/U8String/U8String/blob/main/Sources/U8Str...
    Comme les chaînes courtes dominent la plupart des bases de code, une conversion déroulée pour les longueurs inférieures à la taille de vectorisation est importante, et le switch est compilé en table de saut avec fall-through sans branchement
    Pour l’instant je n’utilise que 256 bits, car sur des architectures comme Zen 3 ou 4, qui n’ont que des unités SIMD 256×4, on est déjà à saturation. Un exemple comparé côte à côte avec une version C est ici : https://godbolt.org/z/eTGYhTPan
    Avec AVX512, il devrait être possible de ramener la transformation à 3 instructions avec vpternlogd, et quand .NET pouvait utiliser du matériel AVX512, il l’optimisait ainsi avec une largeur de 256 bits + AVX512VL, mais pour une raison étrange cela ne se reproduit pas aujourd’hui en largeur 512 bits
    On verra aussi une tentative SWAR ratée du côté du dispatch switch, et je me demande sous quelle licence le code est publié. Si ça passe la suite de tests, j’aimerais bien le réutiliser

    • Clang et GCC ont des manières différentes de traiter les intrinsic, et Clang est plus susceptible que GCC, en particulier sur les instructions AVX-512, de s’écarter des opcode indiqués par le guide Intel et de l’algorithme visé
      Vu l’architecture des deux compilateurs, c’est compréhensible, mais parfois cela améliore le résultat et parfois c’est pire
      Il y a quelques années, en travaillant sur un projet fortement vectorisé qui devait être compilable avec les deux, j’ai fini par conserver dans le dépôt une version C de référence, de l’assembleur inline pour certaines cibles et des fichiers .S
      Le Makefile est devenu sale, il a fallu ajouter des benchmarks à la suite de tests, et le coût de maintenance était élevé ; j’en ai conclu qu’il faut être très prudent quand on utilise les intrinsic comme outil bas niveau censé être meilleur que l’auto-vectorisation
      Par exemple : dans https://godbolt.org/z/T4Pjhrz5d, la sortie GCC était celle attendue, mais celle de Clang était surprenante et en pratique plus lente. Dans une boucle, uiCA donne 7 cycles pour Clang contre 4 pour GCC, et cela s’est aussi vu dans des benchmarks d’application réels où cette fonction était exécutée des milliards de fois dans un algorithme bruteforce
      En fouillant dans le code de LLVM, il me semble aussi avoir vu un problème où Clang 16, à cause d’un refactoring interne, pouvait ne plus émettre du tout certaines instructions AVX-512 à masque
    • L’analyse est très instructive
      Le but n’était pas de viser la meilleure performance possible ; au départ je voulais juste voir si ça marchait, et le fait que le premier essai s’en sorte plutôt bien a été un bonus
      Mon intérêt principal porte sur les chaînes plus courtes qu’un registre vectoriel et sur la suppression du creux dans le graphe de débit
      En suivant le lien vers le code à la fin de l’article de blog, on trouve les informations de licence ; à l’exception des parties MPL-2.0 écrites à l’origine pour BIND, c’est du 0BSD ou du MIT-0
    • Ce n’est pas évident en ne regardant qu’un gros bloc d’assembleur, mais Clang réécrit (x >= 'a' && x <= 'z') sous la forme (x - 'a') < ..., ce qui économise une instruction
      À cause d’un encodage d’opcode un peu étrange, cela peut parfois même réduire le nombre de chargements de registre

  • Je ne sais pas ce qu’est swar

    • C’est l’abréviation de « SIMD Within A Register »
      En général, cela désigne une technique consistant à empaqueter plusieurs éléments dans un seul registre afin de les traiter comme du SIMD sans instruction SIMD explicite
      Par exemple, si l’on met un entier de 31 bits et un entier de 32 bits dans un registre 64 bits en laissant 1 bit pour la retenue, une seule addition 64 bits permet d’effectuer deux additions
      Dans le jeu vidéo, on a utilisé ce genre d’astuces en empaquetant des valeurs RGB(A) dans des entiers 32 bits pour le rendu graphique, et ScummVM a aussi du code qui interpole 2 pixels RGB 16 bits, soit 6 composantes au total, dans une valeur 32 bits : https://github.com/scummvm/scummvm/blob/master/graphics/scal...
    • Cela signifie SIMD à l’intérieur d’un registre

  • Depuis l’arrivée d’Unicode, la notion de majuscules et minuscules est devenue un bourbier
    Pour bien faire, il faut beaucoup de données
    Si vous travaillez sur une tâche dont la réussite dépend du fait que tolower ASCII se termine à temps, il vaudrait mieux changer de cadre et revoir les hypothèses de départ

  • J’ai déjà évité complètement les problèmes de lecture hors tampon en SIMD en ajoutant une bordure noire autour des images
    Cela marchait très bien et, côté performances, pouvait battre certaines implémentations d’OpenCV, mais on ne peut pas toujours contrôler à ce point les entrées

  • Je me demande si cela a été essayé comme ça. Le résultat de l’auto-vectorisation a l’air assez propre
    https://godbolt.org/z/1c5joKK5n

    • C’est essentiellement la même chose que tolower1. Il suffit de regarder les puces sous le graphe