Boost logo

Boost :

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


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


The methods compared to GCBTS are:

  1. cyclic_ptr
  2. mark_sweep_ptr
  3. safeptr
  4. SubjTop_crc
  5. 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.


  1. cyclic_ptr
  2. mark_sweep_ptr


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

  1. Memory use
    1. SmartPointer class

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

    2. 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 ).

  2. Time use
    1. Smart Pointer CTOR
    2. 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:

      1. to allow traversal of "all handles in deque three times to collect garbage" (comment above 'void recycler::recycle() throw()' in cyclic_ptr.cpp).
      2. 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.

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

  3. Ease of use
  4. Just assure operator= does operator= for each contained cyclic_ptr or weak_ptr; however, this is normally what one would do anyway.

  5. Bugs
    1. Only need to call recycle during destruction, as in Lins' method.
    2. 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.

  1. Memory use
    1. SmartPointer class (mark_sweep_ptr :public pointer_base)
      1. instance variables:
        1. handle_base* pointer_base ::handle_
      2. class variables
        1. std ::set<pointer_base*> pointer_base ::tracked_ptrs_s_
        2. tracked_ptrs_s_.size() is the number of smart pointers in the program at any one time.

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

      1. instance variables
        1. void* pointer_base ::handle_base :: raw_object_
        2. This is the actual garbage collected object.

        3. bool pointer_base ::handle_base ::mark_
        4. pointer to virtual function table
      2. class variables
        1. static map<void*, handle_base*>* pointer_base ::handle_base ::tracked_handles_s_
        2. 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_.

        3. bool pointer_base ::handle_base ::current_mark_s_
  2. Time use
    1. Smart Pointer
      1. CTOR
      2. DTOR
    2. Garbage Collection
    3. static void pointer_base ::collect(void) performs the garbage collection. During collection, the following local variables are created:

      1. multimap<handle_base *, pointer_base *> ptr_map

        ptr_map records the pointers contained in each handle's raw_object_.

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

  3. Ease of use
  4. Bugs

Boost list run by bdawes at, gregod at, cpdaniel at, john at