Articles

Seeing Escape Analysis Working

Posted on

du kanske har hört talas om en kompilatoranalysfas som heter escape analysis. Den informerar en optimering som kallas skalär ersättning av aggregat som tar bort onödig tilldelning av Java-objekt. Jag tycker att människor ofta har ett missförstånd om vad denna optimering verkligen gör och en undervärdering av vad den kan. Vi kan veta det bättre genom att se det fungera i praktiken.

Context

jag visar hur GraalVM-kompilatorn, som en del av GraalVM och konfigurerad för just-in-time-kompilering i värdkonfiguration, tillämpar escape-analys och skalär ersättning av aggregat. GraalVM-kompilatorn är kraftfullare i detta avseende än den vanligaste Just-in-time-kompilatorn som du förmodligen är van vid, C2 i HotSpot.

Observera att varje gång jag säger kompilator i den här artikeln betyder jag just-in-time-kompilering, så den typ av kompilering som händer vid körning i JVM. Jag menar inte javac kompilatorn.

jag ska visa hur kompilatorn förstår våra exempelprogram genom att titta på en av de datastrukturer som den använder under kompileringen, dess högre mellanliggande representation. Detta är en graf som fångar betydelsen av ett Java-program eftersom det optimeras och transformeras innan konvertering till maskinkod startar. Det låter förmodligen väldigt avancerat men jag tror att för de flesta med viss erfarenhet av Java är det faktiskt ganska lättillgängligt sätt att förstå vad kompilatorn gör.

denna mellanliggande representation skiljer sig från ett abstrakt syntaxträd, eller AST, som är en syntaktisk representation av texten i ditt program. Det skiljer sig också från ett samtalsdiagram, som bara berättar vilka metoder som kallar vilka andra metoder.

jag använder ett verktyg som heter Seafoam, från Shopifys språkimplementeringsteam, för att skapa diagram över datastrukturerna som dumpas ur Graal. Du kan också använda ett verktyg som heter Ideal Graph Visualizer från Oracle Labs.

terminologi

Escape-analys är en analysprocess. Det upptäcker om ett objekt är synligt utanför en kompileringsenhet (en kompileringsenhet är vanligtvis en metod plus andra metoder som är inlagda i den.) Ett objekt kan bli synligt utanför en kompileringsenhet genom att returneras, eller skickas som ett argument till en annan metod, eller skrivas till ett fält eller liknande.

skalär ersättning av aggregat använder resultatet av escape-analys och fungerar på objekt som inte undgår kompileringsenheten eller bara undviker den på vissa grenar. Den ersätter objekt (aggregat) med enkla värden (skalärer) som liknar lokala variabler. Vi får se detta mer konkret senare.

Objektallokering

vi arbetar med en enkel Vector klass som innehåller double x och y fält. Den har en konstruktör, getters och en add metod som returnerar ett nytt objekt som är detta Vector läggs till en annan.

jag har en main metod som kör en slinga och kallar en

sum

metod som använder

add

för att summera två slumpmässigt genererade vektorer. Slingan är där för att få koden tillräckligt varm för att utlösa Just-in-time-kompilering, randomiseringen är där så att värdena inte profileras för att vara effektivt konstanta, och den separata sum – metoden är där för att skapa ett snyggt kodblock att titta på när man tittar på hur kod sammanställs.

jag kompilerar och kör detta med GraalVM CE på Java 8 20.3.0 på macOS på AMD64. Jag stänger av en optimering som kallas on-stack replacement eftersom denna optimering gör kompileringen lite mer komplicerad och svårare att förstå. Jag använder sedan Graals

dump

alternativ för att be den att dumpa ut sina mellanliggande representationsdatastrukturer.

vi kan nu använda Seafoam för att titta på hur kompilatorn förstår metoden sum, precis innan den körs escape-analys. Filen sum.bgv innehåller datastrukturen som kompilatorn dumpade ut för oss.

% seafoam sum.bgv:14 render

Vad ser vi här? Denna graf är det sätt som Graal förstår metoden sum medan den sammanställer den. Det är Java-kod, men fri från begränsningarna i en textrepresentation. Operationerna representeras som noder (rutorna, diamanterna och ovalerna) och relationerna mellan operationerna representeras som kanter (pilarna). Den tjocka röda pilen betyder att en operation måste ske före en annan. Den tunnare pilen betyder att operationens utgång används som ingång till en annan operation.

