Inline cachelagring
Inline-cachelagring är en optimeringsteknik som används av vissa språkkörningstider och som först utvecklades för Smalltalk . Målet med inline-cachelagring är att påskynda bindning av runtime-metoder genom att komma ihåg resultaten från en tidigare metodsökning direkt på anropsplatsen . Inline-cachelagring är särskilt användbar för dynamiskt typade språk där de flesta om inte all metodbindning sker under körning och där virtuella metodtabeller ofta inte kan användas.
Körtidsmetodbindning
Följande ECMAScript- funktion tar emot ett objekt, anropar dess toString-metod och visar resultaten på sidan som skriptet är inbäddat i.
function dump ( obj ) { dokument . skriv ( obj . toString ()); }
Eftersom typen av objekt inte är specificerad och på grund av potentiell metodöverbelastning är det omöjligt att i förväg bestämma vilken konkret implementering av toString-metoden som ska anropas. Istället måste en dynamisk sökning utföras under körning. I språkkörningstider som inte använder någon form av cachning, utförs denna uppslagning varje gång en metod anropas. Eftersom metoder kan definieras flera steg ner i arvskedjan kan en dynamisk uppslagning vara en dyr operation.
För att uppnå bättre prestanda använder många språkkörningar någon form av icke-inline cachning där resultaten av ett begränsat antal metoduppslagningar lagras i en associativ datastruktur. Detta kan öka prestandan avsevärt, förutsatt att de körda programmen är "cachevänliga" (dvs. det finns en begränsad uppsättning metoder som anropas ofta). Den här datastrukturen kallas vanligtvis den första nivåns metoduppslagscache .
Inline cachelagring
Konceptet med inline caching baseras på den empiriska observationen att de objekt som förekommer vid en viss anropsplats ofta är av samma typ. I dessa fall kan prestandan ökas avsevärt genom att lagra resultatet av en metoduppslag "inline", dvs direkt på samtalsplatsen. För att underlätta denna process tilldelas samtalsplatser olika tillstånd. Inledningsvis anses en samtalsplats vara "oinitialiserad". När väl språkkörtiden når en viss oinitierad anropsplats, utför den den dynamiska sökningen, lagrar resultatet på anropsplatsen och ändrar dess tillstånd till "monomorft". Om språkkörtiden når samma anropsplats igen, hämtar den den anropade från den och anropar den direkt utan att göra några fler uppslagningar. För att ta hänsyn till möjligheten att objekt av olika typer kan förekomma på samma anropsplats, måste språkkörningstiden också infoga skyddsvillkor i koden. Vanligast är att dessa infogas i inledningen av den som ringer snarare än på samtalsplatsen för att bättre utnyttja förutsägelse av gren och för att spara utrymme på grund av en kopia i ingressen jämfört med flera kopior på varje samtalsplats. Om en samtalsplats som är i det "monomorfa" tillståndet stöter på en annan typ än den förväntade, måste den ändra tillbaka till det "oinitierade" tillståndet och utföra en fullständig dynamisk uppslagning igen.
Den kanoniska implementeringen är en registerbelastning av en konstant följt av en anropsinstruktion. Det "oinitialiserade" tillståndet kallas bättre "okopplat". Registret laddas med meddelandeväljaren (vanligtvis adressen till något objekt) och anropet går till runtime-rutinen som kommer att slå upp meddelandet i klassen för den aktuella mottagaren, med hjälp av förstanivåmetodens uppslagscache ovan . Körtidsrutinen skriver sedan om instruktionerna, ändrar laddningsinstruktionen för att ladda registret med typen av den aktuella mottagaren, och anropsinstruktionen att anropa inledningen av målmetoden, nu "länkar" anropsplatsen till målmetoden . Utförandet fortsätter sedan omedelbart efter ingressen. En efterföljande exekvering kommer att anropa ingressen direkt. Ingressen härleder sedan typen av den aktuella mottagaren och jämför den med den i registret; om de är överens är mottagaren av samma typ och metoden fortsätter att utföras. Om inte, anropar inledningen igen körtiden och olika strategier är möjliga, en är att återlänka anropsplatsen för den nya mottagartypen.
Prestandavinsterna kommer från att behöva göra en typjämförelse, istället för åtminstone en typjämförelse och en väljarjämförelse för förstanivåmetodsökningscache, och från att använda ett direktanrop (som kommer att dra nytta av instruktionsförhämtning och pipelining) i motsats till det indirekta anropet i en metodsökning eller en vtable- utskick.
Monomorf inline-cachelagring
Om en viss anropsplats ofta ser olika typer av objekt, kan prestandafördelarna med inline-cachelagring lätt omintetgöras av den overhead som induceras av de frekventa förändringarna i tillståndet hos anropsplatsen. Följande exempel utgör ett värsta scenario för monomorfisk inline-cachelagring:
var värden = [ 1 , "a" , 2 , "b" , 3 , "c" , 4 , "d" ]; for ( var i i värden ) { dokument . skriv ( värden [ i ]. toString ()); }
Återigen anropas metoden toString på ett objekt vars typ inte är känd i förväg. Ännu viktigare är att typen av objekt ändras med varje iteration av den omgivande slingan. En naiv implementering av monomorf inline-cachelagring skulle därför ständigt gå igenom de "oinitierade" och "monomorfa" tillstånden. För att förhindra detta från att hända stödjer de flesta implementeringar av monomorfisk inline-cachelagring ett tredje tillstånd som ofta kallas det "megamorfa" tillståndet. Detta tillstånd inträds när en viss samtalsplats har sett ett förutbestämt antal olika typer. När en samtalsplats väl har gått in i det "megamorfa" tillståndet kommer den att bete sig precis som den gjorde i det "oinitierade" tillståndet med undantaget att den aldrig kommer att gå in i det "monomorfa" tillståndet igen (vissa implementeringar av monomorfisk inline-cachelagring kommer att ändras " megamorfa" anropswebbplatser tillbaka till att vara "oinitialiserade" efter att en viss tid har gått eller när en fullständig sophämtningscykel har utförts).
Polymorf inline-cachelagring
För att bättre hantera samtalswebbplatser som ofta ser ett begränsat antal olika typer, använder vissa språkkörningstider en teknik som kallas polymorf inline-caching. Med polymorf inline caching, när en samtalsplats som är i sitt "monomorfa" tillstånd ser sin andra typ, istället för att återgå till det "oinitialiserade" tillståndet, växlar den till ett nytt tillstånd som kallas "polymorft". En "polymorf" anropsplats bestämmer vilken av en begränsad uppsättning kända metoder som ska anropas baserat på den typ som den för närvarande presenteras med. Med andra ord, med polymorf inline-cachelagring, kan resultat för flera metoduppslagningar registreras på samma anropsplats. Eftersom varje samtalsplats i ett program potentiellt kan se varje typ i systemet, finns det vanligtvis en övre gräns för hur många uppslagsresultat som registreras på varje samtalsplats. När den övre gränsen har nåtts blir samtalsplatserna "megamorfa" och ingen mer inline cachning utförs.
Den kanoniska implementeringen är en hopptabell som består av en inledning som härleder typen av mottagare och en serie konstanta jämförelser och villkorade hopp som hoppar till koden som följer ingressen i den relevanta metoden för varje mottagartyp. Hopptabellen allokeras typiskt för en viss anropsplats när en monomorf anropsplats stöter på en annan typ. Hopptabellen kommer att ha en fast storlek och kunna växa, lägga till fall när nya typer påträffas upp till ett litet maximalt antal fall som 4, 6 eller 8. När den når sin maximala storlek exekvering för en ny mottagartyp kommer att "falla av" slutet och ange körtiden, vanligtvis för att utföra en metodsökning som börjar med metodcachen på första nivån.
Observationen att monomorfa och polymorfa inline-cacher tillsammans samlar in information om mottagartyp per anropsplats som en bieffekt av att optimera programexekveringen ledde till utvecklingen av adaptiv optimering i Self , där körtiden optimerar "hot spots" i program som använder typinformationen i inline-cacher för att vägleda spekulativa inlining-beslut.
Megamorfisk inline-cachelagring
Om en körningstid använder både monomorf och polymorf inline-cache, kommer i det stationära tillståndet de enda olänkade sändningarna som inträffar att vara de från sändningar som faller från ändarna av polymorfa inline-cacher. Eftersom sådana sändningar är långsamma kan det nu vara lönsamt att optimera dessa webbplatser. En megamorfisk inline-cache kan implementeras genom att skapa kod för att utföra en metodsökning på första nivån för en viss anropsplats. I det här schemat skapas en megamorf cache som är specifik för samtalsplatsens väljare när en sändning faller utanför slutet av en polymorf inline-cache (eller delas om en redan finns), och sändningsplatsen länkas om för att anropa den. Koden kan vara betydligt effektivare än en vanlig metoduppslagsprob på första nivån eftersom väljaren nu är en konstant, vilket minskar registertrycket, koden för uppslagningen och utskicket exekveras utan att anropa körtiden, och utskicket kan dra nytta av grenförutsägelse .
Empiriska mätningar visar att i stora Smalltalk-program förblir ungefär 1/3 av alla skickasajter i aktiva metoder olänkade, och av de återstående 2/3 är 90% monomorfa, 9% polymorfa och 1% (0,9%) megamorfa.