Re: Garbage collection (was a spinoff of a spinoff of a GA

[eachus@spectre.mitre.org (Robert I. Eachus)]

In article <JSA.96Oct22152111@alexandria> jsa@alexandria (Jon S Anthony) writes:

   > > Choice Two (in the spec): 
   > >   -- If you intend to use this data type, you had better ensure
   > >   -- that your compiler has a good garbage collector, or get an
   > >   -- add-on that can work with your compiler's allocation
   > >   -- methods.

   > Forget the "add-on" - that will at best be a conservative collector.  For
   > the precise collector:

   > Pro: ...
   >	Faster - allocations can be _much_ faster and collections can be
   >	much more efficient than good ol' "free".

   >	Works across the board (no need for special casing various situations)

   You must have been smoking some good stuff.  Precise collectors can
do the later, but never the former. Think for a second, any reclamation
the garbage collector can do, the free routine can do as well, without
the memory scan for live references.

  > > Choice Three (in the BODY):
  > > 
  > >    procedure Finalization (...) is
  > >    -- this will ensure that cleanup cannot be forgotten.

  > Con: Doesn't work everywhere

  >	Expensive (in time and space)

  >	Requires you to roll your own managers per type per application (but
  >	in those cases where it doesn't work, need to augment with other stuff
  >     - e.g. your own storage pools and management...)

  > > What are the cases Finalization doesn't cover?  (Other than those the
  > > programmer DECIDED not to apply it to.)

  > Lots's of places.  Finalization works pretty darn well for _stack_
  > allocated things, but pretty poorly (even not at all) for long lived
  > shared heap allocated things.  Since the latter are very important in
  > most large scale programs of any note, ...

    Let's take the absolute best example of a structure that "requires"
garbage collection an arbitrary graph consisting of nodes with
arbitrary numbers of edges, and cycles allowed.  Had to implement one
of those recently, and the requirements allowed nodes to be moved from
one graph to another.

   The finalization routine took five lines, and neat trick was in the
Adjust routine.  On assignment, a node (and all the nodes reached from
it) was given a new generation number (always incremented), positive
for the node assigned, and negated for all nodes reachable from it.
From a garbage collection point of view it was "extra overhead" but it
allowed me to do other operations such as reachability more
efficiently.  (You can't reach a node with a lower absolute generation
number.  The biggest win is that you only have to check against nodes
you have visited before with the current generation number.  Beats
marking and unmarking and allows more than one such operation to be
conducted simultaneously.)




--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...