Arborescent Garbage Collection: A Dynamic Graph Approach to Immediate Cycle Collection

Abstract

Reclaiming cyclic garbage has been a long-standing challenge in automatic memory management. Common approaches to this problem often involve extending reference counting with an asynchronous background task to reclaim cycles. While this ensures that cycles are eventually collected, it also introduces unpredictable behaviours, making these approaches unsuitable for applications where deterministic collection is required.

This paper introduces Arborescent Garbage Collection, a synchronous memory management algorithm that immediately reclaims unreachable memory objects, including cyclic structures. Inspired by single-source reachability algorithms on dynamic graphs, it extends the idea of embedding a spanning forest in a program's reference graph to track the reachability of any object from a root. When a reference is removed, the algorithm efficiently rebuilds the forest and immediately reclaims the memory of objects that are no longer reachable. The result is a garbage collection algorithm suitable for applications that require immediate memory reclamation and predictable behaviour.