Automatic Garbage Collection in Java and C++

Automatic Garbage Collection in Java and C++
Stephen Leibowitz

The purpose of this writing is to outline my views on automatic garbage collection (AGC) in Java and C++. It is well known that AGC is standard in Java, but is rarely available in C++. Garbage collection concerns objects with dynamic extent (allocated with a new statement in these languages). Java uses various techniques to automatically discover when these objects are no longer referred to, and to reclaim them. In contrast, C++ programmers manually specify where an object with dynamic extent is to be reclaimed by coding a delete statement.

In order to implement secure Internet applets, certain language restrictions are necessary. Some of these restrictions would also be helpful in implementing AGC. But even if the security restrictions were in place, I would have reservations about AGC.

The benefits of AGC would not be so great in C++:

Utilities such as Bounds-Checker, Purify, and HeapAgent can be used to detect memory leaks in C++. Some C++ development environments have built-in memory leak detectors. Correcting a memory leak has the added benefit of invoking the destructor, if it exists.
Consider the following quotation by Alex Stepanov in the March 1995 issue of Dr. Dobb’s Journal:

STL data structures will eliminate the majority of the needs for using new. Most people should not allocate arrays because STL does an effective job in doing so. I never need to use new in my code, and I pay great attention to efficiency. The code tends to be more efficient than if I were to use new. With the acceptance of STL, new will sort of fade away. STL also solves the problem of deleting because, for example, in the case of a vector, the destructor will destroy it on the exit from the block. You don’t need to worry about releasing the storage as you do when you use new. STL can dramatically minimize the demand for garbage collection. Disciplined use of containers allows you to do whatever you need to do without automatic memory management. The STL constructors and destructors do allocation properly.

In C++, objects can be allocated with automatic extent (on the stack). They are automatically reclaimed when they go out of scope. The term “AGC” is not applied to this reclaiming since it is fairly easy and efficient to implement in the language. The term is reserved for the more controversial proposition of reclaiming dynamic extent (heap) storage in an automated manner.

The Standard Template Library and a number of smart pointer libraries straddle this definition. These libraries themselves reclaim the heap objects that they manage and guard against memory leaks of those objects. But they avoid many of the costs of AGC, although neither AGC nor the smart pointer approach is as efficient as manual reclamation.

Java does not allow user-defined (class) types to be instantiated with automatic extent; they must be instantiated with dynamic extent. Hence, Java has a greater need than C++ for AGC.
I view memory leaks in user-written programs as a bug, but not a security problem. Memory leakage may reach a level where additional memory requests fail. But memory allocation failures can also happen in non-leakage situations. When a program ends, a well designed operating system or sandbox should be able to reclaim memory (and other resources) that the program had itself not freed. More generally, a well designed operating system or sandbox should be able to gracefully manage situations where the free memory or other resources become low.

Java-style AGC has costs besides the language restrictions that were referred to in the second paragraph:

Java classes can have a finalize function. But the facility is weak, compared to the C++ destructor. Java programmers sometimes resort to writing a separate class function for cleanup and calling it explicitly. The Java programmer may forget to call a cleanup function, just as easily as a C++ programmer may forget to use delete. This can cause non-memory leaks and other problems in Java programs. At least C++ programmers can often avail themselves of utilities to detect leakage. And C++ programmers do not use delete for class objects with automatic extent, while a separate cleanup function in Java would always have to be explicitly called.
Java uses run-time processing to discover dead objects (which are eligible for reclamation). In contrast, discovery occurs at compile-time in C++, courtesy of programmer-coded delete statements (for heap objects) and stack objects going out of scope at the end of blocks.

The more complex discovery process in Java uses more resources. The space overhead can be relatively large on small platforms. Compiling a program occurs less frequently than running it, another advantage for C++.

Java implementations may try to turn this extra processing into a virtue by using it to facilitate defragmention and compaction of heap memory (besides relieving the programmer from deleting objects and eliminating memory leaks). This and doing the reclamations en masse is the basis for claims that the overall efficiency of Java’s AGC compares well to C++ memory management.

