Escape Analysis Working

u hebt wellicht gehoord van een compiler analyse fase genaamd escape analysis. Het informeert een optimalisatie genaamd scalaire vervanging van aggregaten die onnodige toewijzing van Java-objecten verwijdert. Ik vind dat mensen vaak een misverstand hebben over wat deze optimalisatie echt doet en een onderwaardering van wat het in staat is. We kunnen het beter leren kennen door het in de praktijk te zien werken.

Context

Ik zal laten zien hoe de graalvm compiler, als onderdeel van GraalVM en geconfigureerd voor just-In-time compilatie in gehoste configuratie, escape analyse en scalaire vervanging van aggregaten toepast. De graalvm compiler is in dit opzicht krachtiger dan de meest voorkomende just-in-time compiler die je waarschijnlijk gewend bent, C2 in HotSpot.

merk op dat elke keer als ik compiler zeg in dit artikel, Ik bedoel just-in-time compilatie, dus het soort compilatie dat gebeurt tijdens runtime in de JVM. Ik bedoel niet de javac compiler.

Ik zal laten zien hoe de compiler onze voorbeeldprogramma ‘ s begrijpt door te kijken naar een van de datastructuren die het gebruikt tijdens het compileren, de hogere tussenliggende representatie. Dit is een grafiek die de Betekenis van een Java-programma vangt zoals het is geoptimaliseerd en getransformeerd voordat de conversie naar machine code begint. Dat klinkt waarschijnlijk erg geavanceerd, maar ik denk dat Voor de meeste mensen met enige ervaring met Java Het is eigenlijk nogal een benaderbare manier om te begrijpen wat de compiler doet.

deze intermediaire representatie verschilt van een abstracte syntaxisboom, of AST, wat een syntactische representatie is van de tekst in uw programma. Het is ook anders dan een aanroepgrafiek, die je gewoon vertelt welke methoden welke andere methoden aanroepen.

Ik zal een tool genaamd Seafoam gebruiken, van Shopify ‘ s language implementation team, om diagrammen te maken van de datastructuren die uit Graal gedumpt zijn. U kunt ook gebruik maken van een tool genaamd De Ideal Graph Visualizer van Oracle Labs.

terminologie

Escape-analyse is een analyseproces. Het detecteert of een object zichtbaar is buiten een compilatie-eenheid (een compilatie-eenheid is meestal een methode plus andere methoden die erin zijn opgenomen.) Een object kan zichtbaar worden buiten een compilatie-eenheid door te worden geretourneerd, of doorgegeven als argument aan een andere methode, of geschreven naar een veld, of iets dergelijks.

scalaire vervanging van aggregaten maakt gebruik van het resultaat van escape-analyse en werkt op objecten die niet ontsnappen aan de compilatie-eenheid, of alleen ontsnappen aan sommige takken. Het vervangt objecten (aggregaten) door eenvoudige waarden (scalars) die vergelijkbaar zijn met lokale variabelen. We zullen dit later concreter zien.

Objectallocatie

we zullen werken met een eenvoudige Vector klasse die double x en y velden bevat. Het heeft een constructor, getters en een add methode die een nieuw object retourneert dat dit Vector is toegevoegd aan een ander object.

ik heb een main methode die een lus uitvoert en een

sum

methode aanroept die

add

gebruikt om twee willekeurig gegenereerde vectoren op te tellen. De lus is er om de code heet genoeg te krijgen om just-In-time compilatie te activeren, de randomisatie is er zodat waarden niet worden geprofileerd om effectief constant te zijn, en de aparte sum methode is er om een nette blok code te maken om naar te kijken wanneer je kijkt naar hoe code wordt gecompileerd.

Ik zal dit compileren en uitvoeren met behulp van GraalVM CE op Java 8 20.3.0 op macOS op AMD64. Ik zet een optimalisatie genaamd on-stack vervanging omdat deze optimalisatie compilatie een beetje ingewikkelder en moeilijker te begrijpen maakt. Ik gebruik dan Graal ‘ s

dump

optie om het te vragen om zijn intermediaire representatie datastructuren te dumpen.

we kunnen nu Seafoam gebruiken om te kijken hoe de compiler de sum methode begrijpt, vlak voordat het escape analysis uitvoert. Het bestand sum.bgv bevat de gegevensstructuur die de compiler voor ons dumpte.

% seafoam sum.bgv:14 render

