Dynamic Region Inference

Dynamic Region Inference, by David Pereira and John Aycock:

We present a garbage collection scheme based on reference counting and region inference which, unlike the standard reference counting algorithm, handles cycles correctly. In our algorithm, the fundamental operations of region inference are performed dynamically. No assistance is required from the programmer or the compiler, making our algorithm particularly well-suited for use in dynamically-typed languages such as scripting languages. We provide a detailed algorithm and demonstrate how it can be implemented efficiently.

A novel garbage collector that solves reference counting's cycle problems by introducing "regions", which demarcate possibly cyclic subgraphs. These regions are updated by merge and split operations that occur on pointer update and incrementally on region allocation, respectively, ie. adding a pointer to B into aggregate C merges their regions, and trying to allocate a new region first attempts to split some random candidate region by computing the local reference counts via union-find of the region's members.

Obviously dynamic regions don't share contiguous storage like their static counterparts, so "regions" here are purely a logical concept to ensure completeness of reference counting. The implementation adds two words to each object, one for pointing to the object's current region, the other for a "next" pointer for the next object in the region.

The practicality of this approach isn't clear compared to other cycle detection algorithms, and no benchmarks are provided. I haven't found any follow-up work either.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Advantages unclear, separate union-find pass unnecessary?

The one clear advantage is that a region can be freed immediately when it's RC=0, but because region splitting is delayed, it seems to basically amount to tracing GC with incrementality benefits in only some cases. Am I missing something? If not, it's not clear that this is really a win, as the extra space overhead increases cache pressure which will swallow some of the performance advantages.

The region split algorithm also seems unnecessarily inefficient. The union-find can be inlined into the region+NEXT pointer update traversal, thus avoiding a second pass:

1. set RC=0 for every active region,
2. create a fresh region for the first root with RC=1, then assign this fresh region to every object reachable from that root
3. for each subsequent root, set RC=1 and trace downwards resetting NEXT pointers and performing the usual region merge as necessary
4. delete all active regions with RC=0

This is still union-find, but doing a single pass and using the region/RC machinery already in place. This should incur fewer reads and writes than running union-find using Tarjan's algorithm in the first pass, and then resetting all the region and NEXT pointers again on a second pass.