Multiplier par 4 les performances du code avec un `if` inutile

 (purplesyringa.moe)
1 points par GN⁺ 3 시간 전 | 1 commentaires | Partager sur WhatsApp
  • En ajoutant une seule condition dans une boucle qui parcourt le chemin d’encodage optimal d’un compresseur spécialisé pour un domaine, le temps d’exécution d’un benchmark synthétique passe de 320 µs à 80 µs
  • Comme, à chaque itération, l’adresse mémoire dépend du j de l’itération précédente, même une unique instruction mov reste contrainte par la latence d’accès mémoire, sans pouvoir exploiter le parallélisme au niveau des instructions
  • En intégrant à la prédiction de branchement le fait que next_j[i][j] est le plus souvent égal au j existant, le CPU peut contourner la dépendance entre itérations et exécuter spéculativement plusieurs itérations
  • Un cast volatile est utilisé pour empêcher le compilateur de supprimer le if, pourtant inutile sémantiquement. Avec LLVM, [[unlikely]] ou __builtin_expect(..., 0) fonctionnent aussi, mais volatile produit un meilleur code et est également pris en charge par GCC
  • Dans une expérience réaliste, un gain d’environ 2× a été obtenu, peut-être dû à une génération de code non optimale par LLVM ; si j est difficile à prédire, pshufb, dont la latence est de 1 cycle, peut être utilisé comme alternative

Parcours du chemin optimal du compresseur

  • Il faut découper la chaîne d’entrée en plusieurs chunks et choisir le plus petit encodage pour chacun
    • Chaque encodage compresse bien des caractères différents, ce qui rend difficile de déterminer directement les frontières des chunks
    • L’algorithme d’un article précédent transforme ce problème en recherche du plus court chemin sur une grille
  • Chaque cellule enregistre la cellule optimale vers laquelle se déplacer ensuite
    • En suivant les références de la première cellule à la dernière, on obtient l’ordre d’encodage optimal
  • La première boucle, qui remplit next_j, est déjà optimisée avec SIMD
    • Le véritable goulet d’étranglement est la simple boucle de parcours de chemin suivante
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • L’opération centrale, hors écritures, j = next_j[i][j], est compilée en une seule instruction mov

Une seule instruction peut aussi être ralentie par les dépendances

  • Les CPU modernes utilisent le parallélisme au niveau des instructions pour exécuter simultanément plusieurs instructions et le travail de différentes itérations
    • C’est la raison pour laquelle, dans une boucle ordinaire, le coût de la vérification i < n_symbols et de i++ ne bloque pas les autres opérations
  • Mais des instructions dépendantes les unes des autres ne peuvent pas s’exécuter simultanément
    • Pour calculer l’adresse mémoire next_j[i][j] de l’itération courante, il faut le j obtenu à l’itération précédente
    • L’itération suivante ne peut pas commencer tant que le résultat de la précédente n’est pas disponible, et subit donc la latence d’accès mémoire même si les données sont en cache

Utiliser la prédiction de branchement comme spéculation de valeur

  • Ce compresseur étant censé ne pas produire beaucoup de chunks, next_j[i][j] est le plus souvent égal au j existant
  • On ne peut pas demander directement au CPU de prédire l’adresse en supposant que j restera inchangé, mais on peut obtenir le même effet avec la prédiction de branchement
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • Si le CPU prédit que le corps du if ne sera pas exécuté, il considère qu’il n’existe pas de dépendance entre itérations pour la mise à jour de j, et exécute spéculativement plusieurs itérations
  • Si la condition est en réalité vraie, une récupération après mauvaise prédiction de branchement se produit
    • Les écritures effectuées sur la base d’une mauvaise spéculation sont annulées
    • L’exécution reprend avec le bon j
  • Tant que j change rarement, le goulet d’étranglement de la boucle passe de la latence au débit

Empêcher le compilateur de supprimer le if

  • Du point de vue du compilateur, le code avec la condition ajoutée a la même sémantique que le code original
    • Si j était en mémoire, on pourrait éviter une écriture inutile ou une écriture vers de la mémoire en lecture seule, mais ici il s’agit d’une valeur en registre
    • Des optimisations comme l’élimination des sous-expressions communes (CSE) peuvent supprimer la condition et l’accès redondant
  • Les hints habituels du compilateur servent à éliminer les branchements, mais ici il faut au contraire conserver sous forme de code avec branchement un code sans branchement
  • On applique un cast volatile du côté de l’affectation pour faire croire que l’accès mémoire du test de condition et celui de l’affectation sont indépendants
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • Lors d’une vérification supplémentaire le 13 juillet, comme dans la méthode trouvée par ibookstein, l’utilisation de [[unlikely]] ou de __builtin_expect(..., 0) permet aussi d’obtenir le même effet avec LLVM
  • L’approche volatile génère un meilleur code et fonctionne aussi avec GCC

Évolution des performances observée dans les benchmarks

  • Dans le benchmark synthétique, le temps d’exécution de la boucle est passé de 320 µs à 80 µs, soit une accélération par 4
    • La différence sur une seule exécution est faible, mais comme la boucle s’exécute plusieurs fois pendant la compression, elle s’accumule dans le coût total
  • Dans une expérience plus réaliste, un gain de performances d’environ 2× a été mesuré
    • C’est peut-être dû à une génération de code non optimale par LLVM, mais le résultat restait suffisamment intéressant pour être appliqué

