Articles

Seeing Escape Analysis Working

Posted on

du har kanskje hørt om en kompilatoranalysefase kalt escape analysis. Det informerer en optimalisering kalt skalar erstatning av aggregater som fjerner unødvendig tildeling Av Java-objekter. Jeg finner at folk ofte har en misforståelse av hva denne optimaliseringen egentlig gjør og en underforståelse av hva den er i stand til. Vi kan vite det bedre ved å se det fungerer i praksis.

Kontekst

jeg skal vise hvordan GraalVM kompilatoren, som en del Av GraalVM og konfigurert for just-in-time kompilering i vert konfigurasjon, gjelder escape analyse og skalar erstatning av aggregater. GraalVM-kompilatoren er kraftigere i denne forbindelse enn den vanligste just-in-time-kompilatoren som Du sannsynligvis er vant Til, C2 I HotSpot.

Merk at hver gang jeg sier kompilator i denne artikkelen, betyr jeg just-in-time-kompilering, så den typen kompilering som skjer under kjøring i JVM. Jeg mener ikke javac kompilatoren.

jeg skal vise hvordan kompilatoren forstår våre eksempelprogrammer ved å se på en av datastrukturene den bruker under kompilering, dens høyere mellomliggende representasjon. Dette er en graf som fanger betydningen Av Et Java-program som det er optimalisert og forvandlet før konvertering til maskinkode starter. Det høres sannsynligvis veldig avansert, men jeg tror for de fleste med Litt Erfaring Med Java, det er faktisk ganske tilnærmet måte å forstå hva kompilatoren gjør.

denne mellomliggende representasjonen er forskjellig fra et abstrakt syntakstre, ELLER AST, som er en syntaktisk representasjon av teksten i programmet ditt. Det er også annerledes enn en samtalegraf, som bare forteller deg hvilke metoder som kaller hvilke andre metoder.

jeg skal bruke et verktøy kalt Seafoam, Fra Shopify språk implementering team, for å lage diagrammer av datastrukturer dumpet Ut Av Graal. Du kan også bruke et verktøy kalt Ideal Graph Visualizer Fra Oracle Labs.

Terminologi

