[gclist] Finalization and object orientation.

[Charles Fiterman]

At 09:48 AM 3/31/97 -0500, you wrote:
>At 07:21 AM 3/31/97 -0600, Charles Fiterman wrote:
>>Great tell me about this method topoSort() does it detect cycles. Where
>>do I get source.
>
>Well, this explains many things.  The most irritating thing about
>your proposals for finalization is that you seem unconcerned by the
>problems pointed out by intelligent, experienced people, as if they
>were merely a bunch of lazy whiners.  topoSort is topological sort,
>and yes, it detects cycles.  Any introductory computer science text
>on algorithms ought to explain it.

I found it there. The overhead was extreme. This is why I haven't
found any collectors that actually do that. Further I've concluded
that finalizer order cannot be deduced from pointers its purely in
the semantics of the mutator. If a buffer object points to a
file object it seems natural to finalize the file object first.
But there is no reason to assume the exception for writing to a
finalized file object is less valid than writing to the file object.

In the case where a list of finalizer objects each writes to a
report only knowledge of the desired order of the report determines
the correct order of the finalizers.

So the topological sort simply allows me to do something useless
in a totally inefficient way.

>There's big problems with your position that finalization ought
>to be certain, timely, and "simply another method".  Certain and
>timely finalization also requires certain and timely collection
>of all garbage. 

By timely I mean not insanely untimely. I keep saying that. By insanely
untimely I mean it can't make finalization impossible in the real world. 

>This is difficult to guarantee; it is essentially
>impossible without a cooperating compiler.  Your proposal that
>finalization is also "just another state change" also conflicts
>somewhat with these requirements, because this (to me) seems to 
>conflict with the goal of timely finalization. The reason of this
>conflict is the possibility of "resurrection" -- if a finalizer
>places an object, or a referenced object, within some data structure
>referenceable from live memory, it potentially converts almost-garbage
>into non-garbage.  If finalizer are run in random order (good for
>timely finalization) then the resurrected object may or may not have
>been finalized.  Previously, only non-finalized objects could have
>been seen by the mutator, but now it can see finalized objects
>and non-finalized objects.  This also breaks encapsulation, because
>if I use a Foo in my data structure, if I choose to resurrect that
>Foo, I had better know whether a finalized Foo can be used for anything
>at all.

Safe finalization implies the existence of post finalized objects
visible by the mutator, assuming finalizers are run at all. If finalizers
get run a finalizer can resurrect its object by saving a pointer to it.
The problem is entirely the result of a safety requirement combined
with running any finalizers at all.

Ordering finalizers only adds the cost of a sort assuming you have
a finalizer order number. The efficiency cost isn't in the sort its
in the safty requirment which puts a write barrier on pointers or
requires that the mark phase be rerun after finalizers are run.

A mark and sweep alternative is.

do {
  run mark phase
  if (unmarked finalizer objects) {
     sort unmarked finalizers
     run finalizers
     continue
  }
  break
}

Note if finalizers clear root pointers this can loop. This might be 
prevented from looping by some pass counting logic. The write barrier
approach never loops.

>The alternative I see is to decide that you have just carried a good
>idea to a ridiculous extreme -- finalizers ought to be employed for
>a FINAL state change, finalized objects ought to be in some sense second
>class, and finalizers should not resurrect garbage.  This is another
>set of consistent positions, that actually make it more possible to
>provide timely finalization (run the finalizers in any order, don't
>worry about resurrection), and that is consistent with how finalizers
>are specified in Java (the fact that they can be run automatically only
>once is a strong clue that you ought not resurrect objects, because
>the resurrected objects will be in a weird state.  Just because the
>language definition specifies how a corner case will behave, does not
>mean that it is a good idea to program using that corner case).

An easy alternative is to say that finalizer order is undefined. But
we can't stop finalizers from resurecting objects without having pointers
to freed storage or not running finalizers.
			-  
Charles Fiterman		Geodesic Systems
414 North Orleans Suite 410	Phone 312 832 1221 x223
Chicago IL 60610-4418		FAX   312 832 1230
				http://www.geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.