Mirek Fidler wrote:
 > Hi,
 >
 > It is possible that I have found idea that perhaps leads to building
 > optional non-GC for C++ without any core language changes.
 >
 > It is so trivial (250 lines of code) that I am afraid I got something wrong.
 > If I did, I apologize. If I reinvented wheel, I apologize too (but then I do
 > not understand why there is boost::shared_ptr but no boost::gc_ptr).
 >

Boost members have talked now and then about gc.  There were several candidates
for several years.  Recently Bouchard tried with his:

    http://groups.yahoo.com/group/boost/files/ptr/

I also have tried.  My (cppljevans) most recent try is in:

    http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/

It has the disadvantage that it uses reference counts with their
associated memory and count update overheads; however, it has the
advantage of rapid memory recovery (i.e. no waiting till the
next gc cycle).  This however is at the cost of the possibly
quadratic behaviour cited by Bacon in figure 1 of:

   http://citeseer.nj.nec.com/bacon01concurrent.html

This quadratic behaviour can be alleviated with a variation of
the lazy cyclic reference counting of Lin's which Bacon demonstrates
in his paper.  Bacon's method is concurrent, which the shared_cyclic_ptr
is not (even though it uses shared_ptr and shared_ptr has code, I think
using mutex's, which suggests it could be used concurrently).

Now, as for as other boost methods, there are 2 methods similar to ogc:

    1) http://www.codeproject.com/cpp/garbage_collect.asp
       Call this one "gcptr".
    2) http://groups.yahoo.com/group/boost/files/2000/GarbageCollector/
       Call this one "jrb_gc".

They are similar in that they maintain a container of the smart
pointers and also of the referents (in graph terminology, the "arcs"
and "vertices").  Also, like your ogc, they maintain the size of the
vertices and determine whether an arc belongs to a vertex by comparing
the location of the arc with the range of memory between the start and
end of a vertex.  Also, like ogc, they before sometimes a lot of work
in the arc CTOR or the vertex CTOR or in the initialization or mark
phase of the collector (the latter especially in the case of ogc). I
_think_ ogc maybe faster than these others because it does most of
it's work in the initialization phase of the collection, whereas the
others do some in their CTOR's and DTOR's of vertices and arcs.

However, shared_cyclic_ptr only performs a single test in the arc CTOR
and minimal initialization during collection.  It does this by
adapting Detlef's method in
http://citeseer.nj.nec.com/detlefs92garbage.html to handle container's
of arcs as well as individual arcs.  The information calculated once,
before the program start, and placed in

boost::mk_internal_pointers_descriptor_of
   <vertex_type
   >::
   c_my_type
     ;

where vertex_type is the referent of the smart pointer,
shared_cyclic_ptr<vertex_type>.  Actually, it's a little more
complicated than that, but that's essentially it.

More precisely, c_my_type contains a vector of functions which iterate
through the vertex returning the arcs contained therein.  More than
one function is used in order to handle the different types of
containers.  For example, there's a specialization for vectors,
another for lists, and so on.  This vector is returned by
c_my_type.the_ip_descriptor().

In conclusion, the shared_cyclic_ptr method of accessing the "internal
pointers", i.e. the contained "arcs" of a vertex should be much faster
than any of the above methods since all the work for calculating the
arcs of a given vertex is done before the 1st statement of main.
Also, as claimed in:

    http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/iplimits.txt

the method of arc enumeration is independent of the garbage collection
method; hence, the Detlef method could be used for the mark sweep
method also.  In addition, the address of
c_my_type.the_ip_descriptor() might be used in place of the GC_descr
described in:

   http://www.hpl.hp.com/personal/Hans_Boehm/gc/gc_source/gc_typedh.txt.

I believe it would also be pretty easy to make this part of the stl
containers since the only thing that needs to be changed in each stl
container is the type of pointer to the beginning of the allocated
objects. For example, in the case of vector, the pointer would be
something that would provide the same information as done by the
scoped_cyclic_container in the shared_cyclic_ptr code.  For the list,
the head pointer would likewise be something like this.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]