I am skeptical of these claims. Stack storage is not fragmented in either language. C++ allows class objects to allocated on the stack, but Java does not. Also, keep in mind that there is a difference in the performance of the various C++ heap managers.
AGC is a significant variable that hurts Java’s suitability for real-time applications. The pauses may also be a disadvantage for interactive applications. There are efforts to improve its suitability, although I expect that C++ will still be better. I also expect that the Java modifications will be a tradeoff, requiring additional programmer effort, or reducing machine efficiency by doing less effective heap compacting.

Reference Counting

Smart pointer templates are commonly used in C++ to implement the memory management technique of reference counting. Unlike ordinary pointers, the smart pointers themselves invoke delete upon the reference count dropping to zero. They guard against memory leaks without resorting to Java-style AGC.

The Boost library has a number of these freely available smart pointer templates. Another freely available smart pointer template is the Loki library’s SmartPtr, which has a more parameterized design. The next C++ standard may incorporate one or more smart pointer templates for reference counting.

Reference counting has a significant limitation. It cannot reclaim a set of objects linked with cyclic (also known as circular) references. If a set loses all references from the outside, it becomes garbage and should be reclaimed. But the reference counts would not be zero, due to the cyclic references. Boost tested a smart pointer implementation that used a hybrid approach so as to correctly reclaim cyclic data structures, but the timing results were poor. Neither the Boost nor the Loki library has a smart pointer for cyclic structures.

In the writing above this section, I discussed the costs of Java-style AGC. I will now contrast that with how reference counting functions in a C++ environment. This assumes that the reference counting is not used for cyclic data:

The destructor is invoked immediately upon the reference count dropping to zero. This is better than AGC techniques. It might even be better than using manual reclamation, since a programmer might not optimally place delete.

Manual reclamation invokes the destructor in a deterministic manner, which is also the case for stack objects going out of scope. Reference counting shares that characteristic, and stands in contrast to most AGC techniques.
Some AGC techniques pause the program while garbage collection occurs. These pauses can vary with overall system conditions. The suitability of these AGC techniques for real-time or interactive applications tends to be less than either reference counting or manual reclamation.
Reference counting is less efficient than manual reclamation. There would be overhead each time a reference is added or removed. Also, the reference count takes up space, either within the smart pointer or the object pointed to.

AGC techniques can introduce significant overhead into a program even if only used for a single object. This is not so for reference counting, which has more of a per-object overhead (with some objects having more active reference counts than others). The per-object nature of reference counted overhead, along with the similarities in behavior noted above between reference counting and manual reclamation, makes it feasible to consider hybrid arrangements. Cyclic data would be the prime candidate to be manually reclaimed, as reference counting does not work correctly with it. But other objects could also be manually reclaimed, for better efficiency. A programmer might use reference counting for objects during the initial phases of development, with the option of later investing time to code delete statements for some or all of these objects.

The Limbo programming language uses a different approach. Except for cyclic data structures (which the programmer marks with the cyclic keyword), the language automatically manages dynamically created objects with reference counting, and considers it a form of AGC. The Limbo literature [Phil Winterbottom and Rob Pike: The design of the Inferno virtual machine] argues that for non-cyclic data, reference counting is superior to an AGC technique known as mark-and-sweep. It also faults Java for not using reference counting.

As explained above, reference counting does not work correctly with cyclic data. The designers of Limbo chose to manage cyclic data with mark-and-sweep AGC, instead of manual reclamation. The Limbo language does not have a destructor. Therefore, mark-and-sweep AGC cannot introduce uncertainties into Limbo programs as to when, or if, a destructor is called. The other characteristics, both good and bad, of the two techniques (reference counting and mark-and-sweep), do surface in Limbo programs.

C++ has powerful template and class facilities not available in Limbo, making smart pointers a logical and attractive approach to implementing reference counting in C++. This is in spite of some advantages to Limbo’s more integrated approach. While I have not benchmarked it, I suspect that Limbo’s automatic reference counting is at least as fast as intrusive_ptr, which in turn is faster than shared_ptr, both C++ smart pointers from Boost. Also, intrusive_ptr requires the programmer to supply definitions for two functions and to place the reference count inside the object being managed. The space for the reference count is wasted when the object is not managed with intrusive_ptr, such as when the object is stored on the stack or is manually reclaimed. Limbo’s reference counting and shared_ptr do not have these disadvantages of intrusive_ptr.