The method used in 3rd-party garbage collector

Question

I am writing to clarify some comments on this website.

1) I know that C++ has no garbage collector. One said that C++ was invented before the idea of garbage collector, so that's the reason. Is that true? I think it makes sense.

2) Whenever garbage collector was discussed, smart point(such as boost::share_ptr) was brought out to be a way. I was once convinced that reference counting is one way to implement garbage collector, but some said, smart point is not an implementation of garbage collector. What's the case?

3) Some said why garbage collector was not included in C++ is because it was hard and a lot of problem couldn't be solved. However, somebody else said that there were 3rd-party garbage collector were available, no matter it is commercial or for-free. So how does these 3rd-party deal with the problems?

I am grateful if anybody could clarify my confusions.

Thanks so much!

Answer 1

With regards to 1 and to a lesser degree 2:

This is a concise yet good explanation.

http://www.devx.com/tips/Tip/12766

Plus there is this similar question posted on here about the topic.

http://stackoverflow.com/questions/147130/why-doesnt-c-have-a-garbage-collector

Check them out.

Answer 2

1. no, garbage collection is far older than C++ (many Lisp versions had it in the '60s, in particular).

2. reference counting is a way to implement garbage collection, but it's quite poor performance-wise (the new Unladen Swallow project, to accelerate the CPython interpreter, includes moving from reference counting to a better garbage collection implementation -- a substantial performance boost).

3. the Boehm collector for C and C++ uses a conservative approach: briefly, anything that looks like an address is taken to be one (so whatever it might "point to" is not collected). Read the page at the URL I've given, and its outgoing links, for much more information on the subject.

Answer 3

According to http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29 Garbage collection was invented in 1959 which would significantly pre-date C++.

The reason C++ does not include a garbage collector is because you, the programmer, manage the memory, a feature inherited from C. A garbage collector is part of a language where memory management is done for you. You could implement one but you'd have to use your implementation to manage all of your memory access - otherwise, you'd be circumventing it. In short, GC is part of a layer between you (in whatever language you're in) and the underlying memory of the system.

Answer 4

Minimal support for garbage collection - but no garbage collector - will be added to the next C++ standard (informally called C++0x). Here's a good paper about it: http://www.hpl.hp.com/techreports/2009/HPL-2009-360.pdf

Answer 5

1. As Alex pointed out, LISP has had garbage collection since well before C++ was invented. OTOH, some of those early implementations used reference counting.

2. Most people discussing garbage collection are thinking of something that's hidden. Reference counting does have a number of problems. It can have performance problems, but as objects are normally used in C++, rarely does. A much bigger problem is that reference counting doesn't normally deal well with cycles in the data. For a trivial example, consider:

   struct node { node *next; };

   node *node1 = new node, node2 = new node;

   node1->next = node2; node2->next = node1;

   Since each node now references the other, their reference counts will remain non-zero, even if nothing else refers to either one. They aren't collected, even after they become inaccessible. This problem is surmountable, however.

3. When you use the third party garbage collectors with C++, the result isn't (quite) a conforming implementation of C++ any more. For example, if you "swizzle" a pointer (e.g. invert all its bits) the GC won't recognize what it points at. When you "un-swizzle" it (flap the bits back) what it pointed at may no longer exist. Problems in real code, however, are sufficiently unusual that people use GC regularly without any problems.

   OTOH, there are also limitations, so most garbage collectors for C and C++ don't really work very well either. Most recent GC designs work by copying objects that still exist so they're all contiguous in the heap after a GC cycle has taken place. To do this, it has to "fix" all the pointers to that object to point to the new address. Since a GC with C or C++ doesn't know for sure what's a pointer or not, it can't modify things (in case something isn't a pointer) so it has to leave objects in place, which hurts performance.

There have been some serious discussions about adding GC to C++. Two comp.lang.c++.moderated threads might be interesting. Warning: they are pretty long, and some arguments get repeated, several times in a few cases. OTOH, they do point out some real issues, and possible solutions.