Garbage Collection Synopsis, and C++

34 thoughts on “Garbage Collection Synopsis, and C++”

1. I remain unconvinced that GC is a great sole solution for memory management. I’ve rarely needed it except in certain complex object graphs. It only addresses one leak point, references can still be leaked. Also having all objects with a non-deterministic lifetime is often inconvenient. From the systems I’ve worked on there are often unsavvory side effects that occur under certain conditions.

   I do want to be able to use it, but I want to dictate when and to what extent I want to use it. C# to some degree allows that with “using”. But that’s still a bit clumbsy. Maybe approached from the opposite direction would be better, where rather than default to GC you have an allocator/pointer that would allow you to indicate objects to be managed by GC. But from my experience with JavaScript and XPCOM’s reference counting mechanism that might prove difficult.

2. GC is for lazy programmers. C++ programmers dont need it.

3. It seems to me that you’d want to be able to classify certain types as only managing memory, so they can be used in GC’d or non-GC’d code (with dtors skipped). Of course we’d need to be able to propagate that information through the type system à la noexcept. Probably that sort of propagation mechanism needs to be generalized.

4. If GC is ever added to the standard I strongly believe it should be limited only to the types with trivial destructors. There should be no change in the current syntax or new keywords or new type of pointers. That limits the useability but it also keeps programs from unholy interraction of GC with destructors. Trivial destructors will be consistent with infinite life time implied by GC, so the program will not be able to detect the difference. Compiler vendors can implement this behavior within the current standard, though adding it as a requirement will make code portable.

   On the positive side, I forsee new books coming about GC gotchas in C++, which makes life even more interesting — You did what? Added a destructor? Now your program leaks! Isn’t that sweet :-)

5. I designed a GC library for C++. It’s not quite automatic, but it has a simple command for quickly going through and picking up unused memory references. The command could be timed, put into some algorithm, or manually inputted at certain points in the code sequence that is natural for a GC sweep. Overall it’s extremely efficient, though I can’t guarantee that is commercial grade since I got bored of it after design.

6. If these questions are “just details” then you and I are having different discussions. I’m trying to address the biggest challenge in achieving your goals (with which I don’t take issue): coming up with a coherent programming model that accomodates both GC and destructors. To get there, you need to determine if/which things that used to be implementation details would subsequently have to be documented in interfaces, and these questions you’re calling “details” make a huge difference in the answers.

   Your goals to clean up shared_ptr cycles and support lock-free programming are great; my skepticism about achieving it with a GC language feature comes from the lack of good answers to questions about the programming model. In my opinion there’s nothing interesting to say about GC in C++ until those questions are addressed.

7. Whatever gc_new or make_gc etc. returns would be GC’d. It’s a separate design decision whether it would be better to call that thing a * or some other pointer type like gc_ptr or something (just as shared_ptr and unique_ptr and weak_ptr and * are all different standard pointer types). I can see benefits and drawbacks both ways, reusing */& or not reusing */&.

   These are interesting design questions that any specific proposal has to answer concretely and that have several promising potential design answers. But for the purposes of this discussion they are really just details that shouldn’t obscure the main goal, which is to not remove/replace any existing uses (e.g., uses of std:: smart pointers or *’s or change the programming model to want to gcnew everything, etc.), only to additionally solve those problems std:: smart pointers cannot (specifically shared_ptr cycles and ABA).

8. Sorry, but that doesn’t answer the question. Let me rephrase. If I take a raw pointer or reference to an object allocated with gc_new, is the existence of that pointer enough to keep the object alive, or not?

9. You still haven’t said whether all pointers or only special pointers participate in refcounting.

   My interest is in cleaning up cycles of shared_ptrs, and objects allocated with an explicit opt-in GC heap allocator (e.g., gc_new T or gc_allocator or some such). Only the cases std::*_ptr can’t deal with today.

