GoSuda

Een kopje groene thee dat de Go-runtime je niet afneemt: GreenTea GC

By snowmerak views ...

Waarom komt er weer een nieuwe GC?

Waarom de bestaande GC

De huidige GC van Go kan als volgt worden beschreven.

  • concurrent tri-color mark and sweep
    • Er worden in totaal drie kleuren (wit, grijs, zwart) gebruikt om de toestand van objecten bij te houden.
      • Wit: objecten die nog niet zijn bezocht
      • Grijs: objecten die zijn bezocht maar waarvan niet alle kindobjecten zijn bezocht
      • Zwart: objecten waarvan alle kindobjecten zijn bezocht
      • Nadat het doorlopen is afgerond, worden alle witte objecten verzameld.
    • Er wordt een Write Barrier gebruikt om het geheugen dat tijdens de GC wordt aangemaakt te beschermen.
      • De tijd waarin de Write Barrier wordt in- en uitgeschakeld, vormt een aanzienlijk deel van de zogenaamde Stop-The-World (hierna STW).
    • Dit proces wordt concurrent uitgevoerd.
  • No Compaction
    • De GC van Go voert geen compactie uit.
    • Geheugenfragmentatie kan optreden.
      • Objecten van 32 KB of kleiner minimaliseren fragmentatie echter door gebruik te maken van de per-P cache van de geheugenallocator (Allocator) van Go.
  • Non-Generational
    • De GC van Go beheert objecten niet per generatie.
    • Alle objecten behoren tot dezelfde generatie.
  • Escape Analysis
    • Go bepaalt via Escape Analysis of een object op de heap of op de stack wordt toegewezen.
    • Grofweg kan men zeggen dat objecten op de heap worden toegewezen wanneer er sprake is van hangende pointers of het gebruik van interfaces.

Wat er echt toe doet

De GC van Go doorzoekt alle objecten vanaf de root en voert de driekleurenmarkering uit. Dit proces kan in één regel worden samengevat als topologische-sorteer-grafiek gelijktijdige doorzoekingsalgoritme. Elk object bevindt zich echter waarschijnlijk in een verschillend geheugengebied. Concreet gesteld:

  1. Stel dat er twee geheugengebieden zijn die ongeveer 32 MB van elkaar verwijderd liggen.
  2. In elk van deze twee geheugengebieden zijn vijf objecten toegewezen.
    1. Objecten A, B en C bevinden zich in gebied 1.
    2. Objecten D en E bevinden zich in gebied 2.
  3. De volgorde van de objectreferenties is A -> D -> B -> E -> C.
  4. Wanneer de GC start, bezoekt deze A, vervolgens D, B, E en tot slot C.
  5. Omdat A en D zich in verschillende geheugengebieden bevinden, moet bij het bezoeken van A en vervolgens D het geheugengebied worden gewisseld.
  6. Dit proces, waarbij het geheugengebied wordt gewisseld en nieuwe cachelijnen moeten worden geladen, veroorzaakt zogenaamde geheugensprongkosten. Een aanzienlijk deel van de CPU-tijd van de applicatie kan hierdoor aan GC-werk worden besteed.
  7. Deze kosten ontstaan voortdurend zolang de GC bezig is.

Wat is het probleem?

Het gedrag van deze GC is ronduit problematisch in de volgende gevallen.

  • Wanneer het aantal cores groot is en het geheugen omvangrijk is
    • De GC van Go wordt standaard concurrent uitgevoerd.
    • Wanneer het geheugengebied groot is en objecten verspreid liggen, doorzoeken meerdere cores tegelijkertijd objecten in verschillende geheugenruimten.
    • Als de bus tussen CPU en geheugen niet voldoende capaciteit heeft, kan de geheugenbandbreedte een bottleneck worden.
    • Omdat de fysieke afstand groot is, zal bovendien elke zoekactie relatief veel vertraging veroorzaken.
  • Wanneer er veel kleine objecten zijn
    • Als u bomen of grafen met grote diepte of veel kindobjecten in Go gebruikt, moet de GC al deze objecten doorzoeken.
    • Wanneer deze objecten verspreid liggen over verschillende geheugengebieden, ontstaat vertraging door de eerste reden.
    • Bovendien moet de GC, wanneer er veel kleine objecten zijn, al deze objecten doorzoeken, waardoor de CPU-cores tijdens de GC een aanzienlijke capaciteit aan de GC moeten besteden.

Om deze problemen op te lossen heeft het Golang-team GreenTea GC aangekondigd.

Je hebt geen tijd meer om nog meer groene thee te drinken

Wat neemt de groene thee weg

