From: bcannard@hppcb36.mentorg.com (Bob Cannard @ PCB x5565)
Subject: Re: Garbage Collection for C++
Originator: bcannard@hppcb36
Date: Fri, 14 Aug 1992 02:15:47 GMT
Organization: Mentor Graphics 
Keywords: 
Followup-To: 


In article <DAVEG.92Aug13025629@synaptx.synaptics.com>, daveg@synaptics.com (Dave Gillespie) writes:
|> Couldn't we get away with having a garbage collector that didn't
|> need pointers to be declared `GC'?  The only thing that would need
|> special `GC' treatment would be "new":  There would be a special
|> "GCnew" or something which would allocate an object with the
|> property that it went away when it was no longer referenced.  Note
|> that it would be safe for an implementation to allocate *all*
|> objects as GC-able, but it would be a good idea at least in the
|> transition period to provide both traditional "new" and "GCnew".

I can't see that this is viable given the basic constraints on C++: among
other things, those who don't want GC shouldn't have to suffer the hits.
Marking classes or pointers (as appropriate, depending on the GC
implementation) means the compiler knows about any extra treatment it has
to give to those pointers/objects, and can leave it out for "ordinary"
code.

In particular, in my own application - which will eventually be quite a big
program - I only want GC for certain classes, where the problem of determining
when an object must be deleted has no sensible solution other than GC. Yet
performance (both run time and memory use) carries a high premium, so I can't
afford to have GC everywhere.

|> Some Lisp systems, such as Kyoto Common Lisp, work this way.  Its
|> garbage collector scans the whole stack as "raw memory," looking
|> for 32-bit words that could be pointers to GC-able objects.  It
|> allocates GC-able objects in such a way that it is relatively
|> easy to tell if a given memory address points to a GC-able object
|> or not.

Exactly what I mean. If the GC has to scan the whole stack (and all the
statics and globals while we're at it), it's doing too much work. The
reference-count solution is more efficient than that, because the need
for GC is restricted to a small but important part of the program. The
idea of languages like C++ is to give the compiler the information it
needs to get the best performance out of the resulting code.

|> This may sound slow, but actually I've found KCL's garbage
|> collector to be quite fast.

Quite fast compared to what? In previous projects I've been involved with
(using C rather than C++) "malloc" and "free" were found to be too slow,
and were replaced by custom ones. I want this GC to clip along as fast as
possible.

|> The vital question is, can a scheme like this be made to work on
|> all architectures on which C++ could reasonably be expected to be
|> used?

If it can be made to work on one common architecture, it can probably be
tweaked for all. The vital question is, would it be useable?

|> I think you'd have to live with no compaction
|> at all:  Whereas it is fairly benign to mark an object because
|> an integer happened to hold its address, you wouldn't want to adjust
|> that integer when you moved the object!  You'd need special GC
|> pointers if you wanted compaction, and those would probably not
|> be practical.

This is why special GC pointers have been proposed in the first place.
If GC is in use, the programmer must accept the "no clever tricks"
constraint, which includes not passing pointers around disguised as
integers. And once that constraint is accepted, there may be no good
reason for not having compaction. My earlier post on this subject
contained some suggestions that would make the combination of GC and
existing libraries practical.

|> If you instead require *classes* to be declared GC, then there is no
|> point in declaring pointers to be GC as well since a pointer is GC
|> if, and only if, the pointed-to type is a GC class.  The problem with
|> this is, suppose you have a GC class which contains a string (i.e.,
|> a pointer to an old-fashioned non-GC'd array of chars).  Suppose you
|> no longer have any pointers a certain object of this class, but you
|> still do have a pointer to its component string.  You lose, if the
|> destructor for the class deletes the string (which it pretty much has
|> to do).  So a GC class could only safely contain pointers to other
|> GC classes, which rules out strings unless you also have GC arrays
|> of predefined types, which sounds too awkward to work.  Oh, well.

What you have described is a programming error. If a collectable object
contains such an old-style pointer, it is the programmer's responsibility
to ensure that the object will not be deleted as long as it is needed.
This in no way prevents us from having old style pointers in GC objects:
it's no different from the existing situation where a class contains a
pointer to a string.

|>   GC objects can be deleted, in which case any remaining pointers
|>   to the object become invalid and must not be used to dereference
|>   an object.

This would accord with existing C++ philosophy, but I don't see how
you could make a GC that's immune to dangling pointers. Anyone out
there know otherwise?

|> What if a pointer to a GC-able object is passed to foreign (non-C++)
|> code, which stashes it somewhere the C++ collector doesn't know to
|> look?  (All garbage-collecting languages have this problem, and as
|> far as I know all they can do is shrug and warn programmers not to
|> let go of the last C++ reference to an object if they know there
|> might be non-C++ references still lurking around.)

Hence the proposal for tagging GC-able objects, and having something
comparable to "const" which declares "I will not do any clever tricks
with this pointer, including converting it to an integer, performing
pointer arithmetic on it, storing it, etc". This only needs a change
to the C++ declarations of library functions, not to the functions
themselves. IMO this makes it feasible to mix GC and libraries.

|> What if you have virtual base classes, and there are only references
|> to the base part of an object?  The derived part of the object has
|> a pointer to the base part but not the other way around, so the
|> derived part might be collected in this case.  Can this ever be a
|> problem?

I don't think so, but I don't know the mechanics of inheritance (and in
particular MI) well enough to say. Comments from those who know the
dirty details of inheritance welcome!

|> Some food for thought,
|> 								-- Dave
|> --
|> Dave Gillespie
|>   daveg@synaptics.com, uunet!synaptx!daveg
|>   or: daveg@csvax.cs.caltech.edu

Much appreciated!

Bob.
-- 
bob_cannard@mentorg.com         "Human beings? ... Well, I suppose they are a
                                 form of life, even if they are unspeakable"
Exprssed opinions are not necessarily those of Mentor Graphics Corporation.