Erez Petrank | 11 Jan 16:08 2010
Picon

Re: Daily gclist MIME digest V5 #121

Jon,

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.

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

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

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 
  .

[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/mostly-concurrent-toplas.ps

[2] Detlefs, D. and Printezis, T. 2000 A Generational Mostly- 
Concurrent Garbage Collector. Available at http://portal.acm.org/citation.cfm?id=974992

[3] Damien Doligez, Georges Gonthier: Portable, Unobtrusive Garbage  
Collection for Multiprocessor Systems. POPL 1994: 70-83.

[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.  The  
2000 International Symposium on Memory Management, October, 2000.   
Available at http://www.cs.technion.ac.il/~erez/Papers/cgc9.pdf

[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  Programming Language Design and  
Implementation (PLDI 2000), June, 2000. Available at http://www.cs.technion.ac.il/~erez/Papers/gen.ps

[6] Hezi Azatchi, Yossi Levanoni, Harel Paz, and Erez Petrank  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  (OOPSLA'03), October 2003.   
Available at http://www.cs.technion.ac.il/~erez/Papers/ms-sliding-views.ps

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

Best,

--Erez

---------------------------------------------------------------------------------------------
Erez Petrank, Assoc. Professor,
Dept. of Computer Science, Technion - Israel Inst. of Technology.
Email: erez <at> cs.technion.ac.il
Phone: +972-4-829-4942.   Fax: +972-4-829-3900
homepage: http://www.cs.technion.ac.il/~erez
---------------------------------------------------------------------------------------------

On 11-Jan-10, at 12:20 PM, gclist-owner <at> lists.iecc.com wrote:

> Daily gclist MIME digest
> Volume 5 : Issue 121 : "text" Format
>
> Messages in this Issue:
>  Re: concurrent garbage collection and POSIX threads
>
> ----------------------------------------------------------------------
>
> Date: Sun, 10 Jan 2010 14:54:08 +0000
> From: Jon Harrop <jon <at> ffconsultancy.com>
> To: "David F. Bacon" <dfb <at> watson.ibm.com>
> Cc: gclist <at> lists.iecc.com
> Subject: Re: concurrent garbage collection and POSIX threads
> Message-ID: <201001101454.08707.jon <at> ffconsultancy.com>
>
> 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
>
> ------------------------------
>
> End of [gclist] Daily gclist MIME digest V5 #121
> **********


Gmane