[comp.object] Garbage Collection

jimad@microsoft.UUCP (Jim ADCOCK) (02/28/90)

In article <2616@ifi.uio.no> kai@ifi.uio.no (Kai Ivo Quale) writes:
>I'm looking for good books, articles, whatever, on garbage collection/
>object (de)allocation...
>
>Anyone out there have some tips ?

Be suspicious of what you read.

ttwang@polyslo.CalPoly.EDU (Thomas Wang) (02/28/90)

jimad@microsoft.UUCP (JAMES ADCOCK) writes:
>In article <2616@ifi.uio.no> kai@ifi.uio.no (Kai Ivo Quale) writes:
>>I'm looking for good books, articles, whatever, on garbage collection/
>>object (de)allocation...

>>Anyone out there have some tips ?

>Be suspicious of what you read.

Why?  Because the claims are too good to be true?

Here are some paper references I obtained while doing my master thesis:

A. W. Appel, "Garbage Collection Can Be Faster Than Stack Allocation",
Information Processing Letters, Vol. 25, no. 4, June 17, 1987, pp. 275-279

J. F. Bartlett, "Compacting Garbage Collection with Ambiguous Roots", no. 88/2
DEC Western Research Laboratory, Feb 1988.

R. Courts, "Improving Locality of Reference in a Garbage-Collecting Memory
Management System", CACM, Vol. 31, no. 9, Sep 1988, pp 1128-1138.

H. Lieberman and C. Hewitt, "A Real-Time Garbage Collector Based on the
Lifetimes of Objects", CACM, Vol. 26, no. 6, June 1983, pp 419-429.

D. Moon, "Garbage Collection in a Large Lisp System", ACM Symposium on Lisp and
Functional Programming, Austin, Texas, 1984, pp. 235-246.

P. R. Wilson and T. G. Moher, "Design of the Opportunistic Garbage Collector",
Proceedings of ACM SIGPLAN 1989 Conference of Object-Oriented Programming:
Systems, Languages, and Applications, New Orleans, Louisiana, Oct 2-6, 1989.

The hypothesis of garbage collection is that it can significantly reduce the
number of memory management errors, while only introducing a small overhead.
This is certainly true for good implementation of garbage collectors.  In
languages such as C, only slow garbage collectors can be made to work.  I
think this and together with the traditional dogma contributed to the belief
that all garbage collectors are slow.

The reduced number of bugs mean lab engineers have more time for performance
improvement.

 -Thomas Wang ("This is a fantastic comedy that Ataru and his wife Lum, an
                invader from space, cause excitement involving their neighbors."
                  - from a badly translated Urusei Yatsura poster)

                                                     ttwang@polyslo.calpoly.edu

jimad@microsoft.UUCP (Jim ADCOCK) (03/06/90)

In article <25eb4850.41d0@polyslo.CalPoly.EDU> ttwang@polyslo.CalPoly.EDU (Thomas Wang) writes:
>jimad@microsoft.UUCP (JAMES ADCOCK) writes:
>>In article <2616@ifi.uio.no> kai@ifi.uio.no (Kai Ivo Quale) writes:
>>>I'm looking for good books, articles, whatever, on garbage collection/
>>>object (de)allocation...
>>>Anyone out there have some tips ?
>>Be suspicious of what you read.
>Why?  Because the claims are too good to be true?

Well yes, actually.  If I were to write the generic GC paper it would go:

We tried Smith's GC written for the language Smirf on hardware Glop and
it was too slow for OurLang.  So we tried this new approach called OurWay 
running on OurGlop.  Initial tests using the representative target
application "LunerLander" were dissapointing, showing only a performance
improvement of 5%.  So we tuned OurWay a little bit.  And we re-wrote it
in OurGlop assembler using the hardware page faults supported on OurGlop
using a bunch of non-portable pointer hacks.  After a number of passes of
tuning OurWay, LunerLander now runs 400% faster than it did initially.
Furthermore, OurWay of GC'ing now only takes 20% of the total execution
time of the prototype OurLang interpreter [which is written in Algol.]

