Garbage collection and quality of implementation issues

A garbage collector deletes objects it is sure will never be needed. The
definition of sure is a quality of implementation issue as long as the
collector never deletes anything it shouldn't have.


Thus a null collector, one that never deletes anything, is a kind of
garbage collector. It is very fast since it does nothing but does a very
poor job of reclaming space. For some programs a smart optomizer might
substitute the null collector. This is especially true if the smart
optimizer was a human or ran after program measurment.


A conservative collector never deletes anything that even appears to have
a pointer aimed at it. If a float looks like a pointer that is enough to
protect what that psudo pointer aims at. This is poor at reclaiming space
but has the advantage of working with languages like C which have
ambiguous data structures such as unions and unstoppable memory moves and
casts.


Better is a collector which understands data structures because it is
built into the language. An OO way of looking at it is the collector asks
objects what other objects they need to keep around. The method which
answers that question (I call it a markRefs method) is built by the
compiler. The markRefs method is often one method that uses tables but
those tables can be projected into code for speed.


This way of looking at it allows a user defined markRefs method. This
would allow ambiguous data structures, calculated pointers etc. It can
also import human knowledge of the program and expand the class "things
the collector is sure will never be needed".


Consider a large array used as a stack. A generated collector will have to
scan the entire array for pointers keeping many objects alive that will
never be reached. A user defined markRefs method for the stack would treat
it as a stack following only pointers below the stack top.


The users can import any knowledge they have. If the collector calls the
destructors of deleted objects it becomes even more usefull to have user
markRefs methods. Now the user can mark objects that are logically needed
by the program allowing the collector to delete others that can and even
would be reached.


Consider a two pass compiler. During the first pass it builds a symbol
table using things like header files. Anything on the table needs to be
kept. References from the parse trees to the symbol table do not need to
be followed as those objects will be kept alive anyway. During the second
pass being on the symbol table should not be enough to keep an object
alive there should be some reference to it from the parse trees. Thus the
markRefs for the symbol table becomes null in the second pass while the
markRefs for the parse trees now tells the collector about needed table
entries. When an object is deleted from the symbol table by the collector
its destructor is called removing it cleanly from the table.


In this case the collector is removing things that are not only physically
reachable they would have been traversed by the table lookup functions.
But it is doing a super smart job of removing things that are no longer
needed by the program because it has used the programmers notion of needed.


BTW some of this assumes a non moveing collector where the collector needs
to be informed of every object but not every pointer as in the Henry Baker
treadmill algorithm.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.