Ne vous moquez pas d’un prédicteur de branchement heureux et amusant (2023)

Ne vous moquez pas d’un prédicteur de branchement heureux

• J’écris beaucoup d’assembleur AArch64 ces derniers temps
• Une idée « intelligente » pour supprimer un saut dans une boucle a dégradé les performances
• J’explique cette erreur pour éviter que d’autres ne la reproduisent

Exemple de code

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

Traduction en assembleur AArch64

// x0: const float* data
// x1: size_t n
// s0: 반환할 float
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // s1에서 읽고 s0에 누적
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

Tentative d’optimisation

• Tentative d’amélioration des performances en réduisant les instructions bl
• Mais les performances se sont au contraire dégradées

Comparaison des performances

• Code d’origine : 969 ns
• Code optimisé : 3.85 µs

Analyse de la cause

• Le prédicteur de branchement est perturbé parce que les paires bl et ret ne correspondent plus
• Selon la documentation ARM, l’instruction ret aide à prédire les retours de fonction

Solution

• Utiliser br x30 à la place de ret
• Performances rétablies : 913 ns

Optimisations supplémentaires

• Inliner foo pour améliorer les performances
• Déroulage de boucle et utilisation d’instructions SIMD

Performances finales

• SIMD + déroulage manuel de boucle : 94 ns

Conclusion

• Ne perturbez pas le prédicteur de branchement
• Le code SIMD est plus rapide, mais comme l’addition en virgule flottante ne suit pas la loi d’associativité, le résultat peut être différent

L’avis de GN⁺

• Cet article montre bien l’importance de l’optimisation en assembleur AArch64
• Comprendre le fonctionnement du prédicteur de branchement est essentiel pour l’optimisation des performances
• L’optimisation à l’aide d’instructions SIMD est très efficace, mais il faut tenir compte des questions de précision
• Avec un langage de haut niveau comme Rust, on peut plus facilement améliorer les performances grâce aux optimisations du compilateur
• Un projet similaire est le guide d’optimisation en assembleur d’Agner Fog

[GN⁺]

Avis Hacker News

• Résumé de l’article avec des amis de l’époque de l’Apple II

  • Un code optimisé met 94 nanosecondes à additionner 1024 nombres à virgule flottante de 32 bits
  • Un 6502 à 1 MHz passerait ces 94 nanosecondes à essayer de récupérer en mémoire le premier octet de la première instruction
  • Ce code n’atteint ses performances optimales que lorsqu’il s’exécute depuis le cache. La DRAM est lente

• Raymond Chen a traité le même sujet il y a presque 20 ans

  • Après avoir vérifié la fin de la boucle, l’exécution passe à la fonction foo sans branchement
  • Cela enfreint les heuristiques de prédiction de base
  • Le fait que le prédicteur de branchement maintienne une pile fantôme des adresses de retour existe depuis des décennies

• Le code SIMD peut effectuer la somme dans un ordre différent, car l’addition en virgule flottante ne suit pas la propriété d’associativité

  • C’est peut-être pour cela que le compilateur ne génère pas d’instructions SIMD
  • Une somme en virgule flottante comporte par nature une marge d’erreur, et toute réponse dans cette plage est valide
  • En présence d’entrées spéciales en virgule flottante, le langage doit fournir un moyen de les encoder explicitement

• Depuis Rust 1.78, le compilateur utilise un déroulage de boucle plus agressif et un peu de SIMD

  • Le déroulage de boucle a commencé avec Rust 1.59
  • Le code sur Github utilisait la version Rust 1.67.0-nightly

• Il y avait de la confusion sur la façon dont x0 est incrémenté en assembleur ARM/ARM64

  • L’instruction ldr s1, [x0], #4 charge tout en incrémentant x0 de 4
  • En x86_64, il n’existe pas d’instruction unique qui charge et incrémente en une seule fois

• Il est surprenant que des méthodes moins complexes n’aient pas été essayées pour optimiser le code assembleur

  • Il est possible de réécrire le code assembleur pour qu’un seul branchement soit nécessaire en bas de la boucle
  • On peut intégrer foo inline et omettre l’instruction RET

• Certains auraient préféré que l’auteur ne change pas constamment d’unité