On 31/08/2013 12:59 PM, David Jeske wrote:
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)
The lazy techniques Bacon and Petrank pioneered for the Recycler would work here to virtually eliminate stop-the-world, and to extend it to concurrent access (although I'm not convinced that's the way to go). Reference counting then loses its incrementality, but it becomes a nearly pauseless on-the-fly algorithm.
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.
This doesn't seem like mark-sweep at all. A region-split traverses only the objects in that region, so at best you could compare it to a conceptual mark-region GC, unless you can demonstrate that most programs necessarily reduce to a single region. I agree some programs would, but they seem contrived.
Union-find has log(n) worst case complexity which isn't too bad, but I too doubt this GC from 2002 would be competitive with modern offerings. It's just an interesting point in the design space, because it performs a typically static operation at runtime in a fairly simple way.
Regions have also been applied to track other types of effects beyond allocation, so this approach may have other applications, ie. region effects have been used to track locks [1], and this algorithm could possibly be applied in that context by replacing the "alloc" operation with "lock-acquire". Region-merge then becomes an N:1 thread join, with only a single thread proceeding. Region-split is then a 1:N thread spawn.
Sandro[1] https://www.usenix.org/system/files/conference/hotpar12/hotpar12-final48.pdf
[2] http://arxiv.org/pdf/1002.0940.pdf
smime.p7s
Description: S/MIME Cryptographic Signature
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
