GoSuda

Die Muße einer Tasse grünen Tees, die die Go-Laufzeitumgebung uns entziehen wird: GreenTea GC

By snowmerak views ...

Warum gibt es schon wieder einen neuen GC?

Warum der bisherige GC

Der aktuelle GC von Go lässt sich mit folgenden Begriffen beschreiben.

  • Concurrent Tri-Color Mark and Sweep
    • Er verwendet insgesamt drei Farben (Weiß, Grau, Schwarz), um den Zustand der Objekte zu verfolgen.
      • Weiß: Ein Objekt, das noch nicht besucht wurde
      • Grau: Ein Objekt, das besucht wurde, dessen Kindobjekte jedoch noch nicht alle besucht wurden
      • Schwarz: Ein Objekt, dessen Kindobjekte alle besucht wurden
      • Nach Abschluss des Durchlaufs werden alle weißen Objekte eingesammelt.
    • Er verwendet eine Write Barrier, um während der GC neu erzeugten Speicher zu schützen.
      • Die Zeit, in der die Write Barrier ein- und ausgeschaltet wird, macht einen erheblichen Teil des sogenannten Stop-The-World (im Folgenden STW) aus.
    • Dieser Prozess wird nebenläufig ausgeführt.
  • No Compaction
    • Der GC von Go führt keine Compaction durch.
    • Speicherfragmentierung kann auftreten.
      • Objekte mit höchstens 32 KB werden jedoch unter Nutzung des per-P-Caches des Speicherallokators (Allocator) von Go so verwaltet, dass die Fragmentierung minimiert wird.
  • Non-Generational
    • Der GC von Go verwaltet Objekte nicht generationenweise.
    • Alle Objekte gehören derselben Generation an.
  • Escape Analysis
    • Go entscheidet mithilfe der Escape Analysis, ob ein Objekt auf dem Heap oder auf dem Stack alloziert wird.
    • Vereinfacht gesagt kann man davon ausgehen, dass ein Objekt auf dem Heap alloziert wird, wenn es hängende Zeiger oder Interfaces verwendet.

Was wirklich wichtig ist

Der GC von Go durchsucht alle Objekte ausgehend von den Wurzeln und führt dabei die Tri-Color-Markierung durch. Dieser Prozess lässt sich in einem Satz als „nebenläufige Durchsuchung eines topologisch sortierten Graphen“ beschreiben. Allerdings befinden sich die einzelnen Objekte mit hoher Wahrscheinlichkeit in unterschiedlichen Speicherbereichen. Vereinfacht gesagt:

  1. Angenommen, es gibt zwei Speicherbereiche, die etwa 32 MB voneinander entfernt liegen.
  2. In diesen beiden Speicherbereichen sind jeweils fünf Objekte alloziert.
    1. Die Objekte A, B und C befinden sich in Bereich 1.
    2. Die Objekte D und E befinden sich in Bereich 2.
  3. Die Reihenfolge der Referenzen lautet A -> D -> B -> E -> C.
  4. Sobald der GC startet, besucht er zuerst A, dann D, dann B, dann E und schließlich C.
  5. Da A und D in unterschiedlichen Speicherbereichen liegen, muss beim Besuch von A und anschließend D der Speicherbereich gewechselt werden.
  6. Bei diesem Vorgang entstehen die sogenannten Speichersprungkosten, da der Speicherbereich gewechselt und neue Cache-Lines geladen werden müssen. Ein erheblicher Teil der CPU-Zeit der Anwendung kann dadurch für diese GC-Arbeit aufgewendet werden.
  7. Diese Kosten fallen während der gesamten Laufzeit des GC kontinuierlich an.

Was ist daran das Problem?

Dieses Verhalten des GC ist in folgenden Fällen besonders ungünstig.

  • Viele Kerne und großer Speicher
    • Der GC von Go wird standardmäßig nebenläufig ausgeführt.
    • Wenn der Speicherbereich jedoch weitläufig ist und die Objekte verstreut liegen, durchsuchen mehrere Kerne gleichzeitig Objekte in verschiedenen Speicherbereichen.
    • Ist der Bus zwischen CPU und Speicher nicht ausreichend breit, kann die Speicherbandbreite zum Engpass werden.
    • Da die physische Entfernung zudem groß ist, kann jeder einzelne Zugriff eine vergleichsweise große Verzögerung verursachen.
  • Viele kleine Objekte
    • Wenn Sie Bäume oder Graphen mit großer Tiefe oder vielen Kindknoten in Go betreiben, muss der GC all diese Objekte durchsuchen.
    • Liegen die Objekte dabei in unterschiedlichen Speicherbereichen verteilt, entsteht aufgrund des ersten Grundes eine Verzögerung.
    • Außerdem muss der GC bei vielen kleinen Objekten alle diese Objekte durchsuchen, sodass während der GC-Ausführung eine beträchtliche Menge an CPU-Kapazität für den GC aufgewendet wird.

Um diese Probleme zu lösen, hat das Golang-Team GreenTea GC vorgestellt.

Du hast keine Zeit mehr für weiteren Grüntee

Was dem Grüntee die Zeit raubt

