Subject: Re: [boost] another approach to memory management that solves thereferential cycles problem
From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2009-02-24 05:40:47
> If you want people to take the trouble to look, a direct link (and a
> little more detail in your email about what you're doing) would help.
The code and readme can be found here (file mm.zip):
The trouble with shared ptrs is that cyclic references can not be reclaimed.
The problem can be solved using weak pointers, but this approach does not
scale well in big projects that evolve over time with different developers.
Sometimes the knowledge of cycles is lost during the transition from one
developer to the other.
The file above contains a test implementation of an idea for solving the
problem of cyclic references reclamation. The idea goes like this:
In order to solve the problem of cyclic references, a garbage collector that
scans the object graph for pointers needs to know the root set.
Unfortunately, this is not possible in c++ because the compiler does not
provide this information. Custom pointer classes can be used to register
pointers to a global pointer container, but then the problem is to identify
which pointers are roots and which are members of objects, so as that only
those pointers that are are truly root are registered as root pointers.
Even if we managed somehow to register pointers to the actual memory areas
they belong, the solution does not work with STL containers because the STL
containers themselves do not use these special pointer classes.
Another approach is possible that does not have these restrictions. Instead
of scanning an object graph from the roots, an object graph can be scanned
towards the roots.
For example, if we have the object graph (R is a root reference, A and B are
R -> A - >B
The traditional collector starts from R, then visits A and then B. But if we
represent the graph like this:
R <- A <- B
We don't need to register the root reference anywhere: we can simply start
from B, then visit A, then visit R: since R is a root, then A and B are
The provided code implements this with two classes:
1) a class 'ptr_base' that represents a ptr with a link to an owner object:
a) knows if it is a root class from the supplied owner object in its
constructor: if no owner is given, the ptr is root. Otherwise, it is a
b) it registers itself to the object it points to.
2) a class 'object' which:
a) contains a list of ptrs that points to that object. The list is
intrusive, using boost::intrusive::list, for performance reasons.
With these two classes, it is possible to traverse the graph of objects
backwards, towards the roots: if an object is not accessible from a root
ptr, then it can be collected.
A class ptr<T> provides a typed ptr that is derived from class ptr_base.
The cycles are broken like this: when an object is not accessible from roots
and still has pointers pointing to it, it means there is a cycle, and
therefore the list of pointers is cleared before deleting the object, thus
breaking the cycle.
The solution works with stl containers, because ptr<T> instances placed in
STL containers are root pointers, and therefore the objects in the container
are not collected until the container is deleted. The file contains an
example of using an std::list to keep the objects around until the list is
The idea is not considered a panacea for all memory management problems. It
is only complementary to shared ptrs and manual memory management.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk