Re: [boost] Proposal for a precise STL-based garbage collection library

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-03-12 08:44:03

On 03/12/2007 06:49 AM, Giovanni Piero Deretta wrote:
 > On 3/12/07, Achilleas Margaritis <axilmar_at_[hidden]> wrote:
[snip]
 > It seems awfully slow (at least without testing it :)).  Do you have
 > any benchmark?

Achilleas, many years ago I had a benchmark for comparing precise
refcounted pointer gc with cycle detection against the Boehm gc.  It
used a specialized smart ptr for both Boehm and another smart ptr for
the refoucnted gc.  If you think you could use it, I could post to the
vault.  It also did poorly vs. Boehm w.r.t. time.  However, the code
was streamlined to speed it up and merged with David Held's policy_ptr
library:

http://boost.cvs.sourceforge.net/boost-sandbox/boost-sandbox/boost/policy_ptr/

However, I've not run any benchmarks.

The version in boost sandbox under policy_ptr has been
adapted on my hard-drive to use a successor to the fields_visitor
library to precisely enumerate the smart ptrs contained in a
"registered" class.  A class is registered by creating an instance of
singleton template with the class as the template argument (see
SELECTED_FIELDS_DESCRIPTION_OF_RECORD in:
<boost-sandbox>/boost/fields_visitor/fields_visitor.hpp
)

 > Wouldn't a reference counted pointer with cycle detection be much
 > simpler AND faster? If you can control the allocator as you do (and
 > thus allocate the refcount together with the object itself) and you do
 > not need to be thread safe, this be much faster than your approach.
 >
 > IMHO, instead of explicitly marking every gc pointer, every
 > potentially gc'ed class should provide a visitor function that
 > provides an iteration interface over all pointers contained in an
 > object. You store the address of such a function right before the
 > allocated object (like a type tag).  The function would also provide a
 > destruction hook and store the size of the allocated object. If you
 > store a run of same type objects, you only need to store one pointer
 > to the visitor at the beginning of the tag.

Giovanni, this is almost what the aforementioned policy_ptr library
does when the precise smart pointers are used.  However, instead of
storing the visitor function pointer inside the allocated memory, the
precise smart pointer, because it knows the type of pointee and,
presumably, the pointee class is registered (see above), it knows the
location of the precise smart pointers within that pointee.

 >
 > With this approach, std containers, tuples and fusion sequences would
 > come for free. You need to provide the visitor of other user defined
 > datatypes, but it is arguable if this is more bothersome than
 > explicitly marking every pointer.

With the precise policy_ptr, fusion sequences and tuples would have to
be registered, I think...  Maybe not.  If the
selected_fields_description_of template (used by the
SELECTED_FIELDS_DESCRIPTION_OF_RECORD macro mentioned above) were
specialized for tuples and fusion sequences, maybe it wouldn't have to
be explicitly registered.  Thinking a little further, I pretty sure
this would be similar to the way stl containers are handled:

   boost/fields_visitor/container_extern/single.hpp

Will investiage to make sure.

 >
 > The user would need to explicitly mark the root set before calling the
 > garbage collector. This means that the gc can only be called
 > explicitly (manipulating the root set is expensive, so you want to do
 > it only when absolutely necessary). If the gc'ed heap runs out of
 > memory would simply throw. Somewhere down in the stack, the exception
 > would be caught, the root pointers saved and and the gc invoked. This
 > way you also get deterministic gc. Or an user callback could be called
 > that would call the gc.

If refcounting with cycle detection were used, there would be no need
for a root set; however, this could lead to quadratic time penalty in
the case of densely connected pointer graph (p. 3 of:

   http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf

).  This quadratic behavious was actually shown by the benchmark code
mentioned above.