High-performance garbage collection voor C++

Omdat de C++ objectgraph rondom de DOM sterk verstrengeld is met JavaScript-objecten, is het Chromium-team een paar jaar geleden overgestapt op een garbage collector genaamd Oilpan voor het beheer van dit type geheugen. Oilpan is een garbage collector geschreven in C++ voor het beheren van C++-geheugen. Deze kan worden verbonden met V8 via cross-component tracing, waarbij de verstrengelde C++/JavaScript objectgraph als één heap wordt behandeld.

Dit bericht is de eerste in een serie blogposts over Oilpan, waarin een overzicht wordt gegeven van de kernprincipes van Oilpan en de bijbehorende C++ API's. In dit artikel behandelen we enkele van de ondersteunde functies, leggen we uit hoe deze interageren met verschillende subsystemen van de garbage collector, en duiken we diep in het gelijktijdig terugwinnen van objecten in de sweeper.

Het meest opwindende is dat Oilpan momenteel is geïmplementeerd in Blink, maar wordt verplaatst naar V8 in de vorm van een garbage collection-bibliotheek. Het doel is om C++ garbage collection gemakkelijk beschikbaar te maken voor alle V8-embedders en C++-ontwikkelaars in het algemeen.

Achtergrond

Oilpan implementeert een Mark-Sweep garbage collector, waarbij de garbage collection is opgesplitst in twee fasen: marking (markeren), waarbij de beheerde heap wordt gescand op levende objecten, en sweeping (vegen), waarbij dode objecten op de beheerde heap worden teruggewonnen.

Het scannen van alle objecten naar levende objecten kan worden gezien als een graafdoorloop (graph traversal), waarbij objecten de knopen zijn en pointers tussen objecten de zijden. De doorloop begint bij de roots: registers, de native executiestack (hierna simpelweg 'stack' genoemd) en andere globalen.

C++ verschilt in dit opzicht niet van JavaScript. In tegenstelling tot JavaScript zijn C++-objecten echter statisch getypeerd en kunnen ze hun representatie tijdens runtime niet veranderen. C++-objecten die via Oilpan worden beheerd, maken gebruik van dit feit en bieden een beschrijving van pointers naar andere objecten (zijden in de graaf) via het visitor pattern. Het basispatroon voor het beschrijven van Oilpan-objecten is als volgt:

class LinkedNode final : public GarbageCollected<LinkedNode> {
public:
  LinkedNode(LinkedNode* next, int value) : next_(next), value_(value) {}
  void Trace(Visitor* visitor) const {
    visitor->Trace(next_);
  }
private:
  Member<LinkedNode> next_;
  int value_;
};

LinkedNode* CreateNodes() {
  LinkedNode* first_node = MakeGarbageCollected<LinkedNode>(nullptr, 1);
  LinkedNode* second_node = MakeGarbageCollected<LinkedNode>(first_node, 2);
  return second_node;
}

In het bovenstaande voorbeeld wordt LinkedNode beheerd door Oilpan, zoals aangegeven door de overerving van GarbageCollected<LinkedNode>. Wanneer de garbage collector een object verwerkt, ontdekt deze uitgaande pointers door de Trace-methode van het object aan te roepen. Het type Member is een smart pointer die syntactisch lijkt op bijvoorbeeld std::shared_ptr; deze wordt door Oilpan geleverd en gebruikt om een consistente staat te behouden tijdens het doorlopen van de graaf tijdens het markeren. Hierdoor weet Oilpan precies waar pointers zich bevinden in de beheerde objecten.

Het is mogelijk dat lezers zich zorgen maken dat firstnode en secondnode in het voorbeeld als ruwe C++-pointers op de stack worden bewaard. Oilpan voegt geen abstracties toe voor het werken met de stack, maar vertrouwt volledig op conservative stack scanning om pointers naar de beheerde heap te vinden bij het verwerken van de roots. Dit werkt door de stack woord voor woord te doorlopen en deze woorden te interpreteren als pointers naar de beheerde heap. Dit betekent dat Oilpan geen prestatiebelemmering veroorzaakt bij het benaderen van stack-gealloceerde objecten. In plaats daarvan wordt de kost verplaatst naar het moment van garbage collection, wanneer de stack conservatief wordt gescand. Oilpan, zoals geïntegreerd in de renderer, probeert garbage collection uit te stellen tot een staat is bereikt waarin gegarandeerd kan worden dat er geen relevante stack aanwezig is. Aangezien het web event-based is en de executie wordt aangestuurd door het verwerken van taken in event-loops, zijn dergelijke kansen talrijk.

