Re: concurrent garbage collection and POSIX threads

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

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.

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

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.

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.

david


On Jan 8, 2010, at 11:25 PM, Jon Harrop wrote:

> On Friday 08 January 2010 20:14:56 you wrote:
>> You don't have to pause any execution of app threads for a concurrent
>> garbage collector. A full concurrent garbage collector can run as a =
lowest
>> priority thread, and never invoke any thr_suspend/resume the like =
calls.
>=20
> Rafael cited the Very Concurrent Garbage Collector (VCGC) which is a =
simple=20
> mostly-concurrent GC.
>=20
> Incidentally, what is the simplest fully concurrent GC? The simplest =
approach=20
> I can think of would be to duplicate every pointer in the heap and use =
a=20
> ragged barrier to allow the system to migrate from using one to the =
other=20
> while the collector operates on the unused pointers (acting as a =
snapshot of=20
> the heap).
>=20
> --=20
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e