Jank-Busters Teil Zwei: Orinoco

In einem früheren Blogpost haben wir das Problem von Rucklern vorgestellt, die durch Garbage Collection verursacht werden und ein flüssiges Surfen beeinträchtigen. In diesem Blogpost stellen wir drei Optimierungen vor, die die Grundlage für einen neuen Garbage Collector in V8 mit dem Codenamen Orinoco bilden. Orinoco basiert auf der Idee, dass die Implementierung eines überwiegend parallelen und gleichzeitig arbeitenden Garbage Collectors ohne strikte Generationengrenzen die Ruckler bei der Garbage Collection und den Speicherverbrauch reduziert, während gleichzeitig eine hohe Durchsatzrate erhalten bleibt. Statt Orinoco als separaten Garbage Collector hinter einem Flag zu implementieren, haben wir uns entschieden, die Funktionen von Orinoco schrittweise auf die V8 Hauptentwicklung einzuführen, um den Benutzern sofort Vorteile zu bieten. Die drei in diesem Beitrag diskutierten Funktionen sind paralleles Kompaktieren, parallele Verarbeitung des Remembered Sets und schwarze Allokation.

V8 implementiert einen generationalen Garbage Collector, bei dem Objekte innerhalb der jungen Generation, von der jungen zur alten Generation und innerhalb der alten Generation verschoben werden können. Das Verschieben von Objekten ist teuer, da der zugrunde liegende Speicher der Objekte an neue Orte kopiert und die Zeiger auf diese Objekte ebenfalls aktualisiert werden müssen. Abbildung 1 zeigt die Phasen und deren Ausführung vor Orinoco. Im Wesentlichen wurden die Objekte zunächst verschoben und anschließend die Zeiger zwischen diesen Objekten in sequenzieller Reihenfolge aktualisiert, was zu beobachtbaren Rucklern führte.

V8 unterteilt seinen Heap-Speicher in feste Größenabschnitte, sogenannte Pages, die entweder dem Speicherbereich der jungen oder der alten Generation zugeordnet werden. Objekte werden zunächst in der jungen Generation zugewiesen. Bei der Garbage Collection werden lebende Objekte innerhalb der jungen Generation einmal verschoben. Objekte, die eine weitere Garbage Collection überleben, werden in die alte Generation verschoben. Für beide Phasen, die wir zusammenfassend als Evakuierung der jungen Generation bezeichnen, parallelisieren wir das Kopieren des Speichers basierend auf Pages. In der jungen Generation beinhaltet das Verschieben von Objekten immer die Allokation von Speicher auf frischen Pages (und das Freigeben der alten Pages), wodurch ein kompaktes Speicherlayout entsteht. In der alten Generation erfolgt dieser Prozess auf etwas andere Weise, da tote Speicherbereiche unbrauchbare Lücken hinterlassen (oder Fragmentierung). Einige dieser Lücken können über Freispeicherlisten wiederverwendet werden, andere bleiben jedoch zurück und erfordern eine Kompaktierung, um lebende Objekte auf eine besser gepackte (möglicherweise neue) Page zu verschieben. Ähnlich wie in der jungen Generation wird dieser Prozess auf Seitenebene parallelisiert.

Da es keine Abhängigkeiten zwischen der Evakuierung der jungen Generation und der Kompaktierung der alten Generation gibt, führt Orinoco diese Phasen nun parallel aus, wie in Abbildung 2 gezeigt. Das Ergebnis dieser Verbesserungen ist eine Reduktion der Kompaktierungszeit um 75%, von ~7ms auf durchschnittlich unter 2ms.

Die zweite von Orinoco eingeführte Optimierung verbessert, wie die Garbage Collection Zeiger verfolgt. Wenn ein Objekt seinen Ort im Heap wechselt, muss der Garbage Collector alle Zeiger finden, die den alten Ort des verschobenen Objekts enthalten, und sie mit dem neuen Ort aktualisieren. Da das Durchlaufen des Heaps, um die Zeiger zu finden, sehr langsam wäre, verwendet V8 eine Datenstruktur namens remembered set, um alle interessanten Zeiger im Heap zu verfolgen. Ein Zeiger ist interessant, wenn er auf ein Objekt zeigt, das während der Garbage Collection verschoben werden könnte. Beispielsweise sind alle Zeiger von der alten Generation zur jungen Generation interessant, da sich Objekte der jungen Generation bei jeder Garbage Collection verschieben. Zeiger auf Objekte in stark fragmentierten Pages sind ebenfalls interessant, da diese Objekte während der Kompaktierung auf andere Pages verschoben werden.

