[comp.lang.c++] Garbage Collection

mgardi@watdcsu.waterloo.edu (M.Gardi - ICR) (12/12/87)

First of all, thanks for all the replies re: my bitmap constructor
question. I havea few more questions.
First I should mention I am using Advantage C++ on a ps/2 model 60.
 
1) is there going to be some implementation of garbage collection in a
future release of c++. If not, could someone explain what happens when I
do a delete, or a destructor is called when a variable goes out of scope?
When will this memory 'reappear' for use?
 
2) Has any one done any studies as to the overhead involved with c++ coding.
It seems that my executables seem rather large when they aren't doing much...
(my fault not c++ :^) )
 
3) Can I get a bit of an idea as to what is forthcoming in c++ for the micro?
 
4) Could someone mention again where one can get some information on topics
  that were in the last c++ workshop?
 
5) Why do I have to have all my classes in a source file defined before I 
  include "stream.h", and why does the order of my includes bother the 
  compilation?
 
thanks
peter

shap@polya.Stanford.EDU (Jonathan S. Shapiro) (12/03/88)

Several people at Stanford seem to feel that C++ would be improved,
for some applications, by garbage collection.  The idea is not to
alter the language always, but to introduce a compiler option to
indicate that support for garbage collection should be compiled in and
link in a garbage collector. [Actually, they wan't to GC on an
object-type by object-type basis, but one step at a time]

The advantgage of garbage collection is that it permits storage
reclamation to be the environment's problem, which for some
applications is desirable.

I have some thoughts on how to do it without changing the semantics of
C++.  I would be curious if others think this idea is worth examining
and how they feel it might be done.

Jon

sjs@ctt.bellcore.com (12/06/88)

In article <5422@polya.Stanford.EDU> shap@polya.Stanford.EDU (Jonathan S. Shapiro) writes:
> 
> The advantgage of garbage collection is that it permits storage
> reclamation to be the environment's problem, which for some
> applications is desirable.
> 
> I have some thoughts on how to do it without changing the semantics of
> C++.  I would be curious if others think this idea is worth examining
> and how they feel it might be done.

This is indeed an an interesting problem and we'd best take care to
keep it from becoming religious.  Certainly there are situations where
GC is very useful and others where you want control of memory
management.

I've been back and forth on this many times myself, but my current
feeling is that unless you are writing an operating system or a
run-time environment or have hard real-time constraints GC is probably
a Good Thing.  It can be argued that having to worry about memory
management seriously compromises the integrity of the object
abstraction.  Nevertheless, it is sometimes worthwhile to have
control.  Of course, nobody ever said that there had to be One
Language for all uses.  (OK, some people DO say this!)

Garbage Collection in C++ raises some interesting issues, though:

How does one reconcile the notion of destructors with the idea of
automatic GC?  After all, destructors can do more than just deallocate
memory (closing files and destroying windows, for instance).

Should a Garbage Collecting C++ abolish unions and type puns (so as to
have a self-describing memory)?

Or should one adopt a "sloppy" (cautious?) approach where memory is
scanned for things that "look like" pointers and not worry too much?
["How I learned to stop worrying and love the Garbage Collector" --
Dr. Strangehack?]  There is a C Garbage collector like this.  It makes
a few reasonable assumptions and in return the worst mistake it makes
is to miss some garbage here and there.  It works surprisingly well.

Or just possibly we should leave well-enough alone and leave Garbage
Collection to other languages.  My own thoughts are that GC is best
designed into a language rather that tacked-on as an afterthought.

Food for thought,

Stan Switzer  sjs@ctt.bellcore.com
"What you can doubt is more important than what you know."

jima@hplsla.HP.COM (Jim Adcock) (12/06/88)

Can't this be reasonably handled using parameterized classes 
and multiple inheritence?

-- The problem I have with garbage collection built into the
language is that it assumes that one scheme for all classes
will be good enough -- which is not my experience.

Even with a compile time option, you have an all or none 
schenerio, which is going to force users of C++ to either
buy into your version of garbage collection / memory management,
or avoid using any libraries based on your scheme.

jima@hplsla.HP.COM (Jim Adcock) (12/07/88)

My concerns with GarbageCollection are 1) What algorithm are
you guys talking about, so we can discuss the shortcomings of
that particular method? 2) Show me a GarbageCollection algorithm
that isn't going to cost me in my classes that don't need it.

Again, the argument that "Well, you can always turn garbage
collection off if you don't want to use it" would seem to me
to force all libraries into one of two categories that can't
be mixed: 1) libraries that use garbage collection 2) libraries
that don't use garbage collection.

So then you don't really have one language anymore, you have two.

