GC a quality of implementation issue

mps@dent.uchicago.edu (Michael Spertus)
Wed, 1 Jun 1994 14:01:37 GMT

          From comp.compilers

Related articles
GC a quality of implementation issue mps@dent.uchicago.edu (1994-06-01)
Re: GC a quality of implementation issue boehm@parc.xerox.com (1994-06-11)
| List of all articles for this month |

Newsgroups: comp.compilers
From: mps@dent.uchicago.edu (Michael Spertus)
Keywords: GC
Organization: Dept. of Mathematics
Date: Wed, 1 Jun 1994 14:01:37 GMT

From: jgmorris+@cs.cmu.edu (Greg Morrisett)

>>No. All power involves risk. I believe that user defined markRefs
>>functions give enough power to justify their risk. In practice users are
>>very carefull writing such things.

>Wait a minute. If programmers are pretty good about writing such things,
>why don't we stick with malloc/free? I mean, can't I just define
>free(obj) to mean overwrite the GC method for obj so that it marks nothing
>when invoked?

We allow malloc/free. There are often times when it is the best and most
efficient and clearest way to control storage. But if you want to write
a method that builds some data structure and you want that cleanly used
garbage collection is the only way. Without garbage collection the user
must figure out when to free. There is a big difference between languages
where you can append two strings and use them and languages where you
must allocate the storage for the result and figure out when to free it.
I think that the line between high level languages and low level languages
is garbage collection.

>I agree that GC methods are a good idea -- I just think that punting on
>the safety issue _entirely_ is going pretty far. I'm asking if there
>isn't some way to verify that, say, 90% of the user-defined markRef
>methods aren't sound.

If their is no difference between the compilers generated markRefs and
the users written one there is no reason for the user to write one. Thus
any rational user markRefs would produce at least one warning from a
robust warning giver. Consider the stack example yes the user could zero
all pointers on poped portions of the stack. But that is extra work and
so is the collector's reading those zeroed pointers. But a user markRefs
for the stack saves both. A robust warning giver would have to see the
user markRefs as a problem as it is ignoring all these pointers.

>There are two other problems with user-defined GC methods. One is closely
>related to finalization methods: GC/finalization methods are invoked
>_asynchronously_, in no order that the programmer can control. The
>asynchrony can be a real problem. What do you do if the GC method is
>invoked in the middle of another method? In particular, suppose that
>interrupted method uses derived pointers in temporaries?

We have a function called gc_minWork in which the user gives an atom of
time to the garbage collector, gc_minWork returns a one when there is no
work left to do (oversimplification here of unimportant matereal). The
user can call gc_minWork when waiting for a mouse click, etc. If the collector
is given enough time it will never take off and slow you down. We also have
a transparent mode where the collector receives n gc_minWork calls for each
object declared collectible. n = 1 is usually a good number. A gc_minWork
call is esentially a call to one markRefs method plus a little other work.

Yes the hard to predict invocation of object finalization is a problem.
If you have to predict when an object will be finalized you shouldn't give
it to the collector to manage and free at its convienience.

>The other
>problem is time overhead during collection. Invoking a method for each
>object to be marked/scanned can be _very_ expensive.

No matter what form of garbage collection you use other than the null collector
you must somehow ask objects what they use. Calling a function is less overhead
than intrepeting a table or examining every word of an object for potential
pointers. This is especially true if you can shift that work to times where
you are waiting for a mouse event or key click.

We are building a language were everything is on top of the table with no
exceptions. Doing this well requires choosing the pieces very carefully because
they all become part of the language definition in some way. The cleanest
way to describe garbage collection in an OO language is to say that the
collector asks each object what it needs to keep around. This description
allows the user to change the collector in usefull incremental ways.
So does gc_minWork and transparent mode.

Post a followup to this message

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