Früher implementierte V8 sogenannte Remembered Sets als Arrays von Zeigeradressen oder Store Buffers. Es gab einen Store Buffer für die jungen Generationen und einen für jede der fragmentierten Seiten der alten Generation. Der Store Buffer einer Seite enthält die Adressen aller eingehenden Zeiger, wie in Abbildung 3 dargestellt. Einträge werden in einem Write Barrier, der Schreiboperationen im JavaScript-Code überwacht, in einen Store Buffer eingefügt. Dies kann zu doppelten Einträgen führen, da ein Store Buffer denselben Zeiger mehrfach enthalten kann und zwei verschiedene Store Buffers denselben Zeiger einschließen können. Doppelte Einträge erschweren die Parallelisierung der Zeigeraktualisierungsphase, da ein Datenrennen entstehen kann, wenn zwei Threads versuchen, denselben Zeiger gleichzeitig zu aktualisieren.

Orinoco beseitigt diese Komplexität, indem es das Remembered Set neu organisiert, um die Parallelisierung zu vereinfachen und sicherzustellen, dass Threads disjunkte Mengen von Zeigern zur Aktualisierung erhalten. Anstatt eingehende relevante Zeiger in einem Array zu speichern, speichert jetzt jede Seite die Offsets der relevanten Zeiger, die von dieser Seite stammen, in Buckets von Bitmaps, wie in Abbildung 4 gezeigt. Jeder Bucket ist entweder leer oder verweist auf eine Bitmap fester Länge. Ein Bit in der Bitmap entspricht einem Zeigeroffset in der Seite. Ist ein Bit gesetzt, ist der Zeiger relevant und befindet sich im Remembered Set. Mit dieser Datenstruktur können wir Zeigeraktualisierungen basierend auf Seiten parallelisieren. Das Fehlen doppelter Einträge und die dichte Darstellung von Zeigern ermöglichten es uns auch, komplexen Code zum Umgang mit einem Überlauf des Remembered Sets zu entfernen. In unserem lang laufenden Gmail-Benchmark reduzierte diese Änderung die maximale Pausenzeit der kompakten Speicherbereinigung um 45 % von 42 ms auf 23 ms.

Die dritte Optimierung, die Orinoco einführt, ist die Black Allocation, eine Verbesserung der Markierungsphase des Garbage Collectors. Black Allocation (in V8 5.1 eingeführt) ist eine Garbage-Collection-Technik, bei der alle Objekte, die in der alten Generation zugewiesen werden (z. B. vorgealterte Zuordnungen oder durch den Garbage Collector beförderte Objekte), sofort schwarz markiert werden, um sie als "lebendig" zu kennzeichnen. Die Intuition hinter der Black Allocation ist, dass Objekte, die in der alten Generation zugeordnet werden, wahrscheinlich langlebig sind. Daher sollten Objekte, die kürzlich in der alten Generation zugewiesen wurden, mindestens die nächste Garbage Collection der alten Generation überleben, andernfalls wurden sie fälschlicherweise befördert. Nachdem neu zugewiesene Objekte schwarz gefärbt wurden, wird der Garbage Collector sie nicht mehr besuchen. Wir beschleunigen das Färben schwarzer Objekte, indem wir sie auf schwarze Seiten zuweisen, auf denen alle Objekte standardmäßig schwarz sind. Ein weiterer Vorteil schwarzer Seiten ist, dass sie nicht gereinigt werden müssen, da alle darauf zugewiesenen Objekte (per Definition) lebendig sind. Black Allocation beschleunigt den inkrementellen Markierungsfortschritt, da die Markierungsarbeit durch neue Zuweisungen nicht ansteigt. Der Einfluss der Black Allocation zeigt sich deutlich im Octane Splay Benchmark, bei dem sich die Durchsatz- und Latenzwerte um etwa 30 % verbesserten, während etwa 20 % weniger Speicher benötigt wurden, dank des schnelleren Markierungsfortschritts und des insgesamt geringeren Aufwands für die Garbage Collection.

Wir planen, bald weitere Orinoco-Features einzuführen. Bleiben Sie gespannt, wir basteln noch!