Une alternative : une représentation fondée sur un bitmask

  • Dans cet algorithme, next_j[i][j] ne peut prendre que deux valeurs
    • Dans la plupart des cas, c’est le j courant
    • Sinon, c’est une valeur indépendante de j et dépendant uniquement de i
  • Le tableau à 8 éléments next_j[i] peut être remplacé par une paire composée d’une valeur de remplacement et d’un bitmask
    • Dans cette représentation, le if est sémantiquement nécessaire, il n’est donc pas nécessaire de contourner le problème avec volatile
    • Toutefois, sur x86, les opérations qui testent un bit à une position variable peuvent être plus lentes qu’une comparaison, ce qui peut au contraire réduire les performances globales

Quand j est impossible à prédire

  • Un article sur l’accélération du parcours de listes chaînées par spéculation de valeur décrit aussi une méthode similaire pour améliorer les performances
  • Si j est difficile à prédire, on peut utiliser pshufb, une opération d’indexation vectorielle
    • La latence de pshufb est de 1 cycle, il est donc difficile de faire mieux sans exécution spéculative
    • Les opérations vectorielles permettent de calculer en parallèle le chemin pour chaque j de départ possible
    • Il est également possible de répartir le travail entre plusieurs threads puis de fusionner les résultats

À lire aussi

1 commentaires

 
GN⁺ 3 시간 전
Avis sur Lobste.rs

  • Il semble que l’attribut [[unlikely]] de C++20 appliqué à une instruction if suffise à empêcher clang d’éliminer ce code : https://clang.godbolt.org/z/r4xYWfPfe
    Je n’ai pas pu vérifier avec d’autres compilateurs

    • Après revérification, cela fonctionnait bien avec LLVM ; j’avais sans doute d’abord testé par erreur avec GCC, où cela n’avait pas d’effet
      Cela dit, [[unlikely]] déplace le code hors du chemin rapide, donc LLVM génère un code un peu inefficace comme ci-dessous 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      La forme suivante semble plus raisonnable 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      Il ajoute aussi une instruction dans la boucle chaude tout en optimisant pour éviter de relire plusieurs fois la valeur depuis la mémoire. Donc la technique utilisant volatile reste utile, mais il est rassurant de voir que le code d’origine peut aussi fonctionner tel quel

  • Cette technique est appelée ailleurs value speculation : https://mazzo.li/posts/value-speculation.html

    • Après avoir réinventé cette méthode, j’ai d’abord pensé qu’elle pourrait aussi s’appliquer aux listes chaînées stockées dans une arène, et l’article lié traite justement exactement de ce sujet, donc j’ai aussi ajouté le lien à mon billet

  • D’ici 2 ou 3 ans, les développeurs deviendront probablement de plus en plus indifférents aux sorties des LLM ; je me demande s’ils s’intéresseront encore à ce genre de billet de blog

    • Même aujourd’hui, très peu de gens s’y intéressent ; à l’échelle de toute la programmation, c’est une connaissance de niche
      Cela reste néanmoins un excellent billet, très utile pour ceux que le sujet intéresse
    • Godbolt est très populaire. Quand on critique l’habitude de ne pas lire le code, les développeurs grisés par les LLM répondent parfois « tu vas jusqu’à regarder l’assembleur ? » comme si c’était une objection décisive, mais en réalité certains vérifient bien l’assembleur et continueront de le faire
      Un développeur qui pense que les détails n’ont pas d’importance aura du mal à devenir un bon développeur. De la même façon qu’un excellent ingénieur civil se soucie jusqu’aux boulons et aux écrous d’un grand projet, un excellent développeur doit creuser les moindres détails. Le tout est fait de détails, donc si l’on attache de l’importance à ce que l’on produit, on ne peut pas l’éviter
    • Je ne pense pas que ce soit fondamentalement différent d’aujourd’hui. Déjà maintenant, la plupart des gens ne s’intéressent pas à la sortie du compilateur pour du code écrit par des humains
      Il y aura peut-être encore moins de personnes pour examiner la sortie du compilateur d’un code écrit par une IA, mais la configuration de base ne changera sans doute pas
    • Le changement relèvera moins de l’existence ou non d’un intérêt que d’une recomposition des priorités d’optimisation
      Il y a dix ans, si un script Bash était un peu lent, on n’aurait pas commencé par se préoccuper du parallélisme au niveau des instructions ou de la prédiction de branchement du CPU. Il peut y avoir une partie critique pour les performances écrite dans un langage compilé et optimisable, puis à l’intérieur un chemin chaud à examiner en détail, puis encore à l’intérieur une ou deux boucles chaudes où il vaut la peine de vérifier la vectorisation ou les différences de comportement des CPU modernes
      Même avec des LLM, les points les plus chauds en performance peuvent exceptionnellement mériter un examen manuel. On peut accepter consciemment la moindre qualité du résultat, ou partir d’un 70 % produit par un LLM puis corriger à la main les 30 % restants, et peut-être améliorer cela jusqu’à 85:15, mais ce billet traite malgré tout d’un domaine de détail relevant du top 1 %
    • Je n’écris pas de C++, donc en ce sens ce n’est déjà pas aujourd’hui un sujet d’intérêt direct pour moi, mais j’ai quand même trouvé la lecture intéressante, et je pense que dans 2 ou 3 ans aussi ce type de contenu restera intéressant