GoSuda

En kop grøn te stjålet af Go-runtime, GreenTea GC

By snowmerak
views ...

Hvorfor endnu en ny GC?

Hvorfor den eksisterende GC?

Go's nuværende GC kan beskrives med følgende termer:

  • concurrent tri-color mark and sweep
    • Den anvender tre farver (hvid, grå, sort) til at spore objekters tilstand.
      • Hvid: Objekter der endnu ikke er besøgt
      • Grå: Objekter der er besøgt, men hvis børneobjekter ikke alle er besøgt
      • Sort: Objekter hvor alle børneobjekter er besøgt
      • Når gennemgangen er afsluttet, indsamles alle hvide objekter.
    • Den anvender Write Barrier til at beskytte nyoprettet hukommelse under GC.
      • Tiden det tager at slå Write Barrier til/fra udgør en betydelig del af det, der ofte kaldes Stop-The-World (herefter STW).
    • Denne proces udføres samtidigt.
  • No Compaction
    • Go's GC udfører ikke komprimering.
    • Hukommelsesfragmentering kan forekomme.
      • Dog minimeres fragmenteringen for objekter under 32kb ved at udnytte Go-sprogets hukommelsesallokators (Allocator) per-P cache.
  • Non-Generational
    • Go's GC administrerer ikke objekter efter generation.
    • Alle objekter tilhører den samme generation.
  • Escape Analysis
    • Go bestemmer gennem Escape Analysis, om et objekt skal allokeres på heapen eller stacken.
    • Groft sagt, hvis en hængende pointer eller et interface anvendes, kan det antages at blive allokeret på heapen.

Det vigtige er

Go's GC udforsker alle objekter fra roden og udfører en tre-farvet markering. Denne proces kan i én linje beskrives som en 'samtidig topologisk sorteringsgraf-traverseringsalgoritme'. Dog er der en høj sandsynlighed for, at hvert objekt befinder sig i forskellige hukommelsesområder. For at give et konkret eksempel:

  1. Antag at der er hukommelsesområder adskilt med cirka 32 MB.
  2. I disse to hukommelsesområder er der allokeret 5 objekter i hvert.
    1. Objekterne A, B, C er i område 1.
    2. Objekterne D, E er i område 2.
  3. Objekternes referenceorden er A -> D -> B -> E -> C.
  4. Når GC starter, besøges A, derefter D, så B, så E, og til sidst C.
  5. Da A og D befinder sig i forskellige hukommelsesområder, skal hukommelsesområdet skiftes under processen med at besøge A og D.
  6. Denne proces medfører en såkaldt hukommelsesspring-omkostning, herunder flytning af hukommelsesområder og udfyldning af nye cachelinjer. En betydelig del af den CPU-tid, applikationen bruger, kan blive allokeret til sådanne GC-opgaver.
  7. Denne omkostning opstår kontinuerligt under GC-processen.

Så hvad er problemet?

Denne GC-adfærd er yderst ufordelagtig i følgende tilfælde:

  • Når antallet af kerner er stort, og hukommelsen er stor
    • Go's GC udføres grundlæggende samtidigt.
    • Men hvis hukommelsesområdet er stort, og objekterne er spredt, vil flere kerner samtidigt søge efter objekter i forskellige hukommelsesområder.
    • Hvis bussen mellem CPU og hukommelse ikke er tilstrækkelig stor i denne proces, kan hukommelsesbåndbredden blive en flaskehals.
    • Desuden vil hver enkelt søgning, på grund af den fysiske afstand, medføre en relativt stor forsinkelse.
  • Når der er mange små objekter
    • Hvis I opererer en dyb eller en træ- eller grafstruktur med mange underordnede elementer i Go, skal GC udforske alle disse objekter.
    • Hvis objekterne er spredt i forskellige hukommelsesområder i denne proces, opstår der en forsinkelse på grund af den første årsag.
    • Desuden, hvis der er mange små objekter, skal GC udforske dem alle, hvilket betyder, at CPU-kerner vil allokere en betydelig mængde kapacitet til GC og arbejde under GC-udførelsen.

For at løse disse problemer har Golang-teamet lanceret GreenTea GC.

Du har ikke råd til mere grøn te

Hvad tager den grønne te fra dig?

