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

From: Mingnan Guo (hnxgc_pub_at_[hidden])
Date: 2007-11-21 12:39:00

  "Larry Evans" <cppljevans_at_[hidden]> дÈëÏûÏ¢ÐÂÎÅ:fi1h0s$s2r$1_at_ger.gmane.org...
  > >   (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<>.
> 
> Ah! That's the key.  So, the programmer has to assure that each
> CLockedPtr<>'s address is in the root area?  If so, then what happens
> if the programmar violates this restriction? Does the CLockedPtr CTOR
> test it's "this" pointer to assure it's *not* in the managed heap?  I
> assume the CLockedPtr CTOR and operator=, when accessing a managed
> pointer, increments the external pointer count of the managed object.
> Of course, this raises the question of whether this is more error
> prone than just using weak pointers to break the cycles.  Then, you'd
> have strong_ptr's and weak_ptr's vs. CLockedPtr's and CMemberPtr's.
> OTOH, if my assumption about CLockedPtr CTOR knowing where it's
> located (in root area or not), then CMemberPtr could do same, and then
> there wouldn't be any need for two different smart-ptrs.  What am I
> missing?

  Yes, application program should guarantee that, 
  (1) CLockedPtr<> smart pointers reside in root set area, they can point to 
  somewhere in managed memory pool. In another word, you should not 
  put the CLockedPtr<> as member variables of a managed object/class;
   
  (2) CMemberPtr<> should only be used as member variables of a managed 
  object/class.
   
  Note 1: But, in fact, the HnxGC API does not require above restriction. 
  Sometime, you can violate them to achieve special effect/goal, in case you 
  know what you are doing. These smart pointers is a high-level layer based
   on HnxGC API to ease programming.)
  . 
  Note2: CWeakPtr<> can be used in managed memory pool or root set area. 
  It is a pure programming sugar. The reference counting & tracing collector 
  does not depend on them. We don't need to break cycles prior to collect them.
   
   
  > >   (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.
> 
> Does Peter's collector asynchronously change pointers of managed
> object?  Maybe he does that to break a cycle and then use delete on a
> pointer to reclaim memory, but I don't see that as a problem.
> 
   
  I don't know whether Peter's collector asynchronously change user objects or not. 
  I just want to say HnxGC users are guaranteed that HnxGC will not touch user objects 
  and no way to do that. HnxGC collector does not know the address of member pointers
  of an object. 
  
 
  > >   HnxGC provides reclamation ordering control to help application to
> >   use RAII design pattern.
> 
> OK, I guess this is needed in case of cycles, and I guess this is used
> to break a cycle before HnxGC uses delete on a pointer to reclaim
> memory, just as described above, only the ordering control is used to
> determine where to break the cycle.  However, this raises again the
> question of why not use weak_ptr's instead.  These, in effect, provide
> reclamation ordering control, AFAICT.
   
  Reclamation ordering is an option. Application programmer can declare one
  or more dependence requirements for their destructors, but they are not required
  to do so. By default, circular referenced garbage are collected out-of-order (can
  be any order). In most case, application program need not declare a dependence
  requirement. The collector does not depend on them to break cycles. It collects
  cycles directly without need to break them in advance. 
   
  
> >   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.
> 
> I'm know very little about threading, but this stuff about RAII sounds
> good.  I'm wondering if you could provide both multi-threading and
> single-threading versions so that those not needing multi-threading
> wouldn't have to pay for the synchronization costs.

  Yes, actually three types of HnxGC library are provided, Single-threading(ST), 
  Multi-threading for Uniprocessor (MT/UP) and Multi-threading for Multiple-processors (MT/MP).
   
  Single-threading perform tracing collection in the only one thread, similar to sp_collect() 
  in http://www.pdimov.com/cpp/enable_sp_collect.cpp. The thread cannot do any 
  other things during the collection.
   
  The other two multi-threading versions can perform pause-less concurrent collection, 
  while MP(multiple-processors) version removes some memory ordering requirement 
  in some platform, such as IA64. You can consider using MT version even in a single 
  thread application, the cost is not so much as people thought. With maximum optimization 
  of modern C++ compiler, the cost is mainly based on atomic reference counting. The 
  synchronization cost does not occur when there is not a concurrent tracing collection running. 
   
  regards
   
  -Mingnan Guo
   
  [welcome join the HnxGC google group 
  http://groups.google.ca/group/HnxGC?hl=en, 
  and get the latest info about HnxGC.]

       
---------------------------------
Be a better sports nut! Let your teams follow you with Yahoo Mobile. Try it now.