GC performance - was Re: [gclist] GC topics

[Basile STARYNKEVITCH]

Hello All,

>>>>> "Darius" == "Darius Blasband" <darius@phidani.be> writes:

[[ I skipped interesting stuff ]]

    Darius> [...] So, 20% of the total execution time is required
    Darius> (someone might even say "wasted") just to keep track of
    Darius> all accessible references, even if no new allocation is
    Darius> performed.

I think that 20% is an acceptable overhead for GC. I also read
somewhere that it is usually less (about 5%?) .

    Darius> I see these 20% as the cost for precise GC when compared
    Darius> to conservative GC, and, given the other advantages of
    Darius> precise GC (determinism, portability, and performance
    Darius> *during* the GC process), I thought it was worth it.

I believe that the following references have some precise timing
(mostly about SML/NJ garbage collector, and SML allocate everything,
even call frames, on the heap - it doesn't use a stack for calls).


@TechReport{Appel:study-stack-heap:94,
  author =       {Andrew W. Appel and Zhong Shao},
  title =        {An Empirical and Analytic Study of Stack vs. Heap Cost for Languages
  with Closures},
  institution =  {Princeton University},
  year =         1994,
  number =       {CS-TR-450-94},
  month =        {march}
}

@InCollection{Appel:GC:91,
  author =       {Andrew Appel},
  title =        {Garbage Collection},
  booktitle =    {Topics in Advanced Language Implementations},
  publisher =    {MIT Press},
  year =         1991,
  editor =       {P. Lee},
  pages =        {89-100},
  note =         {ISBN 0-262-12151-4}
}

@Article{Diwan:MemoryPerfAlloc:95,
  author =       {Amer Diwan and David Tarditi and Eliot Moss},
  title =        {Memory System Performance of Programs with Intensive
                  Heap Allocation},
  journal =      {ACM Trans. Computer Systems},
  year =         1995,
  volume =       13,
  number =       3,
  month =        {august},
  pages =        {244-273}
}

See also the following report, which is answered by the previous one

@TechReport{Miller:gc-stack,
  author =       {James S.Miller and Guillermo J. Rozas},
  title =        {Garbage Collection is Fast, But a Stack is Faster},
  institution =  {M.I.T. AI Lab},
  year =         1994,
  number =       {AIM-1462},
  month =        {mar}
}

My overall non-expert opinion is that using a GC and allocating
everything (without even using a stack) on a GC-ed heap is worth
it. The advantage of reifying call frames (as continuations or
closures) is significant for other reasons (call/cc, powerful control
structures, ease of debugging, etc), so even a 25% penalty is IMHO
acceptable.

Of course, these are precise (non conservative) GCs with cooperating
compilers.

Thanks for reading.
-- 

N.B. Any opinions expressed here are solely mine, and not of my organization.
N.B. Les opinions exprimees ici me sont personnelles et n engagent pas le CEA.

Please cite a **pertinent part** of my mail in all answers
Veuillez citer une **partie pertinente** de mon courrier dans vos reponses



----------------------------------------------------------------------
Basile STARYNKEVITCH   ----  Commissariat a l Energie Atomique (civil)
DRN/DMT/SERMA * CEA/Saclay bat.470 * 91191 GIF/YVETTE CEDEX * France
fax: (33) [1] 69.08.85.68; phone: 69.08.40.66; homephone: 46.65.45.53
email: basile.starynkevitch@cea.fr (or else basile@soleil.serma.cea.fr);  
I speak french, english, russian. Je parle francais, anglais, russe.
----------------------------------------------------------------------