Re: Divide and conquer GC algorithms

As an example, consider storing the heap topology in a k-D tree indexed by
the pair (a, b) where "a" points to the source object and "b" points to the
destination object that the source refers to.

> -----Original Message-----
> From: [email protected] [mailto:[email protected]] On
> Behalf Of Jon Harrop
> Sent: 12 November 2011 12:32
> To: [email protected]
> Subject: [gclist] Divide and conquer GC algorithms
> 
> Reading Richard's excellent book, I was surprised to observe that none of
the
> major GC algorithms seem to be hierarchical. Some algorithms like the
Train
> collector, Beltway and Immix amortize costs by grouping heap-allocated
blocks
> together but they don't seem to use trees to gradually refine the
granularity.
> 
> I've also been looking at "dynamic" graph algorithms for the first time.
> These algorithms allow a small change in the graph (add/remove one
> edge/vertex) to be converted into a small change in their output. The
concept of
> a topology tree, a data structure used in some dynamic graph algorithms,
> caught my attention because this conveys information about the topology of
a
> graph. For example, you might be able to determine quickly that a 1/4
partition
> of the heap contained pointers to another 1/4 partition but not the other
way
> around so there were no cycles spanning the two partitions. Could a GC use
a
> topology tree to do some of its work in O(log
> 
> n) time? Furthermore, what if a dynamic graph algorithm were used to
> incrementally update the GC's topology tree as the write barrier mutates
the
> topology of the heap?
> 
> Do any GC algorithms use divide-and-conquer, trees or yield complexities
> logarithmic in the number of pointers in the heap?  Can we estimate how
big a
> heap would have to be before hierarchical techniques would become
> competitively performant?
> 
> This reminds me of the debate surrounding the use of trees in file systems
as
> opposed to flat collections...
> 
> On the exact opposite end of the spectrum, has anyone tried using GPGPU to
> accelerate garbage collection, e.g. the mark phase?
> 
> --
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com