wat zien we hier? Deze grafiek is de manier waarop Graal de sum methode begrijpt tijdens het compileren. Het is Java-code, maar vrij van de beperkingen van een tekstuele weergave. Operaties worden weergegeven als knooppunten (de dozen, ruiten en ovalen) en de relaties tussen operaties worden weergegeven als Randen (de pijlen). De dikke rode pijl betekent dat de ene operatie voor de andere moet gebeuren. De dunnere pijl betekent dat de output van de operatie wordt gebruikt als input voor een andere operatie.

we zeiden dat het programma was bevrijd van de beperkingen van een tekstuele representatie. Kijk bijvoorbeeld naar de bewerking toevoegen in knooppunt 14. We weten dat het moet gebeuren nadat we de twee waarden uit de twee x velden laden, en voordat we de waarde opslaan in het veld x in knooppunt 19, maar het maakt ons niet uit of het gebeurt voordat of nadat de twee y velden zijn geladen. In Java tekstuele broncode, alles is geschreven in een lineaire volgorde. De grafiek ontspant deze beperking en codeert alleen de beperkingen die de Java-taalspecificatie eigenlijk vereist. De compiler is dan vrij om de uiteindelijke volgorde alles draait in te kiezen.

bij het lezen van deze grafiek kunnen we zien dat we een nieuwe Vector maken, dan de velden x en y laden, ze bij elkaar optellen en ze vervolgens opslaan in de nieuwe Vector die we hebben gemaakt voordat we het retourneren. Er zijn enkele extra details in de grafiek, zoals de null controle, de laatste veld barrière, en meer omdat dit een echte compiler grafiek is, maar we zullen die voor dit artikel negeren om het kort te houden.

het belangrijkste om hier nu te zien is dat er een bepaald punt is waar het nieuwe Vector object wordt gemaakt.

basis scalaire vervanging

laten we eens kijken naar dezelfde methode direct na escape analyse en scalaire vervanging van aggregaten hebben uitgevoerd.

% seafoam sum.bgv:15 render

nu is de grafiek nog verder versoepeld van hoe het in de tekst verschijnt. In plaats van een New Vector operatie hebben we het nu opgesplitst in een generieke operatie om een object toe te wijzen, waarbij de waarde van de velden van dat object wordt genomen. Er is hier geen StoreField meer.

in deze specifieke methode heeft dit niets nuttigs bereikt – de grafiek is versoepeld, maar het onthulde geen echt nuttige optimalisaties. Dat komt omdat het enige object dat we toegewezen echt moet worden toegewezen omdat het de methode verlaat. De ontsnappingsanalyse is uitgevoerd, maar het object is ontsnapt, dus er was geen scalaire vervanging van aggregaten.

om dit verder te gaan, laten we eens kijken naar een methode die drie Vector objecten telt.

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

de grafiek vóór escape-analyse en scalaire vervanging van aggregaten heeft dezelfde structuur als de vorige methode. We hebben twee New Vector operaties. Het resultaat van a.add(b) wordt in het eerste nieuwe object geschreven en vervolgens opnieuw uitgelezen voor de volgende .add(c). We kunnen zien hoe dit verspillend is – het tussenliggende object is nooit zichtbaar buiten de compilatie-eenheid omdat het nergens wordt opgeslagen of doorgegeven-dus waarom het toewijzen en waarom velden erin opslaan die we gewoon meteen opnieuw voorlezen?

als we kijken naar de grafiek na escape-analyse en scalaire vervanging van aggregaten zien we dat het tussenproduct Vector volledig is verwijderd. Er is slechts één Alloc, niet twee. Het aggregaat van de velden van het intermediaire object is vervangen door de scalaire waarden van randen die de producent en de consument rechtstreeks met elkaar verbinden, zonder een intermediair StoreField en vervolgens LoadFieldte doen.

de effectiviteit van scalaire vervanging

enkele voorbeelden zullen laten zien hoe deze optimalisatie iets krachtiger is dan mensen vaak aannemen.

als we een array van Vector objecten optellen, zullen we logischerwijs één Vector per iteratie aanmaken.

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

deze grafiek is nu vrij ingewikkeld, maar het belangrijkste punt is dat je een New Vector operatie kunt zien binnen de lus (binnen de cirkel gevormd door dikke rode pijlen.)

na gedeeltelijke ontsnappingsanalyse en scalaire vervanging van aggregaten run is er nu geen New Vector binnen de lus. Er is een enkele allocatie aan het einde voor de uiteindelijke Vector die wordt geretourneerd, en de waarden voor x en y worden opgebouwd door waarden te accumuleren (de kleine lussen rond knopen 33 en 92, en knopen 36 en 93.) Dit betekent dat er geen geheugen meer wordt toegewezen in de binnenste lus van deze methode.

