Articles

Seeing Escape Analysis Working

Posted on

być może słyszałeś o fazie analizy kompilatora o nazwie escape analysis. Informuje o optymalizacji zwanej skalarną wymianą agregatów, która usuwa zbędną alokację obiektów Java. Uważam, że ludzie często mają niezrozumienie tego, co ta optymalizacja naprawdę robi i niedocenianie tego, do czego jest zdolna. Możemy ją lepiej poznać, widząc, jak działa w praktyce.

kontekst

pokażę, jak kompilator GraalVM, jako część GraalVM i skonfigurowany do kompilacji just-in-time w konfiguracji hostowanej, stosuje analizę escape i skalarną wymianę agregatów. Kompilator GraalVM jest bardziej wydajny pod tym względem niż najpopularniejszy kompilator just-in-time, do którego prawdopodobnie jesteś przyzwyczajony, C2 w hotspocie.

zauważ, że za każdym razem, gdy mówię o kompilatorze w tym artykule, mam na myśli kompilację just-in-time, więc rodzaj kompilacji, która dzieje się w czasie wykonywania w JVM. Nie chodzi mi o kompilator javac.

pokażę, jak kompilator rozumie nasze przykładowe programy, patrząc na jedną ze struktur danych, których używa podczas kompilacji, jej wyższą reprezentację pośrednią. Jest to wykres, który rejestruje znaczenie programu Java, ponieważ jest on optymalizowany i przekształcany przed rozpoczęciem konwersji na kod maszynowy. Prawdopodobnie brzmi to bardzo zaawansowanie, ale myślę, że dla większości ludzi z pewnym doświadczeniem w Javie jest to całkiem przystępny sposób na zrozumienie, co robi kompilator.

ta reprezentacja pośrednia różni się od abstrakcyjnego drzewa składniowego lub AST, które jest składniową reprezentacją tekstu w programie. Różni się to również od wykresu wywołania, który po prostu mówi, które metody wywołują które Inne metody.

będę używał narzędzia Seafoam, z zespołu implementacji języka Shopify, do tworzenia diagramów struktur danych wyrzuconych z Graala. Możesz również użyć narzędzia o nazwie Ideal Graph Visualizer firmy Oracle Labs.

Terminologia

Analiza ucieczki jest procesem analizy. Wykrywa, czy obiekt jest widoczny poza jednostką kompilacji (Jednostka kompilacji jest zwykle metodą plus wszelkie inne metody w niej wbudowane.) Obiekt może stać się widoczny poza jednostką kompilacji przez zwrócenie, przekazanie jako argument do innej metody lub zapisanie do pola, lub podobne.

skalarna wymiana agregatów wykorzystuje wynik analizy escape i działa na obiektach, które nie uciekają z jednostki kompilacji, lub tylko uciekają z niej na niektórych gałęziach. Zastępuje obiekty (Agregaty) prostymi wartościami (skalarami) podobnymi do zmiennych lokalnych. Zobaczymy to dokładniej później.

alokacja obiektów

będziemy pracować z prostą klasą Vector, która posiada pola double x i y. Ma konstruktor, gettery i metodę add, która zwraca nowy obiekt, który jest tym Vector dodanym do innego.

mam main metodę, która uruchamia pętlę i wywołuje

sum

metodę, która używa

add

, aby zsumować dwa losowo wygenerowane wektory. Pętla jest po to, aby uzyskać kod na tyle gorący, aby wywołać kompilację just-in-time, randomizacja jest po to, aby wartości nie były profilowane, aby były skutecznie stałe, a oddzielna metoda sum jest po to, aby stworzyć czysty blok kodu, na który należy spojrzeć, patrząc na sposób kompilacji kodu.

skompiluję i uruchomię to przy użyciu GraalVM CE na Java 8 20.3.0 na macOS na AMD64. Wyłączam optymalizację zwaną on-stack replacement, ponieważ ta optymalizacja sprawia, że kompilacja jest nieco bardziej skomplikowana i trudniejsza do zrozumienia. Następnie używam opcji Graala

dump

, aby poprosić go o zrzucenie jego pośrednich struktur danych reprezentacji.

możemy teraz użyć Seafoam, aby sprawdzić, jak kompilator rozumie metodę sum, tuż przed uruchomieniem escape analysis. Plik sum.bgv zawiera strukturę danych, którą kompilator dla nas wyrzucił.

% seafoam sum.bgv:14 render

co tu widzimy? Ten wykres jest sposobem, w jaki Graal rozumie metodę sum podczas jej kompilacji. Jest to kod Javy, ale wolny od ograniczeń reprezentacji tekstowej. Operacje są reprezentowane jako węzły (pola, diamenty i owale), a relacje między operacjami są reprezentowane jako krawędzie (strzałki). Gruba czerwona strzałka oznacza, że jedna operacja musi nastąpić przed drugą. Cieńsza strzałka oznacza, że wyjście operacji jest używane jako wejście do innej operacji.

