Re: concurrent garbage collection and POSIX threads

--- On Sun, 1/10/10, Jon Harrop <[email protected]> wrote:

> From: Jon Harrop <[email protected]>
> Subject: Re: [gclist] concurrent garbage collection and POSIX threads
> To: "David F. Bacon" <[email protected]>
> Cc: [email protected]
> Received: Sunday, January 10, 2010, 6:54 AM
> On Sunday 10 January 2010 03:14:09
> David F. Bacon wrote:
> > "simplest" and "fully concurrent" are fundamentally in
> conflict.=A0 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?=A0 or only for one frame?
>=20
> Ah yes. :-)
>=20
> I consider the VCGC algorithm to be simple because it does
> not perform any=20
> fine-grained synchronization, just a stop-the-world. I was
> not technically=20
> thinking of fully concurrent GC but, rather, GC without
> global=20
> synchronization.
>=20
> So I suppose my question should have been: what GC design
> that does not stop=20
> the world contains the fewest fine-grained
> synchronizations?
>=20
> I am developing a VM in my spare time as a non-expert so it
> is very important=20
> that I keep my milestones attainable by keeping my
> implementation simple=20
> without sacrificing my goals (e.g. numerical performance).
>=20
> > to put it another way, the basic algorithms for
> marking (and sweeping) are
> > not that complex.=A0 the complexity comes when
> handling the phase transitions
> > and corner cases.=A0 getting all of those things
> done concurrently is the
> > "last mile" of GC.=A0 and it's a long one.
>=20
> I see.
>=20
> > 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.=A0 of course, your
> > language will be running 100x slower because you will
> have to perform
> > barriers on every stack operation.=A0 no free
> lunch.=A0 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
> Right.

Also, should keep in mind that,=20

(1) threads' execution stacks keep changing frequently,=20
the size of them are growing and shrinking all the time.=20
That is one of differences from objects in heap.=20

(2) Usually, threads' execution stacks are treated by=20
threads as _Thread_Private_Data_, not as shared with=20
other threads as objects in heap. So when GC determines=20
root set, it is accessing other threads' _Thread_Private_Data_.

So, for performance reason, accessing execution stacks=20
usually needs a very special kind of synchronization,=20
e.g. suspend thread, instead a regular one that people
use for normal multithreading programming.

- Mingnan Guo
MD5: b91f3768339454e00400b63475be4cb7

>=20
> > the algorithm you outline is basically yuasa's
> snapshot algorithm.=A0 it's by
> > far the simplest and most elegant among the basic
> styles of concurrent
> > collector.
>=20
> Great.
>=20
> > the literature is littered with scads of gc
> algorithms, so many that it's
> > overwhelming to figure out which one to use.=A0 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.=A0 if
> > you can get a clean understanding of those building
> blocks, putting
> > together the right GC for the job becomes much
> easier.=A0 for a pragmatic
> > exploration of this, see my paper with vechev et al in
> ecoop'05; more
> > theoretical treatment is in pldi'06/07.
>=20
> Thanks. I'm reading your ecoop'05 paper now. How would you
> classify VCGC=20
> though? I haven't seen its approach to ageing use anywhere
> else...
>=20
> --=20
> Dr Jon Harrop, Flying Frog Consultancy Ltd.
> http://www.ffconsultancy.com/?e
>