Oilpan wordt gebruikt in Blink, wat een grote C++-codebase is met veel volwassen code. Daarom ondersteunt het ook:

• Meervoudige overerving via mixins en referenties naar dergelijke mixins (interior pointers).
• Het triggeren van garbage collection tijdens het uitvoeren van constructoren.
• Het in leven houden van objecten vanuit niet-beheerd geheugen via Persistent smart pointers, die als roots worden behandeld.
• Collecties die zowel sequentiële (bijv. vector) als associatieve (bijv. set en map) containers omvatten, inclusief compactie van de onderliggende collectiegegevens.
• Zwakke referenties (weak references), zwakke callbacks en ephemerons.
• Finalizer-callbacks die worden uitgevoerd voordat individuele objecten worden teruggewonnen.

Sweeping voor C++

In dit artikel gaan we ervan uit dat de markeerfase is voltooid en Oilpan alle bereikbare objecten heeft ontdekt met behulp van hun Trace-methoden. Alle bereikbare objecten hebben nu hun mark bit ingesteld.

Sweeping is de fase waarin dode objecten (die tijdens het markeren onbereikbaar waren) worden teruggewonnen en hun onderliggende geheugen wordt teruggegeven aan het besturingssysteem of beschikbaar wordt gemaakt voor volgende allocaties. Hieronder leggen we uit hoe de sweeper van Oilpan werkt, zowel vanuit het perspectief van gebruik en beperkingen als de manier waarop een hoge doorvoer bij het terugwinnen wordt behaald.

De sweeper vindt dode objecten door het heapgeheugen te doorlopen en de mark bits te controleren. Om de C++-semantiek te behouden, moet de sweeper de destructor van elk dood object aanroepen voordat het geheugen wordt vrijgegeven. Niet-triviale destructoren worden geïmplementeerd als finalizers.

Vanuit het perspectief van de programmeur is er geen gedefinieerde volgorde waarin destructoren worden uitgevoerd, aangezien de iteratie die door de sweeper wordt gebruikt geen rekening houdt met de volgorde van constructie. Dit brengt de beperking met zich mee dat finalizers geen andere objecten op de heap mogen aanraken. Dit is een veelvoorkomende uitdaging bij het schrijven van gebruikerscode die een specifieke volgorde van finalisatie vereist, aangezien beheerde talen (zoals Java) over het algemeen geen volgorde in hun finalisatie-semantiek ondersteunen. Oilpan maakt gebruik van een Clang-plugin die statisch verifieert dat er geen heap-objecten worden benaderd tijdens de destructie van een object:

class GCed : public GarbageCollected<GCed> {
public:
  void DoSomething();
  void Trace(Visitor* visitor) {
    visitor->Trace(other_);
  }
  ~GCed() {
    other_->DoSomething();  // fout: Finalizer '~GCed' benadert
                           // potentieel reeds gefinaliseerde field 'other_'.
  }
private:
  Member<GCed> other_;
};

Voor de nieuwsgierigen: Oilpan biedt pre-finalization callbacks voor complexe use-cases waarbij toegang tot de heap vereist is voordat objecten worden vernietigd. Dergelijke callbacks veroorzaken echter meer overhead per garbage collection-cyclus dan destructoren en worden in Blink slechts spaarzaam gebruikt.

Incrementele en concurrente sweeping

Nu we de beperkingen van destructoren in een beheerde C++-omgeving hebben besproken, kijken we naar hoe Oilpan de sweeping-fase implementeert en optimaliseert.

Het is belangrijk om te onthouden hoe programma's op het web worden uitgevoerd. Elke executie, zoals JavaScript-programma's maar ook garbage collection, wordt vanaf de hoofdthread aangestuurd door taken in een event-loop te distribueren. De renderer ondersteunt, net als andere applicatieomgevingen, achtergrondtaken die gelijktijdig met de hoofdthread draaien om werk op de hoofdthread te ondersteunen.

