[Gc] integrating collection strategies

skaller skaller at users.sourceforge.net
Tue Nov 22 21:28:58 PST 2005

On Tue, 2005-11-22 at 17:34 -0800, Boehm, Hans wrote:
> You might be better off posting such general questions to
> gclist at iecc.com.

If this is part of:


I don't seem to able to find the subscription page. 

Excuse me if this is the wrong place to post .. however
there is a relationship to the Boehm collector lurking :)

> If I understand correctly, I think you are proposing to essentially wrap
> all GC roots in doubly linked list nodes, so that they can be easily
> removed when say, a container containing some of these roots is
> reclaimed using another mechanism.

Yes, however it isn't just a matter of the container
being reclaimed, it also includes, for example,
simply deleting the element from the container.
Or copying it -- eg typical use of STL::Vector et al.
[Hopefully Vector destroys objects past the 'used' mark
in the reserved storage :]

> I don't see why that wouldn't work as a root tracking mechanism.  The
> main down side is what you mentioned: Pointers in containers are much
> bigger, which also tends to reduce cache effectiveness, etc.

Yes. Hopefully -- for low level use, this won't be an issue.
For higher volumes it will, but hopefully there are more
dedicated alternatives eg: don't use STL, or, use Boehm

Felix collector is exact but has several serious problems:

(1) high overhead per object.

(2) Naive mark/sweep -- can't use copying collector easily
  due to C/C++ object model limitations

(3) Cannot scan machine stack, so cannot be run in 
  functional code

(4) Hard to interface to native C/C++/STL data structures

To solve these problem I plan to use a variety of techniques.

One is: Boehm in malloc/free replacement mode.
Another is: Native use of Boehm collector as well as Felix one
Third: replace Felix collector with Boehm collector.

These combinations can solve different problems in different
ways with different outcomes and have different implementation

In malloc/free (transparent) mode, there is no impact on
the Felix collector -- it just makes it easier to write
raw C level code without worrying about memory management.
Boehm will never free any Felix objects, because they're
always reachable from the Felix collector. However,
Felix objects freed by the Felix collector may still be
reachable from raw C code. These objects will not be freed
by Boehm, and they remain live because Felix uses 'free'
to deallocate them.

So in this mode, Felix will 'finalise' the objects and free
them to Boehm to manage. Thus, for example, an STL Vector
of pointers to Felix objects won't suddenly have dangling
pointers because Felix collector cannot find the pointers:
Boehm can. So it looks like in this mode I have to think
about disabling Felix finalisation, and delegate it to

However this model is very appealing, because it 

(a) works with (almost) arbitrary C code, including
leaky code (whether deliberately leaky or not)

(b) Can almost (if not totally) be loaded as an 
optional extra, transparently to the rest of the system.

The downside is clear: we're running TWO collectors.
The Felix one is fast because it is exact, but slow
because it is naive. Boehm is also slow because it
is conservative.

With some more work and integration, I can do better.
Boehm has the ability to record non-scannable objects,
and Felix knows which of its objects are. In particular,
Boehm can accept a bitmap to allow it to operate
exactly on particular objects. Unfortunately, the format
used is different to what I use (I use an array of offsets).

It is not possible for the compiler to construct a bitmap,
because the offsets are only known symbolically at Felix
compile time. So I would have to equip Felix with additional
language facilities to allow/enforce specification of
object sizes to permit this. The alternative is runtime
construction of the bitmap .. either on every allocation,
or once at startup (which leads to nasty questions about
relocatable code, thread safety, etc ..)

So there is a rather tangled but interesting web of
issues here .. especially when we get to multi-threading
on multi-CPU platforms under various OS (Linux, Solaris,
Win32, Win64, OSX ...)

In trying to get the x86_64 version of Neko running,
we were getting crashes which we eventually tracked
down to Boehm freeing live objects. This wasn't a bug
in Boehm -- there was a bug in the Neko C code which
accidentally chopped the high 32 bits off a 64 bit pointer.
Boehm couldn't see the pointers .. but they worked fine
since no one really has that much memory anyhow :)

Meaning: there is some effort getting Boehm to work
right, even when you're specifically using it and have
absolute control of everything. Unlike Neko, Felix is
designed to cooperate with raw C/C++ .. dynamic loading
and threads too. So it isn't clear what the tradeoffs
will be in which combinations of techniques: the Felix
collector has advantages in some applications, particularly
those running large numbers of independent microthreads,
with real time demands (since the collection can be localised).

John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

More information about the Gc mailing list