Re: concurrent garbage collection and POSIX threads

On Sunday 10 January 2010 03:14:09 David F. Bacon wrote:
> "simplest" and "fully concurrent" are fundamentally in conflict.  the more
> concurrent you want to make it, the more complex it gets: are you willing
> to perform a global barrier when collection starts to snapshot the roots?
> if not, are you willing to pause a thread while snapshotting its entire
> stack?  or only for one frame?

Ah yes. :-)

I consider the VCGC algorithm to be simple because it does not perform any 
fine-grained synchronization, just a stop-the-world. I was not technically 
thinking of fully concurrent GC but, rather, GC without global 
synchronization.

So I suppose my question should have been: what GC design that does not stop 
the world contains the fewest fine-grained synchronizations?

I am developing a VM in my spare time as a non-expert so it is very important 
that I keep my milestones attainable by keeping my implementation simple 
without sacrificing my goals (e.g. numerical performance).

> to put it another way, the basic algorithms for marking (and sweeping) are
> not that complex.  the complexity comes when handling the phase transitions
> and corner cases.  getting all of those things done concurrently is the
> "last mile" of GC.  and it's a long one.

I see.

> of course, if you have a ridiculous implementation it's much easier: just
> keep everything in the heap (even stack frames) and then when you start
> collection all you have to do is record a single root.  of course, your
> language will be running 100x slower because you will have to perform
> barriers on every stack operation.  no free lunch.  but it's useful to
> think about this way because you realize that the stacks are just another
> "special" part of memory, like a nursery.

Right.

> the algorithm you outline is basically yuasa's snapshot algorithm.  it's by
> far the simplest and most elegant among the basic styles of concurrent
> collector.

Great.

> the literature is littered with scads of gc algorithms, so many that it's
> overwhelming to figure out which one to use.  but all of them are made up
> from a set of building blocks, combined in various ways depending on the
> performance demands of the particular language and machine environment.  if
> you can get a clean understanding of those building blocks, putting
> together the right GC for the job becomes much easier.  for a pragmatic
> exploration of this, see my paper with vechev et al in ecoop'05; more
> theoretical treatment is in pldi'06/07.

Thanks. I'm reading your ecoop'05 paper now. How would you classify VCGC 
though? I haven't seen its approach to ageing use anywhere else...

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e