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

Text File | 1992-08-18 | 3.4 KB | 73 lines

Newsgroups: comp.lang.c++
Path: sparky!uunet!decwrl!parc!boehm
From: [e-mail] (Hans Boehm)
Subject: Re: Garbage Collection for C++
Message-ID: <boehm.714158406@siria>
Sender: [e-mail]
Organization: Xerox PARC
References: <[e-mail]>     <[e-mail]>     <[e-mail]>     <[e-mail]> <[e-mail]>
Date: 18 Aug 92 17:20:06 GMT
Lines: 61

Some technical points:

[e-mail] (Dave Gillespie) writes:
>Also:  The trickiest part of a conservative GC like KCL's is checking
>whether a given word really is a valid pointer.  While this can be done
>fairly efficiently, it's still not lightning-fast; KCL has to do a
>modulo operation each time, for example.

>But the test for whether or not a pointer points *somewhere* in the
>GC-able zone of memory is trivial.  So if 90% of a program's allocation
>can use manual deletion, we can do that allocation in a different memory
>space and let the garbage collector do a trivial reject on 90% of
>the pointers (more or less).

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.

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.  Thus the pointer validity check is
basically a single table lookup, once you have the page descriptor
form the two level tree.

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.  The amount of memory you have to read seems to matter
more than anything else.  (Ben Zorn's measurements suggest something
like this, but I have no conclusive evidence that the above is true.)

>>|>  (3) Even in a system with (conservative) GC, you can still return
>>|>      memory to the system using some form of unsafe "free" or "delete"
>>|>      (e.g., as provided by Boehm's collector).

>> Agreed, but there has to be some point in doing so. I see two possible reasons
>> for having an explicit delete:
>> ...
>> Any others?

>The best one (IMHO):

>Significant reduction in the number of GC's!  Again let's suppose 90%
>of our allocation can be deleted manually.  That means that, without
>doing any GC's, the amount of junk in memory grows only 10% as fast
>as with no deletion at all.  So, with GC's, it takes ten times as long
>to accumulate enough junk to cause another GC.

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.

Hans-J. Boehm
([e-mail])