Ne vous moquez pas du prédicteur de branchement Happy Fun (2023)

 (mattkeeter.com)
1 points par GN⁺ 2024-07-05 | 1 commentaires | Partager sur WhatsApp
  • Une optimisation en assembleur AArch64 qui visait à supprimer un branchement dans une boucle a au contraire rendu le code 4 fois plus lent ; la cause était un usage asymétrique du couple appel-retour bl/ret, qui a perturbé le prédicteur de branchement
  • Le code d’origine effectue deux branchements par itération, bl foo et b loop, mais la version modifiée tente de réduire le nombre de branchements avec un unique bl loop pour fixer x30, puis plusieurs ret revenant tous à la même adresse
  • Sur un M1 Max, la somme d’un tableau de 1024 float prenait 969 ns avec un code bl/ret normal, mais la structure un seul bl et plusieurs ret ralentissait à 3,85 µs ; en remplaçant ret par br x30, on revenait à 913 ns
  • Les compteurs de performance d’Instruments ont montré que, lors de la somme d’un milliard d’éléments, les échecs de prédiction des branches de retour dans la structure asymétrique bl/ret atteignaient environ 93 % ; FETCH_RESTART, MAP_DISPATCH_BUBBLE et MAP_REWIND augmentaient aussi fortement
  • Des implémentations plus rapides passent ensuite par l’inlining de foo, Rust avec iter().sum(), puis le SIMD NEON et le déroulage manuel de boucle ; la version SIMD finale descend à 94 ns, mais l’ordre des additions en virgule flottante change, donc le résultat peut différer

Effet contre-productif dans une boucle AArch64

  • La fonction d’exemple parcourt un tableau de float, transmet chaque valeur à foo, et foo met à jour l’accumulateur g
  • Une traduction AArch64 simple suit le flux suivant
    • Vérification en début de boucle de n == 0
    • Lecture d’une valeur avec ldr s1, [x0], #4
    • Appel de la sous-routine avec bl foo
    • Le ret de foo revient à l’instruction qui suit bl
    • Retour au début de boucle avec b loop
  • foo a une forme proche d’une naked function, utilisant la même pile et les mêmes registres que la fonction parente ; elle lit s1 et accumule dans s0

Rôle de bl et ret

  • bl est l’instruction branch and link : elle saute vers un label donné tout en stockant l’adresse de l’instruction suivante dans le registre de lien lr, ou x30
  • ret saute vers l’adresse contenue dans le registre de lien
  • Dans la structure d’origine, bl foo et ret sont appariés, et ret revient toujours à l’instruction qui suit ce bl

L’optimisation ratée pour « supprimer un branchement »

  • La structure modifiée cherche à enlever un branchement dans la boucle sans modifier foo
    • Au début de la fonction, bl loop place l’adresse de début de loop dans x30
    • Après vérification de la condition de fin de boucle, l’exécution tombe dans le code de foo sans branchement séparé
    • Le ret de foo revient à loop, contenu dans x30
  • Dans cette structure, x30 ne change pas dans le corps de boucle ; les ret successifs reviennent donc toujours à la même adresse
  • Le foo simple ressemble à ceci, avec une seule addition de float
foo:
    fadd s0, s0, s1
    ret
  • Dans ce cas, la fonction complète calcule la somme du tableau de float en entrée

Résultats du benchmark et problème de prédiction de branchement

  • Un benchmark avec criterion a été exécuté sur un CPU M1 Max avec un tableau de 1024 éléments
    • bl/ret normal : 969 ns
    • un seul bl, plusieurs ret : 3,85 µs
  • Le code qui supprime un branchement est environ 4 fois plus lent que le code d’origine qui en utilise deux
  • Cliff et Dan ont estimé que le prédicteur de branchement était perturbé parce que les paires bl/ret ne correspondaient plus
  • Selon la documentation ARM, RET permet au processeur de reconnaître un retour de fonction, ce qui améliore la précision de la prédiction de branchement
    • BR LR peut faire fonctionnellement la même chose
    • Mais RET reste une instruction distincte que le processeur peut identifier comme un retour de fonction
    • Si la prédiction est correcte, les bonnes instructions sont injectées dans le pipeline et on évite d’attendre leur chargement depuis la mémoire

