Kompilacja kodu w Javie – JIT teoretycznie

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)

 

Kompilacja kodu w Javie

Ile razy kod Javy trzeba kompilować, aby optymalny…

Wpis ten jest wstępem do kolejnych wpisów, więc może być dosyć ogólny, względnie nudny dla przeciętnego Senior Tech JVM Performance Leada 😉

OpenJDK/OracleJDK

Największą częścią rynku (91%) są dystrybucje JVMa z rodziny OpenJDK (z OracleJDK włącznie). Dystrybucje te bazują na tym samym kodzie źródłowym, zatem można je spokojnie omawiać wspólnie.

Kompilacja plików .java

Chronologicznie należałoby zacząć od kodu źródłowego zapisanego w plikach.java.

Kod kompilowany jest do standardowo bytecode‚u i ta kompilacja jest wykonywana przed uruchomieniem programu. Spokojnie tę kompilację można nazwać pierwszą kompilacją i – bynajmniej – nie jest ona optymalna 😉 Wszelkie metody optymalizacji są tutaj bardzo ograniczone. Można zrobić jakieś Constant Folding (o którym pisałem już chociażby we wpisach o finalach), jednak nie jest to szczyt technik optymalizacyjnych.

Kod kompilowany do bytecode‚u kompiluje się jednak znacznie szybciej, niż kompilowany do kodu natywnego. Jest też bardziej elastyczny. Czyli do developmentu „good enough”.

JIT

Kompilacja just-in-time (swobodne tłumaczenie to „rychło w czas”) polega na kompilowaniu kodu w czasie działania aplikacji.
Jakby się głębiej zastanowić, to widać podobieństwa do samolotu w tejże reklamie.

Założenie jest takie, że większość kodu jest wykonywana na tyle rzadko, że można ją po prostu wykonać w trybie interpretowanym. Szkoda zatem cykli procesora na szalone optymalizacje fragmentów kodu, wykonywanych jednokrotnie. Warto się jednak skupić na metodach wykonywanych tysiące razy.

Co więcej, skoro mamy już pewien narzut na interpretację kodu bajtowego, to do czasu porządnej optymalizacji warto poświęcić procesor i zbierać dodatkowe statystyki. Mogą one być bardzo przydatne – jeśli w ciągu przykładowo 1000 wykonań program ani razu nie wszedł w jakiegoś ifka, to prawdopodobnie przy 1001 wywołaniu również nie wejdzie. Można przykładowo pominąć treść sekcji, którego ten ifek dotyczy (zaoszczędzimy bajtów i nie tylko, acz o tym kiedy indziej). W razie czego, gdyby przez przypadek ifek stał się prawdziwy, można przykładowo odesłać do wykonywania źródeł w bajtkodzie (to tylko przykładowy przykład; trochę inaczej się to robi w realu).

C1, C2

Dawno temi, w zamierzchłych czasach Javy 1.6 istniały dwa osobne kompilatory C1 (szybki, acz niedokładny – kliencki) oraz C2 (wolny, ale zaawansowany – serwerowy/opto). Na starcie wybierało się pożądany kompilator flagą lub JVM sam nam go wybierał bazując na parametrach naszego sprzętu.

W Javie 1.7 została wprowadzona tzn. kompilacja warstwowa. Według niej interpretujemy kod. Po przekroczeniu progu 2 000 wywołań kompilujemy metodę z użyciem C1. Jednak życie toczy się dalej, a metoda dalej jest wywoływana. Po wywoływaniu metody 15 000 razy jest ona kompilowana z użyciem C2.

Jest jednak kilka „ale”.

Wspomniana kompilacja warstwowa ma ponumerowane warstwy. Poziom 0 to nieskompilowana metoda w trybie interpretowanym. Poziom 4 to C2. Za to za warstwy 1-3 odpowiada C1, która ma różne „warianty”. Istnieje wariant z pełnym profilowaniem (3), ale też istnieje lżejsza wersja ze ograniczonym profilowaniem(2) i najlżejsza – bez profilowania (1).

W idealnej sytuacji kompilujemy metodę do warstwy 3 (po 2 000 wykonaniach), a następnie do warstwy 4 (po 15 000 wykonaniach). Jednak nie zawsze tak jest. Trzeba mieć świadomość, że po przekroczeniu tych progów metoda jest wrzucana do kolejki metod do kompilacji. Przykładowo czasem kolejka do kompilatora C2 jest na tyle długa, że może do czasu zwolnienia C2 można ograniczyć profilowanie (przejść z 3 warstwy na 2). Jak głoszą slajdy Oracle’owe, trzeci poziom jest 30% wolniejszy niż drugi.

AoT?

Jak wiemy istnieje też GraalVM i kompilator Graal. Jest to jednak rozwiązanie typowo Oracle’owe, więc w tym wpisie nie będę rozwijał tego tematu.

Są jednak dwie ciekawostki.
Pierwsza jest taka, że jeśli macie ochotę napisać własny kompilator, to nie ma sprawy, OpenJDK (od Javy 9) wesprze Cię w tym wystawiając interfejs,który trzeba zaimplementować pisząc kompilator. Proste 5 metodek 😉

Druga ciekawostka jest mniej znana – również w Javie 9 powstał eksperymentalnie kompilator AoT. Pozwala on kompilować program do kodu natywnego. Istnieje jednak jeszcze drugi tryb kompilacji – kompilowanie do kodu natywnego z profilowaniem. Taka opcja pozwala na rekompilację z użyciem C2 i dodatkowych metadanych zbieranych w czasie działania programu. W założeniu ten tryb miał przyspieszyć włączanie projektu, jednak benchmarki powiadają, że tak się nie dzieje…

Podsumowanie

O ile trochę wiemy co się dzieje, to nie wiemy w jaki sposób. Zatem w kolejnych wpisach napiszę nieco o tym co się kompiluje, kiedy, jak oraz skąd to wszystko mamy wiedzieć…

Z ciekawych linków zostawiam tylko wpis na blogu Microsoftu o AoT i nie tylko.

Gwiazdkujcie, komentujcie i bywajcie zdrów 😉

Pax et Bonum