Data Structures and Algorithms with Object-Oriented Design Patterns in Ruby
next up previous index

What is Garbage?

While Ruby 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 Ruby virtual machine is required to ensure that the object exists. If the Ruby 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, Ruby 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 Ruby program is doomed to eventual failure due to memory exhaustion. Indeed this would be the case, were it not for the fact that the Ruby language specification requires the Ruby 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 Ruby language does not specify precisely how objects are to be represented in the memory of a Ruby 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 Ruby 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 to create a new object is a fixed constant, tex2html_wrap_inline57235, 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 Ruby 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, creating a new object 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.

next up previous index

Bruno Copyright © 2004 by Bruno R. Preiss, P.Eng. All rights reserved.