Purpose

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2001-01-29 17:49:43

Alex Oren wrote:

> On Fri, 26 Jan 2001 13:06:57 -0600, Larry Evans wrote:
>
> } OOPS.  Forgot the attachment.  It's attached here.
>
> Larry, you got me intrigued but your email contained only the top-level
> document.  Can you please send me the whole package?  (preferably
> compressed).  Thank you!
>

OK, but it's still very rough.



Comparison of boost gc methods



Purpose

As requested in a  post , the
various garbage collections methods in the files directory with the 
"GarbageCollectByTmplSpecialization" or  GCBTS .

Methods

The methods compared to GCBTS are:
cyclic_ptr
mark_sweep_ptr
safeptr
SubjTop_crc
SubjTop_cmmPms

Another method, circ_ptr, appears
in the boost files directory; however, circ_ptr appears to be an earlier
"unboostified" version of the mark_sweep_ptr method; consequently, no
analysis was made on this method.

Comparisons
cyclic_ptr
mark_sweep_ptr
References

[GOF95]
  
  Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides
  Design Patterns: Elements of Reusable Object-Oriented Software
  Addison-Wesley, 1995
  





cyclic_ptr analysis


This document analyzes the "cyclic_ptr" garbage collection method for
purposes of comparison according to criteria described here.
Memory use
SmartPointer class

Each cyclic_ptr smart pointer class consumes 2 pointers ( 1 for the
pointee and 1 for the recycler).

Pointee class

Each cyclic_ptr pointee contained in a smart pointer requires an
instance of recycler, which contains 2 reference counts ( 1 for the
strong pointers and 1 for the weak pointers ), and 2 pointers ( 1 one
for the pointee and 1 for the deleter ).


Time use
Smart Pointer CTOR

This calls handles.deque
::push_back and, #ifndef NDEBUG,
no_duplicates.set
::insert.  The void* in set
 is actually
a T* where T is the T in recyclable_base
, the base class for
cyclic_ptr and weak_ptr.

The purpose of the static std::deque
 handles (in
cyclic_ptr.cpp) is:

to allow traversal of "all handles in deque three
times to collect garbage" (comment above 'void recycler::recycle()
throw()' in cyclic_ptr.cpp).

to allow the user to specify a finalizer
(or, in cyclic_ptr's case, a "deleter") for each instance of the
pointee.


However, the no_duplicates actually must be used for
production code and as well as for debugging; otherwise, if the same
pointer is contained in 2 different cyclic_ptr's, then it will be
deleted twice.

Garbage Collection

Traverses handles (size ~= number pointers) 3 times, and for each
element, traverses the pointer graph rooted at that element.

Ease of use

Just assure operator= does operator= for each contained cyclic_ptr
or weak_ptr; however, this is normally what one would do anyway.
Bugs
Only need to call recycle during destruction, as in Lins' method.
double delete of pointee





mark_sweep_ptr analysis


This document analyzes the "mark_sweep_ptr" garbage collection method for
purposes of comparison according to criteria described here.
 
Memory use
SmartPointer class (mark_sweep_ptr :public pointer_base)

instance variables:
handle_base*
pointer_base ::handle_
 
class variables
std ::set<pointer_base*> pointer_base
::tracked_ptrs_s_

tracked_ptrs_s_.size() is the number of smart pointers in the program at
any one time.
 

Pointee decorator class (pointer_base ::handle_base )

Each instance of a pointee class has an associated handle class,
pointer_base::handle_base.  The purpose of this handle class is to
allow garbage collection of any class.  This is in contrast to other
garbage collection methods which require all garbage collected classes
to be derived from some base class which contains the necessary
methods and variables for garbage collections, e.g. reference count
for reference counting garbage collection.  Hence, instance variables
and class variables below will mean instance variables and class
variables for this handle class.
instance variables
void* pointer_base ::handle_base
:: raw_object_

This is the actual garbage collected object.
bool pointer_base ::handle_base ::mark_
pointer to virtual function table
 
class variables
static  map<void*,
handle_base*>*  pointer_base ::handle_base ::tracked_handles_s_

tracked_handles_s_ implements a 1-to-1 map from pointee's
to their associated "handles".  This is the inverse of the relation
ship implemented by pointer_base ::handle_base ::raw_object_.
bool pointer_base ::handle_base ::current_mark_s_

 

 

 

Time use
Smart Pointer
CTOR

DTOR
 

Garbage Collection
 

 static void pointer_base ::collect(void) performs the
garbage collection. During collection, the following local variables
are created:
multimap<handle_base *, pointer_base *> ptr_map

ptr_map records the pointers contained in each handle's
raw_object_.
std::list<pointer_base*>> roots

roots contains the "root" pointers.

pointer_base ::collect(void) creates both ptr_map and roots with a
doubly nested loop where the outer loop has tracked_ptrs_s_.size()
iterations and the inner loop has tracked_handles_s_.size()
iterations.

pointer_base ::collect(void) then 

 

Ease of use

Bugs