On Aug 31, 2013 8:35 AM, "Sandro Magi" <[email protected]> wrote:
> Sorry, I meant, "The number of regions is bounded by the number of stack roots." I like this phrasing, but more precisely.. The number of regions is exactly the number of *disjoint* object graphs pointed to by separate roots (stack or global). (with a special note that every "non-aggregate-object" which does not contain references to other objects is effectively it's own ARC counted region as well, though we don't call it a region) It's true they handle cycles correctly, but merely by doing an inefficient form of mark-and-sweep which they call "region splitting" "Region splitting is an incremental procedure; a single candidate region is selected from the Region Information Table and then split, if possible. Region splitting need not be done until absolutely necessary; it can be triggered by the memory allocator." By my understanding, their region split is an inefficient form of mark-and-sweep GC. Rather than splitting into strictly two subsets (reachable and non-reachable) they do a union-find to split into N disjoint object graphs - which become the new post-split regions. (good luck doing that without stop the world) From there, all roots are traversed to re-compute the root-reference-count of each new post-split region. After this second step, they know what mark-and-sweep knew to begin with, that some of the new sub-regions have no references and are unreachable. One possible advantage appears to be that *IF* a region can be determined to have no more root references, that entire region can be discarded without any tracing. However, the practical utility of this advantage is dependent on both (a) this happening, and (b) the work of runtime region inference being less than the generational GC scavenge. Another possible advantage appears to be that non-aggregate objects can be promptly collected, with the tradeoff that non-aggregate objects must incur the overhead of an independent ARC counter. Combine these tradeoffs together, and IMNSHO... I. It looks worse than generational compacting GC. For (a) short lived disjoint object graphs, I suspect the allocation+collection overhead of gen-compact-GC will be less than this runtime-region-inference/merging+region-ARC. For (b) tenured churn, their region splitting algorithm effectively degenerates to an inefficient GC with extra steps. II. It also looks worse than ARC+cycle finding. First, a notable benefit of ARC is lost, because non-cyclic dropped references are not promptly reclaimed. Their region-splitting looks less efficient than mark-and-sweep cycle finding, and also harder to do concurrently. Their runtime-region-inference work offsets the savings from not counting intra-region-references. Further, their techniques are effectively only useful in a single-threaded environment, as threading would create lock contention on region reference counts which disastrous even compared with ARC's per-object count contention. ... at least that's how I see it... am I missing something there?
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
