Registeroptimierung in RyuJIT mit genetischen Algorithmen

## Optimierung der Registerallokation in RyuJIT mit Genetischen Algorithmen

Genetische Algorithmen eignen sich hervorragend dafür, kontraintuitive Lösungen in Problemen mit riesigen Suchräumen zu finden – zum Beispiel die Optimierung der Reihenfolge von Heuristiken für die Registerallokation im RyuJIT-Compiler. Statt einer starren Sequenz zur Auswahl freier und belegter Register haben Forscher aus dem .NET-Team experimentell eine effizientere Reihenfolge gefunden, die Spills in „hot“ Loops reduziert und den PerfScore verbessert.

Das Problem mit fester Heuristik-Reihenfolge

Der Linear-Scan-Registerallokationsalgorithmus (LSRA) in RyuJIT verwendet 17 Heuristiken zur Registerauswahl während der Methodenkompilierung. Die ersten 13 gelten für freie Register, die letzten 4 für belegte. Standardmäßig ist die Reihenfolge streng festgelegt: ABCDEFGHIJKLMNOPQ. Dieser Ansatz kann suboptimal sein: Wenn freie Register für Variablen außerhalb von Schleifen aufgebraucht sind, führt das innerhalb von Schleifen zu wiederholten Spills aus belegten Registern, was den Code vergrößert und die Leistung beeinträchtigt.

Beispiel aus der Praxis: In einem Benchmark nutzten alle Variablen innerhalb einer Schleife dasselbe Register, was zu ständigen Spill-/Reload-Operationen führte. Das lag nicht am Mangel an Registern, sondern daran, dass die Heuristik immer freie Register priorisierte, auch wenn sie langfristig keine gute Wahl waren.

Umstrukturierung von LSRA für dynamische Reihenfolgen

Um alternative Sequenzen zu testen, haben die Entwickler folgende Änderungen vorgenommen:

• Jede Heuristik in eine eigene Methode mit dem Attribut __forceinline ausgelagert, um Overhead zu vermeiden.
• Eine Hashtabelle erstellt, die Symbole (A–Q) auf Zeiger der entsprechenden Methoden abbildet.
• Die Umgebungsvariable COMPlus_JitLsraOrdering eingeführt, die einen String mit 17 eindeutigen Symbolen für die Heuristik-Reihenfolge annimmt.

Nun können Sie den JIT mit beliebigen Kombinationen ausführen, z. B.:

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

Das erlaubt es, zuerst Heuristiken für belegte Register anzuwenden (z. B. P für PREV_REG_OPT) und dann freie, was freie Register für kritische Codeabschnitte spart.

Wirksamkeit mit PerfScore messen

PerfScore dient zur Bewertung der Registerallokationsqualität – es ist eine gewichtete Bewertung der Ausführungskosten des generierten Codes unter Berücksichtigung von Instruktionslatenz und Durchsatz. Es ist besonders empfindlich gegenüber Spill-/Fill-Operationen (mov [rsp], reg / mov reg, [rsp]), insbesondere in Schleifen.

Das superpmi-Tool vergleicht zwei Versionen von clrjit.dll anhand dieser Metriken:

• CodeSize — Gesamtgröße des Maschinencodes
• InstructionCount — Anzahl der Instruktionen
• PerfScore — die primäre Zielmetrik

Das Optimierungs目標 ist die Minimierung des PerfScore. Der Suchraum ist jedoch enorm: 17! ≈ 3.56 × 10¹⁴ mögliche Permutationen. Eine exhaustive Suche ist unmöglich, selbst auf einem Cluster.

Einsatz eines Genetischen Algorithmus

Ein Genetischer Algorithmus (GA) ist hier ideal:

• Chromosom: Ein String mit 17 eindeutigen Symbolen (A–Q) für die Heuristik-Reihenfolge.
• Fitness-Funktion: Negativer Durchschnitts-PerfScore über einen Satz Testbuilds (niedrigerer PerfScore = höhere Fitness).
• Crossover-Operator: Ordnungsbasierter Crossover (z. B. PMX), der die Eindeutigkeit der Symbole erhält.
• Mutation: Zufälliger Tausch zweier Positionen.

Der Algorithmus iteriert wie folgt:

• Initialisiere eine zufällige Population (z. B. 100 Chromosomen).
• Berechne Fitness für jedes Individuum mit superpmi.
• Wähle Top-Eltern aus (Turnier- oder Rouletteselektion).
• Erzeuge Nachkommen durch Crossover und Mutation.
• Aktualisiere Population; wiederhole bis Konvergenz.

Ergebnisse und Einschränkungen

Experimente zeigten, dass einige Permutationen den Gesamt-PerfScore um 0,5–1,2 % im Vergleich zum Standard senken. Die größten Gewinne gab es bei Methoden mit verschachtelten Schleifen und vielen Temporaries.

Beachten Sie jedoch:

• Verbesserungen sind nicht universell: Eine Reihenfolge hilft bei manchen Methoden und schadet bei anderen.
• Der GA selbst hat hohen Overhead: Er erfordert Tausende superpmi-Durchläufe.
• Die optimale Reihenfolge hängt von der Architektur (x64 vs. Arm64) und dem Workload-Profil ab.

Wichtige Erkenntnisse

• Feste LSRA-Heuristik-Reihenfolgen können in realen Szenarien suboptimal sein.
• COMPlus_JitLsraOrdering erlaubt Anpassungen ohne Quellcode-Änderungen.
• Genetische Algorithmen glänzen in Suchräumen mit faktoriellem Komplexitätsgrad.
• PerfScore ist eine zuverlässige Metrik für Registerallokationsqualität.
• Sogar PerfScore-Reduktionen unter 1 % zählen in Hochdurchsatz-Systemen.

— Editorial Team