Re: Garbage Collection

[billwolf@hubcap.clemson.edu (William Thomas Wolfe,2847,)]

From article <4206@enea.se>, by sommar@enea.se (Erland Sommarskog):
> I'm trying to get Bill Wolfe to explain how he his deallocation-on-
> block-exit scheme would work in an example I had. [...] 
> I repeat the exmample with some clarifcations.
> 
> We have:
>    Generic 
>       Data_type is limited private;
>       Procedure -- Assign, "<" and ">" 
>    Package Tree_handler
>       Tree_type is private;
>       
> Assume further that we instantiate this package with Some_access_type, 
> it could be an imported limited type, it could be a locally defined.
> Then we have the procedure:
> 
>     Procedure Insert_data_to_tree(Tree : in out Tree_type;
>                                   Data_of_some_sort : in Any_type); 
                                                           ^^^^^^^^

                                        You mean Data_type, right?

>     Reference : Some_access_type;

                     How about "access Data_Type"?  It is illegal to
                     reference Some_access_type directly, since it
                     is not a generic formal parameter.  We can only 
                     reference Data_Type, which in this particular 
                     instantiation will refer to Some_access_type.

>     Begin
>        Reference := new Some_type;  -- Or subprogram call for external type

           Let's say "Reference := new Data_Type;", to make things legal.

>        Prepare(Reference, Data_of_some_sort);

           Prepare is not a generic parameter; I frankly don't see
           why you need a call to such a procedure anyway.  I'll replace
           it with "Assign (Reference.all, Data_of_some_sort);". 
 
>        Insert(Tree, Reference);

           What exactly is Insert doing?  It would make more sense to write:

            begin
              -- find the node for which the new value is to
              --   become either the leftmost or rightmost child,
              --   create a new child, and assign the new data value
              --   to the appropriate field of the new node.  At some
              --   point in this process, there may be some pointer 
              --   manipulations; it really doesn't matter where.  But
              --   let's assume the tree is initially empty.  Then, 
              TREE := new BINARY_TREE_NODE;
              ASSIGN (NEW_NODE.DATA_VALUE, DATA_OF_SOME_SORT);
              -- since pointer types are automatically initialized to
              --   null, we don't have to worry about initializing
              --   the left child and right child fields, so we're done.
           end INSERT;
 
>     End Insert_data_to_tree;
>     
> The Assign procedure which we provide when we instantiate the tree handler 
> is simply:
>    Procedure Assign(A : in out Some_access_type; B : in Some_access_type) is
>    Begin
>       A := B;
>    End Assign;
>    
> Now, what happens with Reference.all on exit of Insert_to_data_tree, with    
> your scheme? (Assume there is no user-written DESTROY procedure.) Would
> Reference.all be deallocated although there still is a living reference  
> to it in Tree? 

      First of all, I always require the user to pass in a DESTROY procedure.
      So my initial reaction is that this is a malformed ADT.  But let's
      assume the existence of such a malformed ADT.  We'll assume further
      that we have a pointer variable such as Reference.  Destruction of
      a pointer consists simply of destroying the pointer, and does not
      imply destruction of what it points to.  Destruction of an ADT
      which happens to be implemented via an initial pointer (as in Tree)
      does imply destroying the transitive closure of what it points to.

>>> I forgot: When the system chokes with "heap full" and you as a maintainer
>>> is trying to find where all space is being wasted. With garbage collection
>>> you at least know that all this memory is being used. Without, you don't 
>>> know if it is just memory leakage or real overuse.
>>
>>     Advanced debugging tools should be used to address this issue.
> 
> So why can't these "advanced debugging tools" be used to "pin down
> the exact state of the system" when we have garbage collection?

     They can, but only the exact state of one particular execution,
     and not the precise state of the theoretical system in general.

     A debugging tool exists simply to help you find errors which show
     up in one particular situation.  It does not help you understand
     the piece of software as a theoretical structure, which is essential
     if one is to perform nontrivial modifications to a system.  It is
     this theoretical imprecision which causes problems.

> 
>>   I'm quite aware of Eiffel, and I have just shown (in another article)
>>   how reliance upon garbage collection is a sure way to get your ADT
>>   rejected by users who are programming critical applications.  This
> 
> There is good chance that your ADT will be rejected anyway. The critical 
> developper looks at you and says: "You use Unchecked_dellocation? Sorry, 
> then I can't use your ADT. Memory fragmention will cause too great a 
> time penalty when the system have lived for a while." 

     Allocation/deallocation routines exists which automatically
     collapse adjacent blocks of free storage into larger blocks,
     which minimizes the problem.  In general, this is the *compaction*
     question, which is orthogonal to the GC question.  It is properly
     directed at the allocation/deallocation system and not at the
     ADT designer.  It is conceivable that an allocation/deallocation
     system could be designed in such a way as to spread the costs of
     compaction evenly over each allocation/deallocation request, thus
     meeting all requirements at the same time. 


                                            Bill Wolfe

                                    wtwolfe@hubcap.clemson.edu