C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Papers on garbage collection in C++ ? Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Daniel Guest Posted: Fri Sep 05, 2003 10:17 pm    Post subject: Papers on garbage collection in C++ ? At the risk of starting another debate about it (which, judging from the Google archives, this group needs like a hole in the head) I'm very interested in recent work on garbage collection in C++. I'd like to read some research papers, basically. (I'm bored!) No, I'm interested in the problems encountered adding it to C++, especially without language extensions, and any _recent_ progress in this area, beyond the typical mid-1990s approach (a mark-and-sweep collector that looks for pointer-like data and is conservative.) I want to know if the advent of the Standard and the very significant improvements to the language since the early 90s have supported new solutions to old problems. I stress recent, because the papers I've found so far seem to date to before the arrival of Java. Things get a little thinner after that, just like my hair did. Richard Jones's book 'Garbage Collection' has a section on C++ but appears to conclude with the well-known Ellis-Detlefs language extension proposal from 1992 (please correct me if I'm wrong...) The impression I get is that work in this area began to wind down after that point, because that language's main selling points include a C++-ish syntax combined with garbage collection, making further argument/research into C++ garbage collection seem like a waste of time, and the answer becomes "If you want it, use Java." This is a pity because there's a bunch of other differences, and Java seems in no hurry to become more C++ like in order to attract us over - main problem being generics, and the current proposal for adding those to Java is very disappointing (though understandable given its backward-compatibility constraints.) Meanwhile, the C++ standard library has popularised a very effective way of structuring programs so that they do not often require garbage collection, through the use of data structures that manage dynamic allocation automatically, so I suspect that has reduced interest even further. So if you know of a paper on adding garbage collection to C++, especially in the post-Standard timeframe, please post a link. Especially if it uses standard C++ only - I'm less interested in non-portable language extensions. Thanks. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Walter Guest Posted: Sun Sep 07, 2003 1:47 am    Post subject: Re: Papers on garbage collection in C++ ? "Daniel" <spam (AT) earwicker (DOT) com> wrote Quote: The impression I get is that work in this area began to wind down after that point, because that language's main selling points include a C++-ish syntax combined with garbage collection, making further argument/research into C++ garbage collection seem like a waste of time, and the answer becomes "If you want it, use Java." This is a pity because there's a bunch of other differences, and Java seems in no hurry to become more C++ like in order to attract us over - main problem being generics, and the current proposal for adding those to Java is very disappointing (though understandable given its backward-compatibility constraints.) D is a language evolved from C/C++ that does use garbage collection as its primary memory management paradigm. The currect gc implementation for it is a basic mark/sweep, but the language design leaves the door open for much more sophisticated ones (such as ones that know the types of each member in an allocated object). Quote: So if you know of a paper on adding garbage collection to C++, especially in the post-Standard timeframe, please post a link. Especially if it uses standard C++ only - I'm less interested in non-portable language extensions. D doesn't fit your requirements, because D isn't standard C++. But it is much more C++ like than Java is, has a large emphasis on efficient code generation, does templates, and doesn't need to be backwards compatible with the Java VM <g>. -Walter www.digitalmars.com/d/ The D Programming Language [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thant Tessman Guest Posted: Sun Sep 07, 2003 2:05 am    Post subject: Re: Papers on garbage collection in C++ ? Daniel wrote: Quote: [...] I'm interested in the problems encountered adding it to C++, especially without language extensions, and any _recent_ progress in this area, beyond the typical mid-1990s approach (a mark-and-sweep collector that looks for pointer-like data and is conservative.) I want to know if the advent of the Standard and the very significant improvements to the language since the early 90s have supported new solutions to old problems. I came up with a smart pointer implementation that handles circular references. I use it in an interpreter I'm building (very slowly in my copius spare time): http://www.standarddeviance.com/sigma.html It was a deliberate attempt to remain within the C++ standard. The solution should just work on anything but the most exotic hardware. William Kemph was inspired by an earlier version to implement his own smart pointers and write them up: http://www.codeproject.com/cpp/garbage_collect2.asp My own conclusion is that this is about as far as I want to push GC in C++, even as "research." At some point it just makes more sense to switch to a language that was designed with GC in mind from the start (which I do as circumstances allow). -thant [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel Guest Posted: Sun Sep 07, 2003 3:27 pm    Post subject: Re: Papers on garbage collection in C++ ? Thant Tessman <thant (AT) acm (DOT) org> wrote Quote: Daniel wrote: [...] I'm interested in the problems encountered adding it to C++, especially without language extensions, and any _recent_ progress in this area, beyond the typical mid-1990s approach (a mark-and-sweep collector that looks for pointer-like data and is conservative.) I want to know if the advent of the Standard and the very significant improvements to the language since the early 90s have supported new solutions to old problems. I came up with a smart pointer implementation that handles circular references. I use it in an interpreter I'm building (very slowly in my copius spare time): http://www.standarddeviance.com/sigma.html It was a deliberate attempt to remain within the C++ standard. The solution should just work on anything but the most exotic hardware. Thanks, that's very interesting. I notice from the lib/ptr/notes.txt file: "The assumption is that if a [smart] pointer is within an object pointed at by another [smart] pointer, it is a node. Otherwise it is a root." This would mean that a smart pointer stored in std::vector would always be a root, as std::vector uses ordinary new to allocate a block of storage to hold the internal array of elements, and it references the block with an ordinary pointer. So (unless I'm missing some clever trick): class B; class A { std::vector< Ptr v; }; class B { std::vector< Ptr v; }; Ptr<A> a; // assign instance to it somehow Ptr<B> b; // ditto a->v.push_back(b); b->v.push_back(a); This circular system would leak permanently because both smart pointers appear to be roots, even though "logically" we think of them being stored "inside" A and B. (And if this isn't a problem for you, you might as well use reference counting.) So as with std::auto_ptr, these pointers are not allowed to go in standard containers, which is frustrating, because they do have perfectly acceptable copy semantics (unlike std::auto_ptr.) This is a tricky problem, to be sure! :) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Thant Tessman Guest Posted: Mon Sep 08, 2003 6:30 am    Post subject: Re: Papers on garbage collection in C++ ? Daniel wrote: [...] Quote: This circular system would leak permanently because both smart pointers appear to be roots, even though "logically" we think of them being stored "inside" A and B. [...] Your understanding of the problem is correct. However, the implementation allows you to define your own specialization of the TypedPackage template class which allows you to define your own "contains" function for a given type. There's an example at src/lib/generic/Args.hpp in the source you downloaded. A version for std::vector would work similarly --although I haven't bothered. I guess I should... -thant [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top llewelly Guest Posted: Mon Sep 08, 2003 3:45 pm    Post subject: Re: Papers on garbage collection in C++ ? [email]spam (AT) earwicker (DOT) com[/email] (Daniel) writes: Quote: At the risk of starting another debate about it (which, judging from the Google archives, this group needs like a hole in the head) I'm very interested in recent work on garbage collection in C++. I'd like to read some research papers, basically. (I'm bored!) No, I'm interested in the problems encountered adding it to C++, especially without language extensions, and any _recent_ progress in this area, beyond the typical mid-1990s approach (a mark-and-sweep collector that looks for pointer-like data and is conservative.) I want to know if the advent of the Standard and the very significant improvements to the language since the early 90s have supported new solutions to old problems. I stress recent, because the papers I've found so far seem to date to before the arrival of Java. Things get a little thinner after that, just like my hair did. [snip] What about Hans Boehm's work? http://www.hpl.hp.com/personal/Hans_Boehm/gc/ Some of the papers listed there postdate Java. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel Guest Posted: Mon Sep 08, 2003 7:16 pm    Post subject: Re: Papers on garbage collection in C++ ? Thant Tessman <thant (AT) acm (DOT) org> wrote Quote: Daniel wrote: [...] This circular system would leak permanently because both smart pointers appear to be roots, even though "logically" we think of them being stored "inside" A and B. [...] Your understanding of the problem is correct. However, the implementation allows you to define your own specialization of the TypedPackage template class which allows you to define your own "contains" function for a given type. There's an example at src/lib/generic/Args.hpp in the source you downloaded. A version for std::vector would work similarly --although I haven't bothered. I guess I should... -thant Yes, I've been suspecting that the ability to customise the collection method will be essential. I had a try at writing a library for this last week (so still in the very early stages, and which is how I got interested in all this.) Currently I have all gc objects derived from a specific base class and so they override a virtual method to define "reachability." I suspect your way (using templates) would be more appealing, as it avoids the need for a single-rooted class hierarchy. Thanks again. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel Guest Posted: Tue Sep 09, 2003 6:43 pm    Post subject: Re: Papers on garbage collection in C++ ? "Mirek Fidler" <cxl (AT) volny (DOT) cz> wrote Quote: Anyway, the main problem with this kind of GC is that you have to turn _all_ pointers that could create circular references into smart one. That in turn means you cannot use things like std::vector< gc_ptr foo; because there is an internal pointer in std::vector's implementation that is not gc_ptr and is not allocated by gc_new, and that means mark algorithm is not able to follow inside foo.... I think that's definitely a limitation worth fixing. All you need is some way to "retrofit" a standard class with the necessary understanding of how to reach pointers that it owns. I've considered two ways so far: 1. A single rooted hierarchy for collectable objects. The base class has a virtual method reach(), the default version assumes any pointers will be embedded in the storage of the object. But in addition, you can declare a new template (approximately): template <class E> class fixed_vector : public object, public std::vector< ptr { virtual void reach() { std::vector< ptr::iterator i; for (i = begin(); i != end(); i++) i->reach(); } }; Now this class correctly defines how to reach its pointers, and can be used in place of std::vector (from which it borrows a complete implementation of everything else.) 2. Using the magic of templates. A "traits" template could define the correct way to reach the pointers for a given type. This has the advantage that it doesn't require a single rooted hierarchy, and it doesn't require the user to use a non-standard name for the type they wish to use. It gets "interesting" when you want to provide the traits for a given template, such as std::vector. The traits class much match any use of that template. This means it must take a template as its template parameter, which I believe is called a "template template parameter" and confuses the hell out of me. I haven't tried this yet. Quote: Anyway, if you wish, I can send you sources... Please do! [email]spam (AT) earwicker (DOT) com[/email] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel Guest Posted: Tue Sep 09, 2003 6:55 pm    Post subject: Re: Papers on garbage collection in C++ ? llewelly <llewelly.at (AT) xmission (DOT) dot.com> wrote Quote: spam (AT) earwicker (DOT) com (Daniel) writes: At the risk of starting another debate about it (which, judging from the Google archives, this group needs like a hole in the head) I'm very interested in recent work on garbage collection in C++. I'd like to read some research papers, basically. (I'm bored!) No, I'm interested in the problems encountered adding it to C++, especially without language extensions, and any _recent_ progress in this area, beyond the typical mid-1990s approach (a mark-and-sweep collector that looks for pointer-like data and is conservative.) I want to know if the advent of the Standard and the very significant improvements to the language since the early 90s have supported new solutions to old problems. I stress recent, because the papers I've found so far seem to date to before the arrival of Java. Things get a little thinner after that, just like my hair did. [snip] What about Hans Boehm's work? http://www.hpl.hp.com/personal/Hans_Boehm/gc/ Some of the papers listed there postdate Java. Yes, the Boehm (et al) collector is widely acknowledged as THE solution and is used as the garbage collection backend in a lot of systems. But it relies on things that are not guaranteed by the language definition. Some architecture-specific pieces need to be written specially for each new architecture, and the resulting code is fragile in the face of compiler optimisations. (See "Safety" on this page: http://www.hpl.hp.com/personal/Hans_Boehm/gc/issues.html - "Similarly, C compilers may not hide pointers in the generated object code. In our experience, standard commercial compilers obey this restriction in unoptimized code. Most aggressive optimizing compilers do not obey this restriction for all optimized code.") Here's a specific example of the kind of thing I'm ruling out (nothing necessarily to do with Boehm's collector.) In my fooling around I considered the following trick for deciding if a pointer is "on the stack" and hence a root of reachability: The programmer has to declare an instance of some management class called 'collector', e.g. in the main() function. It has to be an automatic variable. Then they can work with smart pointers, allocate objects using collector::create(), and call collector::collect() whenever they want to clean up. int main() { collector gc; { // do stuff... gc.collect(); } } The implementation of collector::collect() can say: void *stack_start = this; int dummy = 0; void *stack_end = &dummy; That is, the stack is assumed to extend from the address of collector to the address of some local variable inside collect(). So any pointer buried between these two locations is on the stack. I tried it, and it works great - unless you switch on optimisations. The idea that automatic objects must be allocated in some neat order on the stack is completely false and not part of the language definition. It happens to be true with some compilers in some configurations. That's the same kind of constraint that the Boehm collector works under - though the exact technicalities are probably different. If you are happy to extend the language definition and place extra constraints on the compiler, then such tricks are available to you. And this is no doubt fine in some cases. I'm presently interested in implementations that work within the confines of standard C++. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ed Avis Guest Posted: Wed Sep 10, 2003 11:28 pm    Post subject: Re: Papers on garbage collection in C++ ? [email]spam (AT) earwicker (DOT) com[/email] (Daniel) writes: Quote: Yes, the Boehm (et al) collector is widely acknowledged as THE solution and is used as the garbage collection backend in a lot of systems. But it relies on things that are not guaranteed by the language definition. Some architecture-specific pieces need to be written specially for each new architecture, and the resulting code is fragile in the face of compiler optimisations. Also it has been suggested that apps using the Boehm collector would be vulnerable to denial-of-service attacks, if an attacker sends data which looks like it contains lots of pointers and this is stored in raw memory somewhere. The collector wouldn't free the objects pointed to by the bogus pointers. Is this really a possibility? -- Ed Avis <ed (AT) membled (DOT) com> [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Thu Sep 11, 2003 10:48 am    Post subject: Re: Papers on garbage collection in C++ ? Quote: std::vector< gc_ptr foo; because there is an internal pointer in std::vector's implementation that is not gc_ptr and is not allocated by gc_new, and that means mark algorithm is not able to follow inside foo.... I think that's definitely a limitation worth fixing. All you need is some way to "retrofit" a standard class with the necessary understanding of how to reach pointers that it owns. I've considered two ways so far: 1. A single rooted hierarchy for collectable objects. The base class 2. Using the magic of templates. A "traits" template could define the I think you should consider custom memory allocator too. I am not absolutely sure it can solve problem using my style of GC with STL, but I think it should (at least if STL implementation is fully conformant). Anyway, I am almost sure this has no sense. What you would end with is absolute mess, totaly unmaintainable code. GC and C++ do not match... Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Hans-J. Boehm Guest Posted: Sat Sep 13, 2003 8:20 am    Post subject: Re: Papers on garbage collection in C++ ? Ed Avis <ed (AT) membled (DOT) com> wrote Quote: Also it has been suggested that apps using the Boehm collector would be vulnerable to denial-of-service attacks, if an attacker sends data which looks like it contains lots of pointers and this is stored in raw memory somewhere. The collector wouldn't free the objects pointed to by the bogus pointers. Is this really a possibility? I'll admit that conservative collection has weaknesses, but this one strikes me as a stretch. I could probably concoct an application for which this was indeed a problem. But it seems to me that it's very difficult to really guard against other kinds of denial of service attacks. (E.g. if you're accepting arbitrary client data, you at least have to product against cleint data that's too large, or against a single client masquerading as many, which may be hard to detect.) In contrast, it's very easy to allocate untrusted external data as "pointer-free", and thus have the collector not scan it. It seems to me that if your primary concern is DOS attacks, the collector adds an easy problem to many much harder ones. Aside from the lack of standards support, probably the most serious complaints I get about our collector are: 1) It doesn't perform well for large object allocation. That's a problem with any form of tracing collection, and conservative collection aggravates the problem in some subtle ways. If you are going to manage any memory manually (or semi-manually with destructors), clearly large objects are the place to do it. 2) False pointers and excess memory retention often become more of an issue as you get close to exhausting the address space, and hence almost anything looks like a pointer. Since we seem to be on the verge of an address size transition, this is currently more of an issue than it has been, or probably will be 5 or 10 years from now. Several people have run into memory utilization issues with 500MB or larger heaps on a 32-bit machine. Once you switch to a 64-bit machine, this problem disappears, at least for the foreseeable future. Hans [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Mirek Fidler Guest Posted: Mon Sep 15, 2003 9:55 pm    Post subject: Re: Papers on garbage collection in C++ ? Quote: I wonder if it is possible to deal with the fake pointer problem altogether by asking the compiler to align non-pointers at even addresses and pointers at odd addresses. (This could be in terms of bytes or in terms of word addressing.) This would double memory consumption in the worst case (where pointers and small non-pointer objects are directly interleaved) but most of the time it might not be too bad, especially if the compiler can make the layout of structs put all the pointers at the end. Even better way for compiler is to put pointer to description block at the begining of struct, which describes what parts of struct are pointers And another description block per each stack frame and you will not need conservative GC anymore... Mirek [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Hannah Schroeter Guest Posted: Tue Sep 16, 2003 8:36 pm    Post subject: Re: Papers on garbage collection in C++ ? Hallo! Mirek Fidler <cxl (AT) volny (DOT) cz> wrote: Quote: [...] Even better way for compiler is to put pointer to description block at the begining of struct, which describes what parts of struct are pointers And another description block per each stack frame and you will not need conservative GC anymore... You'd also have to somehow mark which *registers* contain pointers. cmucl (a free and open source Common Lisp implementation) differentiates. Architectures with many general purpose registers are handled with a completely exact GC by setting up a convention which GPRs are used for pointers and which for non-pointers. Architectures with few gprs (i386 :-E) are handled using a somewhat conservative GC (all registers *may* be pointers, but elsewhere, the GC can know what's a pointer and what not). GHC (a free Haskell compiler) calls GC only in specific times, but only after having set up a definite register state (IIRC, there's a bitmask per GC invocation point designating which registers hold pointers). Kind regards, Hannah. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Hans-J. Boehm Guest Posted: Wed Sep 17, 2003 9:44 am    Post subject: Re: Papers on garbage collection in C++ ? "Mirek Fidler" <cxl (AT) volny (DOT) cz> wrote Quote: I wonder if it is possible to deal with the fake pointer problem altogether by asking the compiler to align non-pointers at even addresses and pointers at odd addresses. (This could be in terms of bytes or in terms of word addressing.) This would double memory consumption in the worst case (where pointers and small non-pointer objects are directly interleaved) but most of the time it might not be too bad, especially if the compiler can make the layout of structs put all the pointers at the end. Even better way for compiler is to put pointer to description block at the begining of struct, which describes what parts of struct are pointers And another description block per each stack frame and you will not need conservative GC anymore... I don't see how to use alignment to do better. As it stands, misaligned integers tend to look more like pointers than integers with pointer-like alignment. For example, 3 is probably a common integer value. The word 0x3 is not a valid heap address for any C/C++ implementation I'm aware of. On the other hand 0x30000 (or possibly 0x300000000) could possibly be a valid heap pointer. A secondaty issue is that on modern hardware, misaligned data references are usually moderately expensive (if the hardware handles them automagically but sometimes generates a second physical memory operation) or extremely expensive (if the hardware doesn't). The collector can, and ours does, use some tricks internally to minimize false pointers. The most important one is "black-listing": It keeps track of known false pointers to regions near the heap, and refuses to allocate most objects there. I agree that whenever easily possible, the collector should use layout information for heap objects. (Whether ot not you should allocate such a descriptor for every object is a different issue. The answer is probably no; it may be cheaper to provide separate regions for common layouts, e.g. pointerfree objects. And it may be hard to provide full layout information for legacy code that uses C unions.) Stack frame descriptors are a harder problem, and things quickly get more controversial. A single descriptor per function frame works only if every given register or stack location contains always contains a pointer, or always contains a nonpointer, within the entire frame, or at least at every possible GC-point. This is likely to require larger frames and extra initialization of pointer slots. Without the latter, it's not likely to be much better than a conservative scan. (In practice, uninitialized and dead pointers tend to be at least as much of an issue as misidentified pointers on the stack.) Most type-accurate collectors seem to go the route of 1) GC-safe-points, plus 2) A descriptor per safe-point, plus 3) Some mechanism for advancing threads to safe-points (e.g. by executing code at safe-points), plus 4) A fairly messy "foreign function interface" to make legacy code fit into this. This doesn't look so simple anymore. The advantage of a conservative GC is that you get a choice: It can use the type information that you can provide, but it generally still works if that information is painful to provide. (To be fair, it's currently much more painful than it should be to provide stack layout information to our collector. But there are many clients that provide partial or complete information for heap objects. And there are many that don't.) Hans [ 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 Goto page 1, 2  Next Page 1 of 2   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.