powiedzieliśmy, że program został uwolniony od ograniczeń reprezentacji tekstowej. Spójrz na przykład na operację dodawania w węźle 14. Wiemy, że musi to nastąpić po załadowaniu dwóch wartości z dwóch pól x i przed zapisaniem wartości w polu x w węźle 19, ale nie obchodzi nas, czy dzieje się to przed, czy po załadowaniu dwóch pól y. W tekstowym kodzie źródłowym Javy wszystko jest napisane w jednym porządku liniowym. Wykres rozluźnia to ograniczenie i koduje tylko te ograniczenia, których faktycznie wymaga specyfikacja języka Java. Kompilator może wtedy wybrać ostateczną kolejność, w jakiej wszystko działa.

czytając ten wykres, widzimy, że tworzymy nowe Vector, a następnie ładujemy dwa pola input objects’ x i y, dodajemy je razem, a następnie zapisujemy do nowego Vector, który stworzyliśmy, zanim go zwrócimy. Jest kilka dodatkowych szczegółów na wykresie, takich jak sprawdzenie null, ostateczna bariera pola i wiele więcej, ponieważ jest to prawdziwy Wykres kompilatora, ale zignorujemy te dla tego artykułu, aby zachować go krótko.

kluczową rzeczą do zobaczenia jest to, że istnieje określony punkt, w którym tworzony jest nowy obiekt Vector.

podstawowa wymiana skalarna

przyjrzyjmy się tej samej metodzie zaraz po uruchomieniu analizy escape i wymiany skalarnej agregatów.

% seafoam sum.bgv:15 render

teraz wykres został jeszcze bardziej złagodzony od tego, jak pojawia się w tekście. Zamiast operacji New Vector mamy teraz rozłożone go do ogólnej operacji przydzielania obiektu, biorąc wartość pól tego obiektu. Tu już nie ma StoreField

w tej konkretnej metodzie nie osiągnęło to niczego użytecznego – wykres został złagodzony, ale nie ujawnił żadnych naprawdę użytecznych optymalizacji. To dlatego, że jedyny obiekt, który nam przydzielono, musi zostać przydzielony, ponieważ opuszcza metodę. Analiza ucieczki została przeprowadzona, ale obiekt uciekł, więc nie było skalarnej wymiany agregatów.

aby posunąć się dalej, przyjrzyjmy się metodzie, która sumuje trzy obiekty Vector.

private static Vector sum(Vector a, Vector b, Vector c) {return a.add(b).add(c);}

wykres przed analizą escape i wymianą skalarną agregatów ma taką samą strukturę jak poprzednia metoda. Mamy dwie operacje New Vector. Wynik a.add(b)jest zapisywany do pierwszego nowego obiektu, a następnie ponownie odczytywany dla kolejnego .add(c). Widzimy, że jest to marnotrawstwo – obiekt pośredni nigdy nie jest widoczny poza jednostką kompilacji, ponieważ nie jest nigdzie przechowywany ani przekazywany – więc po co go przydzielać i po co przechowywać w nim pola, które natychmiast ponownie odczytujemy?

jeśli spojrzymy na wykres po analizie escape i skalarnej wymianie agregatów, zobaczymy, że pośredni Vector został całkowicie usunięty. Jest tylko jeden Alloc, nie dwa. Agregat pól pośredniego obiektu został zastąpiony skalarnymi wartościami krawędzi bezpośrednio łączących producenta i konsumenta, bez robienia pośredniego StoreField, a następnie LoadField.

skuteczność wymiany skalarnej

jeszcze kilka przykładów pokaże, jak ta optymalizacja jest nieco potężniejsza niż ludzie często zakładają.

jeśli zsumujemy tablicę Vector obiektów, to logicznie stworzymy jeden Vector na iterację.

private static Vector sum(Vector first, Vector... rest) {Vector sum = first;for (Vector vector : rest) {sum = sum.add(vector);}return sum;}

ten wykres jest teraz dość skomplikowany, ale kluczowym punktem jest to, że można zobaczyć operację New Vector wewnątrz pętli (wewnątrz okręgu utworzonego z grubych czerwonych strzałek.)

po częściowej analizie escape ’ u i wymianie skalarnej agregatów nie ma obecnie New Vector wewnątrz pętli. Na końcu jest jedna alokacja dla końcowego Vector, która jest zwracana, a wartości dla x i y są budowane przez gromadzenie wartości (małe pętle wokół węzłów 33 i 92 oraz węzłów 36 i 93.) Oznacza to, że w wewnętrznej pętli tej metody nie jest już przydzielana pamięć.

czasami ludzie mówią o obiektach, które nie unikają jednostki kompilacji przydzielonej na stosie. Oto dlaczego to nieporozumienie. Metoda ta sumuje dwa obiekty Vector, ale zwraca tylko komponent x.

private static double sumX(Vector a, Vector b) {return a.add(b).getX();}

przed uruchomieniem escape analysis ta metoda wygląda dokładnie tak, jak oryginalna sum, z wyjątkiem pola x, które jest następnie ładowane i zwracane. Pole y jest przechowywane, ale nigdy nie jest używane, a pośrednie pole Vector nie opuszcza jednostki kompilacji.

