Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!pa.dec.com!src.dec.com!hudson@yough.cs.umass.edu
From: hudson@yough.cs.umass.edu (Rick Hudson)
Newsgroups: comp.lang.modula3
Subject: GC references (was RE: Two Oberon questions)
Message-ID: <9104222053.AA08928@yough.ucc.umass.edu>
Date: 22 Apr 91 20:53:30 GMT
Reply-To: hudson@vax1.cs.umass.edu
Lines: 73
To: m3
Cc: stolfi

stolfi@src.dec.COM writes:
> 
>     
>     Around here we sit around and count the number of
>     instructions/record it takes to do allocation and garbage collection
>     on our fingers.  This myth that GC takes thousands of instruction
>     for each allocation just isn't true.
>     
> Congratulations, you must be a very happy man...

Actually, I just broke my finger playing basketball, thus ending my
digital computing for a while :-)

> I presume you have a good incremental garbage collector in a favorable
> architecture, and you measured its performance on typical real-world
> programs (whatever that means).

Moon, David ("Garbage Collection in a Large Lisp System" Conference Record of
the 1984 ACM Symposium on Lisp and Functional Programming) and Ungar, David
and Jackson, Frank, ("Tenuring Policies for Generation-Based Storage
Reclamation", OOPSLA 1988 Conference Proceedings) describe techniques aimed at
improving garbage collection in "real" world situations.

> Forgive me if I sound a bit skeptical, but often the cost of garbage
> collection does not scale linearly with working set size.  Do you still
> get tens of instruction/record when you have, say, 5MB worth of active
> nodes?  

The above references discuss your concerns.

> For example, the SRC Modula-3 compiler currently uses a copying
> garbage collector, whose cost per allocation grows rather quickly as
> the size of accessible structures approaches the total available memory
> size.

Does the SRC Modula-3 use Bartlett's, Joel F. (Mostly Copying Garbage
Collection Picks Up Generations and C+, DEC-WRL Tech note TN12) enhancements
that incorporate generations. I would have guessed that this work would have
lessened such problems.

>
> Note also that, depending on the implementation, the mere existence
> of GC may slow down all pointer assignments quite a bit, even when
> the program is not doing any allocations.  

Bartlett (above) reports a 4% to 12% slowdown due to remembered set
maintenance in Scheme->C using some of the Gabriel benches.

> For instance, our Modula-2+
> GC is partly based on reference counts, and the code for an assignment
> of the form ref1^.field := ref2 must update the reference count of
> ref2^.  Since Modula-2+ programs are usually multi-threaded and run
> on multi-processor workstations, that code must be careful to do the
> right thing even when two threads are trying to update the same count
> at the same time.  On a vanilla VAX architecture, this apparently takes
> at least a dozen VAX instructions. 

Reference count GCs also deal poorly with reference count overflow as well as
circular list structures. Mark-and-Sweep collection do not seem practical
either, but Zorn, Benjamin ("Comparing Mark-and-Sweep and Stop-and-Copy
Garbage Collection" 1990 ACM Conference on Lisp and Functional Programming)
has added generations and indicated why we should reconsider Mark-and-Sweep
algorithms.

Apple, Andrew W. and Li, Kai ("Virtual Memory Primitives for User Programs"
Architectural Support for Programming Languages and Operating Systems, 1991)
discusses what support would be needed from the OS to implement faster
incremental, generational GCs, some of their suggestions deal directly with
how to handle pointer updates and other remembered set problems.

Hope this helps.

- Rick