Data Structures and Algorithms with Object-Oriented Design Patterns in Java

What is Garbage?

While Java provides the means to create an object, the language does not provide the means to destroy an object explicitly. As long as a program contains a reference to some object instance, the Java virtual machine is required to ensure that the object exists. If the Java language provided the means to destroy objects, it would be possible for a program to destroy an object even when a reference to that object still existed. This situation is unsafe because the program could attempt later to invoke a method on the destroyed object, leading to unpredictable results.

The situation which arises when a program contains a reference (or pointer) to a destroyed object is called a dangling reference (or dangling pointer ). By disallowing the explicit destruction of objects, Java eliminates the problem of dangling references.

Languages that support the explicit destruction of objects typically require the program to keep track of all the objects it creates and to destroy them explicitly when they are not longer needed. If a program somehow loses track of an object it has created then that object cannot be destroyed. And if the object is never destroyed, the memory occupied by that object cannot be used again by the program.

A program that loses track of objects before it destroys them suffers from a memory leak . If we run a program that has a memory leak for a very long time, it is quite possible that it will exhaust all the available memory and eventually fail because no new objects can be created.

It would seem that by disallowing the explicit destruction of objects, a Java program is doomed to eventual failure due to memory exhaustion. Indeed this would be the case, were it not for the fact that the Java language specification requires the Java virtual machine to be able to find unreferenced objects and to reclaim the memory locations allocated to those objects. An unreferenced object is called garbage and the process of finding all the unreferenced objects and reclaiming the storage is called garbage collection .

Just as the Java language does not specify precisely how objects are to be represented in the memory of a virtual machine, the language specification also does not stipulate how the garbage collection is to be implemented or when it should be done. Garbage collection is usually invoked when the total amount of memory allocated to a Java program exceeds some threshold. Typically, the program is suspended while the garbage collection is done.

In the analyses presented in the preceding chapters we assume that the running time of the new operator is a fixed constant, , and we completely ignore the garbage collection overhead. In reality, neither assumption is valid. Even if sufficient memory is available, the time required by the Java virtual machine to locate an unused region of memory depends very much on the data structures used to keep track of the memory regions allocated to a program as well as on the way in which a program uses the objects it creates. Furthermore, invoking the new operator may trigger the garbage collection process. The running time for garbage collection can be a significant fraction of the total running time of a program.