De snelste oplossing voor de bestaande GC lijkt te zijn gevonden in geheugenlokaliteit. Dat wil zeggen dat objecten dicht bij elkaar worden geplaatst om geheugensprongen te minimaliseren. Echter, de patronen van programmeurs die code schrijven kunnen niet worden afgedwongen, en de objectallocatie is afhankelijk van de workflow en daardoor niet voorspelbaar.

Het door het Golang-team gekozen middel is daarom waarschijnlijk de geheugenspan (Memory Span).

Wat is een geheugenspan?

Een geheugenspan is een relatief groot geheugengebied dat wordt toegewezen om kleine objecten in op te slaan. De nieuwe GC, GreenTea GC genoemd, voert garbage collection uit op deze geheugenspans. De gedetailleerde werking is vrijwel gelijk aan de bestaande Tri-Color Mark and Sweep.

Werking van GreenTea GC

Allereerst wijst GreenTea GC een geheugenspan toe. De grootte is, zoals eerder beschreven, een vrij ruime 8 KiB. Hierin kunnen objecten van maximaal 512 bytes worden toegewezen. Dit is zo ongeveer de grootte die knooppunten van de eerder genoemde bomen of grafen, of structuren die gewoonlijk naar de heap ontsnappen, niet snel zullen overschrijden. Objecten van 512 bytes of kleiner worden telkens wanneer ze naar de heap ontsnappen in deze geheugenspan opgeslagen, en wanneer deze geheugenspan vol is, wordt een nieuwe geheugenspan toegewezen.

Wanneer er een GC plaatsvindt, plaatst GreenTea GC deze geheugenspans in een wachtrij en controleert ze achtereenvolgens. Bij dit proces gebruikt GreenTea GC een planning die vrijwel gelijk is aan het bestaande GMP-model. Ook functies zoals work stealing zijn geïmplementeerd. In ieder geval haalt de worker die een geheugenspan uit de wachtrij haalt de objecten binnen de aan hem toegewezen geheugenspan na. Bij dit proces wordt op dezelfde manier Tri-Color Mark and Sweep gebruikt.

Wat zijn de voordelen?

Het verschil met de bestaande GC is in grote lijnen precies één ding: de eenheid waarop de GC in één keer wordt uitgevoerd, is veranderd van object naar geheugenspan. Hierdoor biedt de GC de volgende voordelen.

  • Geheugenlokaliteit: doordat objecten zich in een geheugenspan bevinden, worden geheugensprongen bij het doorzoeken van objecten geminimaliseerd. Dat wil zeggen dat de CPU-cache optimaal kan worden benut.
  • Verbetering van GC-prestaties: doordat de GC per geheugenspan wordt uitgevoerd, werkt de GC efficiënter in een multicore-omgeving.
  • Optimalisatie van geheugentoewijzing: geheugenspans worden met een vaste grootte toegewezen, waardoor de overhead van geheugentoewijzing bij kleine objecten afneemt en de kans op fragmentatie vermindert. Dit verhoogt de efficiëntie van het vrijgeven van geheugen.

Kort gezegd: vanaf nu kunnen we vaker en met een gerust hart objecten van 512 bytes of kleiner toewijzen.

Toch zijn er enkele situaties die relatief gunstig zijn.

  • Boom- en grafstructuren: situaties met een hoge fan-out die zelden worden gewijzigd
    • B+-bomen, Trie's, AST (Abstract Syntax Tree)
    • Cachevriendelijke datastructuren
  • Batchverwerking: workflows met grootschalige toewijzing van kleine gegevens
    • Veel kleine objecten die worden gegenereerd bij het parsen van JSON
    • DAO-objecten uit databaseresultaatsets

In deze gevallen kan GreenTea GC betere prestaties leveren dan de bestaande GC. Het is echter niet in alle gevallen van toepassing, en met name wanneer objecten verspreid liggen over verschillende geheugengebieden, is een dramatische prestatieverbetering nog steeds moeilijk te verwachten.

Dus

Het Golang-team lijkt van plan te zijn de GC op de lange termijn voortdurend te verbeteren. Deze GreenTea GC kan worden gezien als een kleine wijziging op beperkt gebied en vervangt de bestaande GC niet. GreenTea GC is echter een interessant voorbeeld waarin men een glimp kan opvangen van de problemen waarmee het Golang-team wordt geconfronteerd of die het verwacht. Het is verrassend complex probleem, maar de poging om het op te lossen door het toevoegen van een relatief eenvoudig concept was indrukwekkend. Persoonlijk vind ik het een interessant geval.

GreenTea GC is een experimentele functie die vanaf Go 1.25 wordt geïntroduceerd. Het kan worden ingeschakeld door de omgevingsvariabele GOEXPERIMENT=greenteagc te gebruiken. Aangezien deze functie nog experimenteel is, is grondige testing vereist voordat deze in een productieomgeving wordt gebruikt.

Referenties