Re: Daily gclist MIME digest V5 #121

Hi all,=20

I want to say something about the terminology of "Concurrent", "On-The-Fly"=
 and "Full Concurrent".

Many technical papers have used the term "Concurrent" and "On-The-Fly" rega=
rding stack scanning as:

"Concurrent garbage collectors run concurrently with the application and on=
ly stop it for a short synchronization phase in the beginning or end of the=
 collection. On-the-fly collectors are special concurrent collectors that n=
ever need to stop all threads simultaneously. They stop the application one=
 thread at a time typically for scanning the thread runtime stack"

However, some concurrent GC algorithms do not perform stack scanning at all=
. As far as I know, there are at least two implementations of that kind of =
GC. One is HnxGC based on reference counting, another one is not reference =
counting based. These kinds of GCs are so much different from those "Concur=
rent" and "On-The-Fly" on stack scanning. So, using a different terminology=
, such as "Full Concurrent", is more appropriate for these GC algorithms to=
 avoid confusion. For example,=20

"Full Concurrent garbage collectors run concurrently with the application a=
nd behave like usual application threads, which never involuntarily stop ot=
her threads except for debug purpose."=20

Any comment? Thanks,

-Mingnan Guo


--- On Mon, 1/11/10, Erez Petrank <[email protected]> wrote:

> From: Erez Petrank <[email protected]>
> Subject: Re: [gclist] Daily gclist MIME digest V5 #121
> To: [email protected], "Jon Harrop" <[email protected]>
> Cc: [email protected]
> Received: Monday, January 11, 2010, 7:08 AM
> Jon,
>=20
> I concur with Hans and David. Actually, I agree with most
> of what David says except for the bottom line where he says
> that there are lots of available collectors in the
> literature and therefore it will be easier for you to look
> at a GC generator and use the basic blocks you like. It
> seems to me that this approach may be too complicated to
> start with.
>=20
> I think if I were you, I would look for concurrent
> collectors that have been previously implemented in the
> industry. These are typically chosen for simplicity and
> efficiency. Maybe the most popular concurrent collector is
> the mostly concurrent collector that Hans proposed. It was
> used by IBM, BEA, SUN, and more. a detailed report on an
> IBM's implementation of a modern mostly concurrent algorithm
> (with some algorithmic extensions for efficiency and various
> engineering efforts for scalability) appears in [1].=A0
> SUN's version was published in [2]. The disadvantage of this
> choice is that this collector has a stop-the-world phase in
> the end , and is thus not fully concurrent. (It is
> mostly-concurrent.)
>=20
> The second collector I would check, which has much shorter
> pauses, but is not as simple, is by DLG [3]. It is
> on-the-fly (or fully concurrent.) A report on an
> implementation by IBM for Java appears in [3,4]. Finally, an
> additional collector that is on-the-fly, has very short
> pauses (like DLG), seems somewhat simpler than DLG, but not
> as simple as the mostly-concurrent one, is the sliding views
> collector from [5].
>=20
> All of these (three) collectors were implemented by
> Xiao-Feng Li for the Apache Harmony VM. As far as I know,
> they have not yet performed proper measurements that allow
> publication, but you can probably get his off-line opinion
> on what it takes to implement them. A presentation on his
> work is available at http://people.apache.org/~xli/presentations/harmony_=
tick_concurrent_gc.pdf
> .
>=20
>=20
> [1] Katherine Barabash, Ori Ben-Yitzhak, Irit Goft, Elliot
> K. Kolodner, Victor Leikehman, Yoav Ossia, Avi Owshanko, and
> Erez Petrank. A Parallel, Incremental, Mostly Concurrent
> Garbage Collection for Servers. ACM Transactions on
> Programming Languages and Systems, Vol. 27 No. 6, pp. 1097 -
> 1146, Nov. 2005. Available at http://www.cs.technion.ac.il/~erez/Papers/m=
ostly-concurrent-toplas.ps
>=20
> [2] Detlefs, D. and Printezis, T. 2000 A Generational
> Mostly-Concurrent Garbage Collector. Available at http://portal.acm.org/c=
itation.cfm?id=3D974992
>=20
> [3] Damien Doligez, Georges Gonthier: Portable, Unobtrusive
> Garbage Collection for Multiprocessor Systems. POPL 1994:
> 70-83.
>=20
> [4] Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Elliot
> E. Salant, Katherine Barabash, Itai Lahan, Erez Petrank,
> Igor Yanover and Yossi Levanoni. Implementing an On-the-fly
> Garbage Collector for Java.=A0 The 2000 International
> Symposium on Memory Management, October, 2000.=A0
> Available at http://www.cs.technion.ac.il/~erez/Papers/cgc9.pdf
>=20
> [5] Tamar Domany, Elliot K. Kolodner, Erez Petrank.
> Generational On-the-fly Garbage Collector for Java. An
> extended abstract appears in the ACM SIGPLAN 2000 Conference
> on=A0 Programming Language Design and Implementation
> (PLDI 2000), June, 2000. Available at http://www.cs.technion.ac.il/~erez/=
Papers/gen.ps
>=20
> [6] Hezi Azatchi, Yossi Levanoni, Harel Paz, and Erez
> Petrank=A0 An on-the-fly Mark and Sweep Garbage Collector
> Based on Sliding Views. Proceedings of the ACM Conference on
> Object-Oriented Programming, Systems, Languages, and
> Applications=A0 (OOPSLA'03), October 2003.=A0
> Available at http://www.cs.technion.ac.il/~erez/Papers/ms-sliding-views.p=
s
>=20
> Check out my publication page for some power point
> presentations for some of these collectors (http://www.cs.technion.ac.il/=
~erez/papers-by-area.html).
>=20
> Best,
>=20
> --Erez
>=20
> -------------------------------------------------------------------------=
--------------------
> Erez Petrank, Assoc. Professor,
> Dept. of Computer Science, Technion - Israel Inst. of
> Technology.
> Email: [email protected]
> Phone: +972-4-829-4942.=A0=A0=A0Fax:
> +972-4-829-3900
> homepage: http://www.cs.technion.ac.il/~erez
> -------------------------------------------------------------------------=
--------------------
>=20
>=20
>=20
>=20
>=20
> On 11-Jan-10, at 12:20 PM, [email protected]
> wrote:
>=20
> > Daily gclist MIME digest
> > Volume 5 : Issue 121 : "text" Format
> >=20
> > Messages in this Issue:
> >=A0 Re: concurrent garbage collection and POSIX
> threads
> >=20
> >
> ----------------------------------------------------------------------
> >=20
> > Date: Sun, 10 Jan 2010 14:54:08 +0000
> > From: Jon Harrop <[email protected]>
> > To: "David F. Bacon" <[email protected]>
> > Cc: [email protected]
> > Subject: Re: concurrent garbage collection and POSIX
> threads
> > Message-ID: <[email protected]>
> >=20
> > 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
> > fine-grained synchronization, just a stop-the-world. I
> was not technically
> > thinking of fully concurrent GC but, rather, GC
> without global
> > synchronization.
> >=20
> > So I suppose my question should have been: what GC
> design that does not stop
> > 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
> > that I keep my milestones attainable by keeping my
> implementation simple
> > 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.
> >=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
> > though? I haven't seen its approach to ageing use
> anywhere else...
> >=20
> > --Dr Jon Harrop, Flying Frog Consultancy Ltd.
> > http://www.ffconsultancy.com/?e
> >=20
> > ------------------------------
> >=20
> > End of [gclist] Daily gclist MIME digest V5 #121
> > **********
>=20
>