Als Bereich, in dem sich die schnellste Lösung des bisherigen GC anwenden lässt, scheint das Team die Speicherlokalität betrachtet zu haben. Das heißt, Objekte sollen nahe beieinander liegen, um Speichersprünge zu minimieren. Allerdings lässt sich das Muster der Programmierer, die den Code schreiben, nicht erzwingen, und die Objektallokation ist je nach Workflow nicht vorhersagbar.

Vielleicht deshalb hat das Golang-Team den Ansatz der Speicherspanne (Memory Span) gewählt.

Was ist eine Speicherspanne?

Eine Speicherspanne ist ein Bereich, dem ein vergleichsweise großer Speicherbereich zugewiesen wird und in dem kleine Objekte alloziert werden. Der neue GC mit dem Namen GreenTea GC führt die Speicherbereinigung auf diesen Speicherspannen durch. Die Details des Verhaltens entsprechen nahezu dem bisherigen Tri-Color Mark and Sweep.

Funktionsweise des GreenTea GC

Zunächst alloziert GreenTea GC eine Speicherspanne. Ihre Größe beträgt, wie zuvor beschrieben, 8 KiB, was eine gewisse Größe darstellt. Darin können Objekte mit maximal 512 Bytes alloziert werden. Die Größe der Knoten der zuvor genannten Bäume oder Graphen bzw. die typische Größe von Strukturen, die auf den Heap wandern, dürfte kaum darüber liegen. Objekte mit höchstens 512 Bytes sammeln sich bei jeder Verlagerung auf den Heap in dieser Speicherspanne, und wenn diese voll ist, wird eine neue Speicherspanne alloziert.

Wenn der GC auftritt, reiht GreenTea GC diese Speicherspannen in eine Warteschlange ein und prüft sie nacheinander. Dabei verwendet GreenTea GC eine Planung, die dem bisherigen GMP-Modell nahezu ähnlich ist. Auch Work Stealing ist implementiert. Jedenfalls prüft der Worker, der eine Speicherspanne aus der Warteschlange entnimmt, die Objekte innerhalb der ihm zugewiesenen Speicherspanne. Dabei wird wie bisher Tri-Color Mark and Sweep verwendet.

Welchen Vorteil bringt das?

Der Unterschied zum bisherigen GC liegt im Grunde in genau einem Punkt: Die Einheit, in der der GC auf einmal arbeitet, ist nun nicht mehr das Objekt, sondern die Speicherspanne. Dadurch bietet der GC folgende Vorteile.

  • Speicherlokalität: Da Objekte in einer Speicherspanne zusammenliegen, werden Speichersprünge beim Durchsuchen der Objekte minimiert. Das heißt, der CPU-Cache lässt sich bestmöglich nutzen.
  • Verbesserte GC-Leistung: Indem der GC in Einheiten von Speicherspannen arbeitet, arbeitet er in Umgebungen mit mehreren Kernen effizienter.
  • Optimierte Speicherallokation: Da Speicherspannen mit fester Größe alloziert werden, sinkt beim Allozieren kleiner Objekte der Allokationsaufwand, und die Wahrscheinlichkeit von Fragmentierung nimmt ab. Dies erhöht die Effizienz der Speicherfreigabe.

Kurz gesagt: Ab jetzt können wir Objekte mit höchstens 512 Bytes häufiger und unbeschwerter alloziieren.

Allerdings gibt es auch hier gewisse vorteilhafte Szenarien.

  • Baum- und Graphstrukturen: Fälle mit hohem Fan-out, die selten verändert werden
    • B+-Bäume, Tries, AST (Abstract Syntax Tree)
    • Cache-freundliche Datenstrukturen
  • Batch-Verarbeitung: Workflows mit massenhafter Allokation kleiner Daten
    • Zahlreiche kleine Objekte, die beim JSON-Parsing entstehen
    • DAO-Objekte aus Datenbank-Ergebnismengen

In solchen Fällen kann GreenTea GC eine bessere Leistung als der bisherige GC erzielen. Er ist jedoch nicht in allen Fällen anwendbar, und insbesondere wenn Objekte über verschiedene Speicherbereiche verteilt sind, ist weiterhin keine drastische Leistungssteigerung zu erwarten.

Also

Das Golang-Team hat vermutlich die Absicht, den GC langfristig weiter zu verbessern. Der aktuelle GreenTea GC ist als kleine Änderung in einem begrenzten Bereich zu betrachten und ersetzt den bisherigen GC nicht. Dennoch ist GreenTea GC ein interessantes Beispiel, das einen Einblick in Probleme gibt, mit denen sich das Golang-Team konfrontiert sieht oder rechnet. Überraschend komplex ist das Problem, doch der Versuch, es mit dem Hinzufügen eines vergleichsweise einfachen Konzepts zu lösen, hat mich beeindruckt. Persönlich halte ich es für ein spannendes Beispiel.

GreenTea GC ist ein experimentelles Feature, das ab Go 1.25 eingeführt wird. Es kann durch Setzen der Umgebungsvariable GOEXPERIMENT=greenteagc aktiviert werden. Da diese Funktion noch experimentell ist, sind vor dem Einsatz in Produktionsumgebungen ausführliche Tests erforderlich.

Referenzen