Partial mark and sweep cycle reclamation
by Leandro Lucarella on 2008- 09- 07 18:26 (updated on 2008- 09- 07 18:26)- with 0 comment(s)
This is a more polished version of the last idea about adding a backup tracing GC to collect cycles. We just trace the areas of the heap that can potentially store cycles (instead of tracing all the heap).
So, how do we know which areas may have cycles? When a reference counter is decremented, if it becomes zero, it can't possibly part of a cycle, but when the counter is decremented 1 or more, you never know. So the basics for the algorithm is to store cells which counters have been decremented to 1 or more, and then make a local (partial) mark and sweep to the cell accessible from it.
The trick is to use the reference counters. In the marking phase, the reference counters are decremented as the connectivity graph is traversed. When the marking phase is done, any cell with counter higher than zero is reference from outside the partial graph analyzed, so it must survive (as well as all the cells reachable from it).
Note
The worst case for a partial scan, is to scan the whole heap. But this should be extremely rare.
There are a lot of flavors of this algorithm, but all are based on the same principle, and most of the could be suitable for D.
Backup tracing collector for rc cycles reclamation
by Leandro Lucarella on 2008- 09- 07 04:05 (updated on 2009- 04- 02 21:42)- with 0 comment(s)
The simpler way to reclaim cycles is to use a backup tracing garbage collector. But this way, even when GC frequency could be much lower, the infomation of reference counters are not used, and pauses can be very long (depending on the backup algorithm used).
I think some kind of mixture between RC and tracing GC could be done so I wont discard this option just yet, but I think more specialized algorithms can do better in this case.
Discarded cycles reclamation algorithms
by Leandro Lucarella on 2008- 09- 07 03:50 (updated on 2008- 09- 07 03:50)- with 0 comment(s)
Finally, we address the cyclic structures reclaimation when doing reference counting. But I think there are some algorithms that are clearly unsuitable for D.
All the manual techniques (manually avoiding or breaking cycles or using weak pointers) are unacceptable, because it throws the problem again to the programmer. So I will consider only the options that keep the memory management automatic.
There are several specific cycles reclamation algorithms for functional languages too (like Friedman and Wise), but of course they are unsuitable for D because of the asumptios they make.
Bobrow proposed a general technique, in which a cyclic structure is reference counted as a whole (instead of reference counting their individual cells) but I find this impractical for D too, because it needs programmer intervention (marking "group" of cells).