[Gc] integrating collection strategies

skaller skaller at users.sourceforge.net
Tue Nov 22 09:00:10 PST 2005


Hmm .. I have a problem and a possible solution. Perhaps
someone can comment? [This question is generic, not about
Boehm collector specifically]

The problem: I have a system which uses an exact (precise)
collector. But I want to put pointers to objects managed
by the collector into STL containers (generally, any
C++ polymorphic container).

One way to do this is to register the pointer as a root
first, but that sucks. More precisely, it simply does not
work, because the object will never be collected whilst
it is a root, and there is no way to know when it is
unreachable.

I know of two solutions:

(a) don't make the pointer a root, just forget about it.

This is the best solution when you can be sure the
native system ensures the pointer is reachable whilst
a copy is in the external data structure. 

(b) use ref counting. This is fine provided there are 
no cycles.

but both have onerous conditions. I have devised a third
solution which is fully general! It handles a native
data type T, provided you're happy with containers of
pointers (rather than copies of the object), it has
O(1) performance, and it handles cycles.

The idea is quite simple: use a C++ smart pointer containing
3 pointers: the pointer to the object, and a pair of pointers
implementing a doubly linked list.

Whenever you wrap a native type up to pass to foreign C++ container, 
the new object is added to the head of the list. The list
is universal. Copying, assignment, and deletion operators
ensure the list tracks all the copies.

The list itself is scanned by the collector, but the 
smart pointer objects are not collected.  This allows the 
collector to find all pointers to collectable objects.
[Of course the object pointer to by the smart pointer
IS collected]

The implementation is monomorphic (it is the same for
all data types T, because all pointers are the same).
It does not require any custom allocators. It is extremely
fast (O(1) with no significant overhead). The main downside
is that it requires 3x the usual amount of storage.

Have I missed something? Will it work? Is there any
better technique?

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



More information about the Gc mailing list