I claim the tuning of "OurWay", to optimize it to run on "OurGlop",
supporting "OurLang", used to write "LunerLander", with 10 Megabyte of RAM,
and 40 Megs of swap space, has little or nothing to do with the rest of
the world.

What is traditionally called "GC" encompases many related issues:

Do we attempt to discover objects that are no longer being used?
Do we attempt to re-use memory no longer used?
Do we attempt to avoid memory fragmentation?
Do we attempt to compact memory to get rid of fragmentation?
Do we attempt to make good use of virtual memory hardware?
Do we attempt to make good use of caches?
Do we attempt to be portable to various machines?
Do we have a linear memory or segmented one?
Do we have hardware support for virtual memory?
Do we use special pointer hacks?
Do we require special compiler/interpreter support?
Do we attempt to cluster objects?
Do we tune GC for a particular application? [maxamin]
Do we tune GC to try to match "all" applications? [minamax]
Do we support "real-time" --if so, how real?  one second response?
	one mSec response?

-- I have yet to see any GC scheme that I'd be willing to consider anything
close to general purpose.

ttwang@polyslo.CalPoly.EDU (Thomas Wang) (03/06/90)

jimad@microsoft.UUCP (Jim ADCOCK) writes:

>What is traditionally called "GC" encompases many related issues:

>Do we attempt to discover objects that are no longer being used?
Yes.
>Do we attempt to re-use memory no longer used?
Yes.
>Do we attempt to avoid memory fragmentation?
Periodically fix memory fragmentation.
>Do we attempt to compact memory to get rid of fragmentation?
Yes, see above.
>Do we attempt to make good use of virtual memory hardware?
Not necessary.
>Do we attempt to make good use of caches?
No.
>Do we attempt to be portable to various machines?
Yes.  Less than 3 pages of non-portable code should be good enough.
>Do we have a linear memory or segmented one?
The programmer don't care.  Only the GC implementor need to know the memory
model.
>Do we have hardware support for virtual memory?
Not necessary.
>Do we use special pointer hacks?
No pointer hacks!  This sort of trick is not needed if the language don't
use physical pointers.
>Do we require special compiler/interpreter support?
No.  The GC can be written as an object code library.
>Do we attempt to cluster objects?
Yes.  I am certain that object clustering is a big win.
>Do we tune GC for a particular application? [maxamin]
Tuning by using GC initialization parameters.
>Do we tune GC to try to match "all" applications? [minamax]
No.
>Do we support "real-time" --if so, how real?  one second response?
>	one mSec response?
Yes.  Two flavors.  One with 1/2 second response, the second one with
milli-second response time.

>-- I have yet to see any GC scheme that I'd be willing to consider anything
>close to general purpose.

The one thing that will kill GC performance is the use of physical pointers.
C is a perfect example of this.  If the language would access things through
handles, then a portable GC can be written with good enough performance for
it to be useful.

This has been true for Smalltalk systems for about 4 years now.

"Physical pointers considered harmful."



 -Thomas Wang ("This is a fantastic comedy that Ataru and his wife Lum, an
                invader from space, cause excitement involving their neighbors."
                  - from a badly translated Urusei Yatsura poster)

                                                     ttwang@polyslo.calpoly.edu

barmar@think.com (Barry Margolin) (03/06/90)

In article <25f324e9.1488@polyslo.CalPoly.EDU> ttwang@polyslo.CalPoly.EDU (Thomas Wang) writes:
>  If the language would access things through
>handles, then a portable GC can be written with good enough performance for
>it to be useful.

At the expense of doubling the number of memory references for every
pointer dereference.

The Macintosh system has a reasonable compromise.  They encourage use of
handles, but provide a LockHandle function.  You lock a handle around a
section of code that uses that pointer extensively (e.g. an inner loop),
and only dereference the handle once, right after the lock.  If a GC
happens during that section of code the locked object won't be moved.
--
Barry Margolin, Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar

ncjuul@diku.dk (Niels Christian Juul) (12/27/90)

	     POSITION PAPERS ON GARBAGE COLLECTION ISSUES.
				FROM
	Workshop on Garbage Collection in Object-Oriented Systems.