(If you don't have hard realtime constraints, why not use Smalltalk :-)

dld@F.GP.CS.CMU.EDU (David Detlefs) (02/14/89)

<< Kevin Sullivan asks about garbage collection for C++. >>

I've been doing a literature search in this area recently, and have
found the following relevant references:

Boehm & Weiser: "Garbage Collection in an Uncooperative Environment"
Software Practice & Experience, September 88

Caplinger: "A Memory Allocator with Garbage Collection for C"
Winter 88 Usenix

Both of these present mark & sweep algorithms fairly compatible with
the existing malloc/free/etc interface.

Bartlett: "Compacting Garbage Collection with Ambiguous Roots"
DEC WRL Research Report 88/2

Outlines an approach applicable to a copying collector for C.  (To get,
send a message to wrl-techreports@decwrl.dec.com, with body "help.")

All of these methods are applicable, mutas mutandis, to C++.  There is
also a rumor that Chris Torek of Maryland is working on something
along these lines (Chris, if you read this, could you confirm or deny
to me, along with a pointer to a reference, or a description of what
you're doing?  Thanks...)

Hopefully I've done a service.  Perhaps the collective consciousness
out there can help me in return.  I would like to find some emprical
evidence on just how much more reliable garbage collection makes
programs.  The ideal reference would be one that states "in project X,
we found Y bugs, Z% of which were caused by improper explicit storage
management.  These took W% of the time to debug..."  Any pointers to
such a paper would be greatly appreciated.  Thanks!


--
Dave Detlefs			Any correlation between my employer's opinion
Carnegie-Mellon CS		and my own is statistical rather than causal,
dld@cs.cmu.edu			except in those cases where I have helped to
				form my employer's opinion.  (Null disclaimer.)
--

tma@osc.COM (Tim Atkins) (07/13/89)

I am working on an application that needs to move objects between different
heaps.  The problem I'm attempting to get a handle on is how to avoid a
stack update of what looks like a pointer to one of the objects moved but is
actually some long or other piece of data that happens to contain the same
values.
It occurs to me that compacting garbage collectors must deal with the same
problem.  Does anyone know of a reasonable solution or a reference to some
piece of literature likely to contain one? I understand that Smalltalk and
Lisp don't have to deal with the problem through the use of tagged
architectures.

Thanks in advance for any help.

- Tim Atkins

chase@Ozona.orc.olivetti.com (David Chase) (07/14/89)

In article <404@osc.COM> tma@osc.COM (Tim Atkins) writes:
>
>
>I am working on an application that needs to move objects between different
>heaps.  The problem I'm attempting to get a handle on is how to avoid a
>stack update of what looks like a pointer to one of the objects moved but is
>actually some long or other piece of data that happens to contain the same
>values.

Joel Bartlett at DEC WRL(? if not WRL, then SRC) (both in Palo Alto)
did something with compacting collectors that may help you with this.
I believe that there's a technical report describing this.  The
insight is that a "new" page need not really be "new"; it can be an
old page that you decide to call "new".  Given that, you can either
(a) copy everything out of an old page and recycle it or (b) elect not
to copy something out, because it is pointed to by something in the
stack which you are not allowed to change because it might be an
integer (an "ambiguous root").  That is, Bartlett's scheme "cheats"
and avoids your problem.  (There's obviously more details to this -- get
the tech report or paper if you are interested.)

Plan B (not well thought out, by the way) would be to generate a special
piece of code for each procedure in your application that would manage
its frame.  All this gets put in a table somewhere, and the collector
unwinds the stack, invoking the appropriate piece of code for each
activation record.  Getting this to work correctly is probably not what
most people call "fun", but it's an idea.  (Exception dispatchers based
on similar technology have worked very well.  Non-standard or especially
intricate calling conventions make it very hard.)

I'm not sure, but Robert Shaw (at HP Labs) may be working on a compacting
collector that gets along with C.

Whatever you do, be sure to watch out for "interior pointers"; i.e., a
pointer to a field within a heap-allocated struct.
            (                                    )

David

pierson@xenna (Dan Pierson) (07/14/89)

In article <44731@oliveb.olivetti.com>, chase@Ozona (David Chase) writes:
>Joel Bartlett at DEC WRL(? if not WRL, then SRC) (both in Palo Alto)
>did something with compacting collectors that may help you with this.

    	    	    WRL Research Report 88/2
    	Compacting Garbge Collection with Ambiguous Roots
    	    	    	Joel F. Bartlett
-- 
                                            dan

In real life: Dan Pierson, Encore Computer Corporation, Research
UUCP: {talcott,linus,necis,decvax}!encore!pierson
Internet: pierson@encore.com

ttwang@polyslo.CalPoly.EDU (Thomas Wang) (04/10/90)

rme@wdl1.UUCP (Richard M Emberson Jr) writes:

>   Question: What garbage collection scheme is appropriate for C++.
>   Copy garbage collection has problems with the implicit "this".
>   Are others useful, such as reference counting or fake copying?

A new idea just occurred to me while answering Richard's question.
We can use mostly copying when the size of the stack is small, and switch
to fake copying when the size of the stack is large.  This way, you can
have the cake and eat it too!

I suspect that this idea will be incorporated into MM eventually, and
reference counting will be eliminated all together.

>   Richard M. Emberson
>   rme@spl.fac.ford.com

 -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

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.