Optimalizace registrů v RyuJIT prostřednictvím genetických algoritmů

# Optimalizace rozdělování registrů v RyuJIT pomocí genetických algoritmů

Genetické algoritmy umožňují nalézat neobvyklá řešení v úlohách s obrovským prostorem prohledávání – například při optimalizaci pořadí heuristik rozdělování registrů v kompilátoru RyuJIT. Místo pevně dané sekvence výběru volných a obsazených registrů výzkumníci z týmu .NET experimentálně vybrali efektivnější pořadí, které snižuje počet vykládání (spills) uvnitř „horkých“ smyček a zlepšuje PerfScore.

Problém pevného pořadí heuristik

Algoritmus lineárního rozdělování registrů (LSRA) v RyuJIT používá 17 heuristik pro výběr registru při kompilaci metody. Prvních 13 se aplikuje na volné registry, posledních 4 na obsazené. Výchozí pořadí je přísně pevné: ABCDEFGHIJKLMNOPQ. Takový přístup může být neoptimální: pokud se volné registry spotřebují na proměnné mimo smyčku, uvnitř smyčky dochází k opakovanému vykládání hodnot z obsazených registrů, což zvyšuje velikost kódu a snižuje výkon.

Příklad z praxe: v jednom z benchmarků všechny proměnné uvnitř smyčky používaly stejný registr, což způsobovalo neustálé operace spill/reload. To se nestávalo kvůli nedostatku registrů, ale protože heuristika vždy dávala přednost volným registrům, i když jejich použití bylo v dlouhodobém horizontu méně výhodné.

Refaktoring LSRA pro dynamické nastavení pořadí

Aby bylo možné otestovat alternativní sekvence, vývojáři provedli následující kroky:

• Každou heuristiku vyjmuti do samostatné metody s atributem __forceinline, aby se zabránilo režijním nákladům.
• Vytvořili hash tabulku mapující symbol (A–Q) na ukazatel na odpovídající metodu.
• Zavádějí proměnnou prostředí COMPlus_JitLsraOrdering, která přijímá řetězec se 17 unikátními symboly určujícími pořadí aplikace heuristik.

Nyní lze spustit JIT s libovolnou kombinací, například:

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

To umožňuje nejprve aplikovat heuristiky pro obsazené registry (např. P – PREV_REG_OPT) a poté pro volné, což potenciálně šetří volné registry pro kritické části kódu.

Měření efektivity prostřednictvím PerfScore

Pro hodnocení kvality rozdělování registrů se používá metrika PerfScore – vážené hodnocení nákladů na provedení generovaného kódu s ohledem na latenci a propustnost instrukcí. PerfScore je obzvláště citlivý na operace vykládání/nahrávání (mov [rsp], reg / mov reg, [rsp]), zejména pokud se nacházejí uvnitř smyček.

Nástroj superpmi umožňuje porovnat dvě verze clrjit.dll podle následujících ukazatelů:

• CodeSize – celková velikost strojového kódu
• InstructionCount – počet instrukcí
• PerfScore – hlavní cílová metrika

Cílem optimalizace je minimalizace PerfScore. Prostor hledání je však obrovský: 17! ≈ 3.56 × 10¹⁴ možných permutací. Kompletní prohledání není možné ani na clusteru.

Aplikace genetického algoritmu

Genetický algoritmus (GA) je ideální pro takové úlohy:

• Chromozom: řetězec se 17 unikátními symboly (A–Q) určujícími pořadí heuristik.
• Fitness funkce: záporná hodnota průměrného PerfScore na sadě testovacích sestavení (čím nižší PerfScore, tím vyšší přizpůsobivost).
• Operátor křížení: řazený crossover (např. PMX), který zachovává unikátnost symbolů.
• Mutace: náhodná výměna dvou pozic.

Algoritmus funguje iterativně:

• Inicializuje se náhodná populace (např. 100 chromozomů).
• Pro každého jedince se vypočítá fitness prostřednictvím superpmi.
• Vyberou se nejlepší rodiče (turnajový nebo ruletový výběr).
• Generují se potomci s aplikací křížení a mutace.
• Populační aktualizuje; proces se opakuje do konvergence.

Výsledky a omezení

Experimenty ukázaly, že některé permutace skutečně snižují celkový PerfScore o 0.5–1.2 % oproti výchozímu pořadí. Nejvýznamnější zlepšení bylo pozorováno v metodách s vnořenými smyčkami a velkým množstvím dočasných proměnných.

Je však důležité si uvědomit:

• Zlepšení není univerzální: jedna permutace může zlepšit některé metody a zhoršit jiné.
• Režijní náklady samotného GA jsou vysoké: vyžaduje tisíce spuštění superpmi.
• Optimální pořadí závisí na architektuře (x64 vs Arm64) a profilu zátěže.

Co je důležité

• Pevné pořadí heuristik v LSRA může být neoptimální pro reálné scénáře.
• Přeřazení heuristik prostřednictvím COMPlus_JitLsraOrdering umožňuje experimentovat bez změny zdrojového kódu.
• Genetické algoritmy jsou efektivní pro hledání v prostorech s faktoriální složitostí.
• PerfScore je spolehlivá metrika pro hodnocení kvality rozdělování registrů.
• I malé snížení PerfScore (méně než 1 %) může být významné ve vysoce zatížených systémech.

— Editorial Team