Re: [boost] another approach to memory management that solves thereferential cycles problem

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.

Certainly.

The code and readme can be found here (file mm.zip): 
http://www.boostpro.com/vault/index.php?PHPSESSID=843094baef93383a0caec167435795b3&direction=0&order=&directory=Memory

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 
objects):

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 
reachable.

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 
member ptr.
    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 
destroyed.

The idea is not considered a panacea for all memory management problems. It 
is only complementary to shared ptrs and manual memory management.