Re: Divide and conquer GC algorithms

On 2011-11-12, at 7:31 AM, Jon Harrop wrote:

> 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.
> ...

> 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?

An inexact match for your question is the use of work stealing to parallelize and load-balance the work in some GCs.

http://scholar.google.com/scholar?q=work+stealing+GC&hl=en&as_sdt=0&as_vis=1&oi=scholart

"CH Flood" is "Christine", one door down at work :-).  Working less on GC now, more on making Fortress go faster.

Trying to shuffle stuff around to enhance locality is a general plan.

David