Articles

at se Escape Analysis arbejde

Posted on

du har måske hørt om en kompilatoranalysefase kaldet escape analysis. Det informerer en optimering kaldet skalar udskiftning af aggregater, der fjerner unødvendig tildeling af Java-objekter. Jeg finder ud af, at folk ofte har en misforståelse af, hvad denne optimering virkelig gør, og en undervurdering af, hvad den er i stand til. Vi kan vide det bedre ved at se det arbejde i praksis.

kontekst

jeg vil vise, hvordan GraalVM compiler, som en del af GraalVM og konfigureret til Just-in-time kompilering i hosted konfiguration, anvender escape analyse og skalar udskiftning af aggregater. GraalVM compiler er mere kraftfuld i denne henseende end den mest almindelige just-in-time compiler, som du sandsynligvis er vant til, C2 i HotSpot.

Bemærk, at hver gang jeg siger compiler i denne artikel, betyder Jeg just-in-time kompilering, så den slags kompilering, der sker ved runtime i JVM. Jeg mener ikke javac compiler.

jeg viser, hvordan kompilatoren forstår vores eksempelprogrammer ved at se på en af de datastrukturer, den bruger under kompilering, dens højere mellemrepræsentation. Dette er en graf, der fanger betydningen af et Java-program, da det optimeres og transformeres, før konvertering til maskinkode starter. Det lyder sandsynligvis meget avanceret, men jeg tror for de fleste mennesker med en vis erfaring med Java, at det faktisk er en ganske tilgængelig måde at forstå, hvad kompilatoren laver.

denne mellemliggende repræsentation er forskellig fra et abstrakt syntakstræ eller AST, som er en syntaktisk repræsentation af teksten i dit program. Det er også anderledes end en opkaldsgraf, som bare fortæller dig, hvilke metoder der kalder hvilke andre metoder.

jeg bruger et værktøj kaldet Seafoam fra Shopify ‘ s sprogimplementeringsteam til at oprette diagrammer over datastrukturer, der er dumpet ud af Graal. Du kan også bruge et værktøj kaldet Ideal Graph Visualisator fra Oracle Labs.

terminologi

Escape analyse er en analyseproces. Det registrerer, om et objekt er synligt uden for en kompileringsenhed (en kompileringsenhed er normalt en metode plus andre metoder indbygget i den.) Et objekt kan blive synligt uden for en kompileringsenhed ved at blive returneret eller overført som et argument til en anden metode eller skrevet til et felt eller lignende.

Scalar udskiftning af aggregater bruger resultatet af escape-analyse og arbejder på objekter, der ikke undslipper kompileringsenheden, eller kun undslipper den på nogle grene. Det erstatter objekter (aggregater) med enkle værdier (skalarer) svarende til lokale variabler. Vi vil se dette mere konkret senere.

Objektallokering

vi arbejder med en simpel Vector klasse, der indeholder double x og y felter. Den har en konstruktør, getters og en add metode, der returnerer et nyt objekt, der er dette Vector tilføjet til et andet.

jeg har en main metode, der kører en loop og kalder en

sum

metode, der bruger

add

for at opsummere to tilfældigt genererede vektorer. Sløjfen er der for at få koden varm nok til at udløse just-in-time kompilering, randomiseringen er der, så værdier ikke profileres for at være effektivt konstante, og den separate sum metode er der for at skabe en pæn blok kode at se på, når man ser på, hvordan kode er kompileret.

jeg kompilerer og kører dette ved hjælp af GraalVM CE på Java 8 20.3.0 på macOS på AMD64. Jeg slukker for en optimering kaldet On-stack udskiftning, fordi denne optimering gør kompilering lidt mere kompliceret og sværere at forstå. Jeg bruger derefter Graals

dump

mulighed for at bede den om at dumpe sine mellemliggende repræsentationsdatastrukturer.

vi kan nu bruge Seafoam til at se på, hvordan kompilatoren forstår sum – metoden, lige før den kører escape analysis. Filen sum.bgv indeholder den datastruktur, som kompilatoren dumpede ud for os.

% seafoam sum.bgv:14 render

Hvad ser vi her? Denne graf er den måde, Graal forstår sum – metoden, mens den kompilerer den. Det er Java-kode, men fri for begrænsningerne i en tekstlig repræsentation. Operationer er repræsenteret som noder (bokse, diamanter og ovaler), og forholdet mellem operationer er repræsenteret som kanter (pilene). Den tykke røde pil betyder, at en operation skal ske før en anden. Den tyndere pil betyder, at output fra operationen bruges som input til en anden operation.

