So I started writing a long email today describing how RC-immix works. Writing my way through it as a way to understand it, and making some notes about possible places for improvement along the way. There has sure been a lot of history in the GC world.
Along the way I realized that RC-immix isn't a real-time collector. The problem isn't deferred reference counts (though there are some fixable issues there). The problem is that the allocator is subject to fragmentation, and there is no guarantee that free space is coalesced at any particular rate. It is entirely possible for fragmentation to prevent allocation of medium size objects without extending the heap. And of course, the paper says almost nothing about how LOS works in their scheme. While pondering that, it occurred to me that the same issue is true of malloc and free. The arena can become fragmented in such a way that the storage size you need isn't available. In both cases (malloc and RC-immix) the only real resolution is to grow the heap. And strangely enough, the pause times in some corner cases can get pretty big - more than big enough to stall a CODEC. At which point I realized that the entire notion of a general purpose real-time storage allocator is a chimera. It is not that hard to design a general purpose collector with a pause delay bounded by P that is incurred every M megabytes of allocation. P can be driven to a very small number with very high probability if you are willing to accept some slowdown S on the mutator. Depending on the design, S may actually be less than the slowdown imposed by conventional allocation. But the delay bound P is not backed by any hard guarantee. If our goal is reasonable interactive behavior, it is sufficient to a low pause delay P with very high likelihood. It doesn't have to be perfect. But if our goal is to satisfy a hard real-time guarantee, I only know of three allocation strategies that actually work: - No allocation at all. - Strictly LIFO allocation with a known upper bound using preallocated storage. - Size-partitioned allocation with known sizes and known maxima for each size, again using preallocated storage. Which brings me to the question: what problem are we actually trying to solve here? What RC-immix *appears* to do is lower the delay between the time an object becomes unreferenced and the time it becomes available for allocation. On paper, that should mean that the scheme requires less overall heap space than conventional GC. But the reality is less clear-cut. Lines in a block may go free, but blocks are recycled by GC and/or allocation. The good news is that this is done without a full examination of the heap, because we know where frees have occurred. The bad news is that the delay between object release and recycling of storage can be higher than you might think from an initial reading of the paper. It would be interesting to see metrics on that, but the RC-immix papers offer none. It isn't that hard for RC-immix to put recyclable blocks back in circulation. It is rather harder for RC-immix to arrange for blocks to be entirely free. It surprises me that the heap sizes required for reasonable execution with RC-immix are as large as they are. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