Pile d’adresses de retour et expérience avec br x30

  • Le prédicteur de branchement maintient probablement en interne une pile d’adresses de retour de fonctions
    • À l’exécution de bl, l’adresse de retour est empilée
    • En voyant ret, il suppose un retour vers l’adresse du bl le plus récent
    • Il lance alors le préfetch et l’exécution spéculative à partir de cette adresse, puis dépile l’entrée
  • Ce mécanisme fonctionne bien quand les paires bl/ret sont correctement appariées
  • Si plusieurs ret utilisent en boucle la même adresse, la prédiction échoue et peut provoquer préfetch inutile, mauvaise exécution spéculative, blocage ou vidage du pipeline
  • Comme l’a proposé Dan, remplacer ret par br x30 fait disparaître la dégradation des performances
    • bl/ret normal : 969 ns
    • un seul bl, plusieurs ret : 3,85 µs
    • un seul bl, plusieurs br x30 : 913 ns
  • La version br x30 n’effectue qu’un seul branchement par itération, ce qui la rend légèrement plus rapide que le code d’origine

Compteurs de performance Instruments

  • Les compteurs de performance des deux premiers programmes ont été examinés avec Instruments
  • La mesure a été réalisée pendant la somme d’un tableau d’un milliard d’éléments
  • Dans le cas du bl/ret asymétrique, les échecs de prédiction des branches de retour atteignaient environ 93 %
Compteur bl/ret normal un seul bl, plusieurs ret
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928,644,975
FETCH_RESTART 61,121 987,765,276
MAP_DISPATCH_BUBBLE 1,155,632 7,350,085,139
MAP_REWIND 6,412,734 2,789,499,545
  • Apple ne documente pas complètement ces compteurs
  • Les autres compteurs sont supposés refléter les effets en aval d’une mauvaise prédiction de branchement
    • FETCH_RESTART : probablement lié à un mauvais préfetch
    • MAP_DISPATCH_BUBBLE : probablement lié à un pipeline stall
    • MAP_REWIND : probablement lié à une exécution spéculative erronée qu’il faut rembobiner

Comment aller plus vite

  • L’exemple est un code pédagogique, et si foo est une sous-routine, c’est davantage pour l’explication que pour obtenir « le code le plus rapide possible »
  • Si le contenu de foo est connu à la compilation et reste dans la portée maximale de saut, on peut supprimer totalement bl et ret par inlining
    • On passe de 969 ns à 911 ns, soit environ 6 % de gain
  • En Rust, un simple f.iter().sum() descend à 833 ns
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD et déroulage manuel de boucle

  • L’implémentation SIMD manuelle en AArch64 se compose de trois boucles
    • loop : ajoute individuellement les valeurs dans s0 jusqu’à ce que le nombre restant soit un multiple de 4
    • simd : ajoute 4 valeurs à la fois dans le registre vectoriel v1, jusqu’à ce que le nombre restant soit un multiple de 8
    • simd2 : déroule simd par 2 pour traiter 8 valeurs par itération et accumuler dans v1 et v2
  • À la fin de la fonction, les valeurs de v1 et v2 sont accumulées dans s0 puis renvoyées
  • Le type punning consiste à traiter x0, de type float*, comme un double*, afin de lire 128 bits, soit 4 float, dans d3 et d4
    • mov v3.d[1], v4.d[0] déplace les 64 bits de d4 dans la moitié haute de v3
    • Dans fadd v1.4s, v1.4s, v3.4s, le suffixe .4s permet de les traiter comme quatre float
  • Cette implémentation SIMD s’exécute en 94 ns, soit environ 8,8 fois plus vite que la meilleure version précédente en Rust à 833 ns

Résumé global des performances et point d’attention

Implémentation Temps
bl/ret normal 969 ns
un seul bl, plusieurs ret 3,85 µs
un seul bl, plusieurs br x30 913 ns
boucle classique avec b 911 ns
réécriture en Rust 833 ns
SIMD + déroulage manuel de boucle 94 ns
  • Le code SIMD modifie l’ordre des additions en virgule flottante
  • Comme l’addition en virgule flottante n’est pas associative, la version SIMD peut ne pas produire exactement le même résultat que le code linéaire
  • C’est peut-être aussi pour cette raison que le compilateur n’a pas généré d’instructions SIMD pour cette somme
  • Tout le code est disponible sur GitHub
  • Il suffit d’exécuter cargo bench sur une machine ARM64 pour reproduire le benchmark