soms praten mensen over objecten die niet ontsnappen aan een compilatie-eenheid die op de stack wordt toegewezen. Dit is waarom dat een misverstand is. Deze methode somt twee Vector objecten op, maar geeft alleen de x component terug.

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

voordat de escape-analyse wordt uitgevoerd, ziet deze methode er precies uit als het origineel sum, behalve dat het veld x dan wordt geladen en geretourneerd. Het veld y is opgeslagen maar nooit gebruikt, en de tussenliggende Vector ontsnapt niet aan de compilatie-eenheid.

na escape analyse en scalaire vervanging van aggregaten, zien we een belangrijk punt om op te merken – nadat het object werd vervangen door scalars, was er geen consument van de y waarde, dus de code om het te genereren had niets om het te verbinden met de grafiek en dus werd het verwijderd.

als we het object letterlijk op de stack toewijzen en het object in hetzelfde formaat opslaan, alleen in het stackgeheugen in plaats van het heapgeheugen, zouden we nog steeds de tussenwaarde y moeten genereren. We wijzen het object nergens toe-in plaats daarvan hebben we het vervangen door dataflow-randen.

merk op dat stack allocatie van objecten echt een ding is, en het wordt voorgesteld voor standaard HotSpot en C2, maar het is voor een iets ander doel waar we hier niet op ingaan voor eenvoud.

in vergelijking met handmatige optimalisatie

zou u enkele van deze methoden willen herschrijven om de x en y in lokale variabelen te accumuleren en geen tussenliggende Vector objecten te maken? Kunt u bijvoorbeeld sum herschrijven over een array van Vector objecten zoals deze:

deze grafiek is inderdaad efficiënter dan de grafiek van onze som met tussenliggende Vector objecten voor escape-analyse. Er is geen toewijzing binnen de lus.

maar als we terugkijken naar onze vorige sum lus met tussenliggende Vector objecten na escape analyse en scalaire vervanging van aggregaten, zien ze er in principe hetzelfde uit. Er was geen voordeel bij het herschrijven van deze methode van de versie op hoog niveau met eenvoudige tussenliggende Vector objecten naar de handmatig geoptimaliseerde versie.

(nou eigenlijk is er misschien – de handmatig geoptimaliseerde versie is sneller te compileren en draait sneller terwijl het wordt geïnterpreteerd totdat het is gecompileerd.)

partiële ontsnappingsanalyse

iets dat Graal kan doen dat C2 niet kan, en een belangrijk voordeel van GraalVM is partiële ontsnappingsanalyse. In plaats van het bepalen van een binaire waarde van of een object ontsnapt aan de compilatie-eenheid of niet, kan dit bepalen op welke branches een object ontsnapt, en de toewijzing van het object verplaatsen naar alleen die branches waar het ontsnapt.

deze gekunstelde methode somt twee Vector objecten op, en dan op basis van een voorwaarde s geeft het deze als parameter door aan een andere methode genaamd blackhole, die ervoor zorgt dat het ontsnapt, of het voegt een derde vector toe en geeft het vervolgens terug.

de tussenliggende Vector opgeslagen in x ontsnapt op de eerste branch, maar niet op de tweede.

we voorkomen dat blackhole wordt weergegeven door -XX:CompileCommand=dontinline,Vector.blackholeop te geven.

voordat een gedeeltelijke escape analyse wordt uitgevoerd, kunnen we zien dat New Vector voor x wordt uitgevoerd voor beide branches.

na gedeeltelijke ontsnappingsanalyse en scalaire vervanging van aggregaten is het tussenproduct New Vector verdwenen. In plaats daarvan hebben we op de branch waar het ontsnapt het Alloc object, dat verwijst naar de waarden die het zou moeten hebben van x en y, en op de andere branch waar het object niet ontsnapt worden de waarden voor x en y gewoon direct gebruikt.

de allocatie is verplaatst naar alleen het bijkantoor waar ze daadwerkelijk nodig is.

hopelijk helpt dit alles u te begrijpen wat ontsnappingsanalyse en scalaire vervanging van aggregaten is door het in de praktijk te zien werken. Ook hoop ik dat het je laat zien dat het niet echt stack allocatie is en eigenlijk iets krachtiger is dan dat, en dat het je laat zien wat extra de Graalvm Compiler voor je kan doen.

meer informatie

Graal ‘ s partial escape analysis algoritme wordt beschreven in Partial Escape Analysis and Scalar Replacement voor Java.

ik heb meer geschreven over deze compiler grafieken en hoe ze te lezen in het begrijpen van fundamentele Graal grafieken.