On 11/20/07 07:21, Mingnan Guo wrote:
The HnxGC Library for C++ is released at
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: More specifically, we use reference counting technique to count the number of references from outside of the managed heap. When the count is not zero, it means that the object is marked-out and belongs to root objects of tracing collection. Therefore, by dynamically marking out root objects in application program execution, tracing collector can treat the managed heap boundary as the consideration boundary of tracing garbage collection, it need not to know about the outside of the managed heap and avoids analyzing complicated outside environments, such as program's stack and processors' registers. suggests a similarity to the three-phase cyclic refcounting garbage collectors mentioned on p. 62 of the 1996 edition of: http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html The following is from that page: Their general idea is to perform three partial traversals of the data structure, in the first place removing the contribution of pointers internal to the sub-graph being traversed from cell reference counts. At the end of the first traversal, the reference counts will only reflect external pointers to nodes in the sub-graph. The first phase sounds like its similar to the "count the number of references from outside of the managed heap" part of algo_overview.htm. Is that about right? Also, I see on: http://hnxgc.harnixworld.com/algo_rootobj.htm there's: References inside managed heap, such as pointer fields of managed objects, can be easily described by a "traverse" method. and also: Normally, each class should have its own traverse routine defined. However, IIRC, Peter Dimov provided an accurate GC with this same requirement for a traverse routine, called sp_enumerate here: http://www.pdimov.com/cpp/shared_ptr_0x.html#cycles and a similar method, AFAICT, for determining the external pointers to an object. 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, at least according to: In both cases, trial decrements are made to the reference coungs of the descendants of cells encountered. from p. 71 of the aforementioned gcbook; however, I do remember going over that code (or an earlier version of it) where it was doing essentially the same thing to determine the number of external counts. Maybe Peter could clarify. So, the question now is: How is the HnxGC method for precisely collecting cycles better than the enable_sp_collect.cpp method? -regards, Larry