In het begin implementeerde Oilpan een stop-the-world sweeping, die draaide als onderdeel van de finalisatiepauze van de garbage collection en de uitvoering van de applicatie op de hoofdthread onderbrak.

Voor applicaties met soft real-time beperkingen is latentie de bepalende factor bij garbage collection. Stop-the-world sweeping kan aanzienlijke pauzes veroorzaken, wat resulteert in voor de gebruiker zichtbare latentie. Om dit te verminderen, werd sweeping incrementeel gemaakt.

Bij de incrementele aanpak wordt sweeping opgesplitst en gedelegeerd aan extra taken op de hoofdthread. In het beste geval worden deze taken volledig in idle time uitgevoerd, waardoor interferentie met de reguliere applicatie-executie wordt voorkomen. Intern verdeelt de sweeper het werk in kleinere eenheden op basis van het concept 'pagina's'. Pagina's kunnen zich in twee interessante staten bevinden: to-be-swept pagina's die de sweeper nog moet verwerken, en already-swept pagina's die al zijn verwerkt. Allocatie houdt alleen rekening met already-swept pagina's en vult lokale allocatiebuffers (LAB's) aan vanuit free lists die een lijst van beschikbaar geheugen bijhouden. Om geheugen uit een free list te halen, probeert de applicatie eerst geheugen te vinden in already-swept pagina's, probeert vervolgens te helpen bij het verwerken van to-be-swept pagina's door het sweeping-algoritme in de allocatie te integreren, en vraagt pas nieuw geheugen aan bij het OS als er niets anders beschikbaar is.

Oilpan maakt al jaren gebruik van incrementele sweeping, maar naarmate applicaties en hun objectgraphs groter werden, begon sweeping invloed te hebben op de applicatieprestaties. Om dit te verbeteren, zijn we achtergrondtaken gaan gebruiken voor het gelijktijdig (concurrent) terugwinnen van geheugen. Er zijn twee basisinvarianten die worden gebruikt om data-races tussen achtergrondtaken van de sweeper en de applicatie die nieuwe objecten alloceert uit te sluiten:

1. De sweeper verwerkt alleen dood geheugen, dat per definitie niet bereikbaar is voor de applicatie.
2. De applicatie alloceert alleen op already-swept pagina's, die per definitie niet meer door de sweeper worden verwerkt.

Beide invarianten zorgen ervoor dat er geen strijd zou mogen zijn om het object en het geheugen. C++ vertrouwt echter sterk op destructoren, die zijn geïmplementeerd als finalizers. Oilpan dwingt af dat finalizers op de hoofdthread worden uitgevoerd om ontwikkelaars te helpen en data-races binnen de applicatiecode uit te sluiten. Om dit op te lossen, stelt Oilpan de object-finalisatie uit naar de hoofdthread. Concreet: telkens wanneer de concurrente sweeper een object tegenkomt met een finalizer (destructor), plaatst deze dit op een finalisatie-wachtrij. Deze wachtrij wordt verwerkt in een aparte finalisatiefase, die altijd wordt uitgevoerd op de hoofdthread waar ook de applicatie draait.

Omdat finalizers toegang kunnen vereisen tot alle gegevens van het object, wordt het toevoegen van het bijbehorende geheugen aan de free list uitgesteld tot na de uitvoering van de finalizer. Als er geen finalizers worden uitgevoerd, voegt de sweeper op de achtergrondthread het teruggewonnen geheugen onmiddellijk toe aan de free list.

Resultaten

Background sweeping is geïmplementeerd in Chrome M78. Ons benchmarking-framework voor echte scenario's laat een vermindering van de sweeping-tijd op de hoofdthread zien van 25%-50% (gemiddeld 42%).

De resterende tijd op de hoofdthread wordt besteed aan het uitvoeren van finalizers. Er wordt momenteel gewerkt aan het verminderen van finalizers voor objecttypes die zeer vaak worden aangemaakt in Blink. Het interessante is dat al deze optimalisaties in de applicatiecode worden gedaan, aangezien sweeping zich automatisch aanpast bij de afwezigheid van finalizers.

***

Geplaatst door Anton Bikineev, Omer Katz (@omerktz), en Michael Lippautz (@mlippautz), C++ memory whisperers.