10. Here are my answers to your main questions. I think Bjarne would give similar answers; he’s long been a proponent of optional GC (#2) for ISO C++.

    Briefly:

    Adding a new feature to a language should be based on good reasoning, such as:

    a) How likely will the feature be abused more than used well?
    
    b) How often is the feature needed at all?

    c) What cost or how viral is the feature? (does it force itself on those who might not want it)

    @Herb, what are your answers to these a/b/c questions? Can I see your answers?

    The fundamental point is that something is worth standardizing iff it’s important to support in portable code, and pulls its weight including being worth whatever cost there might be. To evaluate that, the committee members consider issues like those above as input.

    The answers to the above could be different for different GC proposals, but for the one I have in mind (GC for shared_ptr cycles + memory allocated with an explicitly GC-requested allocator such as a gc_new T or gc_allocator<T>), I think the answers are:

    a) I think it would be used well and rarely, because we’d teach to never use it by default (shared_ptr et al. are and should continue to be the recommended default);

    b) The feature should be needed rarely, but is required for interesting and important cases that simply can’t be handled in portable C++ code today. It’s kind of like what Booch said about multiple inheritance: You rarely need it, but when you need it you really need it and nothing else will do.

    c) I would hope it would be contained and not viral at all. I don’t see why it couldn’t be done in a very targeted way.

    Secondly, are you sure your motivation is not more driven by the desire to make C++ play better with languages that already have pervasive GC, rather than by the value that GC brings to C++ itself?

    That’s a natural question, because I’m heavily involved in C++/CLI and C++/CX.

    Yes, I’m sure. My motivation here is not related to those, though I’ve learned a lot from doing them. C++/CLI and C++CX are a different topic because they are bindings to foreign object models and runtime systems. C++/CLI binds to .NET, which supports GC (#3 above). C++/CX binds to Windows 8 WinRT, which uses pure reference counting only (#1 above), cycle leaking and all, and here ^ and ref new can basically be thought of as a flavor of shared_ptr and make_shared baked into the compiler, plus COM details that shared_ptr and make_shared can’t handle which is why we couldn’t just use shared_ptr itself.

    In this post’s topic, I am only interested in what makes sense for native (and possibly standard) C++, and the value GC (specifically #2) brings there. My motivation is to be able to write portable C++ code that can deal with shared_ptr cycles, and portable code to express those relatively rare, but genuinely interesting and important, algorithms that actually do require GC, which include important high-performance lock-free algorithms.

    Note that for several years now I’ve been writing and teaching about Effective Concurrency in all the major languages — C++, Java, C#, and C+pthreads – and in the lock-free code section I keep having to add comments about how certain examples are easy/easier in Java and C#, and hand-wave about what it would take to do them in C++. I hate that.

    I mean, if the discussion continues as is, which seems to be roughly trying to answer the isolated question of:

    “what is the value of GC to C++?”

    then I suspsect the majority of C++ people will just conclude the answer is “GC offers insufficient value to warrant making it pervasive in the language”

    I was with you until the last sentence, which shifted to “pervasive.” I don’t know of anyone (including me) who is arguing for making it pervasive in the language; as I argued in my Writing Modern C++ Code talk at Build, C++ is doing very well with ref counting as its primary memory and resource management tool.

    The answer to “what is the value of GC to C++?” is “to handle the remaining important cases ref counting can’t, such as shared_ptr cycles and ABA problems in high-performance lock-free code,” not to replace any existing use of ref counting. GC should be purely additive.

11. Pingback: Garbage collection/reference counting in C++11 - Devalot
12. Adding a new feature to a language should be based on good reasoning, such as:

    a) How likely will the feature be abused more than used well?
    b) How often is the feature needed at all?
    c) What cost or how viral is the feature? (does it force itself on those who might not want it)

    If a feature fails these tests, then the feature should most likely not be included, or be included in a mitigated way.

    In the case of adding the GC feature to C++, if these tests could be considered in isolation, I thoroughly (so far) fail to see enough value in adding GC to C++; because when I apply these tests to GC, I get these results:

    on point a), I think GC will be considered the “easy” option so will be used to excess as a magic bullet when it is not.
    on point b), I rarely, if ever, find myself writing much code where I think “wow, if only I had GC right now…”
    on point c), if point a) turns out to be true, I will find my application becoming the undesired “beneficiary” of a lot of garbage I didn’t create and can’t control.

    So given these are my answers, thus far (and I am open to being convinced), I strongly agree with @Frank Davis that adding GC to C++ will make GC virus like for C++, and quite likely to the detriment of C++’s own superior way of doing things.

    @Herb, what are your answers to these a/b/c questions? Can I see your answers? Secondly, are you sure your motivation is not more driven by the desire to make C++ play better with languages that already have pervasive GC, rather than by the value that GC brings to C++ itself?

    If that’s the real motivation, then @everybody, perhaps we should just deal to that question instead? If we try to justify (or not) GC and C++ on their own terms as the discussion seems to be framed thus far, I suspect we will get the wrong or limited answers. I think to get better answers we need to ask a broader question:

    I mean, if the discussion continues as is, which seems to be roughly trying to answer the isolated question of:

    “what is the value of GC to C++?”

    then I suspsect the majority of C++ people will just conclude the answer is “GC offers insufficient value to warrant making it pervasive in the language” and that will be that, for reasons very much like the ones I have given above.

    However, if the right question is really this:

    “Given that many other languages (possibly wrongly) have chosen to make GC pervasive, how can (or even should) C++ interoperate with those languages, and can it be done without destructing/debasing C++ itself? If we don’t allow such easy interoperability, are we doing more damage to C++ by marginalising C++ than by providing the choice?”

    If we ask that question, I think we’ll get different and possibly more useful answers?

    What says @others?

    I think what we are really talking about here is “should we, and how do we integrate c++ with C#, Java, and javascript etc and other languages.”

    Isn’t Herb’s answer to this (in the context of MS at least) already known, it’s C++/CX and C++/CLI?

    @others: Regardless of whether Herb convinces others of the value of GC, the question of if/how to integrate better with languages that have it still needs to be answered. Does it not? If one says simply C++ does not need GC (which I currently feel) are we not also saying C++ can’t easily integrate with those that already have GC? That part I’m not sure how I feel. I do feel both questions go together though.

    I think minds against GC should be aware of that when answering about saying no to it.

    Is C++/CLI or C++/CX the answer? Can we improve on it or mitigate it? and can/should it be part of ISO C++?

    @Dave, I’m keen to hear your thoughts on all this point of view and these questions. Thanks. :)

