GoSuda

Go-runtimens tekoppsbrygd som ingen får ta ifrån dig, GreenTea GC

By snowmerak views ...

Varför kommer ytterligare en ny GC?

Varför den nuvarande GC:n

Den nuvarande GC:n i Go kan beskrivas med följande begrepp.

  • concurrent tri-color mark and sweep
    • Den använder totalt tre färger (vit, grå, svart) för att spåra objektens tillstånd.
      • Vit: objekt som ännu inte har besökts
      • Grå: objekt som har besökts men vars barnobjekt inte alla har besökts
      • Svart: objekt vars alla barnobjekt har besökts
      • När traverseringen är klar samlas alla vita objekt in.
    • Den använder en Write Barrier för att skydda minne som skapas under GC:n.
      • Tiden för att slå på/av Write Barrier utgör en betydande del av den så kallade Stop-The-World (nedan STW).
    • Denna process utförs samtidigt (concurrent).
  • No Compaction
    • Go:s GC utför ingen kompaktering.
    • Minnesfragmentering kan uppstå.
      • Objekt på 32 KB eller mindre minimerar dock fragmenteringen genom att utnyttja den per-P-cache som Go:s minnesallokator (Allocator) använder.
  • Non-Generational
    • Go:s GC hanterar inte objekt generationsvis.
    • Alla objekt tillhör samma generation.
  • Escape Analysis
    • Go avgör genom Escape Analysis om ett objekt allokeras på heapen eller på stacken.
    • Grovt sett kan man säga att om en dangling pointer eller ett gränssnitt (interface) används, allokeras objektet på heapen.

Det viktiga

Go:s GC utför tri-color mark genom att traversera alla objekt från rötterna (roots). Denna process kan sammanfattas som en samtidig traverseringsalgoritm för en riktad graf med topologisk ordning. Men varje objekt finns troligen i olika minnesregioner. Konkret, låt oss anta följande:

  1. Det finns två minnesregioner som ligger ungefär 32 MB från varandra.
  2. I var och en av dessa minnesregioner är fem objekt allokerade.
    1. Objekt A, B och C finns i region 1.
    2. Objekt D och E finns i region 2.
  3. Referensordningen mellan objekten är A -> D -> B -> E -> C.
  4. När GC startar besöker den A, sedan D, sedan B, sedan E och sedan C.
  5. Eftersom A och D finns i olika minnesregioner måste man flytta sig mellan minnesregioner när man besöker A och sedan D.
  6. I denna process uppstår s.k. minneshoppskostnad (memory jump cost), t.ex. genom att byta minnesregion och fylla nya cache-linjer. En betydande del av applikationens CPU-tid kan komma att ägnas åt detta GC-arbete.
  7. Denna kostnad uppstår kontinuerligt under hela den tid GC:n pågår.

Så vad är problemet?

Detta beteende hos GC:n är ett verkligt problem i följande fall.

  • När antalet kärnor är stort och minnet är stort
    • Go:s GC utförs som standard samtidigt.
    • Men när minnesregionen är stor och objekten är spridda, söker flera kärnor samtidigt efter objekt i olika minnesutrymmen.
    • I detta fall kan minnesbandbredden bli en flaskhals om bussen mellan CPU och minne inte är tillräckligt bred.
    • Dessutom leder det fysiska avståndet till att varje sökning får en relativt stor fördröjning.
  • När det finns många små objekt
    • Om du driftar träd eller grafer med stort djup eller många barn i Go, måste GC traversera alla dessa objekt.
    • Om objekten är spridda över olika minnesregioner uppstår fördröjning på grund av det första skälet.
    • Dessutom, när det finns många små objekt måste GC traversera alla dessa, vilket gör att CPU-kärnorna under GC-körningen ägnar betydande resurser åt GC-arbete.

För att lösa dessa problem presenterade Golang-teamet GreenTea GC.

Du har inte längre tid att dricka mer grönt te

Vad tar det gröna teet?