Det område, der blev anset for at være det hurtigste at anvende en løsning på den eksisterende GC, var hukommelseslokalitet. Det vil sige at minimere hukommelsesspring ved at placere objekter tæt på hinanden. Dog kan programmørens kodningsmønstre ikke tvinges, og objektallokering kan ikke forudsiges ud fra arbejdsgangen.

Derfor har Golang-teamet valgt Memory Span.

Hvad er en Memory Span?

En Memory Span er et sted, hvor et relativt stort hukommelsesområde er allokeret til allokering af små objekter. Og den nye GC, kaldet GreenTea GC, udfører garbage collection på denne Memory Span. Den detaljerede funktion er næsten identisk med den eksisterende Tri-Color Mark and Sweep.

GreenTea GC's funktionalitet

Først allokerer GreenTea GC en Memory Span. Som tidligere nævnt er størrelsen 8 KiB, hvilket er en vis størrelse. Indenfor denne kan der allokeres objekter på op til 512 bytes. Dette svarer til størrelsen af noder i et træ eller en graf som eksempler, eller størrelsen af generelle strukturer, der undslipper til heapen, hvilket er en størrelse, der sjældent overskrides. Objekter under 512 bytes akkumuleres i denne Memory Span, hver gang de undslipper til heapen, og når denne Memory Span er fuld, allokeres en ny Memory Span.

Når GC opstår, placerer GreenTea GC denne Memory Span i en kø og inspicerer den sekventielt. Under denne proces anvender GreenTea GC en skedulering, der er næsten identisk med den eksisterende GMP-model. Implementering af Work Stealing er også til stede. Under alle omstændigheder trækker en arbejder, der trækker en Memory Span ud af køen, de interne objekter i den tildelte Memory Span. Under denne proces anvendes Tri-Color Mark and Sweep på samme måde.

Hvad er fordelene ved dette?

Forskellen mellem denne proces og den eksisterende GC er i det store og hele kun én: Enheden for GC-udførelse er ændret fra et objekt til en Memory Span. Dette giver GC følgende fordele:

  • Hukommelseslokalitet: Da objekter er samlet i en Memory Span, minimeres hukommelsesspring under objektudforskning. Det vil sige, at CPU-cachen kan udnyttes maksimalt.
  • Forbedret GC-ydeevne: Ved at udføre GC på Memory Span-niveau fungerer GC mere effektivt i et multi-core miljø.
  • Optimeret hukommelsesallokering: Da Memory Span er allokeret i faste størrelser, reduceres overhead ved hukommelsesallokering for små objekter, og sandsynligheden for fragmentering mindskes. Dette øger effektiviteten af hukommelsesfrigørelse.

Kort sagt kan vi nu allokere objekter under 512 bytes oftere og med større lethed.

Der er dog visse områder, hvor dette er fordelagtigt:

  • Træ-/grafstrukturer: Hvor fan-out er høj, og ændringer sjældent forekommer.
    • B+ træer, Trie'er, AST (Abstract Syntax Tree)
    • Cache-venlige datastrukturer
  • Batchbehandling: Arbejdsgange med massiv allokering af små data
    • Mange små objekter oprettet ved JSON-parsing
    • DAO-objekter fra databasesæt

I disse tilfælde kan GreenTea GC yde bedre end den eksisterende GC. Det gælder dog ikke i alle tilfælde, og især hvor objekter er spredt i forskellige hukommelsesområder, er det stadig svært at forvente en dramatisk ydelsesforbedring.

Konklusion

Golang-teamet ser ud til at have til hensigt at fortsætte med at forbedre GC på lang sigt. Denne GreenTea GC kan betragtes som en mindre ændring inden for et lille område og erstatter ikke den eksisterende GC. Men GreenTea GC fremstår som et interessant eksempel, der giver et indblik i de problemer, Golang-teamet står over for eller forventer. Det var også imponerende at se forsøget på at løse et overraskende komplekst problem med tilføjelsen af et relativt simpelt koncept. Personligt synes jeg, det er et interessant eksempel.

GreenTea GC er en eksperimentel funktion, der introduceres fra Go 1.25. Den kan aktiveres og bruges ved at anvende miljøvariablen GOEXPERIMENT=greenteagc. Da denne funktion stadig er eksperimentel, kræves der tilstrækkelig test, før den anvendes i produktionsmiljøer.

Referencer