{n} fois plus rapide que C

 (owen.cafe)
1 points par GN⁺ 2023-07-07 | 1 commentaires | Partager sur WhatsApp
  • Même pour une petite boucle en C, la sortie du compilateur n’est pas toujours optimale : après ajustement manuel de l’assembleur x86_64, une version avec suppression des branches conditionnelles s’est révélée 6,73 fois plus rapide que la sortie de clang
  • La fonction ciblée traite, dans une chaîne, 's' comme +1, 'p' comme -1 et '\0' comme fin ; la sortie de clang 16 découpe ce flux en trois branches conditionnelles
  • En modifiant l’ordre des branches, en réorganisant les blocs de base et en remplaçant des sauts par de l’arithmétique, le temps d’exécution est passé de 3,23 s à 2,87 s, atteignant à ce stade la même vitesse que GCC 12
  • La version la plus rapide utilise cmove pour choisir, pour chaque caractère, la valeur à ajouter parmi 0, 1 et -1, puis exécute toujours add, avec un résultat de 0,48 s et un débit de 1,94 GiB/s
  • Le benchmark a été réalisé sur un AMD Ryzen 5 5625U avec Linux 6.1.33, en traitant 1000 fois une liste aléatoire d’un million de caractères 'p'/'s' ; le meilleur résultat parmi plusieurs exécutions a été retenu

Fonction testée et sortie du compilateur

  • La fonction cible incrémente un pointeur de chaîne caractère par caractère et met à jour l’entier res selon le caractère rencontré
    • 's' : res += 1
    • 'p' : res -= 1
    • '\0' : renvoie res
    • Autres caractères : aucun changement
  • Comme la fonction est petite, l’expérience part de l’idée que gcc ou clang pourraient l’optimiser assez bien, voire de façon optimale
  • L’assembleur initial produit par clang sépare les quatre cas en trois branches conditionnelles (je, je, jne)
    • Démarre avec res = 0
    • Lit un caractère et vérifie d’abord s’il s’agit de '\0'
    • Compare ensuite avec 'p' et 's'
  • Résultat initial de clang
    • Temps d’exécution : 3,23 s
    • Débit : 295,26 MiB/s
  • GCC générait un peu plus de code, mais était légèrement plus rapide

Tester les caractères fréquents avant la condition de fin rare

  • La boucle ne se termine que lorsqu’elle rencontre le caractère nul final '\0', qui apparaît au plus une seule fois dans cette fonction
  • La sortie de clang vérifie '\0' en premier, ce qui impose de tester la condition de fin pour chaque caractère 'p' et 's'
  • La première modification manuelle consiste à changer l’ordre des comparaisons pour tester d’abord 'p' et 's'
  • Résultat
    • Temps d’exécution : 3,10 s
    • Accélération : 1,04 fois
    • Débit : 307,64 MiB/s

Réorganisation des blocs de base et réduction des sauts

  • Les deux cas fréquents, 'p' et 's', sautent tous deux au début de la boucle ; on peut donc réduire les branches en plaçant l’un des blocs au-dessus de la boucle
  • En plaçant le bloc 's' juste avant la boucle, le traitement de 's' enchaîne directement avec la boucle sans saut séparé
  • En contrepartie, il faut sauter une fois vers la boucle au début de la fonction pour éviter le bloc 's'
    • Le saut au démarrage de la fonction ne se produit qu’une seule fois
    • Le caractère 's' peut être rencontré de nombreuses fois, ce qui rend le compromis acceptable
  • Résultat
    • Temps d’exécution : 2,98 s
    • Accélération totale : 1,08 fois
    • Débit : 320,02 MiB/s