vi sagde, at programmet blev befriet fra begrænsningerne i en tekstlig repræsentation. Se for eksempel på tilføjelsesoperationen i node 14. Vi ved, at det skal ske, når vi indlæser de to værdier fra de to x felter, og før vi gemmer værdien i feltet x i node 19, Men vi er ligeglade med, om det sker før eller efter de to y felter er indlæst. I Java tekstkildekode er alt skrevet i en lineær rækkefølge. Grafen slapper af denne begrænsning og koder kun de begrænsninger, som Java-Sprogspecifikationen faktisk kræver. Kompilatoren er derefter fri til at vælge den endelige ordre, alt kører ind.

når vi læser denne graf, kan vi se, at vi opretter en ny Vector, indlæser derefter de to inputobjekter’ x og y felter, Tilføj dem sammen og gem dem derefter i den nye Vector, vi oprettede, før vi returnerede den. Der er nogle ekstra detaljer i grafen, såsom null check, den endelige feltbarriere og mere, fordi dette er en rigtig kompilatorgraf, men vi ignorerer dem for denne artikel for at holde den kort.

den vigtigste ting at se her nu er, at der er et bestemt punkt, hvor det nye Vector objekt oprettes.

grundlæggende skalar udskiftning

lad os se på den samme metode lige efter escape analyse og skalar udskiftning af aggregater har kørt.

% seafoam sum.bgv:15 render

nu er grafen blevet endnu mere afslappet fra, hvordan den ser ud i teksten. I stedet for en New Vector operation har vi nu nedbrudt den til en generisk operation for at allokere et objekt og tage værdien af felterne i det objekt. Der er ingen StoreField længere her.

i denne særlige metode har dette ikke opnået noget nyttigt – grafen er blevet afslappet, men den afslørede ikke nogen virkelig nyttige optimeringer. Det skyldes, at det eneste objekt, vi tildelte, virkelig skal tildeles, fordi det forlader metoden. Flugtanalysen er kørt, men objektet slap væk, så der var ingen skalar udskiftning af aggregater.

for at tage dette videre, lad os se på en metode, der opsummerer tre Vector objekter.

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

grafen før flugtanalyse og skalar udskiftning af aggregater har samme struktur som den foregående metode. Vi har to New Vector operationer. Resultatet af a.add(b) skrives ind i det første nye objekt og læses derefter igen for det efterfølgende .add(c). Vi kan se, hvordan dette er spildt – mellemobjektet er aldrig synligt uden for kompileringsenheden, fordi det ikke er gemt eller passeret overalt – så hvorfor allokere det og hvorfor gemme felter i det, som vi lige straks læser op igen?

hvis vi ser på grafen efter flugtanalyse og skalær udskiftning af aggregater, ser vi, at mellemproduktet Vector er blevet fjernet helt. Der er kun en Alloc, ikke to. Aggregatet af det mellemliggende objekts felter er blevet erstattet med de skalære værdier af kanter, der direkte forbinder producenten og forbrugeren, uden at lave et mellemprodukt StoreField og derefter LoadField.

effektiviteten af skalar udskiftning

et par flere eksempler vil vise, hvordan denne optimering er lidt mere kraftfuld end folk ofte antager.

hvis vi opsummerer en række Vector objekter, vil vi logisk oprette en Vector pr.

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

denne graf er nu ret kompliceret, men nøglepunktet er, at du kan se en New Vector operation inde i sløjfen (inde i cirklen dannet af tykke røde pile.)

efter delvis flugtanalyse og skalar udskiftning af aggregater kører der nu ingen New Vector inde i sløjfen. Der er en enkelt tildeling i slutningen for den endelige Vector, der returneres, og værdierne for x og y er opbygget ved at akkumulere værdier (de små sløjfer omkring knudepunkter 33 og 92 og knudepunkter 36 og 93.) Dette betyder, at der ikke længere tildeles nogen hukommelse i den indre sløjfe af denne metode.

nogle gange taler folk om objekter, der ikke undslipper en kompileringsenhed, der tildeles på stakken. Her er hvorfor det er en misforståelse. Denne metode opsummerer to Vector objekter, men returnerer kun x komponenten.

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

før escape analysis kører, ser denne metode nøjagtigt ud som den oprindelige sum, undtagen feltet x indlæses og returneres derefter. Feltet y gemmes, men bruges aldrig, og det mellemliggende Vector slipper ikke for kompileringsenheden.