Fluktanalyse er en analyseprosess. Det oppdager om et objekt er synlig utenfor en kompileringsenhet (en kompileringsenhet er vanligvis en metode pluss andre metoder innlagt i den. Et objekt kan bli synlig utenfor en kompileringsenhet ved å bli returnert, eller sendt som et argument til en annen metode, eller skrevet til et felt eller lignende.

Skalar erstatning av aggregater bruker resultatet av rømningsanalyse og arbeider med objekter som ikke unnslipper kompileringsenheten, eller bare unnslipper den på enkelte grener. Den erstatter objekter (aggregater) med enkle verdier (skalarer) som ligner på lokale variabler. Vi vil se dette mer konkret senere.

Objektallokering

vi arbeider med en enkel Vector klasse som inneholder double x og y felt. Den har en konstruktør, getters og en add metode som returnerer et nytt objekt som er dette Vector lagt til en annen.

jeg har en main metode som kjører en sløyfe og kaller en

sum

metode som bruker

add

for å summere to tilfeldig genererte vektorer. Sløyfen er der for å få koden varm nok til å utløse just-in-time-kompilering, randomiseringen er der slik at verdiene ikke profileres for å være effektivt konstant, og den separate sum – metoden er der for å lage en fin blokk med kode for å se på når man ser på hvordan koden er kompilert.

jeg skal kompilere og kjøre Dette ved Hjelp Av GraalVM CE På Java 8 20.3.0 på macOS PÅ AMD64. Jeg slår av en optimalisering kalt on-stack replacement fordi denne optimaliseringen gjør kompilering litt mer komplisert og vanskeligere å forstå. Jeg bruker Da Graals

dump

alternativ for å be Den om å dumpe sine mellomliggende representasjonsdatastrukturer.

Vi kan nå bruke Seafoam til å se på hvordan kompilatoren forstår sum – metoden, rett før den kjører rømningsanalyse. Filen sum.bgv inneholder datastrukturen som kompilatoren dumpet ut for oss.

% seafoam sum.bgv:14 render

Hva ser vi her? Denne grafen er Måten Graal forstår sum – metoden mens Den samler den. Det Er Java-kode, men fri for begrensningene i en tekstlig representasjon. Operasjoner er representert som noder (boksene, diamanter og ovaler) og forholdet mellom operasjoner er representert som kanter (pilene). Den tykke røde pilen betyr at en operasjon må skje før en annen. Den tynnere pilen betyr at utgangen av operasjonen brukes som inngang til en annen operasjon.

vi sa at programmet ble frigjort fra begrensningene i en tekstlig representasjon. Se på add-operasjonen i node 14 for eksempel. Vi vet at det må skje etter at vi har lastet de to verdiene fra de to x – feltene, og før vi lagrer verdien i feltet x i node 19, men vi bryr oss ikke om det skjer før eller etter at de to y – feltene er lastet. I Java tekstlig kildekode er alt skrevet i en lineær rekkefølge. Grafen slapper av denne begrensningen og koder bare de begrensningene Som Java – Språkspesifikasjonen faktisk krever. Kompilatoren er da fri til å velge den endelige bestillingen alt går inn.

Leser denne grafen, vi kan se at vi lager en ny Vector, last deretter inn de to inngangsobjektene’ x og y feltene, legg dem sammen og lagre dem i den nye Vector vi opprettet før du returnerte den. Det er noen ekstra detaljer i grafen, for eksempel null – sjekken, den endelige feltbarrieren og mer fordi dette er en ekte kompilatorgraf, men vi ignorerer dem for denne artikkelen for å holde den kort.

det viktigste å se her nå er at det er et klart punkt der det nye Vector objektet er opprettet.

Grunnleggende skalar erstatning

La oss se på samme metode rett etter rømningsanalyse og skalar erstatning av aggregater har kjørt.

% seafoam sum.bgv:15 render

nå har grafen blitt enda mer avslappet fra hvordan den vises i tekst. I stedet for en New Vector – operasjon har vi nå dekomponert den til en generisk operasjon for å tildele et objekt, og ta verdien av feltene til det objektet. Det er ingen StoreField lenger her.

i denne spesielle metoden har dette ikke oppnådd noe nyttig-grafen har blitt avslappet, men det avslørte ikke noen virkelig nyttige optimaliseringer. Det er fordi det eneste objektet vi tildelte virkelig trenger å bli tildelt fordi det forlater metoden. Rømningsanalysen har kjørt, men objektet rømte, så det var ingen skalar erstatning av aggregater.

for å ta dette videre, la oss se på en metode som summerer tre Vector objekter.

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

grafen før rømningsanalyse og skalar erstatning av aggregater har samme struktur som forrige metode. Vi har to New Vector operasjoner. Resultatet av a.add(b)skrives inn i det første nye objektet, og leses deretter ut igjen for den påfølgende .add(c). Vi kan se hvordan dette er sløsing – mellomobjektet er aldri synlig utenfor kompileringsenheten fordi det ikke er lagret eller sendt hvor som helst – så hvorfor allokere det og hvorfor lagre felt inn i det som vi bare umiddelbart leser ut igjen?

hvis vi ser på grafen etter rømningsanalyse og skalarutskifting av aggregater, ser vi at mellomproduktet Vector er fjernet helt. Det er bare en Alloc, ikke to. Aggregatet av mellomobjektets felt har blitt erstattet med skalarverdiene av kanter som direkte forbinder produsent og forbruker, uten å gjøre et mellomliggende StoreField og deretter LoadField.

effektiviteten av skalar erstatning

noen flere eksempler vil vise hvordan denne optimaliseringen er litt kraftigere enn folk ofte antar.

hvis vi summerer en rekke Vector objekter, vil vi logisk opprette en Vector per iterasjon.

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

denne grafen er nå ganske komplisert, men nøkkelpunktet er at du kan se en New Vector operasjon inne i løkken (inne i sirkelen dannet av tykke røde piler.)

etter delvis rømningsanalyse og skalar erstatning av aggregater kjører det nå ingen New Vector inne i sløyfen. Det er en enkelt tildeling på slutten for den endelige Vector som returneres, og verdiene for x og y bygges opp av akkumulerende verdier (de små sløyfer rundt noder 33 og 92, og noder 36 og 93.) Dette betyr at ingen minne er allokert lenger i den indre sløyfen til denne metoden.

noen ganger snakker folk om objekter som ikke unnslipper en kompileringsenhet som tildeles på stakken. Her er hvorfor det er en misforståelse. Denne metoden summerer to Vector objekter, men returnerer bare komponenten x.

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

før rømningsanalyse kjører, ser denne metoden ut akkurat som originalen sum, bortsett fra x – feltet lastes og returneres. Feltet y er lagret, men aldri brukt, og mellom Vector unnslipper ikke kompileringsenheten.

etter rømningsanalyse og skalarutskifting av aggregater kan vi se et viktig poeng å merke seg – etter at objektet ble erstattet med skalarer, var det ingen forbruker av y – verdien, så koden for å generere den hadde ingenting å koble den til grafen og så ble den fjernet.

hvis vi bokstavelig talt allokerer objektet på stakken, lagrer objektet i samme format bare i stack-minne i stedet for heap-minne, må vi fortsatt generere mellomliggende y – verdien . Vi tildeler ikke objektet hvor som helst – vi har erstattet det med dataflytkanter i stedet.

Merk at stakkallokering av objekter virkelig er en ting, og det blir foreslått for standard HotSpot Og C2, men det er for en litt annen hensikt som vi ikke vil gå inn på her for enkelhet.

Sammenlignet med manuell optimalisering

vil du skrive om noen av disse metodene for å samle x og y i lokale variabler og ikke opprette mellomliggende Vector objekter? For eksempel kan du omskrive sum over en rekke Vector objekter som dette:

denne grafen er faktisk mer effektiv enn grafen til summen vår med mellomliggende Vector objekter før rømningsanalyse. Det er ingen tildeling inne i sløyfen.

Men hvis vi ser tilbake til vår forrige sum loop med mellomliggende Vector objekter etter fluktanalyse og skalar erstatning av aggregater, ser de i utgangspunktet det samme ut. Det var ingen fordel å omskrive denne metoden fra høynivåversjonen med enkle mellomliggende Vector – objekter til den manuelt optimaliserte versjonen.

(Vel faktisk kanskje det er-den manuelt optimaliserte versjonen er raskere å kompilere og kjører raskere mens den tolkes til den er kompilert.)

Delvis fluktanalyse

Noe Som Graal kan gjøre Som C2 ikke kan, og en viktig fordel Med GraalVM, er delvis fluktanalyse. I stedet for å bestemme en binær verdi av om et objekt unnslipper kompileringsenheten eller ikke, kan dette bestemme hvilke grener et objekt unnslipper det, og flytte allokering av objektet til bare de grenene der det unnslipper.

denne konstruerte metoden summerer to Vector objekter, og deretter basert på en betingelse s sender den enten den som en parameter til en annen metode kalt blackhole, som får den til å unnslippe, eller den legger til en tredje vektor, og returnerer den deretter.

mellom Vector lagret i x unnslipper på den første grenen, men ikke den andre.

vi forhindrer blackhole fra å bli inlined ved å spesifisere -XX:CompileCommand=dontinline,Vector.blackhole.

Før delvis fluktanalyse kjører, kan vi se New Vector for x kjøres for begge grener.

etter delvis rømningsanalyse og skalar erstatning av aggregater har mellomproduktet New Vector gått. I stedet, på grenen der den unnslipper, har vi Alloc – objektet ,som refererer til verdiene den skal ha av x og y, og på den andre grenen der objektet ikke unnslipper verdiene for x og y brukes bare direkte.

tildelingen er flyttet til bare grenen der den faktisk er nødvendig.

Forhåpentligvis hjelper alt deg med å forstå hva rømningsanalyse og skalarutskifting av aggregater er ved å se at det fungerer i praksis. Også jeg håper det viser deg at det egentlig ikke er stakkallokering og faktisk er noe kraftigere enn Det, og at det viser deg hva Ekstra GraalVM-Kompilatoren kan gjøre for deg.

Mer informasjon

Graals algoritme for delvis rømningsanalyse er beskrevet I Delvis Rømningsanalyse og Skalar Erstatning For Java.

jeg har skrevet mer om disse kompilatorgrafene og hvordan du leser dem for Å Forstå Grunnleggende Graalgrafer.

Forfatter: Chris Seaton

Chris Er Forsker (Senior Stab Ingeniør) På Shopify, hvor han jobber På Ruby programmeringsspråk, Og En Besøkende Ved University Of Manchester.

Han var Tidligere Forskningsleder ved Oracle Labs Virtual Machine Research Group, hvor han ledet TruffleRuby-implementeringen Av Ruby, og jobbet med andre språk-og virtuelle maskinprosjekter. Før dette fullførte Han En Doktorgrad Ved Manchester hvor han forsket på programmeringsspråk og uregelmessig parallellisme, og en MEng ved University Of Bristol på språk med foranderlig syntaks og semantikk.

På fritiden er Han Skvadronleder For Cheshire Yeomanry squadron av Queen ‘ S Own Yeomanry, cheshires historic reserve light cavalry squadron.

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert.