Efficient cycle detection on a partially reference counted heap

Abstract

Two essential garbage collection techniques exist: tracing and reference counting. The goal of this work is to find an algorithm, to efficiently combine both approaches and collect cycles in partially reference counted heaps, a problem which is typically found in compiler-level language integrations, while keeping the impact on both integrated technologies and their existing garbage collector low. Two versions of the algorithm are implemented in the PyPy just-in-time compiler to support the integration of CPython extension modules. The final algorithm has been influenced by Jython's GC integrations for JyNI, but still stands on its own. Semi- and fully-incremental versions of this algorithm are designed and their correctness is established by a semi-formal proof. The implementations are verified using sophisticated tests and their efficiency is measured by running several benchmarks. The results reveal, that the fully-incremental version of the algorithm seems to behave quite well and is able to compensate a lot of the introduced overhead, of fully integrating both garbage collection mechanisms.

Zur automatisierten Speicherbereinigung, kurz Garbage Collection, existieren zwei grundlegende Ansätze: Tracing und Reference Counting. Ziel dieser Arbeit ist es, einen Algorithmus zu finden, der beide Ansätze auf effiziente Weise vereint, und der es ermöglicht Zyklen auf teilweise referenzgezählten Heaps zu erkennen, ein Problem das typischerweise in Sprachintegrationen auf Compiler-Ebene gefunden werden kann, und gleichzeitig die Auswirkungen auf die zu integrierenden Technologien und deren Garbage Collector niedrig hält. Zwei Versionen dieses Algorithmus wurden im PyPy Just-in-time-Compiler implementiert, um die Integration von CPython-Erweiterungsmodulen zu unterstützen. Der finale Algorithmus ist an Jython's JyNI-Integration angelehnt, kann aber als eigenständig betrachtet werden. Eine teilweise und eine vollständig inkrementelle Version dieses Algorithmus wurden entworfen und deren Korrektheit semiformell bewiesen. Die Implementierungen wurden mittels aufwändiger Tests verifiziert und mithilfe eigener Benchmarks verglichen. Die Ergebnisse zeigen, dass das Verhalten der vollständig inkrementellen Version des Algorithmus relativ gut ist und ein großer Teil des Mehraufwands kompensiert werden kann, der durch die vollständige Integration beider Ansätze entsteht.