Supprimer un saut inconditionnel avec de l’arithmétique

  • De l’arithmétique est utilisée pour supprimer le jmp inconditionnel qui, dans le bloc p:, revient à la boucle
  • Une décrémentation de 1 peut être obtenue par sub eax, 2 puis inc eax, ce qui permet, après le traitement de 'p', d’enchaîner avec le bloc 's'
  • Cette méthode supprime une autre instruction de branchement
  • Résultat
    • Temps d’exécution : 2,87 s
    • Accélération totale : 1,12 fois
    • Débit : 332,29 MiB/s
  • À ce stade, les performances sont identiques à celles du code généré par GCC 12
    • Le code de GCC 12 s’exécute lui aussi en 2,87 s
    • La version écrite à la main compte 13 instructions
    • La sortie de GCC compte 19 instructions
    • Le code de GCC semble dérouler la boucle et réutiliser dans une certaine mesure les blocs de case

Remplacer les branches conditionnelles par cmove

  • Si les branches conditionnelles sont le goulet d’étranglement, on peut se passer du prédicteur de branchement et supprimer les branches conditionnelles elles-mêmes
  • La version la plus rapide utilise cmove, c’est-à-dire un déplacement conditionnel en cas d’égalité
  • Les règles de fonctionnement sont simples
    • La valeur par défaut est 0
    • Si le caractère courant est 's', la valeur est 1
    • Si le caractère courant est 'p', la valeur est -1
    • À chaque itération, la valeur choisie est toujours ajoutée à res
  • Cette approche supprime de nombreuses flèches dans le graphe de flot de contrôle
  • Résultat
    • Temps d’exécution : 0,48 s
    • Accélération totale : 6,73 fois
    • Débit : 1,94 GiB/s
  • Dans l’assembleur d’une boucle C compacte écrite à la main, une optimisation que le compilateur n’a pas automatisée a donc permis un gain de vitesse de l’ordre de 6 fois

Tentative d’économie de registres et autres expériences infructueuses

  • Une version utilisant sete de x86_64 pour définir conditionnellement un registre d’un octet à 0 ou 1 a également été essayée
  • Cette version supprime l’utilisation de r8d, mais elle est plus lente que la version n’utilisant que cmov
  • Résultat
    • Temps d’exécution : 0,51 s
    • Accélération totale : 6,33 fois
    • Débit : 1,83 GiB/s
  • Utiliser moins de registres, ou des opérations sur 8 bits au lieu d’opérations sur 32 bits, ne rendait pas le code plus rapide
  • D’autres essais ont eux aussi réduit les performances
    • Déroulage de la boucle de la meilleure version : plus lent
    • Alignement du début de la boucle sur une frontière de 16 octets : plus lent
    • Dans GNU assembler, placer .align <bytes> avant un label permet d’insérer des nop

Environnement de benchmark et code

  • La liste du code se trouve sur GitHub
  • Environnement de benchmark
    • OS : Linux 6.1.33
    • CPU : AMD Ryzen 5 5625U with Radeon Graphics
    • CPU family 25, 6 cœurs, 2 threads par cœur, 1 socket
    • clang : 16.0.1
    • gcc : 12.2.0
  • La version C est compilée avec -march=native afin de générer du code adapté au CPU précis
  • Le benchmark porte sur une liste d’un million de caractères composée aléatoirement de 'p' et de 's'
    • Chaque version de la fonction traite cette liste 1000 fois
    • Chaque version est exécutée plusieurs fois, et le meilleur résultat est sélectionné
  • Un article de suivi, part two, est également lié

À lire aussi

