Optimisation des registres dans RyuJIT à l'aide d'algorithmes génétiques

Optimisation de l'allocation des registres dans RyuJIT à l'aide d'algorithmes génétiques

Les algorithmes génétiques excellent à trouver des solutions contre-intuitives dans des problèmes à espaces de recherche massifs — par exemple, optimiser l'ordre des heuristiques pour l'allocation des registres dans le compilateur RyuJIT. Au lieu d'une séquence rigide pour sélectionner les registres libres et occupés, les chercheurs de l'équipe .NET ont expérimentalement trouvé un ordre plus efficace qui réduit les spills dans les boucles chaudes et améliore PerfScore.

Le problème avec l'ordre fixe des heuristiques

L'algorithme d'allocation de registres par balayage linéaire (LSRA) dans RyuJIT utilise 17 heuristiques pour sélectionner les registres pendant la compilation de la méthode. Les 13 premières s'appliquent aux registres libres, les 4 dernières aux occupés. Par défaut, l'ordre est strictement fixe : ABCDEFGHIJKLMNOPQ. Cette approche peut être sous-optimale : si les registres libres sont épuisés sur des variables hors boucles, à l'intérieur des boucles vous finissez par déverser répétitivement des valeurs des registres occupés, gonflant la taille du code et nuisant aux performances.

Exemple concret : dans un benchmark, toutes les variables à l'intérieur d'une boucle utilisaient le même registre, causant des opérations de spill/reload constantes. Ce n'était pas dû à un manque de registres, mais parce que l'heuristique priorisait toujours les registres libres, même quand ils n'étaient pas le meilleur choix à long terme.

Refonte de LSRA pour un ordre dynamique

Pour tester des séquences alternatives, les développeurs ont apporté ces changements :

• Déplacé chaque heuristique dans sa propre méthode avec l'attribut __forceinline pour éviter les surcoûts.
• Créé une table de hachage associant les symboles (A–Q) à des pointeurs vers les méthodes correspondantes.
• Introduit la variable d'environnement COMPlus_JitLsraOrdering, qui prend une chaîne de 17 symboles uniques définissant l'ordre des heuristiques.

Maintenant vous pouvez exécuter le JIT avec n'importe quelle combinaison, par exemple :

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

Cela permet d'appliquer d'abord les heuristiques pour registres occupés (p. ex., P pour PREV_REG_OPT), puis les libres, potentiellement en réservant les registres libres pour les sections de code critiques.

Mesurer l'efficacité avec PerfScore

PerfScore est utilisé pour évaluer la qualité de l'allocation des registres — c'est un score pondéré du coût d'exécution du code généré, intégrant les latences d'instructions et le débit. Il est particulièrement sensible aux opérations de spill/fill (mov [rsp], reg / mov reg, [rsp]), particulièrement dans les boucles.

L'outil superpmi compare deux versions de clrjit.dll sur ces métriques :

• CodeSize — taille totale du code machine
• InstructionCount — nombre d'instructions
• PerfScore — la métrique cible principale

L'objectif d'optimisation est de minimiser PerfScore. Mais l'espace de recherche est énorme : 17! ≈ 3.56 × 10¹⁴ permutations possibles. Une recherche exhaustive est impossible, même sur un cluster.

Application d'un algorithme génétique

Un algorithme génétique (AG) est parfait pour cela :

• Chromosome : une chaîne de 17 symboles uniques (A–Q) définissant l'ordre des heuristiques.
• Fonction d'adéquation : négative de la moyenne de PerfScore sur un ensemble de builds de test (PerfScore plus bas = fitness plus élevée).
• Opérateur de croisement : croisement basé sur l'ordre (p. ex., PMX) qui préserve l'unicité des symboles.
• Mutation : échange aléatoire de deux positions.

L'algorithme itère comme suit :

• Initialiser une population aléatoire (p. ex., 100 chromosomes).
• Calculer l'adéquation pour chaque individu en utilisant superpmi.
• Sélectionner les meilleurs parents (sélection par tournoi ou roulette).
• Générer la descendance via croisement et mutation.
• Mettre à jour la population ; répéter jusqu'à convergence.

Résultats et limitations

Les expériences ont montré que certaines permutations réduisent le PerfScore global de 0,5–1,2 % par rapport au défaut. Les plus grands gains étaient dans les méthodes avec boucles imbriquées et nombreux temporaires.

Cependant, gardez à l'esprit :

• Les améliorations ne sont pas universelles : un ordre peut aider certaines méthodes et en pénaliser d'autres.
• L'AG lui-même a un surcoût élevé : il nécessite des milliers d'exécutions de superpmi.
• L'ordre optimal dépend de l'architecture (x64 vs Arm64) et du profil de charge.

Enseignements clés

• L'ordre fixe des heuristiques LSRA peut être sous-optimal pour les scénarios réels.
• COMPlus_JitLsraOrdering permet d'ajuster les ordres sans modifier le code source.
• Les algorithmes génétiques excellent dans les espaces de recherche de complexité factorielle.
• PerfScore est une métrique fiable pour la qualité de l'allocation des registres.
• Même des réductions de PerfScore inférieures à 1 % comptent dans les systèmes à haut débit.

— Editorial Team