po analizie escape i wymianie skalarnej agregatów, możemy zauważyć ważny punkt – po zastąpieniu obiektu skalarami, nie było konsumenta wartości y, więc kod do jej wygenerowania nie miał nic do podłączenia go do wykresu i tak został usunięty.

gdybyśmy dosłownie przydzielali obiekt na stosie, przechowując obiekt w tym samym formacie tylko w pamięci stosu, a nie w pamięci stosu, nadal musielibyśmy wygenerować pośrednią wartość y. Nie przydzielamy obiektu nigdzie-zamiast tego zastąpiliśmy go krawędziami przepływu danych.

zauważ, że alokacja obiektów na stos jest naprawdę rzeczą i jest proponowana dla standardowego hotspota i C2, ale jest to dla nieco innego celu, do którego nie będziemy tu wchodzić dla uproszczenia.

porównując do ręcznej optymalizacji

czy mógłbyś przepisać niektóre z tych metod, aby gromadzić x i y w zmiennych lokalnych i nie tworzyć pośrednich obiektów Vector? Na przykład możesz przepisać sum na tablicę Vector obiektów takich jak ten:

ten wykres jest rzeczywiście bardziej wydajny niż Wykres naszej sumy z obiektami pośrednimi Vector przed analizą escape. Nie ma alokacji wewnątrz pętli.

ale jeśli spojrzymy wstecz na naszą poprzednią pętlę sum z obiektami pośrednimi Vector po analizie escape i skalarnej wymianie agregatów, wyglądają one zasadniczo tak samo. Nie było korzyści w przepisywaniu tej metody z wersji wysokiego poziomu z prostymi obiektami pośrednimi Vector do wersji ręcznie zoptymalizowanej.

(właściwie może jest – ręcznie zoptymalizowana wersja jest szybsza w kompilacji i działa szybciej podczas interpretacji, dopóki nie zostanie skompilowana.)

częściowa analiza ucieczki

coś, co Graal może zrobić, czego C2 nie może, a kluczową zaletą GraalVM jest częściowa analiza ucieczki. Zamiast określać binarną wartość tego, czy obiekt opuszcza jednostkę kompilacji, czy nie, może określić, na których gałęziach obiekt ucieka, i przenieść alokację obiektu tylko na te gałęzie, do których ucieka.

ta wymyślona metoda sumuje dwa obiekty Vector, a następnie na podstawie warunku s przekazuje go jako parametr do innej metody o nazwie blackhole, co powoduje jej ucieczkę, lub dodaje trzeci wektor, a następnie go zwraca.

pośredni Vector przechowywany w x ucieka na pierwszej gałęzi, ale nie na drugiej.

zapobiegamy inlinedowi blackhole, określając -XX:CompileCommand=dontinline,Vector.blackhole.

przed uruchomieniem analizy częściowej możemy zobaczyć New Vector dla x uruchamianych dla obu gałęzi.

po częściowej analizie ucieczkowej i zastąpieniu skalarowym agregatów wartość pośrednia New Vector zniknęła. Zamiast tego, w gałęzi, w której obiekt ucieka, mamy obiekt Alloc, który odwołuje się do wartości, które powinien mieć x i y, a w innej gałęzi, w której obiekt nie ucieka, wartości dla x i y są po prostu używane bezpośrednio.

przydział został przeniesiony tylko do gałęzi, w której jest faktycznie potrzebny.

mam nadzieję, że wszystko pomoże Ci zrozumieć, czym jest analiza escape i skalarna wymiana agregatów, widząc, że działa w praktyce. Mam również nadzieję, że pokazuje, że nie jest to naprawdę alokacja stosu i jest czymś potężniejszym niż to, i że pokazuje, co dodatkowy kompilator GraalVM może dla ciebie zrobić.

więcej informacji

algorytm analizy częściowej ucieczki Graala jest opisany w częściowej analizie ucieczki i zastępowaniu skalarnym dla Javy.

pisałem więcej o tych wykresach kompilatora i o tym, jak je odczytać w zrozumieniu podstawowych wykresów Graala.

autor: Chris Seaton

Chris jest pracownikiem naukowym (Senior Staff Engineer) w Shopify, gdzie pracuje nad językiem programowania Ruby, oraz gościem na Uniwersytecie w Manchesterze.

był wcześniej kierownikiem badań w Oracle Labs Virtual Machine Research Group, gdzie kierował implementacją Ruby TruffleRuby i pracował nad innymi projektami języków i maszyn wirtualnych. Wcześniej ukończył doktorat w Manchesterze, gdzie badał języki programowania i nieregularny równoległość, oraz MEng na Uniwersytecie w Bristolu na temat języków z mutowalną składnią i semantyką.

w wolnych chwilach jest dowódcą Szwadronu Cheshire Yeomanry squadron Of The Queen ’ s Own Yeomanry, historycznego rezerwowego szwadronu lekkiej kawalerii w Cheshire.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.