À lire aussi

1 commentaires

 
GN⁺ 2024-07-05
Commentaires Hacker News

  • Le dernier code optimisé termine la somme d’un tableau de 1 024 nombres flottants 32 bits en 94 ns.
    Pendant ces 94 ns, notre vieil ami le 6502 à 1 MHz en serait à peine au stade où il commence à se demander s’il doit signaler à la puce mémoire de récupérer le premier octet de la première instruction du programme.
    Cela dit, ce code repose entièrement sur l’hypothèse qu’il s’exécute dans le cache. Sinon, même le puissant M1 Max cité dans l’article serait resté bloqué à attendre le premier accès mémoire. La DRAM est lente.

    • Heureusement, la taille totale du cache L1 est désormais aussi grande que toute la mémoire que le 6502 pouvait adresser. Nous vivons vraiment une époque étonnante.

  • Raymond Chen a traité du même sujet il y a près de 20 ans : https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • En tant que personne qui possède la version papier du manuel de référence des instructions de l’architecture x86/64 d’Intel, les fameux gros livres bleus, et qui lit attentivement les datasheets et la documentation, je me méfie toujours quand j’entends « intuitivement, on s’attendrait à X, mais c’est Y qui se produit ».
      À part une compréhension de base des propriétés semi-conductrices du silicium et du dopage, il n’y a presque rien d’intuitif là-dedans. Si vous n’avez pas vu le schéma du die, le câblage et les chemins, il y a très peu de raisons de s’attendre à ce que A soit plus rapide que B, sauf si les ingénieurs et les datasheets le disent explicitement. C’est encore plus vrai, à mon avis, avec ARM.
    • L’article de Raymond Chen est excellent et fournit un bon contexte pour interpréter celui-ci.
      Ce que le présent article ajoute, c’est une simple correction consistant à remplacer ret par une autre instruction br. Ainsi, la paire redevient « symétrique », et l’on peut obtenir un code un peu plus rapide sans perturber le prédicteur de branchement.
    • Raymond Chen est vraiment un trésor. Je suis reconnaissant à Microsoft de lui laisser la latitude de continuer à tenir son blog ; j’y ai énormément appris.
    • Sur les processeurs x86 récents, cela ne semble plus être vrai : https://news.ycombinator.com/item?id=40767676

  • Bien sûr, tout est possible, et une boucle ordinaire qui additionne un tableau demande effectivement à l’ordinateur d’accumuler les éléments un par un.
    Mais, par exemple, il est difficile de dire que créer quatre accumulateurs en parallèle avec SIMD, puis les additionner à la fin, est plus incorrect que d’additionner les éléments un par un.
    Il faut considérer que les additions en virgule flottante ont, par nature, une marge d’erreur, et qu’une réponse située dans cette marge doit être valide. Si l’on sait quelque chose de particulier sur les nombres flottants en entrée, le langage devrait fournir un moyen d’exprimer explicitement cette intention. Comme la boucle la plus simple est le comportement par défaut, il me semble normal que, par défaut, elle offre les meilleures performances.

    • Même pour une tâche aussi simple que l’addition d’une liste de nombres, il existe étonnamment plusieurs algorithmes de sommation.
      La méthode naïve consistant à les ajouter un par un dans une boucle est évidente, mais il existe des méthodes plus sophistiquées qui offrent de meilleures bornes sur l’erreur cumulée totale, et la sommation de Kahan en est un exemple bien connu : https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      Avec des données en streaming, on n’a parfois pas d’autre choix que d’ajouter les valeurs une par une ; mais si l’on peut utiliser N tampons de taille fixe, des questions apparaissent : quel sous-ensemble transformer en somme partielle lorsqu’un nouveau nombre arrive, comment l’ajouter à la somme cumulée, et ce choix apporte-t-il une amélioration démontrable de l’erreur ?
    • Lorsque l’écart de magnitude entre les valeurs en virgule flottante est important, cela devient un vrai problème.
      Par exemple, calculer [1e50, -1e50, 1e3, 1e3] sous la forme (((1e50 + -1e50) + 1e3) + 1e3) donne 2e3, tandis que le calculer sous la forme ((1e50 + 1e3) + (-1e50 + 1e3)) donne 0.
      C’est similaire lorsqu’on ajoute beaucoup de petites valeurs à une seule grande valeur : (((1e3 + 1e3) + 1e3) ... + 1e50) et (((1e50 + 1e3) + 1e3) ... + 1e3) sont assez différents.
    • Il y a beaucoup de « il faudrait », mais en pratique cela se passe rarement ainsi. La seule information fournie par l’expression d’origine est l’ordre des opérations arithmétiques.
      Si les résultats arithmétiques ne sont pas stables d’un build à l’autre, cela devient un cauchemar absolu. On ne devrait pas obtenir un résultat différent en recompilant puis en exécutant le logiciel avec les mêmes entrées.
      J’ai aussi connu, il y a longtemps, un cas spécifique à Intel : le FPU utilisait en interne des registres 80 bits, mais stockait 64 bits en mémoire ; donc si le moment où les registres étaient remplis ou vidés changeait, le moment de l’arrondi changeait aussi, et le résultat avec lui. On pouvait définir un drapeau FPU global au démarrage du programme pour forcer l’arrondi à chaque opération.
    • Trier les valeurs en virgule flottante réduit l’erreur. Je pense donc que l’utilisation de plusieurs accumulateurs peut diminuer la précision. Des données déjà triées ne sont pas rares non plus.
      Il existe toujours une bonne réponse, et je pense que le compilateur ne devrait pas effectuer, du moins par défaut, une transformation incorrecte. Cela dit, tout moyen permettant au programmeur d’exprimer plus clairement son intention est toujours bienvenu.
    • Beaucoup de code dépend du fait que les opérations en virgule flottante soient déterministes au sein d’une architecture de jeu d’instructions donnée.
      Appliquer SIMD aux boucles en virgule flottante aurait pu devenir le comportement par défaut, mais cela casserait beaucoup de code existant et modifierait souvent les sorties de façon non déterministe ; c’est donc devenu une fonctionnalité que le programmeur doit choisir explicitement.
      De plus, beaucoup de programmeurs peuvent ignorer ce fait, si bien que si float Sum(float[] values) commence à renvoyer une valeur différente, ils n’auront peut-être aucun moyen de savoir que la vectorisation en est la cause. C’est pourquoi, par exemple, la bibliothèque standard .NET utilise SIMD pour integers.Sum(), mais pas pour floats.Sum().

  • Rien qu’en lisant la ligne « après avoir vérifié la fin de la boucle, on tombe directement dans la fonction foo sans branchement », je me suis dit : « ah, voilà le problème ».
    Je pensais que ce serait une discussion approfondie sur des heuristiques sophistiquées de prédiction de branchement, mais au final c’était une violation d’une heuristique de base.
    Il ne faut pas croire qu’on peut obtenir un énorme gain de performance en utilisant des instructions call/ret qui ne correspondent pas. Le fait que le prédicteur de branchement maintienne une pile fantôme des adresses de retour existe depuis des décennies.

    • C’est bien de connaître en détail le fonctionnement des prédicteurs de branchement, mais beaucoup de gens ne le connaissent pas, et pour eux cela peut être une information nouvelle, voire utile. Cet article n’était simplement pas écrit pour vous, et ce n’est pas grave.
    • Sur les systèmes disposant d’une pile d’appels fantôme au niveau architectural comme fonctionnalité de sécurité, cela peut casser l’exécution du programme de manière plus fondamentale, c’est-à-dire provoquer un crash.
    • D’un côté, l’objectif de conception du RISC est d’améliorer les performances du code compilé au détriment de la plupart des autres aspects.
      Ce genre de risque doit donc être documenté, mais les concepteurs devraient pouvoir partir du principe que les personnes qui écrivent directement de l’assembleur ont lu la documentation.
      D’un autre côté, Sophie Wilson a écrit l’implémentation originale de BBC BASIC pour ARM, mais à l’époque il n’y avait pas de prédicteur de branchement. Même si les règles diffèrent parce que c’était du 32 bits, je me demande comment AArch64 ralentit le code lorsque les hypothèses architecturales changent.
    • Cela reste toutefois un article instructif, puisqu’il montre aussi comment ces optimisations et d’autres ont effectivement été obtenues.

  • C’est une référence à un classique de SNL, « Do not taunt happy fun ball » : https://www.youtube.com/watch?v=GmqeZl8OI2M

    • Si de la fumée commence à sortir du happy fun prédicteur de branchement, il faut évacuer immédiatement.
    • La phrase « Happy Fun Ball a été expédiée à nos soldats en Arabie saoudite, et est aussi larguée depuis des avions de combat au-dessus de l’Irak » donne vraiment l’impression de se demander : « mais on est en quelle année, là !? »
    • C’est encore légal dans 16 États : https://www.youtube.com/watch?v=2AzAFqrxfeY

  • Il ne faut pas oublier que l’article date de 2023. Il est déjà un peu dépassé aujourd’hui, et depuis Rust 1.78, le compilateur utilise un déroulage de boucle plus agressif et un peu de SIMD : https://godbolt.org/z/zhbobW7rr
    L’article original disait « en regardant l’assembleur, on voit qu’il déroule la boucle » et renvoyait vers https://godbolt.org/z/Kv77abW6c, mais il utilisait le « Rust Nightly », qui évolue en permanence. Aujourd’hui, le déroulage de boucle est plus important.
    Le déroulage de boucle a commencé avec Rust 1.59 : https://godbolt.org/z/5PTnWrWf7
    D’après le code GitHub, il utilisait Rust 1.67.0-nightly, version du 27/11/2022.

    • Le lien a été mis à jour pour sélectionner explicitement Rust 1.67.
    • Rust 1.67.0, qui semble être ce que l’auteur original a vu, produit ce résultat : https://godbolt.org/z/4Y61d9seh
      J’ai relancé le benchmark moi-même sur le même matériel avec le déroulage de boucle agressif du dernier nightly, Rust 1.81, mais il n’y avait pas de différence : la vitesse était la même qu’il y a 1,5 an.

  • C’est un article de 2023. Discussion de l’époque : https://news.ycombinator.com/item?id=34520498

    • Pour préciser, il s’agit de la discussion de janvier 2023 sur « Do not taunt happy fun branch predictor », avec 171 commentaires : https://news.ycombinator.com/item?id=34520498
      Qu’un article soit republié environ un an plus tard ne pose pas de problème, et le lien vers l’ancien fil est destiné aux lecteurs qui veulent en savoir plus.

  • N’étant pas très familier avec l’assembleur ARM/ARM64, j’ai été troublé par la façon dont x0 est incrémenté.
    const float f = *data++; devient ldr s1, [x0], #4, et cette instruction semble lire la valeur tout en incrémentant x0 de 4.
    On peut apparemment aussi utiliser une valeur négative, ce qui permettrait de parcourir en sens inverse. C’est plutôt élégant. Sur x86_64, il ne semble pas y avoir d’instruction unique qui fasse à la fois la lecture et l’incrémentation.

    • lods et stos font respectivement une lecture/écriture avec incrémentation sur rsi ou rdi. Il y a aussi movs, qui copie entre deux adresses mémoire tout en incrémentant.
      On l’utilise généralement avec rep, qui répète l’opération rcx fois. Par exemple, un memset de 10 octets peut s’écrire sous la forme mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb.
      Avec les suffixes w, d, q, on avance respectivement de 2, 4 et 8 octets.

  • L’article était bon, mais j’ai regretté qu’il alterne constamment entre les unités µs et ns dans les tableaux, ce qui rend les comparaisons difficiles au survol.

    • Le passage de C à Rust au milieu de l’article m’a aussi un peu pris au dépourvu.

  • Je suis surpris qu’une méthode moins maligne n’ait pas été essayée avant d’optimiser le code.
    En réécrivant l’assembleur, une seule branche est nécessaire en bas de la boucle, et pour X1 aussi, on peut utiliser une seule opération ALU au lieu de faire séparément une soustraction pour la comparaison et un décrément.
    En allant plus loin, on pourrait simplement inliner foo et supprimer aussi l’instruction RET, sans recourir au tour de passe-passe de BL/RET non appariés. Je ne l’ai pas benchmarké moi-même, donc je ne sais pas à quel point ce serait plus rapide en pratique.

    • Il y a une coquille. La ligne qui dit cbnz devrait être cbz. CBZ branche vers l’étiquette si le registre vaut 0, tandis que CBNZ branche s’il ne vaut pas 0.