vi sa att programmet befriades från begränsningarna i en textrepresentation. Titta på add-operationen i nod 14 till exempel. Vi vet att det måste hända när vi laddar de två värdena från de två x – fälten och innan vi lagrar värdet i fältet x i nod 19, Men vi bryr oss inte om det händer före eller efter att de två y – fälten laddas. I Java-textkällkod skrivs allt i en linjär ordning. Grafen slappnar av denna begränsning och kodar bara de begränsningar som Java-språkspecifikationen faktiskt kräver. Kompilatorn är då fri att välja den slutliga ordningen som allt går in.

när vi läser den här grafen kan vi se att vi skapar en ny Vector, sedan laddar de två inmatningsobjekten’ x och y fält, lägger till dem och lagrar dem sedan i den nya Vector vi skapade innan vi returnerade den. Det finns några extra detaljer i diagrammet, till exempel null – kontrollen, den slutliga fältbarriären och mer eftersom det här är en riktig kompilatorgraf, men vi ignorerar dem för den här artikeln för att hålla den kort.

det viktigaste att se här nu är att det finns en bestämd punkt där det nya Vector – objektet skapas.

grundläggande skalär ersättning

Låt oss titta på samma metod direkt efter att escape-analys och skalär ersättning av aggregat har körts.

% seafoam sum.bgv:15 render

nu har grafen blivit ännu mer avslappnad från hur den visas i text. Istället för en New Vector – operation har vi nu sönderdelat den i en generisk operation för att allokera ett objekt och ta värdet på fälten för det objektet. Det finns ingen StoreField längre här.

i den här metoden har detta inte uppnått något användbart – grafen har varit avslappnad men det avslöjade inte några riktigt användbara optimeringar. Det beror på att det enda objektet vi tilldelade verkligen behöver tilldelas eftersom det lämnar metoden. Escape-analysen har kört men objektet flydde så det fanns ingen skalär ersättning av aggregat.

för att ta detta vidare, Låt oss titta på en metod som summerar tre Vector objekt.

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

grafen före escape-analys och skalär ersättning av aggregat har samma struktur som den tidigare metoden. Vi har två New Vector operationer. Resultatet av a.add(b)skrivs in i det första nya objektet och läses sedan ut igen för den efterföljande .add(c). Vi kan se hur det här är slöseri – det mellanliggande objektet är aldrig synligt utanför kompileringsenheten eftersom det inte lagras eller skickas någonstans – så varför allokera det och varför lagra fält i det som vi bara läser omedelbart igen?

om vi tittar på grafen efter escape-analys och skalär ersättning av aggregat ser vi att mellanprodukten Vector har tagits bort helt. Det finns bara en Alloc, inte två. Summan av mellanobjektets fält har ersatts med skalära värden på kanter som direkt förbinder producenten och konsumenten, utan att göra en mellanliggande StoreField och sedan LoadField.

effektiviteten av skalär ersättning

några fler exempel visar hur denna optimering är lite kraftfullare än människor ofta antar.

om vi summerar en array med Vector objekt skapar vi logiskt en Vector per iteration.

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

denna graf är nu ganska komplicerad, men nyckelpunkten är att du kan se en New Vector – operation inuti slingan (inuti cirkeln som bildas av tjocka röda pilar.)

efter partiell flyktanalys och skalär ersättning av aggregat körs det nu ingen New Vector inuti slingan. Det finns en enda allokering i slutet för den slutliga Vector som returneras, och värdena för x och y byggs upp genom att ackumulera värden (de små slingorna runt noderna 33 och 92 och noderna 36 och 93.) Detta betyder att inget minne tilldelas längre i den inre slingan av denna metod.

ibland pratar människor om objekt som inte undgår en kompileringsenhet som tilldelas på stacken. Här är varför det är ett missförstånd. Denna metod summerar två Vector objekt men returnerar bara komponenten x.

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

innan escape-analysen körs ser den här metoden ut exakt som originalet sum, förutom att fältet x sedan laddas och returneras. Fältet y lagras men används aldrig, och mellanvärdet Vector undviker inte kompileringsenheten.

