Miesiąc: sierpień 2020

W poprzednim wpisie pisałem ogólnie o kompilacji kodu w Javie. W tym głównym bohaterem jest JIT, a dokładniej techniki optymalizacji w nim stosowane.

Uwagi wstępne

Na początku zarysować sytuację niskopoziomową.

Otóż mamy procesor. Dla ułatwienia załóżmy, że jeden. Ten procesor służy do wykonywania różnych prostych operacji. Operacje przeważnie mają dodatkowe argumenty i jakiś rezultat.

Skąd procesor ma wiedzieć jakie instrukcje wykonać i skąd te argumenty operacji?

Otóż wszystkie dane zapisane są w pamięci operacyjnej. Jednak każdorazowe sięgnięcie do pamięci ram byłoby mało optymalne, dlatego dane pobierane są w większej ilości. Pamięć – podobnie do instrukcji – jest ułożona sekwencyjnie. Zatem pobierane są fragmenty pamięci najbliżej pobieranej instrukcji. Potrzebujemy w danym momencie jedną instrukcję (i tylko jedną), zatem reszta pobranych danych trafia do cache‚ów procesora.

Kod operacji oraz argumenty są ładowane do rejestrów. Jednak nie wszystkie rejestry są wykorzystywane w przetwarzaniu operacji – niektóre służą za „najszybszą pamięć” szybszą od cache‚ów procesora.

Jak działa procesor?

Z wykonywaniem instrukcji procesora jest trochę, jak czytaniem książki. Ale tylko trochę…

Standardowo, ludzie czytają książki od początku do końca, słowo po słowie. Czytają z pewną stałą prędkością (stała ilość słów w czasie). Gdy skończymy czytać stronę (skończą się instrukcje w cache‚ach procesora), to musimy przerzucić kartkę (wczytać z pamięci do cache‚ów nową stronę). To zajmuje jakiś czas i zmniejsza ilość przeczytanych słów w czasie.

Najlepiej się czyta słowa będące obok siebie – w linii. Gdy zaczynamy czytać kolejną linię, również czasem to wybija z rytmu. Podobnie i procesor najchętniej wykonuje wszystkie operacje po kolei, znając już następną instrukcję. To porównanie jest nieco naciągane, jednakże potokowość bazuje właśnie na najbliższych operacjach. Gdy linia się kończy, musimy (nawet w obrębie widzianej strony) spojrzeć na następną linię. Analogiczną sytuacją jest wykonanie instrukcji skoku w obrębie instrukcji w cache‚u – gubimy wówczas kontekst następnych operacji.

Najgorzej (biorąc pod uwagę wydajność czytania) za to czyta się powieści interaktywne, gdzie co chwilę trzeba skakać z jednej strony na inną. Tutaj alegorią może być małe procedurki (rozumiane jako pewne ciągi instrukcji), które są wywoływane co chwila i w ten sposób procesor „skacze” po skompilowanym kodzie.

Generalnie wszelkiego rodzaju instrukcje skoku (wysokopoziomowo mówiąc wywołania metod, if-else‚y, switch-case‚y itp) są trudne.

A co to ma do kompilacji?

Wiedząc o tym, w jak działa procesor możemy w taki sposób skompilować aplikację, aby procesor dział jak najszybciej.

W JVMie JIT kompiluje poszczególne metody. Na tej metodzie są wykonywane optymalizacje, które usprawniają działanie metody. Musimy zatem przeanalizować cały kod metody.

W metodach bardzo często są wywoływane inne metody. Aby dowiedzieć się, co się w nich dzieje, należy do nich zajrzeć i – jeśli to możliwe – przepisać do analizowanej metody treści wywoływanych metod. W ten sposób nie tylko rozszerzamy poznany kontekst metody, ale również ograniczamy ilość skoków do wywoływanych metod.
O inliningu jednak zrobię osobny wpis, zatem nie będę się o tym rozpisywał.

Jeśli już kontekst wywoływanej metody jest wystarczająco szeroki, można pokusić się o poszukanie usunięcie martwego kodu. Przykładowo, gdy w jednej metodzie przekazujemy do drugiej zawsze nienullowy parametr, a w wywoływanej metodzie na początku mamy „nullchecka”, to można spokojnie go usunąć (to tylko przykład, bo nullchecki są inaczej obsługiwane).

Profilowanie

Wspomniane wcześniej optymalizacje można wykonać zarówno AoT jak i JIT. Bardzo dużą wartość daje profilowanie wykonania metody, które jest specyficzne dla JIT.

Dzięki temu uzyskujemy specyficzny kontekst działania naszej aplikacji. Przykłady:

• Załóżmy, że mamy jakąś flagę, która po uruchomieniu nie zmienia swojej wartości oraz ifka, który od tejże zależy. Jeśli 15 000 razy wartość się nie zmieniła, to możemy założyć, że i 15 001 raz wartość się nie zmieni. O ile samo sprawdzenie musimy wykonać, to domyślną ścieżką powinno być wykonanie treści if, a ewentualne else przerzucone gdzieś możliwie daleko w skompilowanym kodzie. Tak, żeby nie tracić miejsca na „stronie” naszej książki, skoro i tak się to prawie na pewno nie zdarzy.
• Załóżmy, że zarówno if, jak i else są wykonywane, jednak blok wewnątrz if jest 3 krotnie częściej niż blok else. Zatem, aby zaoszczędzić na skokach, treść częstszego bloku powinna być zaraz po sprawdzeniu warunku. Wówczas ograniczamy rozmiar straty potokowości.
• Podobnie dla switcha kolejność case można uszeregować wg częstości występowania.

Profilowanie dotyczy jednak również typu. Pozwala ono – analogicznie do profilowania ifów – na umiejscowienie najczęściej wywoływanego kodu najbliżej wywołania metody. W optymistycznym przypadku możemy stwierdzić, że obiekt tylko jednego typu pojawia się w wywołaniu wirtualnym, a w pozostałych przypadkach zostawić pułapkę, która spowoduje deoptymalizację metody do pierwotnej postaci.

Inne optymalizacje

W szczególny sposób optymalizowane są pętle.

Pod koniec każdej iteracji pętli domyślnie wstawiana jes instrukcja skoku do początku pętli. Zakładając, że pętla wykona się wielokrotnie, możemy ograniczyć ilość skoków poprzez wielokrotny „copy-paste” bloku pętli po każdym sprawdzając warunek pętli.

Dodatkowo, jeśli pętla wykonywana jest tysiącami razy, to o ile nie wykonuje żadnej specyficznej metody, którą można by skompilować, to kod wewnątrz pętli nie miał by okazji do kompilacji. Jednak istnieje mechanizm (On Stack Replacement), który pozwala skompilować kod samej pętli oraz przełączyć się na wykonywanie skompilowanej treści pętli bez zatrzymania programu.

Inną ciekawostką jest, że nie wszystkie metody są kompilowane „od zera” w czasie JIT. Istnieją takie metody zwane intrinsics, które są gotowe do inline’owania. Przykłady to Math.max(), Object.hashCode(), System.copyArray() czy bardziej używane StringBuilder.append() lub Integer.toLongValue().

O ile niektóre „zmienne” możemy przechowywać w rejestrach procesora, to rejestrów tych jest niewiele. Na tyle niewiele, aby w czasie kompilacji metody decydować, które zmienne powinny tam trafić. Ten problem nie należy do banalnych. A bardziej szczegółowo jest to problem NP trudny – problem kolorowania grafu. Jednak C2 taką analizę wykonuje.

Podsumowanie

Temat jest na tyle obszerny, że trudno omówić w jednym wpisie wszystkie optymalizacje. Mogę tylko zostawić kilka ciekawych linków:

Kolejny wpis będzie prawdopodobnie o inliningu, gdyż najważniejszy temat, jeśli chodzi kompilację kodu.
Standardowo prośba o ocenę wpisu, żebym wiedział, że ktoś to przeczytał 😉

Pax et bonum
(und gesundheit, bo korona)