efter flugtanalyse og skalær udskiftning af aggregater kan vi se et vigtigt punkt at bemærke – efter at objektet blev erstattet med skalarer, var der ingen forbruger af y – værdien, så koden til at generere den havde intet at forbinde den til grafen, og så blev den fjernet.

hvis vi bogstaveligt talt tildelte objektet på stakken og lagrede objektet i samme format bare i stackhukommelse snarere end heap-hukommelse, ville vi stadig være nødt til at generere den mellemliggende y værdi. Vi tildeler ikke objektet nogen steder – vi har erstattet det med dataforløbskanter i stedet.

Bemærk, at stakallokering af objekter virkelig er en ting, og det foreslås til standard HotSpot og C2, men det er til et lidt andet formål, som vi ikke vil gå ind på her for enkelhed.

sammenligning med manuel optimering

vil du omskrive nogle af disse metoder til at akkumulere x og y i lokale variabler og ikke oprette mellemliggende Vector objekter? For eksempel kan du omskrive sum over en række Vector objekter som dette:

denne graf er faktisk mere effektiv end grafen for vores sum med mellemliggende Vector objekter før flugtanalyse. Der er ingen tildeling inde i løkken.

men hvis vi ser tilbage på vores tidligere sum loop med mellemliggende Vector objekter efter escape analyse og skalar udskiftning af aggregater, ser de stort set det samme ud. Der var ingen fordel ved at omskrive denne metode fra versionen på højt niveau med enkle mellemliggende Vector objekter til den manuelt optimerede version.

(ja faktisk er der måske – den manuelt optimerede version er hurtigere at kompilere og kører hurtigere, mens den fortolkes, indtil den er kompileret.)

delvis flugtanalyse

noget, som Graal kan gøre, som C2 ikke kan, og en vigtig fordel ved GraalVM, er delvis flugtanalyse. I stedet for at bestemme en binær værdi af, om et objekt slipper ud af kompileringsenheden eller ej, kan dette bestemme, hvilke grene et objekt slipper ud af det, og flytte tildeling af objektet til kun de grene, hvor det slipper ud.

denne konstruerede metode opsummerer to Vector objekter, og derefter baseret på en betingelse s passerer den enten som en parameter til en anden metode kaldet blackhole, som får den til at undslippe, eller den tilføjer en tredje vektor og returnerer den derefter.

mellemproduktet Vector gemt i x undslipper på den første gren, men ikke den anden.

vi forhindrer blackholei at blive indbygget ved at specificere -XX:CompileCommand=dontinline,Vector.blackhole.

før delvis flugtanalyse kører, kan vi se New Vector for x køres for begge grene.

efter delvis flugtanalyse og skalar udskiftning af aggregater er mellemproduktet New Vector gået. I stedet for på den gren, hvor den undslipper, har vi Alloc objektet, som refererer til de værdier, det skal have af x og y, og på den anden gren, hvor objektet ikke undslipper værdierne for x og y bruges bare direkte.

tildelingen er kun flyttet til den filial, hvor den faktisk er nødvendig.

forhåbentlig hjælper Alt dig med at forstå, hvad escape analyse og skalar udskiftning af aggregater er ved at se det arbejde i praksis. Jeg håber også, det viser dig, at det ikke rigtig er stakallokering og faktisk er noget mere kraftfuldt end det, og at det viser dig, hvad ekstra GraalVM-kompilatoren kan gøre for dig.

mere information

Graals algoritme til delvis flugtanalyse er beskrevet i delvis Flugtanalyse og skalar erstatning for Java.

jeg har skrevet mere om disse compiler grafer og hvordan man læser dem i forståelse grundlæggende Graal grafer.

forfatter: Chris Seaton

Chris er forsker (Senior Staff Engineer) hos Shopify, hvor han arbejder på Ruby programmeringssprog, og en besøgende ved University of Manchester.

han var tidligere forskningschef hos Oracle Labs Virtual Machine Research Group, hvor han ledede TruffleRuby-implementeringen af Ruby og arbejdede på andre sprog-og virtuelle maskinprojekter. Før dette afsluttede han en ph.d. i Manchester, hvor han undersøgte programmeringssprog og uregelmæssig parallelisme, og en Meng ved University of Bristol om sprog med foranderlig syntaks og semantik.

i sin fritid er han Skvadronleder for Cheshire Yeomanry eskadrille af Dronningens egen Yeomanry, Cheshires historiske reserve lys kavaleri eskadrille.

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.