Re: GC a quality of implementation issue

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


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


mps@dent.uchicago.edu (Michael Spertus) writes:
>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 not clear to me. Assume that pointers may point to places
other than the collected heap. (If not, then you incur other costs
that need to be considered.) Now consider the cost of traversing
a cons-cell. In the method case, you need a method invocation, plus two
checks that the pointers point to the collected heap. With
nonprocedural type descriptors, you replace the method by a few
bit manipulations. In the conservative case, you replace the
method invocation by slightly more involved pointer validity tests
and some operations to determine the size. Admittedly, you need
something similar to a method lookup in any case, to retrieve the
descriptor. But you save the indirect procedure call, register saves,
etc.


Using mark methods also costs code size. It becomes expensive in
either code size or mark time if objects with embedded subobjects are
frequent. (Do you replicate the mark code or use a procedure call?)
Separate compilation issues may get in the way of optimizing compiler
generated mark procedures. You can optimize descriptors at run-time.


>This is especially true if you can shift that work to times where
>you are waiting for a mouse event or key click.


This seems like an orthogonal issue. I can also interpret a table while
I'm waiting for a mouse event.


Hans-J. Boehm
(boehm@parc.xerox.com)


--

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