13. I’ve written a
    lock-free doubly linked list using portable C++11 style threads/atomics. The limitations of hazard pointers that I think you’re talking about can be patched up with what basically amounts to GC, but it’s a GC optimized for the problem domain and turns out to be quite trivial, deterministic and lock-free.

14. Final judgement reserved of course, but I’ve spent a lot of time thinking about this problem and haven’t seen or found anything that solves it yet, so forgive me if I’m skeptical.

    If the calling code that owns the object wants it to be destroyed deterministically, and the object may participate in a cycle, then the code has to break the cycle. The object itself doesn’t and shouldn’t care so its code is unaffected.

    Great; you insulate the object from the knowledge that it might be leaked. But you don’t insulate client code from the knowledge that the object participates in a cycle or that its destructor (possibly indirectly) handles non-memory resources. Now every class that might participate in a reference cycle or manage non-memory resources needs to advertise that fact; it can never be an implementation detail.

    You still haven’t said whether all pointers or only special pointers participate in refcounting.

    With regard to “relying on accurate GC,” I can’t imagine what visible effects would allow a program to determine that it has an accurate GC, and I can’t imagine what standard language you could write that would force an implementation to provide an accurate GC… or any GC for that matter. For what it’s worth, I don’t have a position on accurate-vs-conservative GC; everything I’ve said about the programming model applies equally to both.

    Hazard pointers seem reasonably straighforward to me, and it doesn’t seem to me that merely having a GC is going to make the shark-infested waters of lockfree programming seem easy and safe to anyone.

