On 30/08/2013 11:27 PM, David Jeske wrote:
Can anyone else who reads this enlighten me about how this algorithm is useful?By my read, it recursively collects an object and any objects it references into a "region". The only way I can see two regions can exist is if two different global variables point to two totally disjoint graphs of objects. I don't understand how this is at all useful.
You seem to have misunderstood something critical. Each newly created object starts in its own fresh region. This region is merged into a larger region only if the larger region gets a pointer to this object.
Like static region inference, each function parameter is bound to a region, but in dynamic region inference this region is specified in the object's header word. Merging and splitting seem like pretty standard analogues for static region inference.
Your concerns about contention are only applicable if we assume regions can be shared across threads, which isn't the case for most region systems because then there would be no way to safely free a shared region. Regions are owned by their thread, so inter-thread contention isn't an issue.
Furthermore, thrashing on refcount operations is *less* likely because the set of regions is much smaller than the set of objects, and so the refcounts will be far more likely bein cache.
I'd be much more concerned with the requirement for two additional words in the header and the time complexity of union-find as compared to other cycle detection options.
Sandro
Most programs I can think of would end up with all objects in one big region, degenerating this solution into an inefficient ARC+cycle finding algorithm.Further, instead of merely having the bad thread-contention of reference counts on objects, this system requires a count per region of all references into the region, which is going to be even more heavily contended.If anyone can offer an explanation as to where this algorithm would be useful, I'm really curious what that might be._______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
smime.p7s
Description: S/MIME Cryptographic Signature
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
