Re: [boost] Accurate, pauseless & deterministic GC for C++

From: Mingnan Guo (hnxgc_pub_at_[hidden])
Date: 2007-11-21 03:41:07

  "Larry Evans" <cppljevans_at_[hidden]> дÈëÏûÏ¢ÐÂÎÅ:fhvbf1$cc4$1_at_ger.gmane.org...
  > On 11/20/07 07:21, Mingnan Guo wrote:
> >
> >   The HnxGC Library for C++ is released at
> >
> >   http://hnxgc.harnixworld.com
> 
> >   This garbage collector provides accurate, pause-less (lock-free,
> >   block-free) concurrent garbage collection with deterministic
> >   reclamation for C++ application. Efficient, portable, no need
> >   registeration of root set pointers, no scanning of root set area,
> >   and more.
> [snip]
> Hi Mingnan,
> 
> This sounds interesting. I've looked briefly at:
> 
> http://hnxgc.harnixworld.com/algo_overview.htm
> 
> which contains:
>  ...
  > [snip]
   
    Hi Larry, 
   
  Thanks for your interest in the HnxGC Library and raise such good question. Actually, there are so many variations of garbage collection algorithm that had forced me to give up the crazy idea many years ago to learn about them all. So, based on the HnxGC algorithm, I am answering your questions as follows:
   
  (1)
  > which contains:
  > 
  >    More specifically, we use reference counting technique to count the
  >    number of references from outside of the managed heap. When the
  >    ¡­
  > suggests a similarity to the three-phase cyclic refcounting garbage
  > collectors mentioned on p. 62 of the 1996 edition of:
   
  I did *NOT* suggest such similarity. In HnxGC, the counts reflecting external pointers to an object is directly maintained by CLockedPtr<> smart pointer throughout the execution of application. At any point of time, we maintain a count for every object reflecting the number of reference from root set (external pointers). So, when performing tracing collection, the root objects have already identified. 
   
  In your quotation of three-phase cyclic refcounting algorithm, the count only reflect external pointers to nodes at the end of the first traversal, which I think it means the counts are calculated when performing tracing collection, as described in Peter Dimov¡¯s paper
   
  http://www.pdimov.com/cpp/shared_ptr_0x.html#cycles. 
   
  The following is from the page:
  [Note: The reachability analysis may be performed using Christopher's algorithm. Using the instance graph, compute the use counts the objects would have if there were no external shared_ptr instances. Compare the computed use counts with the actual use counts. For every mismatch, mark the object as reachable from the outside. Propagate reachability throughout the graph. --end note]
   
  (2) 
  >However, after briefly looking at the code:
  > 
  >    http://www.pdimov.com/cpp/enable_sp_collect.cpp
  > 
  > I can't tell where the trial decrements for each external reference is
  > done, which is what both [Chritopher,1984] and [Lins,1992a] methods
  > do, ¡­
   
  I agree with you. The enable_sp_collect.cpp seems use another algorithm to determine the root objects that traversal will begin with. I guess, it registers every external pointers by sp_track() function as:
  int main() {
      boost::shared_ptr<X> root( new X );
      sp_track( root );
         ¡­
  }
   
  This design will introduce some costs, especially when function-local variables are frequently accessed. In HnxGC, there is not such registration requirement. 
   
  (3)
  From an especial angle of view on various garbage collectors, they can be divided into several types based on how to determine the root objects. Most GCs, such as .NET and official Java JVM, scan the root set area for references, including in threads¡¯ execution stack, static data, CPU¡¯s registers etc. Some others use data structures to collect pointers from root set, the most dedicated and fast design I have seen was patent US 6,907,437. It uses a single-linked list to link all pointers in a thread¡¯s stack. Microsoft also use gc_ptr to register some root pointers as well as a very early version of Sun Java GC use indirect pointer array to avoid scanning root set. Their main pitfalls are the performance cost, especially for multi-threading concurrent collector. 
   
  HnxGC use reference counting to mark root object and provide deterministic reclamation. The cost is mainly based on atomic RC operation, such as LOCK INC/DEC instruction in the x86 platform. Because the RC operation has already required atomic semantics, HnxGC is easy to implement a concurrent collector without introducing too much lock/synchronization cost. There is no requirement to use locks to protect register/de-register operation of external pointers, which costs very high since external pointer may be frequently created, gain a reference, lost a reference, and/or be destroyed. 
   
  (4) One major difference between HnxGC and Peter Dimov¡¯s algorithm is: in HnxGC, we use different type of smart pointers in different area, such as CLockedPtr<> in root area (external pointers in pdimov¡¯s words), and CMemberPtr<> in managed heap (internal pointer?), while Peter only uses one type of smart pointer shared_ptr<>. Our approach does introduce some inconveniences but I think it is acceptable. This type of design also helps to significantly reduce RC cost by using ¡°move¡± assignment of CLockedPtr<>. 
   
  (5) As concerning tracing collection, HnxGC uses a mark & sweep algorithm similar to the Peter¡¯s choice. We needs a Traverse() routine defined by application program like Peter¡¯s sp_enumerate() except we do not require user-class to derives from a base class, e.g. enable_sp_collect, and disallow that collector asynchronously changes pointers of managed objects. HnxGC provides reclamation ordering control to help application to use RAII design pattern. 
   
  >    How is the HnxGC method for precisely collecting cycles better than
  >    the enable_sp_collect.cpp method? 
   
  In comparison with enable_sp_collect.cpp method, HnxGC has more considerations by design for a multi-threading environment. It provide pause-less concurrent garbage collection (lock-free, no-suspension, no memory ordering for SMP); it removes significant portion of the cost of regular reference counting; it provides reclamation ordering control for RAII design pattern; it provides rich programming features, such as interior pointer, resurrection, etc. 
   
  BTW: I also paste this message to HnxGC google group, which is public opened and welcome all HnxGC discussions.
   
  - Mingnan Guo

       
---------------------------------
Get easy, one-click access to your favorites.  Make Yahoo! your homepage.