15. All I ask is that you reserve your judgment until hearing out a complete proposal. :)

    Briefly answering your questions:

    Ordered destructors must always get called deterministically (only), as today. They cannot be called while automatically/lazily cleaning up cycles because cycle cleanup is unordered. The natural tool for unordered cleanup is the unordered finalizer, if unordered cleanup is to be supported at all of course.

    It’s up to the calling code that owns a particular object to manage its lifetime. If the calling code that owns the object wants it to be destroyed deterministically, and the object may participate in a cycle, then the code has to break the cycle. The object itself doesn’t and shouldn’t care so its code is unaffected.

    All existing C++ garbage collectors, notably the Boehm collector, aren’t enough for many interesting uses for several reasons, the main one being that they’re conservative, not accurate. See Hans Boehm’s page Advantages and Disadvantages of Conservative Garbage Collection for more discussion of tradeoffs.

    As usual, there’s something to standardize iff we want to enable portability. So in this case the question is whether it’s interesting to enable portable programs that rely on GC — and note that typically if they rely on GC, they rely specifically on accurate GC, not conservative “maybe-GC.” For example, C++11 atomics enable writing many kinds of portable lock-free code, but not all; we need a standard for #2 [*] if we want to enable people to write portable lock-free singly-linked lists, where the only known practical algorithms require automatic (non-refcount) GC and so they cannot be implemented in portable C++ today without some nonportable platform-specific code underneath. [**]

    [*] Or #3, but that’s more invasive in the language. Normal pointers can handle #2, but not #3.

    [**] Again, appeals to hazard pointers fail because the obscure convolutions and limitations of hazard pointers only expose the limits of even the most heroic efforts to work around the lack of true automatic GC. The main contribution of hazard pointers, unfortunately, is that they thoroughly motivate why direct support for automatic GC is needed. It’s similar to how Boost.Lambda is wonderful for a few basic cases if: (a) you can live within the limitations (e.g., on member functions) and remember them every time and don’t accidentally reach for something they can’t do; and (b) spell everything correctly the first time so you avoid the undebuggable template error cascades. Both (a) and (b) are routinely violated even by developers familiar with the library, and so Boost.Lambda mostly serves as thorough motivation for why language support for lambdas is needed, and are cited as such in the original C++0x lambda proposal (see section 1.1).

16. Jones and Lins is indeed great but it’s a decade and a half old. Jones just published an updated version with two different co-authors, Hosking and Moss, The Garbage Collection Handbook, available here. I haven’t had time to really look at this new edition, although it comments that many foundational explanations are more concise in the new book and if they’re problematic you might want to look at the older one.

    Speaking of books, Mr. Cutter, when are you going to publish your’s on the fun of low level concurrency? At the end, your superb column was the only reason I was still reading the paper magazine….

17. GC type 2 and 3 would be a bad addition to the language. If those are needed for a *particular* type of application, then they sould be provided as libraries. Most kind of applications only need the first type.

18. Some important details missing here: do regular C++ pointers refcount, or just some special GC/smart pointer (I presume the latter)? Do you plan to call destructors during cycle reclamation (I presume not)?.

    Regardless of the answers, I think this approach is problematic. It doesn’t matter what small fraction of objects get reclaimed by GC; as long as GC is in the system and a GC’d object can contain an object whose destructor matters, we’re breaking the implicit contract with class authors that destructors will be called, (or that they’ll work as designed if you do intend to call them).

    The basic programming model remains the same: if you leak stuff, it won’t (necessarily) get destroyed and its memory might eventually be reclaimed. These are exactly the guarantees that the C++ standard gives you today. Personally, I wouldn’t waste the cycles on refcounting if that’s all you’re getting. To leak objects and get their destructors called, you need to know they don’t participate in any cycles, which is very difficult in general, even if you have a special GC pointer (because people will use it liberally).

    Any vendor who wants to support the programming model where leaking memory is (sometimes) harmless can ship the Boehm collector as part of their runtime. I seriously don’t think there’s anything to standardize here.