efter escape-analys och skalär ersättning av aggregat kan vi se en viktig punkt att notera – efter att objektet ersattes med skalärer fanns det ingen konsument av y – värdet, så koden för att generera den hade inget att ansluta den till grafen och så togs den bort.

om vi bokstavligen allokerade objektet på stacken, lagrade objektet i samma format bara i stackminne snarare än heapminne, skulle vi fortfarande behöva generera mellanvärdet y. Vi fördelar inte objektet någonstans-vi har istället ersatt det med dataflow edges.

Observera att stackallokering av objekt verkligen är en sak, och det föreslås för standard HotSpot och C2, men det är för ett något annat syfte som vi inte kommer att gå in här för enkelhet.

jämför med manuell optimering

skulle du skriva om några av dessa metoder för att ackumulera x och y i lokala variabler och inte skapa mellanliggande Vector objekt? Till exempel kan du skriva om sum över en array med Vector objekt så här:

denna graf är verkligen effektivare än grafen för vår summa med mellanliggande Vector objekt före flyktanalys. Det finns ingen fördelning inuti slingan.

men om vi ser tillbaka till vår tidigare sum loop med mellanliggande Vector objekt efter flyktanalys och skalär ersättning av aggregat, ser de i princip samma ut. Det fanns ingen fördel med att skriva om denna metod från högnivåversionen med enkla mellanliggande Vector – objekt till den manuellt optimerade versionen.

(ja faktiskt kanske finns det – den manuellt optimerade versionen är snabbare att kompilera och körs snabbare medan den tolkas tills den kompileras.)

partiell flyktanalys

något som Graal kan göra som C2 inte kan, och en viktig fördel med GraalVM, är partiell flyktanalys. Istället för att bestämma ett binärt värde om ett objekt flyr från kompileringsenheten eller inte, kan detta bestämma på vilka grenar ett objekt flyr från det och flytta allokering av objektet till endast de grenar där det flyr.

denna konstruerade metod summerar två Vector objekt, och sedan baserat på ett villkor s skickar det antingen det som en parameter till en annan metod som heter blackhole, vilket får den att fly, eller det lägger till en tredje vektor och returnerar sedan den.

mellanprodukten Vector lagrad i x flyr på den första grenen, men inte den andra.

vi förhindrar att blackhole infogas genom att ange -XX:CompileCommand=dontinline,Vector.blackhole.

innan partiell flyktanalys körs kan vi se New Vector för x körs för båda grenarna.

efter partiell flyktanalys och skalär ersättning av aggregat har mellanprodukten New Vector gått. Istället, på grenen där den flyr har vi Alloc – objektet, som refererar till värdena det borde ha av x och y, och på den andra grenen där objektet inte undviker värdena för x och y används bara direkt.

allokeringen har flyttats till endast den gren där den faktiskt behövs.

förhoppningsvis hjälper Allt dig att förstå vad flyktanalys och skalär ersättning av aggregat är genom att se det fungera i praktiken. Jag hoppas också att det visar dig att det inte är riktigt stackallokering och faktiskt är något kraftfullare än det, och att det visar dig vad Extra GraalVM-kompilatorn kan göra för dig.

mer information

Graals algoritm för partiell flyktanalys beskrivs i partiell Flyktanalys och skalär ersättning för Java.

jag har skrivit mer om dessa kompilatorgrafer och hur man läser dem för att förstå grundläggande Graalgrafer.

författare: Chris Seaton

Chris är forskare (Senior Staff Engineer) på Shopify, där han arbetar med Ruby programmeringsspråk och en besökare vid University of Manchester.

han var tidigare forskningschef vid Oracle Labs Virtual Machine Research Group, där han ledde truffleruby-implementeringen av Ruby och arbetade med andra språk-och virtuella maskinprojekt. Innan detta avslutade han en doktorsexamen vid Manchester där han forskat programmeringsspråk och oregelbunden parallellitet, och en MEng vid University of Bristol på språk med föränderlig syntax och semantik.

på sin fritid är han Skvadronledare för Cheshire Yeomanry squadron av drottningens egen Yeomanry, Cheshire ’ s historic reserve light cavalry squadron.

Lämna ett svar

Din e-postadress kommer inte publiceras.