C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Howto: Garbage collection for objects in a connected graph?          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Yuraukar Guest Posted: Wed Aug 25, 2004 8:56 pm    Post subject: Howto: Garbage collection for objects in a connected graph? While GC has been a topic in this newsgroups and there are quite a few webpages covering the topic, I have been unable to find a suitable solution for the problem below: I have a number of objects pointing to each other, thus forming a directed graph. Cycles are very likely to happen. Less abstract: e.g., object A has a member that points to object B and object B has a member that points to A. Various variables may point to objects in the directed graph. Less abstract: e.g. variable x points to A and variable y points to B. None of the variables actually own the graph or the object. I am looking for an algorithm or approach how to implement garbage collection for this situation. An object may be released if (a) no variable points to it [=it is not reachable] and (b) no other object that is reachable points to it. Less abstract: if x no longer points to A, that doesn't mean that A can be released, because y still points to B and B points to A. I looked into smart pointers and found the concept of strong and weak pointers interesting, but don't think its usable here. I looked into some GC implementations and articles, but as I am not in need for a general GC that replaces malloc() and free(), I don't see any use in those either. And most of the other articles cover GC based on reference counting, which clearly is not applicable here. I would appreciate if someone could point me to a good algorithm that would solve my problem. Yuraukar. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top _ Guest Posted: Wed Aug 25, 2004 10:10 pm    Post subject: Re: Howto: Garbage collection for objects in a connected gra Yuraukar wrote: Quote: An object may be released if (a) no variable points to it [=it is not reachable] and (b) no other object that is reachable points to it. Less abstract: if x no longer points to A, that doesn't mean that A can be released, because y still points to B and B points to A. The traditional approach is called mark-sweep. It works in two phases and requires there be some "root" from which you can reach all nodes regardless of their connectivity within the graph (say a vector of pointers to all nodes currently instantiated). The first phase is where you traverse the connected nodes and "mark" them as being reachable. As you traverse the graph the "marked" flag tells you if you've visited a particular node and therefore don't have to visit it again (i.e. marks the cycles). When the mark is complete it leaves unreachable nodes as not marked. In the second phase you traverse all the nodes and delete those that are not marked (and, if the mark flags are stored in the nodes, reset the mark flag). If you can afford the space then keeping sets of nodes can eliminate the second traversal (have two sets, reachable and unreachable and move nodes between the two, the sweep step can simply be "delete everything in the unreachable set" and clearing the mark can be "delete the set of reachable nodes"). Mark-sweep is simple but may have some undesirable properties depending upon the situation. Time complexity is determined by the number of nodes and their connectivity and performing frequent collections can be time consuming, creating pauses in execution whilst collection occurs. One way to, at least minimize, the impact is to therefore to not do it all the time, i.e. only run a collection if some measure of waste is too high. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Larry Evans Guest Posted: Thu Aug 26, 2004 7:38 am    Post subject: Re: Howto: Garbage collection for objects in a connected gra On 08/25/2004 03:56 PM, Yuraukar wrote: Quote: While GC has been a topic in this newsgroups and there are quite a few webpages covering the topic, I have been unable to find a suitable solution for the problem below: I looked into smart pointers and found the concept of strong and weak pointers interesting, but don't think its usable here. Because you don't know which should be the strong vs. weak pointers? Quote: I looked into some GC implementations and articles, but as I am not in need for a general GC that replaces malloc() and free(), I don't see any use in those either. I assume this includes the BW collector: http://www.hpl.hp.com/personal/Hans_Boehm/gc/ Is this because you don't want to pay the extra overhead of having everything in the heap garbage collected? I thought BW provided a means for doing this: http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcinterface.html However, I haven't looked real close at that page. Quote: And most of the other articles cover GC based on reference counting, which clearly is not applicable here. Is this because refcounting can't collect cycles? If so, then: http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/libs/managed_ptr/test/ shows a test driver for "eager cyclic refcounting" using the algorithm in [mart90] ( see http://www.cs.kent.ac.uk/people/staff/rej/gcbib/ for defintion of this and further references ). The doc directory describes what compilers it works on. Compiling problems are caused by the non-deduced context problem discussed here: http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=10709vpp8mcgtdd%40corp.supernews.com I'm still working on the doc's :< This eager method can suffer from quadratic collection time since, at each decrement, it makes a local traversal of the pointer graph. This can be alleviated with the "lazy" version of the algorithm [lins90a] or even the "asleep" version [chri84]. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Bradley Guest Posted: Thu Aug 26, 2004 7:42 am    Post subject: Re: Howto: Garbage collection for objects in a connected gra Yuraukar wrote: Quote: While GC has been a topic in this newsgroups and there are quite a few webpages covering the topic, I have been unable to find a suitable solution for the problem below There's not enough information to know for sure, but would an Arena be a simpler solution for you? It works well if you have a group of tightly related objects that all have a similar lifetime. Meaning you know when everything in the arena will be dead. And the no object holds a non-memory resource. You can get around that as well by providing an "arena" for those resources. Thought I'd throw it out just in case it might fit the bill in your case. David Bradley [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Larry Evans Guest Posted: Fri Aug 27, 2004 2:57 am    Post subject: Re: Howto: Garbage collection for objects in a connected gra On 08/26/2004 02:42 AM, David Bradley wrote: Quote: There's not enough information to know for sure, but would an Arena be a simpler solution for you? It works well if you have a group of tightly related objects that all have a similar lifetime. Meaning you know when everything in the arena will be dead. And the no object holds a non-memory resource. You can get around that as well by providing an "arena" for those resources. Ah! That reminds me of Attardi, et.al.'s "Customizable Memory Manager", which uses a different heap for each method of garbage collection. One method just allocates from an "uncollected" heap without any collection, and then "deallocates" the whole heap, or something like that. Jones has a link to it at: http://www.cs.kent.ac.uk/people/staff/rej/gc.html#Software [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.