19. and Apple added and promoted GC to Objective-C only to kind of back down. now not so promoted and iOS does not support it. besides ref counting is not very hard to do and works just fine. atleast in ObjC :)

    http://arstechnica.com/apple/reviews/2011/07/mac-os-x-10-7.ars/10#arc

20. See other comments, but briefly: cleaning up cycles of shared_ptrs, which you can often design away but sometimes naturally arise; and lock-free coding to solve the ABA problem and other issues, where it really makes the code way simpler, and you really don’t want to dip into the murky waters of hazard pointers which are mainly useful to show the extent of the heroic efforts to deal with this problem without automatic non-RC GC.

21. That’s not the only alternative. Destructors and finalizers are different and complementary (and you virtually always want the former, as mentioned in other comments below).

    Reference counting (#1) is often the best and it’s C++’s default form of GC. But there are reasons to also (not instead) want lazy mark-sweep (#2) garbage collection in C++ to deal with things ref counting can’t deal with, including when potential cycles are unavoidable (in some cases some objects may naturally be shared, but then might refer to each other) and lock-free ABA issues.

    My impression is that the best memory management model for future C++ will be reference counting nearly always (#1) plus mark-sweep GC (#2) to reclaim ref count cycles and enable important lock-free code styles that smart pointers alone can’t support.

    Using #2 as a backup for #1 in this way has been well explored in the past in other languages and systems. It is known to work well, it makes #2 faster because you have less memory to inspect (e.g., Bacon’s observation that you can’t get a cycle unless a ref count decrement results in a nonzero count, so you only add those to a root list), and you only need unordered finalizers (if at all) for the objects cleaned up by #2 (e.g., if there’s a cycle you have to pick a loser and break it somewhere, and for the non-cycle cases you typically can arrange for those objects to not own resources so no finalizer is necessary).

    So my current position is to support: (a) adding mark-sweep GC to a future C++ standard, but to use it only for cleaning up shared_ptr cycles and objects allocated with a separate “gcnew” or similar opt-in GC allocation to cover the lock-free uses; and (b) not support finalizers at all, which I think we can get away with — they’re strongly discouraged even in the systems like Java and .NET that have way more potential need for them because they lack any kind of standard reference counting to have a stronger deterministic destruction story.

22. For example, see this 2005 chapter from the .NET Design Guidelines, especially the annotations I provided.

    C++/CLI has prior art showing an elegant way to expose finalizers in C++. It uses the T::!T() syntax. But yes, you should not rely on unordered finalizers, deterministic ordered destructors are much preferable in all languages including C# and Java, and C++ does them best including when using smart pointers.

23. Ask any GC expert and they’ll tell you that confusing finalizers with destructors is a fatal error. They’re really distinct beasts, in so many ways: finalizers have no ordering constraints, no guarantee they will ever get called, etc…. Read what the Josh Bloch has to say about finalizers in Java: his guideline is basically, “don’t use finalizers for anything that matters.”

24. @Martin Vejnár: That is one argument that’s been made. Last I heard, it helps in lock-free programming because nobody knows how to do deallocation efficiently without stopping the world.

25. Or you could have special destructors for releasing memory, and then you would know if its a GC type or non-GC type by checking if it has a non trivial destructor. If GC is disabled(I assume if it was built-in to C++ it would be optional), it would make the memory destructor part of the main destructor. So ultimately it would have a non trivial destructor with the GC disabled and a trivial destructor when the GC is enabled.

    Especially on multi-core machine, the GC generally has better performance than reference counting, because the collection can be done in separate thread.

26. Garbage collected object can still have a sort of destructors, traditionally called “finalizer”s, which could close files, etc, i.e. release non-memory resources. Finalizers have their own set of problems, though. For example, since the garbage collectors conservatively approximate object lifetime with object reachability, it’s not clear what do to when a finalizer is run on an unreachable object, but that finalizer makes the object reachable again (i.e. the reachability approximation of lifetime no longer holds. Oh well, one can always take the “undefined behavior” escape route :). Another issue is triggering of collection – one can reasonably assume that a shortage of memory would cause unreachable, but not yet collected object to be collected, in effect releasing memory, whereas shortage of non-memory resources … well it will need to be integrated with the garbage collector somehow …

27. I don’t want to come across as stubborn or stuck in my ways, but I really do not want to see a built in GC as a part of the C++ standard.

    I think memory can be managed easily if you are willing to learn the simple smart pointer abstractions. Shared pointer is basically a rudimentary GC which maintains constant execution time.

    Furthermore I know that if it was to be introduced, libraries would quickly introduce it and it would become be hard to build a non GC (therefore known execution time) out of component libraries. Look at Objective C and D as examples of to the metal languages with a GC, almost all of the code written for them usually the GC by default. They have a place but it isn’t the same as C++.

28. Reference counting covers a lot,, if not most of cases. It requires careful planning not to introduce cycles via subclasses, but it is quite ubiquitous in the C++ world nowadays, and therefore GC is not really required.

    In case someone is interested, I have a new idea regarding collection: instead of tracing objects from roots, let the roots be traced from objects. I’ve made an implementation here: https://github.com/axilmar/a5gc

29. “what anyone would use GC for”
    I’ve come across one case where GC actually makes things easier: a data-structure for storing un-rooted trees, where the inner nodes are represented by circular linked lists (this kind of structure is common in computational phylogenetics). The circular links don’t work with ref-counting and the trees can be freely split/merged, so it’s kind of cumbersome to keep track of the separate trees for manual de-allocation. A manual mark/sweep GC was the most convenient solution. Apart from that, I’ve been quite happy without mandatory GC. Have not seen a memory-leak for a while…

30. I was wandering the same thing. Is there perhaps a performance benefit in delaying memory releases so that multiple of them can be processed in batch?

31. Pingback: 조영일의 자리 매김 · [번역] shared_ptr
32. Hi,
    This is perhaps a good place to ask what anyone would use GC for. I understand that it is indispensable in Java because you cannot allocate objects on “the stack”. In contrast, C++ offers automatic life-time and memory management.

    What are the practical uses of GC in C++? What are the practical uses of shared_ptr?

    Regards,
    &rzej

33. “OK, GC was invented half a century ago. When it is going to land in the C++ world?”

    Honest question: what uses have you seen for GC?

    Getting rid of the ABA tag in some lock-free algorithms is one, but there are other solutions with similar efficiency and flexibility.

    .NET has a lot of small heap allocations so compaction is pretty nice for maintaining low fragmentation (and possibly locality). The heap is touched far less often in C++, so I see compaction as less important here.

    Resource management in C++ has been easy for some time now. Easier than in C#, even. I can’t remember the last time I had a memory leak.

34. The greatest obstacle to integrating GC with C++ is the lack of a programming model for mixing GC with destructors. Today, when I write a class with a destructor, I can, as an implementation detail, make it hold a file open, claim mutexes, or handle any other non-memory resource I want it to, so long as I clean those resources up in the destructor. I can be assured that—so long as the user of my class plays by the rules—the destructor will always get called and those resources will be released.

    Now, in a world with GC, it’s de-rigeur to place objects into data structures and simply leak them, secure in the knowledge that they will be cleaned up as necessary. The problem, if we start doing that, is that the destructors of objects managing non-memory resources are no longer called. So what’s the programming model for using GC in C++? If we still have to write code to destroy/delete objects, then the programming model isn’t changed, and there’s no benefit to users in standardizing GC. Any vendor who wants to can add a GC for cleaning up leaked memory as a conforming extension.

    The alternative is to declare some classes as GC’d-only and some as non-GC’d, and disallow non-GC’d classes inside GC’d classes. But that’s awful :-)

Comments are closed.