From: jimad@microsoft.com (Jim Adcock)
Subject: Re: Garbage Collection for C++
Date: 25 Aug 92 18:54:58 GMT
Organization: Microsoft Corporation

In article <boehm.714410546@siria> boehm@parc.xerox.com (Hans Boehm) writes:
|jimad@microsoft.com (Jim Adcock) writes:
|>In generation schemes, both long-lived and short-lived objects have
|>allocation and deallocations costs that are very very small -- IE "0"
|>There are significant allocation and deallocation costs only for object
|>that fall in between these two extremes -- objects that live to be middle
|>aged.  And the cost of these objects is not really the cost of allocating
|>or deallocating them, but rather the cost of keeping them young.
|
|Could you clarify your accounting for long-lived objects here?  Are you
|assuming that you know at allocation time that the object will be
|permanent?  Otherwise it must be copied at least once out of the youngest
|generation.  That's certainly nonzero cost.  Furthermore, it will probably
|be copied (or traced) several more times as the result of full collections.
|(If I don't know that all my objects are essentially permanent, and I
|see my heap growing, I presumably have to initiate full collections
|occasionally.)  In addition to this, I need some way of tracking
|pointer stores into the old object.  I would claim that all of this adds
|up to significantly more than malloc/free time for the object.

My accounting is simply that the cost of keeping an object alive is
not the cost of either allocating or deallocating the object.  Before you
cry "foul" please note that non-moveable-object memory management schemes
*also* have a cost of keeping objects alive -- namely their non-locality
of reference leads to costs of cache misses, page turns, and ultimately
thrashing on heavily loaded systems.  Such costs need to be factored into
the cost of any memory management scheme -- but estimating such costs is
extremely variable depending on a given system and how that system is loaded.
Whereas the costs of allocating and deallocating can be more reasonably
estimated.

|Generational (esp. copying) collectors win dramatically on short-lived
|objects, provided you have some efficient way of tracking stores
|into old objects.  Fortunately most objects fall into this category
|for most programs.
|
|(Ben Zorn has some measurements that substantiate this for some
|interesting C programs.  It is clearly the case for all known
|Lisp and Smalltalk implementations.)

I've found surprisingly similar results on a limited number of C++ programs
I've tested.

|A generational copying collector is probably the worst possible choice if
|all your program allocates are large long-lived bitmaps  (and indeed
|generational copying collectors usually treat such things as a special
|case).

But such cases can already be well handled in C++ using reference counting
schemes.  Again, I see a Modula-3 like approach where classes of objects
are either GC or not GC -- and the GC class objects are movable.  Backwards
compatibility is maintained because adding GC'ed classes is a pure extension.
Moveable objects need to be supported not merely for GC, but for more 
interesting problems of distributed networks, persistence, ODBMS, etc.

Newsgroups: comp.lang.c++