Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!mcsun!ukc!cam-cl!scc
From: scc@cl.cam.ac.uk (Stephen Crawley)
Newsgroups: comp.sw.components
Subject: Re:  Re:  Re: Real-time Garbage Collection
Message-ID: <900@scaup.cl.cam.ac.uk>
Date: 20 Sep 89 22:30:10 GMT
References: <896@scaup.cl.cam.ac.uk> <6519@hubcap.clemson.edu>
Sender: news@cl.cam.ac.uk
Organization: U of Cambridge Comp Lab, UK
Lines: 78


From Bill Wolfe:
>>>>> It's safe to [reclaim a dynamicly allocated ADT]:
>>>>>  1) When the variable goes out of scope
>>>>>  2) When the programmer specifies that it's to be destroyed sooner.
>>>   [...] the basic thrust of the position is that the programmer
>>>   should generally not use pointers explicitly; rather, the use of 
>>>   pointers should be made safe via encapsulation within a secure ADT.
>>    
>> It makes no difference whether references to an ADT is implicit 
>> or explicit.  The ADT cannot know whether or not the application 
>> that uses it still holds a reference to a given instance.
>
> The pointers are INTERNAL to the ADT, and the user will never
> see them.  When the ADT goes out of scope, it dies just like 
> any predefined type would.  We are considering here an ADT which 
> is declared at the beginning of a (procedure, function, block).
> This ADT will do dynamic allocation INTERNALLY so as to facilitate
> its own expansion and contraction as necessary.  Upon block exit, 
> the ADT's destroy procedure will be invoked, and all the space
> occupied by the ADT will be released.


OK ... in the trivial case your scheme does work.  The conditions
for it to work include:

a)	NO references to the ADT are passed out of scope.

b)	the scope exits before you run short of space.

c)	the programmer (i.e. the application!) does not incorrectly tell 
	the ADT to release an instance too soon.

If either a), b) or c) do not hold the program dies.  Condition a) can 
be shown to be true, provided that you can trace all of the side-effects
that occur within the scope and PROVE that they do not violate the
condition.  Condition b) is hard to reason about formally except to the
extent that it is possible to place an upper bound on the amount of 
memory allocated within the scope.  Condition c) is virtually impossible
to reason about ... unless you do something drastic like forbidding
all side-effects.

There are other problems with your scheme:

  o  Point 2) is in fact the application taking a hand in an ADT's 
     storage management ... something that he has been saying is
     unnecessary.  [If you leave out 2), then your scheme is equivalent
     to a stack based storage management with an extra stack!]

  o  GC'ed memory management can reclaim junk (heap nodes that are no longer
     needed) whenever it runs out of space, whereas a scope based scheme
     can in general only identify and hence reclaim junk on scope exit.
     In other words, scope based reclamation of memory will in general 
     need more memory.

Finally, don't forget that the case where condition a) is not true; i.e.
some of the dynamically allocated ADT instance are passed out of scope
either explicitly (as a result) or implicitly (by side-effect).

----
  
This whole GC versus non-GC debate seems to hinge the following trade-off.
Do we want programs that

  are slower (by say 25%), but are intrinsicly free of a large class of 
  storage management errors.
  
or

  are usually faster (not always), but may use more storage, may have 
  potential storage leaks and other storage management bugs, and which 
  arguably take longer to develop.
  
----

I would recommend that people should read Chapter 16 (Memory Management)
of Bertrand Meyer's book "Object Oriented Software Construction" for a
calm and rational analysis of the pros and cons of various methods of