lotus

previous page: 3.8.7) Books, Articles, And Literature (OMG/OMA/ORB/CORBA - Object-Oriented Technology)
  
page up: Object-Oriented Technology FAQ
  
next page: 3.9b) Why is Garbage Collection Necessary for Object-Oriented Programming? (Object-Oriented Technology)

3.9) Why is Garbage Collection A Good Thing? (Object-Oriented Technology)




Description

This article is from the Object-Oriented Technology FAQ, by Bob Hathaway rjh@geodesic.com with numerous contributions by others.

3.9) Why is Garbage Collection A Good Thing? (Object-Oriented Technology)

There are two entries on garbage collection, the first is an excellent entry
written for the FAQ by Paul Johnson and the second is from the FAQ author's
company on the necessity of garbage collection for object-oriented programming
and technique.

From: Paul Johnson (paj@gec-mrc.co.uk)

Garbage collection (GC) is a facility in the run-time system associated with a
language which will automatically reclaim objects which are no longer used.
OO Languages which require garbage collection include Eiffel, Smalltalk and
CLOS. C and C++ can have garbage collection retrofitted (see [3] and [4]
below). [Ada has switchable GC, too -bob]

Without GC programmers must explicitly deallocate dynamic storage when
it is no longer needed (in C this is done by a call to free(3)).
There are a number of problems with this:

1: Bugs due to errors in storage deallocation are very hard to find,
although products are available which can help.

2: In some circumstances the decision about whether to deallocate
storage cannot be made by the programmer. Drawing editors and
interpreters often suffer from this. The usual result is that the
programmer has to write an application-specific garbage collector.

3: An object which is responsible for deallocating storage must be
certain that no other object still needs that storage. Thus many
modules must co-operate closely. This leads to a tight binding
between supposedly independent modules.

4: Libraries with different deallocation strategies are often
incompatible, hindering reuse.

5: In order to avoid problems 3 and 4, programmers may end up copying
and comparing whole objects rather than just references. This is a
particular problem with temporary values produced by C++ overloaded
operators.

6: Because keeping track of storage is extra work, programmers often
resort to statically allocated arrays. This in turn leads to
arbitrary restrictions on input data which can cause failure when
the assumptions behind the chosen limits no longer apply. For
instance many C compilers limit expression nesting, identifier
length, include file nesting and macro stack depth. This causes
problems for programs that generate C.

One partial solution to a lack of GC is reference counting. In this
scheme each object keeps a count of references to it. When this count
drops to zero the object is automatically deallocated. However this
is inefficient (swapping two references will result in three
decrements, three increments and six comparisons) and cannot reclaim
circular data structures. Two systems that use a reference count GC
are the Interviews C++ graphics library and the Unix file system (the
link count).

Opponents of GC reply that it introduces an overhead which is
unacceptable in some applications. However the overhead of manual
storage deallocation is probably as high as GC. GC algorithms are
also available with good real-time behaviour.

[Further, GC can perform compaction improving locality of reference.]

Further Reading:

[1] "Object-Oriented Software Construction" by Meyer puts the argument
for GC.

[2] "Uniprocessor Garbage Collection Techniques," by Paul R. Wilson,
in Memory Management (proceedings of 1992 Int'l Workshop on Memory
Management, Sept. 1992, St. Malo, France, Yves Bekkers and Jacques Cohen,
eds.), Springer Verlag Lecture Notes in Computer Science #637.

This is an excellent summary of the state of the art in GC algorithms. This
and other papers about garbage collection are available in PostScript via
anonymous ftp (cs.utexas.edu:pub/garbage/gcsurvey.ps. [See APPENDIX E]

[3] "Garbage Collection in an Uncooperative Environment" by Boehm and
Weiser. Software --- Practise and Experience vol 18(9), pp 807-820.
Sept 1988. This describes GC in C and C++.
ftp://parcftp.xerox.com/pub/gc/gc.html

[4] Geodesic Systems provides GC for C and C++. See http://www.geodesic.com
and Appendix G.

 

Continue to:













TOP
previous page: 3.8.7) Books, Articles, And Literature (OMG/OMA/ORB/CORBA - Object-Oriented Technology)
  
page up: Object-Oriented Technology FAQ
  
next page: 3.9b) Why is Garbage Collection Necessary for Object-Oriented Programming? (Object-Oriented Technology)