Generational and parallel garbage collection

Abstract

Viele Programmiersprachen verwenden Tracing Garbage Collection (GC) zur automatischen Speicherverwaltung. Der GC gibt nicht mehr erforderlichen Speicher automatisch wieder frei, allerdings hat die Applikation selbst kaum Einfluss darüber, wann dies erfolgt. Der GC pausiert die Anwendung spätestens, wenn kein freier Speicher mehr verfügbar ist. Dazu berechnet der GC den transitiven Abschluss aller von der Anwendung erreichbaren Objekte im Arbeitsspeicher. Speicherbereiche, die nicht mehr erreicht werden können, werden vom GC wieder freigegeben. Im Anschluss daran kann die Ausführung der Applikation fortgeführt werden. Dora ist eine Laufzeitmaschine für eine statisch getypte Programmiersprache. Funktionen werden bei ihrem ersten Aufruf in Maschinensprache übersetzt, ohne vorher interpretiert zu werden. Diese Arbeit präsentiert den auf Generationen basierenden Speicherbereiniger Swiper. Dazu wird der Speicher in zwei Teilbereiche aufgeteilt: neue und alte Generation. Dies basiert auf der Annahme, dass die meisten Objekte relativ früh sterben. Objekte werden zunächst in der neuen Generation allokiert und werden in die alte Generation verschoben, sobald sie genug Speicherbereinigungen überlebt haben. Swiper implementiert zwei verschiedene Arten von Speicherbereinigungen. Eine häufig auftretende, aber verhältnismäßig kleine Bereinigung, die tote Objekte ausschließlich in der neuen Generation findet. Dazu gibt es noch eine volle Speicherbereinigung, die den gesamten Speicher behandelt. Swiper ist in etwa genauso schnell wie der Copy Collector obwohl nur die Hälfte des Speichers benötigt wird. Die Performance verschlechtert sich nur wenn die meisten jungen Objekte nicht früh sterben. Unterbrechungen der Applikation zur Bereinigung werden von Swiper minimiert, indem die anstehende Arbeit auf mehrere Threads aufgeteilt und gleichzeitig abgearbeitet wird. Je mehr Threads verwendet werden, desto schneller wird die gesamte Speicherbereinigung. Allerdings ist die serielle Speicherbereinigung schneller als die parallele mit nur einem Thread aufgrund von Mehraufwand zur Synchronisierung. Allokationen werden durch sogenannte thread-local allocation buffers (TLAB) beschleunigt. Diese erlauben der Applikation die meisten Objekte ohne Synchronisierung und ohne Aufruf der Laufzeitmaschine zu allokieren. Die Laufzeit verbessert sich im binarytrees Benchmark beinahe um das vierfache. Die meisten anderen Benchmarks verbessern sich auch signifikant.

Tracing Garbage Collection (GC) is a technique for automatic memory management used by many programming languages. The application only allocates new memory, while the GC automatically frees unreachable memory again. In such systems the developer has almost no control when memory is reclaimed. When the GC runs out of memory or when it decides a collection would be worthwhile, the collector stops the application to release memory. It computes the transitive closure of all objects reachable from the application. Then the memory for unreachable objects can be reclaimed. Immediately after discarding the memory, execution of the application can continue. Dora is a runtime for a statically typed programming language. Functions are lazily compiled to machine code on their first invocation by the baseline compiler. This work presents the generational GC Swiper for the Dora runtime. The collector is based on the weak generational hypothesis, that states that most objects die young. Based on this empirical observation the heap is split into young and old generation. Objects are allocated in the young generation and promoted into the old one as soon as they become old enough. The GCs duty is to reclaim unused memory. A collection is more effective when applied on memory regions that are more likely to continue garbage. Therefore Swiper performs two different kinds of collection: minor and full collection. Frequent minor collections discover garbage solely in the young generation, whereas the less common full collection handles the full heap. Swiper uses different collection schemes for the different collections: copy collection during minor collections and mark-compact for full collections. Swipers performance is competitive to pure copy collection, while using half the memory. However, it is less efficient than pure copy collection and mark-compact in non-generational workloads. Pause times are reduced by distributing work to multiple worker threads. Serial collection is faster than parallel collection with one worker thread due to synchronization overhead. Using multiple worker threads reduces pause times compared to serial minor and full collection. Swiper also improves allocation performance through the implementation of thread-local allocation buffers (TLAB). This allows the mutator to allocate most objects without synchronization using only a few assembly instructions. The binarytrees benchmark becomes almost 4 times as fast with TLAB allocation, most benchmarks improve significantly.