Re: GC a quality of implementation issue

boehm@parc.xerox.com (Hans Boehm)
Sat, 11 Jun 1994 00:07:24 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: boehm@parc.xerox.com (Hans Boehm)
Keywords: GC
Organization: Xerox Palo Alto Research Center
References: 94-06-016
Date: Sat, 11 Jun 1994 00:07:24 GMT



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)


--


Post a followup to this message

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