[Gc] integrating collection strategies

Boehm, Hans hans.boehm at hp.com
Tue Nov 22 17:34:51 PST 2005

You might be better off posting such general questions to
gclist at iecc.com.

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.

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.

It was mentioned that there is a tracing implementation of Boost
shared_ptr.  I would expect that to do something similar.

> -----Original Message-----
> From: gc-bounces at napali.hpl.hp.com 
> [mailto:gc-bounces at napali.hpl.hp.com] On Behalf Of skaller
> Sent: Tuesday, November 22, 2005 9:00 AM
> To: GC mailing list
> Subject: [Gc] integrating collection strategies
> 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++: https://felix.sf.net
> _______________________________________________
> Gc mailing list
> Gc at linux.hpl.hp.com 
> https://www.hpl.hp.com/hosted/linux/mail-archives/gc/

More information about the Gc mailing list