[boost] request for discussion - yet another approach to automated memory management that solves the cycles problem and is very efficient

Subject: [boost] request for discussion - yet another approach to automated memory management that solves the cycles problem and is very efficient
From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2009-02-26 19:07:04

Dear boost members,

The file 'mm2.zip' (in boost vault/memory) contains yet another solution 
for automatic memory management.

The solution has the following attributes:

1) it solves the problem of cycles.

2) it releases resources deterministically.

3) it does not scan the graph of objects for reachability. It uses 
simple numeric values (i.e. keys) to determine if an object can be 
collected or not.

The idea is very simple: pointers obtain keys during their construction 
(a simple global variable that is incremented). The key remains constant 
throughout the lifetime of a ptr.

During pointer release, the pointers that point to an object are 
scanned: if there is no pointer that points to the object that has a 
lower key from the key of the releasing pointer, then the object can be 
deleted.

The pointer semantics are normal C pointer semantics, except for the 
construction: the solution requires that pointers that are lvalues 
should obtain a key before the heap object that they will be assigned 
to. i.e. you can't do this:

     ptr p1 = new object;

You have to do this:

     ptr p1;
     p1 = new object;

All the operations have O(1) complexity, except the release operation, 
which has O(N) complexity, whereas N is the number of pointers that 
point to an object. Practically, the complexity is minimal, because it 
is rare to have that many different pointers to a single object (I think 
:-)).

I have no idea if it works for all cases. The file 'main2.cpp' contains 
a lot of tests, which all pass.

I have also included the benchmark of the Boehm GC modified to use my 
special ptr classes. In my machine, an Athlon 64 2.2 GHz, the benchmark 
is executed, using boost pools, at roughly 1900 milliseconds, whereas 
the Boehm gc benchmark, using the Boehm gc collector, is executed at 
roughly 1200 milliseconds (and the Java benchmark at roughly 600 
milliseconds).

The amazing thing is that it looks like it works, but I am not sure. I 
am sure there is a catch :-).