Re: 'conservative' GC == 'risky' GC

wright@asia.cs.rice.edu (Andrew Wright)
Mon, 23 May 1994 14:58:22 GMT

          From comp.compilers

Related articles
'conservative' GC == 'risky' GC hbaker@netcom.com (1994-05-21)
Re: 'conservative' GC == 'risky' GC jgmorris+@cs.cmu.edu (1994-05-22)
Re: 'conservative' GC == 'risky' GC wright@asia.cs.rice.edu (1994-05-23)
Re: 'conservative' GC == 'risky' GC pardo@cs.washington.edu (1994-05-24)
Re: 'conservative' GC == 'risky' GC tmb@arolla.idiap.ch (1994-05-25)
Re: 'conservative' GC == 'risky' GC markt@harlequin.co.uk (1994-05-26)
Re: 'conservative' GC == 'risky' GC jgmorris+@cs.cmu.edu (1994-05-27)
Re: 'conservative' GC == 'risky' GC boehm@parc.xerox.com (1994-05-27)
Re: 'conservative' GC == 'risky' GC chase@Think.COM (1994-05-26)
[5 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: wright@asia.cs.rice.edu (Andrew Wright)
Keywords: GC, C
Organization: Rice University, Houston
References: 94-05-084
Date: Mon, 23 May 1994 14:58:22 GMT

hbaker@netcom.com (Henry G. Baker) writes:
>What's a 'Conservative' Garbage Collector?
>
>It has recently become clear from various postings on the Internet that
>the phrase 'conservative garbage collector' is not being used correctly.
>This is especially distressing, because people are starting to use
>'conservative' garbage collectors, and they have not been properly
>informed of their characteristics and _risks_. In this post, I would like
>to clarify the meaning of this phrase, and possibly some other
>misconceptions about 'garbage collection' in general.


I agree with Henry's discomfort with some current uses of the term
"conservative collector", but I disagree with his correction:


>_However_, a 'conservative' GC _can fail_, and _can produce dangling
>pointers_. This happens when some object is accessible from a root that
>isn't _evident_ in the ambiguous root set. This can happen, for example,


I think the term "conservative collector" should be reserved for a
collector that truly is conservative: it begins collection with a
conservative root set, and finds pointers conservatively. From Boehm &
Weiser: "We assume that for every accessible object there is an accessible
pointer to the beginning of the object". They also note that their
collector requires both the user and the compiler to not encode pointers
"in clever ways" nor refer to objects solely by pointers to the middle of
an object.


>if an object is directly addressed by a RISC architecture by loading a
>half-word constant into a register, and then later addressing the object
>via a half-word offset to the constant in the register. Note that a
>proper pointer to the object _never_ appears in any register (except for
>an inaccessible memory address register), and so the object may be
>erroneously reclaimed by a 'conservative' garbage collector and later
>cause the program to crash due to a doubly allocated object.


Such a compiler does not satisfy Boehm & Weiser's constraints. So I would
say it is not a conservative collector. With a little cooperation from
the compiler, this particular problem is easy to fix. Include in the
image a static data area of full pointers to the various objects loaded by
code, and include this static area in the root set.


>Thus, the word 'conservative' in the phrase 'conservative garbage
>collection' is a _misnomer_ in the sense that it isn't conservative at all
>-- a conservative garbage collector is actually taking _risks_. In this
>sense, the phrase 'conservative garbage collection' should really be read
>as 'risky garbage collection'.


It may be that there are some garbage collectors that are being called
"conservative" when they aren't. I agree that we should be careful about
what we call a "conservative collector".


>On the other hand, _as a temporary measure_ until C and C++ can get their
>act together to start supplying proper root information to memory
>managers, conservative garbage collection may be very useful in a
>_development_ or _research_ environment. _Just don't get too comfortable,


Again, we must be careful about indicting C and C++ systems as a whole.
Certain C/C++ implementations may meet the constraints required by
conservative collection. Others may not.


Andrew Wright
--


Post a followup to this message

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