1 commentaires

 
GN⁺ 2023-07-07
Avis Hacker News

  • La bonne conclusion est moins l’assembleur écrit à la main est 6 fois plus rapide que le C que les sauts peuvent être bien plus lents que l’arithmétique conditionnelle
    En C aussi, on peut facilement obtenir le même effet sans switch, avec un ou deux if. En réécrivant la fonction C pour faire quelque chose comme incrémenter si c’est s, décrémenter si c’est p et terminer si c’est \0, elle est devenue 5,5 fois plus rapide, passant dans l’exemple de 3,58 s à 0,65 s

    • Bien. Dans la partie 2, le C a été réécrit et a obtenu un gain de vitesse de 12x : https://owen.cafe/posts/the-same-speed-as-c/
      Comme d’autres l’ont dit, on peut aussi vectoriser l’algorithme après avoir ajusté l’entrée. J’y ai vu un exercice pédagogique, et j’espère sincèrement qu’on n’en viendra pas à descendre en assembleur sans très bonne raison
    • Dire que les sauts sont plus lents que l’arithmétique conditionnelle est vrai quand les sauts sont imprévisibles. Si les sauts sont prévisibles, ils sont plus rapides
      Linus a d’ailleurs écrit longuement autrefois sur le fait que cmov n’est pas utile pour les branches prévisibles : https://yarchive.net/comp/linux/cmov.html
    • Je me demande quelle version de GCC est utilisée. J’ai obtenu les mêmes performances sur Ubuntu et Windows, et avec gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0, lone et ltwo prenaient tous deux environ 3,58 s
    • Je me demande si remplacer un switch par plusieurs if est toujours plus rapide. À partir de combien de cas un switch redevient-il plus rapide ? Et si c’est cohérent, cela devrait relever d’une optimisation du compilateur
    • On pourrait penser que le compilateur devrait être capable d’effectuer ce genre de transformation

  • À mon avis, le code d’origine n’était pas écrit de façon très favorable au compilateur. Écrit comme result += *s == 's'; result -= *s == 'p';, le compilateur génère un code sans branchement avec sete/cmov approprié, et on obtient presque la même vitesse que l’assembleur optimisé de l’article
    En revanche, il ne fait ni déroulage de boucle ni vectorisation. Si on passe la taille de la chaîne séparément pour itérer avec size, le compilateur connaît la taille de la boucle et peut la dérouler, voire utiliser des instructions AVX-512 si possible. C’est bien plus rapide sur de grandes entrées, mais je n’ai pas envie de le benchmarker moi-même. Si vous êtes un programmeur C qui ne suit pas la longueur des chaînes, faites comme vous voulez, mais à mon avis il ne faut vraiment pas faire ça : https://godbolt.org/z/rde51zMd8

    • Une version plus favorable au compilateur figure dans la partie 2 : https://owen.cafe/posts/the-same-speed-as-c/
      Cette version atteint 3,88GiB/s. Je n’ai volontairement pas poussé jusqu’à la vectorisation, parce que je voulais garder un périmètre réduit et montrer les astuces assembleur de l’article. Il y aura peut-être plus tard un article sur le padding de la chaîne d’entrée et la vectorisation de l’algorithme
    • Il manque une ligne importante dans le code : /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • En Nim aussi, cela semble se déclencher ainsi : activer {.overflowChecks:off.} et parcourir input, en incrémentant si 's' == c et en décrémentant si 'p' == c
      Sur un Apple M1, cela a donné environ 5x de gain de vitesse, et avec la vérification de débordement activée, ce n’était qu’environ 2x plus rapide que la version C de base. C’est toujours utile de connaître de bons motifs pour déclencher des optimisations SIMD
    • Est-ce que « il ne faut vraiment pas faire ça » signifie qu’il ne faut pas éviter de suivre la longueur des chaînes ?

  • En tant que personne assez proche du profil d’expert en optimisation, je résoudrais probablement ce problème d’une manière complètement différente. Sur ma machine, la version C initiale traitait 389MB/s, et si l’assembleur de l’article apporte bien le même gain de 6,2x, on arrive à environ 2,4GB/s
    Sur de longs buffers, cette version C++ dépasse 24GB/s sur ma machine : https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Sans assembleur, avec des intrinsics AVX2, elle est 61 fois plus rapide que la version d’origine

    • Intéressant. Au lieu de garder des compteurs dans les registres ymm, on pourrait peut-être vectoriser le prologue avec movemask et popcnt
      Je n’ai pas encore testé ce code, donc il faudrait le benchmarker, mais il semble possible d’aborder le problème en construisant des masques pour s, p et \0, puis en utilisant tzcnt et bzhi pour compter les bits jusqu’à la fin de la chaîne
    • Par curiosité, j’aimerais savoir si c’est aussi faisable avec std::experimental::simd : https://en.cppreference.com/w/cpp/experimental/simd
    • Ce serait bien de réécrire ça dans un format compatible avec le dépôt de @414owen
    • Je me demande quelles sont de bonnes ressources pour apprendre et pratiquer AVX

  • Ce code semble vraiment parfaitement adapté au SIMD. Si on peut modifier le prototype pour qu’il reçoive une longueur explicite, il devient facile de lire et traiter 16 octets à la fois
    Il suffit d’additionner et soustraire directement les résultats des comparaisons, et le simple fait d’appeler strlen() au début de la fonction pour obtenir une longueur explicite en vaudrait probablement déjà la peine

  • J’ai rapidement bricolé une implémentation vectorisée RISC-V. L’idée est de lire la chaîne avec rvv, de trouver la position de \0, puis de compter le nombre de s et de p avec vcpop
    Sur un Mangopi MQ Pro (C906, rv64gc + rvv 0.7.1, longueur de vecteur 128 bits), switch donnait 0,19 octet/cycle, l’implémentation C avec table 0,17 octet/cycle, et rvv 1,57 octet/cycle, avant de retomber à 1,35 après environ 30KiB. En alignant le pointeur sur une page et en s’assurant que vl ne dépasse pas la taille d’une page, on peut monter à 2/1,7 octets/cycle

    • Pour être complètement correct, les chargements devraient être des fault-only-first load. rvv dispose de cette fonctionnalité ; sinon, cela peut échouer si l’octet nul se trouve juste avant la fin de la mémoire allouée

  • Cela ressemble à une propriété propre à l’architecture x86. Le coût de l’absence de branchement y est tellement faible que le branchement paraît relativement coûteux : https://wordsandbuttons.online/challenge_your_performance_in...
    Mais ce n’est pas forcément vrai sur d’autres processeurs : https://wordsandbuttons.online/using_logical_operators_for_l...
    La question plus générale est de savoir pourquoi on a besoin du C. Si l’on va ajuster à la main pour obtenir les meilleures performances sur un matériel précis, alors C est le mauvais outil, et il faut de l’assembleur avec un système de macros correct. L’objectif initial du C était de faciliter le portage du code système d’une plateforme à l’autre, en acceptant au passage une perte d’efficacité. C’est un peu comme écrire un poème hindi en espéranto pour le traduire automatiquement ensuite dans la langue voulue, au lieu de le traduire directement en ourdou. On n’obtient pas deux grands poèmes, mais rapidement deux mauvaises traductions, et c’est précisément le rôle du C

  • Avec une compilation FDO/PGO, le réagencement des branches et des blocs peut clairement avoir lieu. Sans FDO, le compilateur ne peut pas savoir à quelle fréquence chaque branche sera prise. Dans certains cas, FDO peut aussi activer cmov
    Cela dit, l’efficacité de cmov par rapport à un simple test/jump dépend fortement du degré de prédictibilité de la branche, et en général cmov fonctionne mieux quand la branche est très difficile à prédire. Si cmov donne un facteur 6, je suppose que les entrées de test sont des chaînes aléatoires presque entièrement composées de s et de p. Ce n’est pas faux, mais l’article me paraît un peu trompeur, car il spécialise le benchmark en exploitant des propriétés non mentionnées des données

    • Le code de test est ici : https://github.com/414owen/blog-code/blob/master/02-the-same...
      Il choisit aléatoirement 's' ou 'p', et aucun autre caractère que 's', 'p' ou le nul terminal ne peut apparaître. Si l’on connaît cette propriété des entrées, on peut même faire une optimisation excessivement maligne comme result += (1 | *s++) - 'r';. C’est un code trop astucieux, mais il illustre parfaitement l’idée d’exploiter les propriétés des données
    • Dans la chaîne, '\0' ne peut être rencontré qu’au plus une fois, puisque la fonction retourne à ce moment-là, alors que les autres caractères peuvent apparaître plusieurs fois. Cela semble être une information à laquelle le compilateur pourrait avoir accès même sans PGO
      Bien sûr, la PGO aide, et sur ma machine j’obtiens 2,80 s, ce qui est meilleur que le code de la fin de la section Rearranging blocks. L’entrée est décrite dans Benchmarking setup et se trouve aussi dans le dépôt : https://github.com/414owen/blog-code/blob/master/01-six-time...
      Dans la deuxième partie liée en bas de l’article, ils rendent le code C aussi rapide que possible et battent ainsi tout l’assembleur de cet article. Je n’ai jamais dit qu’écrire en assembleur était forcément une bonne idée ; je pense simplement que l’optimisation et l’analyse du code généré par le compilateur constituent un défi intéressant et une bonne occasion d’apprentissage

  • Je pense avoir fait plus rapide que l’article et son billet de suivi. Il y a toutefois un prix à payer : c’est spécialisé pour les cas où la chaîne ne contient que 's' et 'p'
    Le benchmark ne teste lui aussi que des chaînes composées de 's' et 'p', donc cela me paraît équitable. L’idée est la suivante : on veut incrémenter res de 1 quand le caractère suivant est s, mais res += c - 'r' vaut bien 1 pour s, alors que pour p cela donne -2, donc ça échoue. En revanche, si on interprète 'p' - 'r' comme un entier non signé, cela provoque un underflow qui positionne le carry flag, et adc sur x64 additionne ensemble deux registres et le carry flag. On peut donc remplacer deux cmp, cmov par un seul sub, adc. Cette version était 1,08 fois plus rapide que la version C du billet de suivi, et 1,66 fois plus rapide que l’ancienne x64-7. Bien sûr, on peut encore améliorer avec SWAR/SIMD

    • Approche intéressante. J’aurais probablement dû préciser que l’assembleur assez simple de 02-the-same-speed-as-c/loop-5.x64.s était simplement la version la plus rapide que j’avais alors
      Sur ma machine, loop-5.x64.s prend 0,244 s, alors que l’implémentation ci-dessus prend 0,422 s. Je ne sais pas exactement d’où vient cet écart ; à première vue, l’implémentation ci-dessus semble plus rapide. C’est pour cela qu’il faut toujours benchmarker sur le matériel réel d’exécution
    • Plus simplement, on peut additionner tous les éléments du tableau, puis soustraire à la fin 'p' * len, et diviser par ('s' - 'p') pour obtenir le nombre de s. Le nombre de p vaut alors len - s_count
      La somme initiale se vectorise aussi facilement. Sauf erreur, cela devrait fonctionner, et le seul vrai problème est le risque de débordement de la somme cumulée. Je n’ai pas la motivation de le benchmarker moi-même. Correction : j’avais oublié la partie qui décrémente quand on voit un s, donc le résultat final est p_count - s_count

  • strlen() est probablement implémenté de manière assez rapide, et si la taille du buffer est connue, le compilateur peut vectoriser automatiquement la boucle interne
    En pratique, un code qui fait len = strlen(buf) puis additionne (buf[i] == 's') - (buf[i] == 'p') dans une boucle for est automatiquement vectorisé : https://gcc.godbolt.org/z/qYfadPYoq

  • J’ai déjà écrit un décodeur UTF-8 en Common Lisp pour SBCL. Il y avait déjà un décodeur intégré, donc c’était surtout pour m’exercer
    En dehors des optimisations évidentes et faciles, presque tous les gains de performance venaient du fait de structurer le code pour que le compilateur génère des instructions cmov* au lieu de branches

    • Je serais curieux de voir un exemple des modifications apportées au code. Et aussi de savoir si tu as désassemblé la fonction en boucle pour vérifier l’usage des bonnes instructions, ou si tu as confirmé l’amélioration réelle par benchmark
    • Si le branchement est correctement prédit, il peut très bien être plus rapide qu’un déplacement conditionnel, car le branchement n’allonge pas la longueur du chemin critique
      Un décodeur UTF-8 s’exécute souvent sur des entrées entièrement ASCII. Je serais curieux de savoir avec quelles entrées le benchmark a été fait