La fonction `tolower()` avec AVX-512

• Il y a quelques années, j’ai écrit un billet sur une méthode pour accélérer tolower() à l’aide d’astuces SWAR. Il y a quelques jours, un article d’Olivier Giniaux a éveillé mon intérêt pour une optimisation utilisant des instructions SIMD afin de traiter de petites chaînes. Cette méthode est utilisée dans une fonction de hachage rapide écrite en Rust.

• Les instructions SIMD permettent de traiter facilement des chaînes courtes, mais le transfert entre la mémoire et les registres vectoriels a toujours été un point gênant. L’article d’Olivier propose une manière intéressante de résoudre ce problème.

Signes d’espoir

• Certains jeux d’instructions SIMD offrent des fonctions utiles de chargement et de stockage masqués pour le traitement de chaînes. Elles fonctionnent au niveau de l’octet.

  • ARM SVE : disponible sur de récents gros cœurs ARM Neoverse, par exemple Amazon Graviton. En revanche, indisponible sur Apple Silicon.
  • AVX-512-BW : disponible sur les récents processeurs AMD Zen. AVX-512 est un ensemble d’extensions complexe, avec une prise en charge aléatoire chez Intel.

• Comme je dispose d’une machine Zen 4, j’ai décidé d’essayer AVX-512-BW.

tolower64()

• En utilisant le guide des intrinsics Intel, j’ai écrit une fonction tolower() de base capable de traiter 64 octets à la fois.
  • J’ai recherché mm512*epi8 en utilisant * comme joker afin de trouver les fonctions AVX-512 opérant au niveau de l’octet.
  • J’ai rempli quelques registres avec 64 octets utiles.
  • J’ai défini les constantes nécessaires pour convertir les majuscules en minuscules.
  • J’ai comparé les caractères d’entrée à A et Z pour vérifier s’ils sont en majuscule.
  • J’ai utilisé un masque pour convertir en minuscule lorsqu’il s’agit bien de majuscules.

Chargements et stockages en masse

• Il faut encapsuler le noyau tolower64() dans une fonction plus pratique. Par exemple, une fonction qui copie une chaîne tout en la convertissant en minuscules.
  • Pour les longues chaînes, on utilise des instructions de chargement et de stockage vectoriels non alignés.

Chargements et stockages masqués

• Pour les petites chaînes ainsi que la fin des longues chaînes, on utilise des chargements et stockages non alignés masqués.
  • Le masque a ses len premiers bits activés.
  • Les opérations de chargement et de stockage ressemblent à leurs versions pleine largeur avec un masque en plus.

Benchmarks

• Les performances de plusieurs fonctions similaires ont été mesurées.

  • Compilation avec Clang 16 et exécution sur un AMD Ryzen 9 7950X.
  • Chaque fonction a été compilée séparément afin d’éviter les interférences liées à l’inlining et aux déplacements de code.

• Résultats :

  • tolower64 est la plus rapide de toutes les fonctions testées.
  • copybytes64 utilise aussi AVX-512 d’une manière similaire à tolower64, mais n’est pas beaucoup plus rapide.
  • copybytes1 effectue un memcpy octet par octet et montre que l’auto-vectorisation de Clang 11 est relativement médiocre.
  • La fonction standard tolower() est la plus lente.
  • tolower1 est une version octet par octet de tolower() compilée avec Clang 16 ; l’auto-vectorisation s’est améliorée, mais cela reste lent.
  • tolower8 est la version SWAR de tolower() présentée dans un précédent billet de blog ; Clang tente une auto-vectorisation, mais le résultat n’est pas bon.
  • memcpy est rapide au début, puis tombe à la moitié de la vitesse de copybytes64.

Conclusion

• AVX-512-BW est très utile, en particulier pour le traitement des chaînes courtes.

• C’est très rapide sur Zen 4, et les fonctions intrinsèques sont faciles à utiliser.

• Les performances d’AVX-512-BW sont très régulières.

• Je n’ai pas pu examiner ARM SVE en détail faute de machine compatible, mais je suis curieux de voir à quel point SVE fonctionne bien sur les chaînes courtes.

• J’espère que ces extensions de jeu d’instructions seront plus largement utilisées. Elles pourraient nettement améliorer les performances du traitement de chaînes.

• Le code de ce billet de blog est disponible sur mon site web.

Résumé de GN⁺

• Cet article explique comment traiter efficacement de courtes chaînes à l’aide d’instructions SIMD.
• Il montre que les jeux d’instructions AVX-512-BW et ARM SVE sont utiles pour le traitement de chaînes.
• Les benchmarks montrent qu’AVX-512-BW offre d’excellentes performances, en particulier sur les chaînes courtes.
• Cet article sera utile aux développeurs intéressés par l’optimisation des performances.

[GN⁺]

Commentaires Hacker News

• Dans le modèle mémoire de Rust et LLVM, l’astuce de l’« unsafe read beyond of death » est considérée comme un comportement indéfini

  • Le compilateur peut supposer qu’un tel comportement ne se produit pas afin d’optimiser
  • Pour l’éviter, il faut utiliser de l’assembleur inline

• Cela suscite de la curiosité au sujet de l’implémentation AVX512 d’AMD et de la concurrence avec AVX10 d’Intel

  • AVX10 vise à résoudre le problème des cœurs P vs E chez Intel
  • AMD utilise soit toute la largeur de Zen5, soit le double pompage 256 bits de Zen4 et de Zen5 mobile selon le contexte
  • Le gain de performance important se produit sur les cœurs Zen4

• L’optimisation SWAR n’est utile que pour les chaînes alignées sur des adresses de 8 octets

  • Si on l’applique à des chaînes non alignées, elle est plus lente que l’algorithme d’origine
  • Découper l’algorithme en trois parties nécessite davantage d’instructions

• L’ajout d’un masque paraît propre

  • Ce serait bien qu’il existe dans les fonctionnalités intégrées de .NET un moyen de manipuler directement les registres de masque d’AVX512

• Avec Clang, on peut obtenir de meilleurs résultats

  • Il offre une meilleure sélection d’instructions et un résultat mieux déroulé

• La boucle principale pour les chaînes de petite taille utilise une instruction en moins

  • Il est important de traiter rapidement les chaînes courtes

• Une implémentation similaire de conversion majuscules/minuscules ASCII en UTF-8 a été écrite en C#

  • Comme les chaînes courtes dominent la plupart des bases de code, il est important de les traiter rapidement

• Il existe un exemple d’utilisation de SIMD avec AVX512 pour transformer du texte en uwu

• Ce serait encore plus impressionnant en prenant en compte la conversion des caractères Unicode

  • La plupart des programmeurs ne se préoccupent que de l’ASCII, mais il existe tout un monde au-delà du jeu de caractères standard

• Quelqu’un a déjà évité des problèmes de buffer SIMD par le passé en ajoutant une bordure noire autour des images

  • On ne contrôle pas toujours totalement les entrées