Optymalizacja rejestrów w RyuJIT za pomocą algorytmów genetycznych

# Optymalizacja przydzielania rejestrów w RyuJIT za pomocą algorytmów genetycznych

Algorytmy genetyczne pozwalają znajdować nieoczywiste rozwiązania w zadaniach z ogromną przestrzenią przeszukiwania — na przykład przy optymalizacji kolejności heurystyk przydzielania rejestrów w kompilatorze RyuJIT. Zamiast sztywno ustalonej sekwencji wyboru wolnych i zajętych rejestrów badacze z zespołu .NET eksperymentalnie dobrali bardziej efektywną kolejność, która zmniejsza liczbę wyładowań (spills) wewnątrz „gorących” pętli i poprawia PerfScore.

Problem sztywnej kolejności heurystyk

Algorytm liniowego przydzielania rejestrów (LSRA) w RyuJIT wykorzystuje 17 heurystyk do wyboru rejestru podczas kompilacji metody. Pierwsze 13 stosuje się do wolnych rejestrów, ostatnie 4 — do zajętych. Domyślnie kolejność jest ściśle ustalona: ABCDEFGHIJKLMNOPQ. Taki sposób może być nieoptymalny: jeśli wolne rejestry są zużywane na zmienne poza pętlą, to wewnątrz pętli trzeba wielokrotnie wyładowywać wartości z zajętych rejestrów, co zwiększa rozmiar kodu i obniża wydajność.

Przykład z praktyki: w jednym z benchmarków wszystkie zmienne wewnątrz pętli używały tego samego rejestru, powodując ciągłe operacje spill/reload. Nie wynikało to z braku rejestrów, lecz z tego, że heurystyka zawsze dawała priorytet wolnym rejstrom, nawet jeśli ich użycie było mniej opłacalne w dłuższej perspektywie.

Refaktoryzacja LSRA dla dynamicznej konfiguracji kolejności

Aby przetestować alternatywne sekwencje, deweloperzy wykonali następujące kroki:

• Każdą heurystykę wydzielono do osobnej metody z atrybutem __forceinline, aby uniknąć narzutów.
• Utworzono tablicę haszującą, mapującą symbol (A–Q) na wskaźnik do odpowiedniej metody.
• Wprowadzono zmienną środowiskową COMPlus_JitLsraOrdering, przyjmującą ciąg z 17 unikalnych symboli określających kolejność heurystyk.

Teraz można uruchomić JIT z dowolną kombinacją, na przykład:

set COMPlus_JitLsraOrdering=PEHDCGAIJNLKOBFMQ

Pozwala to najpierw stosować heurystyki dla zajętych rejestrów (np. P — PREV_REG_OPT), a potem dla wolnych, co potencjalnie oszczędza wolne rejestry na krytyczne fragmenty kodu.

Pomiar efektywności za pomocą PerfScore

Do oceny jakości przydzielania rejestrów używa się metryki PerfScore — ważonej oceny kosztu wykonania wygenerowanego kodu z uwzględnieniem opóźnień i przepustowości instrukcji. PerfScore jest szczególnie czuły na operacje wyładowania/załadowania (mov [rsp], reg / mov reg, [rsp]), zwłaszcza jeśli występują wewnątrz pętli.

Narzędzie superpmi pozwala porównać dwie wersje clrjit.dll pod względem następujących wskaźników:

• CodeSize — całkowity rozmiar kodu maszynowego
• InstructionCount — liczba instrukcji
• PerfScore — główna metryka docelowa

Celem optymalizacji jest minimalizacja PerfScore. Jednak przestrzeń poszukiwań jest ogromna: 17! ≈ 3.56 × 10¹⁴ możliwych permutacji. Pełne przeszukanie jest niemożliwe nawet na klastrze.

Zastosowanie algorytmu genetycznego

Algorytm genetyczny (GA) idealnie nadaje się do takich zadań:

• Chromosom: ciąg z 17 unikalnych symboli (A–Q) określający kolejność heurystyk.
• Funkcja fitness: ujemna wartość średniego PerfScore na zbiorze testowych kompilacji (im niższy PerfScore, tym wyższa przystosowalność).
• Operator krzyżowania: uporządkowane krzyżowanie (np. PMX), zachowujące unikalność symboli.
• Mutacja: losowa zamiana dwóch pozycji.

Algorytm działa iteracyjnie:

• Inicjalizuje się losową populację (np. 100 chromosomów).
• Dla każdego osobnika obliczana jest funkcja fitness za pomocą superpmi.
• Wybierani są najlepsi rodzice (selekcja turniejowa lub ruletkowa).
• Generowane są potomstwo z krzyżowaniem i mutacją.
• Populacja jest aktualizowana; proces powtarzany do zbieżności.

Wyniki i ograniczenia

Eksperymenty wykazały, że niektóre permutacje rzeczywiście obniżają ogólny PerfScore o 0,5–1,2% w porównaniu z kolejnością domyślną. Największe zyski obserwowano w metodach z zagnieżdżonymi pętlami i dużą liczbą zmiennych tymczasowych.

Warto jednak pamiętać:

• Poprawa nie jest uniwersalna: jedna permutacja może poprawić niektóre metody, a pogorszyć inne.
• Narzuty samego GA są znaczne: wymaga tysięcy uruchomień superpmi.
• Optymalna kolejność zależy od architektury (x64 vs Arm64) i profilu obciążenia.

Co ważne

• Sztywna kolejność heurystyk w LSRA może być nieoptymalna dla rzeczywistych scenariuszy.
• Zmiana kolejności heurystyk za pomocą COMPlus_JitLsraOrdering pozwala eksperymentować bez modyfikacji kodu źródłowego.
• Algorytmy genetyczne są efektywne do poszukiwań w przestrzeniach o złożoności faktorialnej.
• PerfScore to wiarygodna metryka oceny jakości przydzielania rejestrów.
• Nawet niewielka redukcja PerfScore (poniżej 1%) może być znacząca w systemach o wysokim obciążeniu.

— Editorial Team