The workshop was held in conjunction with the Joint ECOOP/OOPSLA'90 
Conference at Hotel Chateau Laurier, Ottawa, Canada on Sunday October, 
21st, 1990.

Most of the position papers from the workshop are now made available 
for anonymous FTP from  

	midgard.ucsc.edu (North America) in:  /pub/gc/
	(IP. 128.114.134.15)		 Only available until 1 Feb 1991
and
	ftp.diku.dk 	 (Europe) 	 in:  /pub/GC90/
	(IP. 129.142.96.1)		 Available until further notice.

Login as anonymous and state your own email-address as password.

THE PAPERS ARE SUBMITTED IN POSTSCRIPT FORMAT AND COMPRESSED.
TO PRINT THE PAPERS:

	uncompress xxxxx.ps.Z 
and
	lpr  xxxxx.ps		'on your favorite printer'

Further information on the individual papers are available by contacting the
appropriate authors; see list of attendees in file: Attendees.ps

In case of trouble you may contact:

	daniel@terra.ucsc.edu 	(Daniel Edelson)
or:
	ncjuul@diku.dk		(Niels Christian Juul)


Enclosed you find a list of the available position papers.
Good luck,	
1990.DEC.27.

		Daniel Edelson		&	Niels Christian Juul
		UCSC, CA, USA			DIKU, Denmark, Europe
-------------------------------------------------------------------------

CONTENTS:

	A Generational, Compacting Garbage Collector for C++
	Joel F. Bartlett, WRL/DEC, Palo Alto, CA, USA.

	Real-Time Compacting Garbage Collection
	Mats Bengtsson and Boris Magnusson, Lund University, Sweden.

	Experience with Garbage Collection for Modula-2+ in the Topaz 
	Environment
	John DeTreville, SRC/DEC, Palo Alto, CA, USA.

	Concurrent, Atomic Garbage Collection
	David L. Detlefs, SRC/DEC, Palo Alto, CA, USA.

	The Case for Garbage Collection in C++
	Daniel Edelson, University of California, Santa Cruz, CA, USA.

	Garbage Collection in an Object Oriented, Distributed, Persistent 
	Environment
	A. El-Habbash, Trinity College, Dublin, Ireland.

	Storage Reclamation
	Paulo Ferreira, INESC/IST, Lisboa, Portugal.

	Open Systems Require Conservative Garbage Collection
	Barry Hayes, Stanford University, CA, USA.

	Adaptive Garbage Collection for Modula-3 and Smalltalk
	Richard Hudson and Amer Diwan, University of Massachusetts, 
	Amherst, MA, USA.

	A Distributed, Faulting Garbage Collector for Emerald
	Niels Christian Juul, DIKU, Copenhagen, Denmark.

	SPiCE Collector: The Run-Time Garbage Collector for Smalltalk-80 
	Programs Translated into C
	Satoshi Kurihara, Norihisa Doi, and Kazuki Yasumatsu, 
	Keio University, Japan.

	Real-Time Concurrent Collection in User Mode
	Kai Li, Princeton University, NJ, USA.

	A Fast Expected-Time Compacting Garbage-Collection Algorithm
	Christer Mattsson, Lund University, Sweden.

	Garbage Collecting Persistent Object Stores
	J. Eliot B. Moss, University of Massachusetts, Amherst, MA, USA.

	Hardware Support for Garbage Collection of Linked Objects and Arrays in
	Real Time
	Kelvin Nielsen and William J. Schmidt, Iowa State Univesity, Ames, 
	IA, USA.

	A garbage detection protocol for a realistic distributed
	object-support system
	Marc Shapiro, INRIA, Rocquencourt, France.

	Three Issues In Obejct-Oriented Garbage Collection
	Jon L. White, Lucid, Inc., Menlo Park, CA, USA.

	Garbage Collection in a High-Performance System
	Mario Wolczko, The University, Manchester, UK.

	Designing Systems for Evaluation: A Case Study of Garbage Collection
	Benjamin Zorn, University of Colorado at Boulder, CO, USA.