NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/lang/cplus/12619

Internet Message Format | 1992-08-19 | 3.5 KB

Path: sparky!uunet!synaptx!synaptics.com!daveg
From: [e-mail] (Dave Gillespie)
Newsgroups: comp.lang.c++
Subject: Re: Garbage Collection for C++
Message-ID: <[e-mail]>
Date: 20 Aug 92 09:25:59 GMT
References: <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]>
    <[e-mail]> <boehm.714158406@siria>
Sender: [e-mail]
Organization: Synaptics, Inc., San Jose, CA
Lines: 63
In-reply-to: [e-mail]'s message of 18 Aug 92 17:20:06 GMT

In article <boehm.714158406@siria> [e-mail] (Hans Boehm) writes:
>> But the test for whether or not a pointer points *somewhere* in the
>> GC-able zone of memory is trivial.

> This is highly system dependent.  In the latest versions of our collectors,
> things may well be the other way around.  You generally can't assume
> contiguity of the garbage collected heap.  You also don't really
> want any bookkeeping information on the pages of the garbage collected
> heap.  That way a page containing pointerfree objects is never touched
> during a collection.  Neither is an entirely empty page.  Thus we find out
> whether a page is in a GC-able zone by a lookup in a two-level tree.

I was actually thinking of this as within the bounds of "trivial,"
in the sense that one or maybe two fast memory lookups per pointer
validation is probably fast enough not to both anyone, especially
if, as you point out, the lookups are in a single table somewhere
rather than spread all throughout virtual memory.

> Determining whether a pointer points to the beginning of a small object
> doesn't really require a mod operation.  (We stopped doing that when
> we moved to machines with a really slow mod operation.)  There are typically
> a small number of distinct small object sizes.  You simply precompute
> a layout map for pages for each size.  [...]

Of course that's the way to do it; I should have put a little more
thought into it before posting.

You could also just round object sizes like 12 up to 16, and then
use bitwise operations.

> In general, aside from anomalies like slow mod operations, I conjecture that
> an important complexity measure for all of these algorithms is the number
> of cache misses.  [...]

All these page tables and layout maps would wind up in cache, which
is a big plus.

>>> [questioning why one would ever need to do explicit deletes]

>> Significant reduction in the number of GC's!  [Manually deleting
>> some objects means GC-inducing junk accumulates more slowly.]

> Presumably you're really worried about pause times, and frequency of pauses.
> That's usually a valid concern, but in the presence of concurrent or
> incremental collection, things become less clear.  Even in the presence
> of generational collection, it may not buy you much if the short-lived
> objects are the ones that are being handled manually.

Do you really think incremental or generational collectors are
feasible in C++?  I've never looked in the guts of one of these
collectors, but as I understand it they tend to depend on the
ability to move data around, and other things that a C++ collector
might not be able to get away with.  (C++'s use of pointers is so
unrestricted that it's a minor miracle it's possible to do garbage
collection at all...)

I would love to be proved wrong in this guess!

                                -- Dave
--
Dave Gillespie
  [e-mail], uunet!synaptx!daveg
  or: [e-mail]