Det tycks att teamet betraktade minneslokalitet (memory locality) som det område där den snabbaste lösningen på den befintliga GC:n kunde tillämpas. Det vill säga att minimera minneshopp genom att placera objekt nära varandra. Men man kan inte tvinga programmerare att följa ett visst kodmönster, och objektallokeringen är oförutsägbar beroende på arbetsflödet.

Kanske därför valde Golang-teamet metoden Memory Span.

Vad är en memory span?

En memory span är en relativt stor minnesregion som allokeras för att lagra små objekt. Den nya GC:n, kallad GreenTea GC, utför skräpinsamling på dessa memory spans. De detaljerade operationerna är nästan identiska med den traditionella Tri-Color Mark and Sweep.

GreenTea GC:s funktionssätt

Först allokerar GreenTea GC en memory span. Storleken är, som tidigare beskrivits, 8 KiB, vilket är en ganska stor storlek. Inom denna kan objekt upp till 512 bytes allokeras. Storleken på noderna i de träd eller grafer som nämnts som exempel, eller på strukturer som normalt flyttas till heapen, är svår att föreställa sig större än detta. Objekt på 512 bytes eller mindre staplas i denna memory span varje gång de flyttas till heapen, och när memory span:en är full allokeras en ny.

När GC inträffar köar GreenTea GC dessa memory spans och kontrollerar dem sekventiellt. I denna process använder GreenTea GC ett schemaläggningssystem som nästan liknar den befintliga GMP-modellen. Även områden som work stealing är implementerade. Hur som helst tar den worker som plockar en memory span från kön och kontrollerar objekten inom den tilldelade memory span:en. I denna process används Tri-Color Mark and Sweep på samma sätt.

Vilka fördelar finns?

Skillnaden jämfört med den befintliga GC:n är i stora drag en enda sak. Enheten för att utföra GC på en gång har ändrats från objekt till memory span. Därför har GC följande fördelar.

  • Minneslokalitet: eftersom objekten samlas i en memory span minimeras minneshopp vid traversering av objekt. Det innebär att CPU-cachen kan utnyttjas maximalt.
  • Förbättrad GC-prestanda: genom att utföra GC per memory span arbetar GC mer effektivt i en multikärnmiljö.
  • Optimerad minnesallokering: eftersom memory spans allokeras med fast storlek minskar overhead vid allokering av små objekt, och risken för fragmentering minskar. Detta ökar effektiviteten vid frigörande av minne.

Kort sagt innebär detta att vi från och med nu kan allokera objekt på 512 bytes eller mindre oftare och med lättare sinne.

Det finns dock vissa gynnsamma situationer även här.

  • Träd./grafstrukturer: när fan-out är hög och förändringar sker sällan
    • B+-träd, Trie, AST (Abstract Syntax Tree)
    • Cache-vänliga datastrukturer
  • Batchbearbetning: arbetsflöden med massallokering av små data
    • Många små objekt som skapas vid JSON-parsning
    • DAO-objekt från databasens resultatuppsättningar

I dessa fall kan GreenTea GC prestera bättre än den befintliga GC:n. Den tillämpas dock inte i alla fall, och särskilt när objekten är spridda över olika minnesregioner är det fortfarande svårt att förvänta sig en dramatisk prestandaförbättring.

Så

Golang-teamet verkar sannolikt ha för avsikt att fortsätta förbättra GC:n på lång sikt. Denna GreenTea GC kan ses som en mindre förändring inom ett begränsat område och ersätter inte den befintliga GC:n. Men GreenTea GC är ett intressant exempel som ger en glimt av de problem som Golang-teamet står inför eller förutser. Det är ett oväntat komplext problem, men det var imponerande att de försökte lösa det genom att lägga till ett relativt enkelt koncept. Personligen tycker jag att det är ett intressant exempel.

GreenTea GC är en experimentell funktion som introduceras från Go 1.25. Den kan aktiveras genom att använda miljövariabeln GOEXPERIMENT=greenteagc. Eftersom funktionen fortfarande är experimentell krävs omfattande testning innan den används i produktionsmiljö.

Referenser