ASP.NET
C#
C++
ColdFusion
COM/COM+
Delphi-Kylix
Design Usability
Development Cycles
DHTML
Embedded Tools
Flash
Graphic Design
HTML
IIS
Interviews
Java
JavaScript
MySQL
Oracle
Photoshop
PHP
Reviews
Ruby-on-Rails
SQL
SQL Server
Style Sheets
VB.Net
Visual Basic
Web Authoring
Web Services
Web Standards
XML
Mobile Linux
App Generation ROI
IBM® developerWorks
Weekly Newsletter
Developer Updates
Free Website Content
IBM developerWorks
RSS Articles
RSS Forums
RSS All Feeds
Write For Us Get Paid
Request Media Kit
Contact Us
Site Map
Privacy Policy
Support
USERNAME
PASSWORD
>>> SIGN UP!
Lost Password?
C++
RSS
A Simple Garbage Collector for C++
# By: McGraw-Hill/Osborne Search For More Articles!
# Disclaimer
# Author Terms
Rating: 4 stars4 stars4 stars4 stars4 stars / 46
2005-06-21
Table of Contents:
# A Simple Garbage Collector for C++
# Comparing the Two Approaches to Memory Management
# Choosing a Garbage Collection Algorithm
# What About auto_ptr?
# An Overview of the Garbage Collector Classes
# GCPtr In Detail
# The Overloaded Assignment Operators
# GCInfo
# How to Use GCPtr
# Allocating Arrays
# A Larger Demonstration Program
# Load Testing
Rate this Article: Poor Best
ADD THIS ARTICLE TO:
Del.ici.ous Digg
Blink Simpy
Google Spurl
Y! MyWeb Furl
Email Me Similar Content When Posted
Add Developer Shed Article Feed To Your Site
Email Article To Friend
Print Version Of Article
PDF Version Of Article
BTM Corporation
ADVERTISEMENT
Free Web 2.0 Code Generator! Generate data entry and reporting .NET Web apps in minutes. Quickly create visually stunning, feature-rich apps that are easy to customize and ready to deploy. Download Now!
1.
[Sponsor: Web 2.0 Code Generator - Create robust database and reporting apps from your data! Try it FREE! ] Web 2.0 Code Generator - Create robust database and reporting apps from your data! Try it FREE!
(Sponsor)
2.
[Dev Articles News: What`s the Address? Pointers] What`s the Address? Pointers
(2005-07-28)
3.
[ASP Free News: SatView: Pointer Perfect, part 3.5] SatView: Pointer Perfect, part 3.5
(2004-12-17)
4.
[ASP Free News: SatView: Pointer Perfect, part 4] SatView: Pointer Perfect, part 4
(2004-12-22)
5.
[ASP Free News: Satview: Pointer Perfect, Part 3] Satview: Pointer Perfect, Part 3
(2004-12-09)
6.
[Dev Articles News: Pointers In C - A Boon Or A Bane?] Pointers In C - A Boon Or A Bane?
(2002-08-19)
7.
[ASP Free News: SatView: Pointer Perfect, Part 2: Construction / Destruction] SatView: Pointer Perfect, Part 2: Construction / Destruction
(2004-12-03)
8.
[DevShed News: Developing a URL Handling Helper Class in PHP 5] Developing a URL Handling Helper Class in PHP 5
(2009-07-10)
A Simple Garbage Collector for C++ - Choosing a Garbage Collection Algorithm
(Page 3 of 12 )
Before implementing a garbage collector for C++, it is necessary to decide what garbage collection algorithm to use. The topic of garbage collection is a large one, having been the focus of serious academic study for many years. Because it presents an intriguing problem for which there is a variety of solutions, a number of different garbage collection algorithms have been designed. It is far beyond the scope of this book to examine each in detail. However, there are three archetypal approaches: reference counting, mark and sweep, and copying. Before choosing an approach, it will be useful to review these three algorithms.
Reference Counting
In reference counting, each dynamically allocated piece of memory has associated with it a reference count. This count is incremented each time a reference to the memory is added and decremented each time a reference to the memory is removed. In C++ terms, this means that each time a pointer is set to point to a piece of allocated memory, the reference count associated with that memory is incremented. When the pointer is set to point elsewhere, the reference count is decremented. When the reference count drops to zero, the memory is unused and can be released.
The main advantage of reference counting is simplicity—it is easy to understand and implement. Furthermore, it places no restrictions on the organization of the heap because the reference count is independent of an object’s physical location. Reference counting adds overhead to each pointer operation, but the collection phase is relatively low cost. The main disadvantage is that circular references prevent memory that is otherwise unused from being released. A circular reference occurs when two objects point to each other, either directly or indirectly. In this situation, neither object’s reference count ever drops to zero. Some solutions to the circular reference problem have been devised, but all add complexity and/or overhead.
Mark and Sweep
Mark and sweep involves two phases. In the first phase, all objects in the heap are set to their unmarked state. Then, all objects directly or indirectly accessible from program variables are marked as “in-use.” In phase two, all of allocated memory is scanned (that is, a sweep of memory is made), and all unmarked elements are released.
There are two main advantages of mark and sweep. First, it easily handles circular references. Second, it adds virtually no runtime overhead prior to collection. It has two main disadvantages. First, a considerable amount of time might be spent collecting garbage because the entire heap must be scanned during collection. Thus, garbage collection may cause unacceptable runtime characteristics for some programs. Second, although mark and sweep is simple conceptually, it can be tricky to implement efficiently.
Copying
The copying algorithm organizes free memory into two spaces. One is active (holding the current heap), and the other is idle. During garbage collection, in-use objects from the active space are identified and copied into the idle space. Then, the roles of the two spaces are reversed, with the idle space becoming active and the active space becoming idle. Copying offers the advantage of compacting the heap in the copy process. It has the disadvantage of allowing only half of free memory to be in use at any one time.
Which Algorithm?
Given that there are advantages and disadvantages to all of the three classical approaches to garbage collection, it might seem hard to choose one over the other. However, given the constraints enumerated earlier, there is a clear choice: reference counting. First and most importantly, reference counting can be easily “layered onto” the existing C++ dynamic allocation system. Second, it can be implemented in a straightforward manner and in a way that does not affect preexisting code. Third, it does not require any specific organization or structuring of the heap, thus the standard allocation system provided by C++ is unaffected.
The one drawback to using reference counting is its difficulty in handling circular references. This isn’t an issue for many programs because intentional circular references are not all that common and can usually be avoided. (Even things that we call circular, such as a circular queue, don’t necessarily involve a circular pointer reference.) Of course, there are cases in which circular references are needed. It is also possible to create a circular reference without knowing you have done so, especially when working with third-party libraries. Therefore, the garbage collector must provide some means to gracefully handle a circular reference, should one exist.
To handle the circular reference problem, the garbage collector developed in this chapter will release any remaining allocated memory when the program exits. This ensures that objects involved in a circular reference will be freed and their destructors called. It is important to understand that normally there will be no allocated objects remaining at program termination. This mechanism is explicitly for those objects that can’t be released because of a circular reference. (You might want to experiment with other means of handling the circular reference problem. It presents an interesting challenge.)
Implementing the Garbage Collector
To implement a reference counting garbage collector, there must be some way to keep track of the number of pointers that point to each piece of dynamically allocated memory. The trouble is that C++ has no built-in mechanism that enables one object to know when another object is pointing to it. Fortunately, there is a solution: you can create a new pointer type that supports garbage collection. This is the approach used by the garbage collector in this chapter.
To support garbage collection, the new pointer type must do three things. First, it must maintain a list of reference counts for active dynamically allocated objects. Second, it must keep track of all pointer operations, increasing an object’s reference count each time a pointer is pointed to that object and decreasing the count each time a pointer is redirected to another object. Third, it must recycle those objects whose reference counts drop to zero. Aside from supporting garbage collection, the new pointer type will look and feel just like a normal pointer. For example, all pointer operations, such as * and –>, are supported.
In addition to being a convenient way to implement a garbage collector, the creation of a garbage collection pointer type satisfies the constraint that the original C++ dynamic allocation system must be unaffected. When garbage collection is desired, garbage collection-enabled pointers are used. When garbage collection is not desired, normal C++ pointers are available. Thus, both types of pointers can be used within the same program.
To Multithread or Not?
Another consideration when designing a garbage collector for C++ is whether it should be single-threaded or multithreaded. That is, should the garbage collector be designed as a background process, running in its own thread and collecting garbage as CPU time permits? Or, should the garbage collector run in the same thread as the process that uses it, collecting garbage when certain program conditions occur? Both approaches have advantages and disadvantages.
The main advantage to creating a multithreaded garbage collector is efficiency. Garbage can be collected when idle CPU cycles are available. The disadvantage is, of course, that C++ does not provide any built-in support for multithreading. This means that any multithreaded approach will depend upon operating system facilities to support the multitasking. This makes the code nonportable.
The main advantage to using a single-threaded garbage collector is portability. It can be used in situations that do not support multithreading or in cases in which the price of multithreading is too high. The main disadvantage is that the rest of the program stops when garbage collection takes place.
In this chapter, the single-threaded approach is used because it works in all C++ environments. Thus, it can be used by all readers of this book. However, for those readers wanting a multithreaded solution, one is given in Chapter 3, which deals with the techniques needed to successfully multithread a C++ program in a Windows environment.
When to Collect Garbage?
One final question that needs to be answered before a garbage collector can be implemented: When is garbage collected? This is less of an issue for a multithreaded garbage collector, which can run continuously as a background task, collecting garbage whenever CPU cycles are available, than it is for a single-threaded garbage collector, such as that developed in this chapter, which must stop the rest of the program to collect garbage.
In the real world, garbage collection usually takes place only when there is sufficient reason to do so, such as the case of memory running low. This makes sense for two reasons. First, with some garbage collection algorithms, such as mark and sweep, there is no way to know that a piece of memory is unused without actually performing the collection. (That is, sometimes there is no way to know that there is garbage to be collected without actually collecting it!) Second, collecting garbage is a time-consuming process which should not be performed needlessly.
However, waiting for memory to run low before initiating garbage collection is not suitable for the purposes of this chapter because it makes it next to impossible to demonstrate the collector. Instead, the garbage collector developed in this chapter will collect garbage more frequently so that its actions can easily be observed. As the collector is coded, garbage is collected whenever a pointer goes out of scope. Of course, this behavior can easily be changed to fit your applications.
One last point: when using reference-count based garbage collection, it is technically possible to recycle unused memory as soon as its reference count drops to zero, rather than using a separate garbage collection phase. However, this approach adds overhead to every pointer operation. The method used by this chapter is to simply decrement the memory’s reference count each time a pointer to that memory is redirected and let the collection process handle the actual recycling of memory at more convenient times. This reduces the runtime overhead associated with pointer operations, which one typically wants to be as fast as possible.
Next: What About auto_ptr? >>
A Simple Garbage Collector for C++ - What About auto_ptr?
(Page 4 of 12 )
As many readers will know, C++ defines a library class called auto_ptr. Because an auto_ptr automatically frees the memory to which it points when it goes out of scope, you might think that it would be of use when developing a garbage collector, perhaps forming the foundation. This is not the case, however. The auto_ptr class is designed for a concept that the ISO C++ Standard calls “strict ownership,” in which an auto_ptr “owns” the object to which it points. This ownership can be transferred to another auto_ptr, but in all cases some auto_ptr will own the object until it is destroyed. Furthermore, an auto_ptr is assigned an address of an object only when it is initialized. After that, you can’t change the memory to which an auto_ptr points, except by assigning one auto_ptr to another. Because of auto_ptr’s “strict ownership” feature, it is not particularly useful when creating a garbage collector, and it is not used by the garbage collectors in this book.
-----------------------------------------------------------------
A Simple C++ Garbage Collector
The entire garbage collector is shown here. As explained, the garbage collector works by creating a new pointer type that provides built-in support for garbage collection based on reference counting. The garbage collector is single-threaded, which means that it is quite portable and does not rely upon (or make assumptions about) the execution environment. This code should be stored in a file called gc.h.
There are two things to notice as you look through the code. First, most of the member functions are quite short and are defined inside their respective classes in the interest of efficiency. Recall that a function defined within its class is automatically in-lined, which eliminates the overhead of a function call. Only a few functions are long enough to require their definition to be outside their class.
Secondly, notice the comment near the top of the file. If you want to watch the action of the garbage collector, simply turn on the display option by defining the macro called DISPLAY. For normal use, leave DISPLAY undefined.
// A single-threaded garbage collector.
#include
#include
#include
#include
using namespace std;
// To watch the action of the garbage collector, define DISPLAY.
// #define DISPLAY
// Exception thrown when an attempt is made to
// use an Iter that exceeds the range of the
// underlying object.
//
class OutOfRangeExc {
// Add functionality if needed by your application.
};
// An iterator-like class for cycling through arrays
// that are pointed to by GCPtrs. Iter pointers
// ** do not ** participate in or affect garbage
// collection. Thus, an Iter pointing to
// some object does not prevent that object
// from being recycled.
//
template
T *ptr; // current pointer value
T *end; // points to element one past end
T *begin; // points to start of allocated array
unsigned length; // length of sequence
public:
Iter() {
ptr = end = begin = NULL;
length = 0;
}
Iter(T *p, T *first, T *last) {
ptr = p;
end = last;
begin = first;
length = last - first;
}
// Return length of sequence to which this
// Iter points.
unsigned size() { return length; }
// Return value pointed to by ptr.
// Do not allow out-of-bounds access.
T &operator*() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
return *ptr;
}
// Return address contained in ptr.
// Do not allow out-of-bounds access.
T *operator->() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
return ptr;
}
// Prefix ++.
Iter operator++() {
ptr++;
return *this;
}
// Prefix --.
Iter operator--() {
ptr--;
return *this;
}
// Postfix ++.
Iter operator++(int notused) {
T *tmp = ptr;
ptr++;
return Iter
}
// Postfix --.
Iter operator--(int notused) {
T *tmp = ptr;
ptr--;
return Iter
}
// Return a reference to the object at the
// specified index. Do not allow out-of-bounds
// access.
T &operator[](int i) {
if( (i < 0) || (i >= (end-begin)) )
throw OutOfRangeExc();
return ptr[i];
}
// Define the relational operators.
bool operator==(Iter op2) {
return ptr == op2.ptr;
}
bool operator!=(Iter op2) {
return ptr != op2.ptr;
}
bool operator<(Iter op2) {
return ptr < op2.ptr;
}
bool operator<=(Iter op2) {
return ptr <= op2.ptr;
}
bool operator>(Iter op2) {
return ptr > op2.ptr;
}
bool operator>=(Iter op2) {
return ptr >= op2.ptr;
}
// Subtract an integer from an Iter.
Iter operator-(int n) {
ptr -= n;
return *this;
}
// Add an integer to an Iter.
Iter operator+(int n) {
ptr += n;
return *this;
}
// Return number of elements between two Iters.
int operator-(Iter
return ptr - itr2.ptr;
}
};
// This class defines an element that is stored
// in the garbage collection information list.
//
template
public:
unsigned refcount; // current reference count
T *memPtr; // pointer to allocated memory
/* isArray is true if memPtr points
to an allocated array. It is false
otherwise. */
bool isArray; // true if pointing to array
/* If memPtr is pointing to an allocated
array, then arraySize contains its size */
unsigned arraySize; // size of array
// Here, mPtr points to the allocated memory.
// If this is an array, then size specifies
// the size of the array.
GCInfo(T *mPtr, unsigned size=0) {
refcount = 1;
memPtr = mPtr;
if(size != 0)
isArray = true;
else
isArray = false;
arraySize = size;
}
};
// Overloading operator== allows GCInfos to be compared.
// This is needed by the STL list class.
template
const GCInfo
return (ob1.memPtr == ob2.memPtr);
}
// GCPtr implements a pointer type that uses
// garbage collection to release unused memory.
// A GCPtr must only be used to point to memory
// that was dynamically allocated using new.
// When used to refer to an allocated array,
// specify the array size.
//
template
// gclist maintains the garbage collection list.
static list
// addr points to the allocated memory to which
// this GCPtr pointer currently points.
T *addr;
/* isArray is true if this GCPtr points
to an allocated array. It is false
otherwise. */
bool isArray; // true if pointing to array
// If this GCPtr is pointing to an allocated
// array, then arraySize contains its size.
unsigned arraySize; // size of the array
static bool first; // true when first GCPtr is created
// Return an iterator to pointer info in gclist.
typename list
public:
// Define an iterator type for GCPtr
typedef Iter
// Construct both initialized and uninitialized objects.
GCPtr(T *t=NULL) {
// Register shutdown() as an exit function.
if(first) atexit(shutdown);
first = false;
list
p = findPtrInfo(t);
// If t is already in gclist, then
// increment its reference count.
// Otherwise, add it to the list.
if(p != gclist.end())
p->refcount++; // increment ref count
else {
// Create and store this entry.
GCInfo
gclist.push_front(gcObj);
}
addr = t;
arraySize = size;
if(size > 0) isArray = true;
else isArray = false;
#ifdef DISPLAY
cout << "Constructing GCPtr. ";
if(isArray)
cout << " Size is " << arraySize << endl;
else
cout << endl;
#endif
}
// Copy constructor.
GCPtr(const GCPtr &ob) {
list
p = findPtrInfo(ob.addr);
p->refcount++; // increment ref count
addr = ob.addr;
arraySize = ob.arraySize;
if(arraySize > 0) isArray = true;
else isArray = false;
#ifdef DISPLAY
cout << "Constructing copy.";
if(isArray)
cout << " Size is " << arraySize << endl;
else
cout << endl;
#endif
}
// Destructor for GCPTr.
~GCPtr();
// Collect garbage. Returns true if at least
// one object was freed.
static bool collect();
// Overload assignment of pointer to GCPtr.
T *operator=(T *t);
// Overload assignment of GCPtr to GCPtr.
GCPtr &operator=(GCPtr &rv);
// Return a reference to the object pointed
// to by this GCPtr.
T &operator*() {
return *addr;
}
// Return the address being pointed to.
T *operator->() { return addr; }
// Return a reference to the object at the
// index specified by i.
T &operator[](int i) {
return addr[i];
}
// Conversion function to T *.
operator T *() { return addr; }
// Return an Iter to the start of the allocated memory.
Iter
int size;
if(isArray) size = arraySize;
else size = 1;
return Iter
}
// Return an Iter to one past the end of an allocated array.
Iter
int size;
if(isArray) size = arraySize;
else size = 1;
return Iter
}
// Return the size of gclist for this type
// of GCPtr.
static int gclistSize() { return gclist.size(); }
// A utility function that displays gclist.
static void showlist();
// Clear gclist when program exits.
static void shutdown();
};
// Creates storage for the static variables
template
list
template
bool GCPtr
// Destructor for GCPtr.
template
GCPtr
list
p = findPtrInfo(addr);
if(p->refcount) p->refcount--; // decrement ref count
#ifdef DISPLAY
cout << "GCPtr going out of scope.\n";
#endif
// Collect garbage when a pointer goes out of scope.
collect();
// For real use, you might want to collect
// unused memory less frequently, such as after
// gclist has reached a certain size, after a
// certain number of GCPtrs have gone out of scope,
// or when memory is low.
}
// Collect garbage. Returns true if at least
// one object was freed.
template
bool GCPtr
bool memfreed = false;
#ifdef DISPLAY
cout << "Before garbage collection for ";
showlist();
#endif
list
do {
// Scan gclist looking for unreferenced pointers.
for(p = gclist.begin(); p != gclist.end(); p++) {
// If in-use, skip.
if(p->refcount > 0) continue;
memfreed = true;
// Remove unused entry from gclist.
gclist.remove(*p);
// Free memory unless the GCPtr is null.
if(p->memPtr) {
if(p->isArray) {
#ifdef DISPLAY
cout << "Deleting array of size "
<< p->arraySize << endl;
#endif
delete[] p->memPtr; // delete array
}
else {
#ifdef DISPLAY
cout << "Deleting: "
<< *(T *) p->memPtr << "\n";
#endif
delete p->memPtr; // delete single element
}
}
// Restart the search.
break;
}
} while(p != gclist.end());
#ifdef DISPLAY
cout << "After garbage collection for ";
showlist();
#endif
return memfreed;
}
// Overload assignment of pointer to GCPtr.
template
T * GCPtr
list
// First, decrement the reference count
// for the memory currently being pointed to.
p = findPtrInfo(addr);
p->refcount--;
// Next, if the new address is already
// existent in the system, increment its
// count. Otherwise, create a new entry
// for gclist.
p = findPtrInfo(t);
if(p != gclist.end())
p->refcount++;
else {
// Create and store this entry.
GCInfo
gclist.push_front(gcObj);
}
addr = t; // store the address.
return t;
}
// Overload assignment of GCPtr to GCPtr.
template
GCPtr
list
// First, decrement the reference count
// for the memory currently being pointed to.
p = findPtrInfo(addr);
p->refcount--;
// Next, increment the reference count of
// the new address.
p = findPtrInfo(rv.addr);
p->refcount++; // increment ref count
addr = rv.addr;// store the address.
return rv;
}
// A utility function that displays gclist.
template
void GCPtr
list
cout << "gclist<" << typeid(T).name() << ", "
<< size << ">:\n";
cout << "memPtr refcount value\n";
if(gclist.begin() == gclist.end()) {
cout << " -- Empty --\n\n";
return;
}
for(p = gclist.begin(); p != gclist.end(); p++) {
cout << "[" << (void *)p->memPtr << "]"
<< " " << p->refcount << " ";
if(p->memPtr) cout << " " << *p->memPtr;
else cout << " ---";
cout << endl;
}
cout << endl;
}
// Find a pointer in gclist.
template
typename list
GCPtr
list
// Find ptr in gclist.
for(p = gclist.begin(); p != gclist.end(); p++)
if(p->memPtr == ptr)
return p;
return p;
}
// Clear gclist when program exits.
template
void GCPtr
if(gclistSize() == 0) return; // list is empty
list
for(p = gclist.begin(); p != gclist.end(); p++) {
// Set all reference counts to zero
p->refcount = 0;
}
#ifdef DISPLAY
cout << "Before collecting for shutdown() for "
<< typeid(T).name() << "\n";
#endif
collect();
#ifdef DISPLAY
cout << "After collecting for shutdown() for "
<< typeid(T).name() << "\n";
#endif
}
A Simple Garbage Collector for C++ - An Overview of the Garbage Collector Classes
(Page 5 of 12 )
The garbage collector uses four classes: GCPtr, GCInfo, Iter, and OutOfRangeExc. Before examining the code in detail, it will be helpful to understand the role each class plays.
GCPtr
At the core of the garbage collector is the class GCPtr, which implements a garbage-collection pointer. GCPtr maintains a list that associates a reference count with each piece of memory allocated for use by a GCPtr. In general, here is how it works. Each time a GCPtr is pointed at a piece of memory, the reference count for that memory is incremented. If the GCPtr was previously pointing at a different piece of memory prior to the assignment, the reference count for that memory is decremented. Thus, adding a pointer to a piece of memory increases the memory’s reference count. Removing a pointer decreases the memory’s reference count. Each time a GCPtr goes out of scope, the reference count associated with the memory to which it currently points is decremented. When a reference count drops to zero, that piece of memory can be released.
GCPtr is a template class that overloads the * and –> pointer operators and the array indexing operator [ ]. Thus, GCPtr creates a new pointer type and integrates it into the C++ programming environment. This allows a GCPtr to be used in much the same way that you use a normal C++ pointer. However, for reasons that will be made clear later in this chapter, GCPtr does not overload the ++, – –, or the other arithmetic operations defined for pointers. Thus, except through assignment, you cannot change the address to which a GCPtr object points. This may seems like a significant restriction, but it isn’t because the Iter class provides these operations.
For the sake of illustration, the garbage collector runs whenever a GCPtr object goes out of scope. At that time, the garbage collection list is scanned and all memory with a reference count of zero is released, even if it was not originally associated with the GCPtr that went out of scope. Your program can also explicitly request garbage collection if you need to recycle memory earlier.
GCInfo
As explained, GCPtr maintains a list that links reference counts with allocated memory. Each entry in this list is encapsulated in an object of type GCInfo. GCInfo stores the reference count in its refcount field and a pointer to the memory in its memPtr field. Thus, a GCInfo object binds a reference count to a piece of allocated memory.
GCInfo defines two other fields: isArray and arraySize.If memPtr points to an allocated array, then its isArray member will be true and the length of the array will be stored in its arraySize field.
The Iter Class
As explained, a GCPtr object allows you to access the memory to which it points by using the normal pointer operators * and –>, but it does not support pointer arithmetic. To handle situations in which you need to perform pointer arithmetic, you will use an object of type Iter. Iter is a template class similar in function to an STL iterator, and it defines all pointer operations, including pointer arithmetic. The main use of Iter is to enable you to cycle through the elements of a dynamically allocated array. It also provides bounds checking. You obtain an Iter from GCPtr by calling either begin( ) or end( ), which work much like their equivalents in the STL.
It is important to understand that although Iter and the STL iterator type are similar, they are not the same, and you cannot use one in place of the other.
OutOfRangeExc
If an Iter encounters an attempt to access memory outside the range of the allocated memory, an OutOfRangeExc exception is thrown. For the purposes of this chapter, OutOfRangeExc contains no members. It is simply a type that can be thrown. However, you are free to add functionality to this class as your own applications dictate.
A Simple Garbage Collector for C++ - GCPtr In Detail
(Page 6 of 12 )
GCPtr is the heart of the garbage collector. It implements a new pointer type that keeps a reference count for objects allocated on the heap. It also provides the garbage collection functionality that recycles unused memory.
GCptr is a template class with this declaration:
template
GCPtr requires that you specify the type of the data that will be pointed to, which will be substituted for the generic type T. If an array is being allocated, you must specify the size of the array in the size parameter. Otherwise, size defaults to zero, which indicates that a single object is being pointed to. Here are two examples.
GCPtr
Here, p can point to single objects of type int, and ap can point to an array of 5 ints.
In the preceding examples, notice that you do not use the * operator when specifying the name of the GCPtr object. That is, to create a GCPtr to int, you do not use a statement like this:
GCPtr
This declaration creates a normal C++ pointer called p that can point to a GCPtr
Be careful when specifying the type parameter to GCPtr. It specifies the type of the object to which the GCPtr object can point. Therefore, if you write a declaration like this:
GCPtr
you are creating a GCPtr object that points to int * pointers, not a GCPtr to ints.
Because of its importance, each member of GCPtr is examined in detail in the following sections.
GCPtr Data Members
GCPtr declares the following data members:
// gclist maintains the garbage collection list.
static list
// addr points to the allocated memory to which
// this GCPtr pointer currently points.
T *addr;
/* isArray is true if this GCPtr points
to an allocated array. It is false
otherwise. */
bool isArray; // true if pointing to array
// If this GCPtr is pointing to an allocated
// array, then arraySize contains its size.
unsigned arraySize; // size of the array
static bool first; // true when first GCPtr is created
The gclist field contains a list of GCInfo objects. (Recall that GCInfo links a reference count with a piece of allocated memory.) This list is used by the garbage collector to determine when allocated memory is unused. Notice that gclist is a static member of GCPtr. This means that for each specific pointer type, there is only one gclist. For example, all pointers of type GCPtr
GCPtr stores the address of the memory to which it points in addr. If addr points to an allocated array, then isArray will be true, and the length of the array will be stored in arraySize.
The first field is a static variable that is initially set to true. It is a flag that the GCPtr constructor uses to know when the first GCPtr object is created. After the first GCPtr object is constructed, first is set to false. It is used to register a termination function that will be called to shut down the garbage collector when the program ends.
The findPtrInfo( ) Function
GCPtr declares one private function: findPtrInfo( ). This function searches gclist for a specified address and returns an iterator to its entry. If the address is not found, an iterator to the end of gclist is returned. This function is used internally by GCPtr to update the reference counts of the objects in gclist. It is implemented as shown here:
// Find a pointer in gclist.
template
typename list
GCPtr
list
// Find ptr in gclist.
for(p = gclist.begin(); p != gclist.end(); p++)
if(p->memPtr == ptr)
return p;
return p;
}
The GCIterator typedef
At the start of the public section of GCPtr is the typedef of Iter
GCPtr
The GCPtr Constructor
The constructor for GCPtr is shown here:
// Construct both initialized and uninitialized objects. GCPtr(T *t=NULL) {
// Register shutdown() as an exit function.
if(first) atexit(shutdown);
first = false;
list
p = findPtrInfo(t);
// If t is already in gclist, then
// increment its reference count.
// Otherwise, add it to the list.
if(p != gclist.end())
p->refcount++; // increment ref count
else {
// Create and store this entry.
GCInfo
gclist.push_front(gcObj);
}
addr = t;
arraySize = size;
if(size > 0) isArray = true;
else isArray = false;
#ifdef DISPLAY
cout << "Constructing GCPtr. ";
if(isArray)
cout << " Size is " << arraySize << endl;
else
cout << endl;
#endif
}
GCPtr( ) allows both initialized and uninitialized instances to be created. If an initialized instance is declared, then the memory to which this GCPtr will point is passed through t. Otherwise, t will be null. Let’s examine the operation of GCPtr( ) in detail.
First, if first is true, it means that this is the first GCPtr object to be created. If this is the case, then shutdown( ) is registered as a termination function by calling atexit( ).The atexit( ) function is part of the standard C++ function library, and it registers a function that will be called when a program terminates. In this case, shutdown( ) releases any memory that was prevented from being released because of a circular reference.
Next, a search of gclist is made, looking for any preexisting entry that matches the address in t. If one is found, then its reference count is incremented. If no preexising entry matches t, a new GCInfo object is created that contains this address, and this object is added to gclist.
GCPtr( ) then sets addr to the address specified by t and sets the values of isArray and arraySize appropriately. Remember, if you are allocating an array, you must explicitly specify the size of the array when you declare the GCPtr pointer that will point to it. If you don’t, the memory won’t be released correctly, and, in the case of an array of class objects, the destructors won’t be called properly.
The GCPtr Destructor
The destructor for GCPtr is shown here:
// Destructor for GCPtr.
template
GCPtr
list
p = findPtrInfo(addr);
if(p->refcount) p->refcount--; // decrement ref count
#ifdef DISPLAY
cout << "GCPtr going out of scope.\n";
#endif
// Collect garbage when a pointer goes out of scope.
collect();
// For real use, you might want to collect
// unused memory less frequently, such as after
// gclist has reached a certain size, after a
// certain number of GCPtrs have gone out of scope,
// or when memory is low.
}
Garbage collection takes place each time a GCPtr goes out of scope. This is handled by ~GCPtr( ). First, a search of gclist is made, looking for the entry that corresponds to the address pointed to by the GCPtr being destroyed. Once found, its refcount field is decremented. Next, ~GCptr( ) calls collect( ) to release any unused memory (that is, memory whose reference count is zero).
As the comment at the end of ~GCPtr( ) states, for real applications, it is probably better to collect garbage less often than each time a single GCPtr goes out of scope. Collecting less frequently will usually be more efficient. As explained earlier, collecting each time a GCPtr is destroyed is useful for demonstrating the garbage collector because it clearly illustrates the garbage collector’s operation.
Collect Garbage with collect( )
The collect( ) function is where garbage collection takes place. It is shown here:
// Collect garbage. Returns true if at least
// one object was freed.
template
bool GCPtr
bool memfreed = false;
#ifdef DISPLAY
cout << "Before garbage collection for ";
showlist();
#endif
list
do {
// Scan gclist looking for unreferenced pointers.
for(p = gclist.begin(); p != gclist.end(); p++) {
// If in-use, skip.
if(p->refcount > 0) continue;
memfreed = true;
// Remove unused entry from gclist.
gclist.remove(*p);
// Free memory unless the GCPtr is null.
if(p->memPtr) {
if(p->isArray) {
#ifdef DISPLAY
cout << "Deleting array of size "
<< p->arraySize << endl;
#endif
delete[] p->memPtr; // delete array
}
else {
#ifdef DISPLAY
cout << "Deleting: "
<< *(T *) p->memPtr << "\n";
#endif
delete p->memPtr; // delete single element
}
}
// Restart the search.
break;
}
} while(p != gclist.end());
#ifdef DISPLAY
cout << "After garbage collection for ";
showlist();
#endif
return memfreed;
}
The collect( ) function works by scanning the contents of gclist, looking for entries that have a refcount of zero. When such an entry is found, it is removed from gclist by calling the remove( ) function, which is a member of the STL list class. Then the memory associated with that entry is freed.
Recall that in C++, single objects are freed by delete, but arrays of objects are freed via delete[ ]. Thus, the value of the entry’s isArray field determines whether delete or delete[ ] is used to free the memory. This is one reason you must specify the size of an allocated array for any GCPtr that will point to one: it causes isArray to be set to true. If isArray is not set correctly, it is impossible to properly release the allocated memory.
Although the point of garbage collection is to recycle unused memory automatically, you can take a measure of manual control if necessary. The collect( ) function can be called directly by user code to request that garbage collection take place. Notice that it is declared as a static function within GCPtr. This means that it can be invoked without reference to any object. For example:
GCPtr
This causes gclist
A Simple Garbage Collector for C++ - The Overloaded Assignment Operators
(Page 7 of 12 )
GCPtr overloads operator=( ) twice: once for the assignment of a new address to a GCPtr pointer, and once for the assignment of one GCPtr pointer to another. Both versions are shown here:
// Overload assignment of pointer to GCPtr.
template
T * GCPtr
list
// First, decrement the reference count
// for the memory currently being pointed to.
p = findPtrInfo(addr);
p->refcount--;
// Next, if the new address is already
// existent in the system, increment its
// count. Otherwise, create a new entry
// for gclist.
p = findPtrInfo(t);
if(p != gclist.end())
p->refcount++;
else {
// Create and store this entry.
GCInfo
gclist.push_front(gcObj);
}
addr = t; // store the address.
return t;
}
// Overload assignment of GCPtr to GCPtr.
template
GCPtr
list
// First, decrement the reference count
// for the memory currently being pointed to.
p = findPtrInfo(addr);
p->refcount--;
// Next, increment the reference count of
// the new address.
p = findPtrInfo(rv.addr);
p->refcount++; // increment ref count
addr = rv.addr;// store the address.
return rv;
}
The first overload of operator=( ) handles assignments in which a GCPtr pointer is on the left and an address is on the right. For example, it handles cases like the one shown here:
GCPtr
// ...
p = new int(18);
Here, the address returned by new is assigned to p. When this happens, operator=(T *t) is called with the new address passed to t. First,the entry in gclist for the memory that is currently being pointed to is found, and its reference count is decremented. Next, a search of gclist is made for the new address. If it is found, its reference count is incremented. Otherwise, a new GCInfo object is created for the new address, and this object is added to gclist. Finally, the new address is stored in the invoking object’s addr, and this address is returned.
The second overload of the assignment operator, operator=(GCPtr &rv), handles the following type of assignment:
GCPtr
GCPtr
// ...
p = new int(88);
q = p;
Here, both p and q are GCPtr pointers, and p is assigned to q. This version of the assignment operator works much like the other. First, the entry in gclist for the memory that is currently being pointed to is found, and its reference count is decremented. Next, a search of gclist is made for the new address, which is contained in rv.addr, and its reference count is incremented. Then the invoking object’s addr field is set to the address contained in rv.addr. Finally, the right-hand object is returned. This allows a chain of assignments to take place, such as:
p = q = w = z;
There is one other important point to make about the way that the assignment operators work. As mentioned earlier in this chapter, it is technically possible to recycle memory as soon as its reference count drops to zero, but doing so puts an extra overhead on each pointer operation. This is why, in the overloaded assignment operators, the reference count for the memory previously pointed to by the left-hand operand is simply decremented, and no further action is taken. Thus, the management overhead associated with actually releasing memory and performing maintenance on gclist is avoided. These actions are deferred to later, when the garbage collector runs. This approach makes for faster runtimes for the code that uses a GCPtr. It also lets garbage collection take place at times that are (potentially) more convenient in terms of runtime performance.
The GCPtr Copy Constructor
Because of the need to keep track of each pointer to allocated memory, the default copy constructor (which makes a bitwise identical copy) cannot be used. Instead, GCPtr must define is own copy constructor, which is shown here:
// Copy constructor.
GCPtr(const GCPtr &ob) {
list
p = findPtrInfo(ob.addr);
p->refcount++; // increment ref count
addr = ob.addr;
arraySize = ob.arraySize;
if(arraySize > 0) isArray = true;
else isArray = false;
#ifdef DISPLAY
cout << "Constructing copy.";
if(isArray)
cout << " Size is " << arraySize << endl;
else
cout << endl;
#endif
}
Recall that a class’ copy constructor is invoked when a copy of an object is required, such as when an object is passed as an argument to a function, when an object is returned from a function, or when one object is used to initialize another. GCPtr’s copy constructor duplicates the information contained in the original object. It also increments the reference count associated with the memory pointed to by the original object. When the copy goes out of scope, this reference count will be decremented.
Actually, the extra work performed by the copy constructor is not usually necessary because the overloaded assignment operators properly maintain the garbage collection list in most cases. However, there are a small number of cases in which the copy constructor is needed, such as when memory is allocated inside a function and a GCPtr to that memory is returned.
The Pointer Operators and Conversion Function
Because GCPtr is a pointer type, it must overload the pointer operators * and –>, plus the indexing operator [ ]. This is done by the functions shown here. Given that it is the ability to overload these operators that makes it possible to create a new pointer type, it is amazing how simple they are.
// Return a reference to the object pointed
// to by this GCPtr.
T &operator*() {
return *addr;
}
// Return the address being pointed to.
T *operator->() { return addr; }
// Return a reference to the object at the
// index specified by i.
T &operator[](int i) {
return addr[i];
}
The operator*( ) function returns a reference to the object pointed to by the addr field of the invoking GCPtr, operator–>( ) returns the address contained in addr, and operator[ ] returns a reference to the element specified by the index. operator[ ] should be used only on GCPtrs that point to allocated arrays.
As mentioned earlier, no pointer arithmetic is supported. For example, neither the ++ nor the –– operator is overloaded for GCPtr. The reason is that the garbage collection mechanism assumes that a GCPtr is pointing to the start of allocated memory. If a GCPtr could be incremented, for example, then when that pointer was garbage collected, the address used with delete would be invalid.
You have two options if you need to perform operations that involve pointer arithmetic. First, if the GCPtr is pointing to an allocated array, you can create an Iter that will let you cycle through that array. This approach is described later. Second, you can convert a GCPtr into a normal pointer by use of the T * conversion function defined by GCPtr. This function is shown here:
// Conversion function to T *.
operator T*() { return addr; }
This function returns a normal pointer that points to the address stored in addr. It can be used like this.
GCPtr
double *p;
p = gcp; // now, p points to same memory as gcp
p++; // because p is a normal pointer, it can be incremented
In the preceding example, because p is a normal pointer, it can be manipulated in any way that any other pointer can. Of course, whether such manipulations yield meaningful results is dependent upon your application.
The main advantage of the conversion to T * is that it lets you use GCPtrs in place of normal C++ pointers when working with preexisting code that requires such pointers. For example, consider this sequence:
GCPtr
strcpy(str, "this is a test");
cout << str << endl;
Here, str is a GCPtr pointer to char that is used in a call to strcpy( ). Because strcpy( ) is expecting its arguments to be of type char *, the conversion to T* inside GCPtr is automatically invoked because, in this case, T is char. The same conversion is automatically invoked when str is used in the cout statement. Thus, the conversion function enables GCPtrs to seamlessly integrate with existing C++ functions and classes.
Keep in mind that the T * pointer returned by this conversion does not participate in or affect garbage collection. Thus, it is possible for the allocated memory to be freed even if a regular C++ pointer is still pointing to it. So, use the conversion to T* wisely––and infrequently.
The begin( ) and end( ) Functions
The begin( ) and end( ) functions, shown next, are similar to their counterparts in the STL:
// Return an Iter to the start of the allocated memory. Iter
int size;
if(isArray) size = arraySize;
else size = 1;
return Iter
}
// Return an Iter to one past the end of an allocated array.
Iter
int size;
if(isArray) size = arraySize;
else size = 1;
return Iter
}
The begin( ) function returns an Iter to the start of the allocated array pointed to by addr. The end( ) function returns an Iter to one past the end of the array. Although there is nothing that stops these functions from being called on a GCPtr that points to a single object, their purpose is to support operations on allocated arrays. (Obtaining an Iter to a single object is not harmful, just pointless.)
The shutdown( ) Function
If a program creates a circular reference of GCPtrs, then when the program ends there will still be dynamically allocated objects that need to be released. This is important because these objects might have destructors that need to be called. The shutdown( ) function handles this task. This function is registered by atexit( ) when the first GCPtr is created, as described earlier. This means that it will be called when the program terminates.
The shutdown( ) function is shown here:
// Clear gclist when program exits.
template
void GCPtr
if(gclistSize() == 0) return; // list is empty
list
for(p = gclist.begin(); p != gclist.end(); p++) {
// Set all reference counts to zero
p->refcount = 0;
}
#ifdef DISPLAY
cout << "Before collecting for shutdown() for "
<< typeid(T).name() << "\n";
#endif
collect();
#ifdef DISPLAY
cout << "After collecting for shutdown() for "
<< typeid(T).name() << "\n";
#endif
}
First, if the list is empty, which it will normally be, then shutdown( ) simply returns. Otherwise, it sets to zero the reference counts of the entries that still exist in gclist, and then it calls collect( ). Recall that collect( ) releases any object that has a reference count of zero. Thus, setting the reference counts to zero ensures that all objects will be freed.
Two Utility Functions
GCPtr ends by defining two utility functions. The first is gclistSize( ), which returns the number of entries currently held in gclist. The second is showlist( ), which displays the contents of gclist. Neither of these are necessary for the implementation of a garbage collection pointer type, but they are useful when you want to watch the operation of the garbage collector.
A Simple Garbage Collector for C++ - GCInfo
(Page 8 of 12 )
The garbage collection list in gclist holds objects of type GCInfo. The GCInfo class is shown here:
// This class defines an element that is stored
// in the garbage collection information list.
//
template
public:
unsigned refcount; // current reference count
T *memPtr; // pointer to allocated memory
/* isArray is true if memPtr points
to an allocated array. It is false
otherwise. */
bool isArray; // true if pointing to array
/* If memPtr is pointing to an allocated
array, then arraySize contains its size */
unsigned arraySize; // size of array
// Here, mPtr points to the allocated memory.
// If this is an array, then size specifies
// the size of the array.
GCInfo(T *mPtr, unsigned size=0) {
refcount = 1;
memPtr = mPtr;
if(size != 0)
isArray = true;
else
isArray = false;
arraySize = size;
}
};
As mentioned earlier, each GCInfo object stores a pointer to allocated memory in memPtr and the reference count associated with that memory in refcount. If the memory pointed to by memPtr contains an array, then the length of that array must be specified when the GCInfo object is created. In this case, isArray is set to true, and the length of the array will be stored in arraySize.
GCInfo objects are stored in an STL list. To enable searches on this list, it is necessary to define operator==( ), as shown here:
// Overloading operator== allows GCInfos to be compared.
// This is needed by the STL list class.
template
const GCInfo
return (ob1.memPtr == ob2.memPtr);
}
Two objects are equal only if both their memPtr fields are identical. Depending upon the compiler you are using, other operators may need to be overloaded to enable GCInfos to be stored in an STL list.
------------------------------------------------------------------Iter
The Iter class implements an iterator-like object that can be used to cycle through the elements of an allocated array. Iter is not technically necessary because a GCPtr can be converted to a normal pointer of its base type, but Iter offers two advantages. First, it lets you cycle through an allocated array in a fashion similar to the way in which you cycle through the contents of an STL container. Thus, the syntax for using an Iter is familiar. Second, Iter will not allow out-of-range accesses. Thus, an Iter is a safe alternative to using a normal pointer. Understand, however, that Iter does not participate in garbage collection. Thus, if the underlying GCPtr on which an Iter is based goes out of scope, the memory to which it points will be freed whether or not it is still needed by that Iter.
Iter is a template class defined like this:
template
The type of data to which the Iter points is passed through T.
Iter defines these instance variables:
T *ptr; // current pointer value
T *end; // points to element one past end
T *begin; // points to start of allocated array
unsigned length; // length of sequence
The address to which the Iter currently points is held in ptr. The address to the start of the array is stored in begin, and the address of an element one past the end of the array is stored in end. The length of the dynamic array is stored in length.
Iter defines the two constructors shown here. The first is the default constructor. The second constructs an Iter, given an initial value for ptr, and pointers to the beginning and end of the array.
Iter() {
ptr = end = begin = NULL;
length = 0;
}
Iter(T *p, T *first, T *last) {
ptr = p;
end = last;
begin = first;
length = last - first;
}
For use by the garbage collector code shown in this chapter, the initial value of ptr will always equal begin. However, you are free to construct Iters in which the initial value of ptr is a different value.
To enable Iter’s pointer-like nature, it overloads the * and –> pointer operators, and the array indexing operator [ ], as shown here:
// Return value pointed to by ptr.
// Do not allow out-of-bounds access.
T &operator*() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
return *ptr;
}
// Return address contained in ptr.
// Do not allow out-of-bounds access.
T *operator->() {
if( (ptr >= end) || (ptr < begin) )
throw OutOfRangeExc();
return ptr;
}
// Return a reference to the object at the
// specified index. Do not allow out-of-bounds
// access.
T &operator[](int i) {
if( (i < 0) || (i >= (end-begin)) )
throw OutOfRangeExc();
return ptr[i];
}
The * operator returns a reference to the element currently being pointed to in the dynamic array. The –> returns the address of the element currently being pointed to. The [ ] returns a reference to the element at the specified index. Notice that these operations do not allow an out-of-bounds access. If one is attempted, an OutOfRangeExc exception is thrown.
Iter defines the various pointer arithmetic operators, such as ++, – –, and so on, which increment or decrement an Iter. These operators enable you to cycle through a dynamic array. In the interest of speed, none of the arithmetic operators perform range checks themselves. However, any attempt to access an out-of-bounds element will cause an exception, which prevents a boundary error. Iter also defines the relational operators. Both the pointer arithmetic and relational functions are straightforward and easy to understand.
Iter also defines a utility function called size( ), which returns the length of the array to which the Iter points.
As mentioned earlier, inside GCPtr, Iter
-----------------------------------------------------------------
A Simple Garbage Collector for C++ - How to Use GCPtr
(Page 9 of 12 )
Using a GCPtr is quite easy. First, include the file gc.h. Then, declare a GCPtr object, specifying the type of the data to which it will point. For example, to declare a GCPtr object called p that can point to an int, use this kind of declaration:
GCPtr
Next, dynamically allocate the memory using new and assign the pointer returned by new to p, as shown here:
p = new int; // assign p the address of an int
You can assign a value to the allocated memory using an assignment operation like this:
*p = 88; // give that int a value
Of course, you can combine the three preceding statements like this:
GCPtr
You can obtain the value of the memory at the location pointed to by p, as shown here:
int k = *p;
As these examples show, in general you use a GCPtr just like a normal C++ pointer. The only difference is that you don’t need to delete the pointer when you are through with it. The memory allocated to that pointer will be automatically released when it is no longer needed.
Here is an entire program that assembles the pieces just shown:
#include
#include
#include "gc.h"
using namespace std;
int main() {
GCPtr
try {
p = new int;
} catch(bad_alloc exc) {
cout << "Allocation failure!\n";
return 1;
}
*p = 88;
cout << "Value at p is: " << *p << endl;
int k = *p;
cout << "k is " << k << endl;
return 0;
}
The output from this program with the display option turned on is shown here. (Recall that you can watch the operation of the garbage collector by defining DISPLAY within gc.h.)
Constructing GCPtr.
Value at p is: 88
k is 88
GCPtr going out of scope.
Before garbage collection for gclist
memPtr refcount value
[002F12C0] 0 88
[00000000] 0 ---
Deleting: 88
After garbage collection for gclist
memPtr refcount value
-- Empty --
When the program ends, p goes out of scope. This causes its destructor to be called, which causes the reference count for the memory pointed to by p to be decremented. Because p was the only pointer to this memory, this operation sets the reference count to zero. Next, p’s destructor calls collect( ), which scans gclist, looking for entries that have a reference count of zero. Because the entry previously associated with p has a reference count of zero, its memory is freed.
One other point: notice that prior to garbage collection, a null pointer entry is also in gclist. This null pointer was created when p was constructed. Recall that if a GCPtr is not given an initial address, the null address (which is zero) is used. Although it is not technically necessary to store a null pointer in gclist (because it is never freed), doing so simplifies other parts of GCPtr because it ensures that every GCPtr has a corresponding entry in gclist.
Handling Allocation Exceptions
As the preceding program shows, because the garbage collector does not change the way that memory is allocated via new, you handle allocation failures in the same way as usual, by catching the bad_alloc exception. (Recall that when new fails, it throws an exception of type bad_alloc.) Of course, the preceding program won’t run out of memory, and the try/catch block isn’t really needed, but a real-world program might exhaust the heap. Thus, you should always check for this possibility.
In general, the best way to respond to a bad_alloc exception when using garbage collection is to call collect( ) to recycle any unused memory and then retry the allocation that failed. This technique is employed by the load-testing program shown later in this chapter. You can use the same basic technique in your own programs.
A More Interesting Example
Here is a more interesting example that shows the effect of a GCPtr going out of scope before the end of the program:
// Show a GCPtr going out of scope prior to the end
// of the program.
#include
#include
#include "gc.h"
using namespace std;
int main() {
GCPtr
GCPtr
try {
p = new int(10);
q = new int(11);
cout << "Value at p is: " << *p << endl;
cout << "Value at q is: " << *q << endl;
cout << "Before entering block.\n";
// Now, create a local object.
{ // start a block
GCPtr
cout << "Value at r is: " << *r << endl;
} // end the block, causing r to go out of scope
cout << "After exiting block.\n";
} catch(bad_alloc exc) {
cout << "Allocation failure!\n";
return 1;
}
cout << "Done\n";
return 0;
}
This program produces the following output when the display option is turned on:
Constructing GCPtr.
Constructing GCPtr.
Value at p is: 10
Value at q is: 11
Before entering block.
Constructing GCPtr.
Value at r is: 12
GCPtr going out of scope.
Before garbage collection for gclist
memPtr refcount value
[002F31D8] 0 12
[002F12F0] 1 11
[002F12C0] 1 10
[00000000] 0 ---
Deleting: 12
After garbage collection for gclist
memPtr refcount value
[002F12F0] 1 11
[002F12C0] 1 10
After exiting block.
Done
GCPtr going out of scope.
Before garbage collection for gclist
memPtr refcount value
[002F12F0] 0 11
[002F12C0] 1 10
Deleting: 11
After garbage collection for gclist
memPtr refcount value
[002F12C0] 1 10
GCPtr going out of scope.
Before garbage collection for gclist
memPtr refcount value
[002F12C0] 0 10
Deleting: 10
After garbage collection for gclist
memPtr refcount value
-- Empty --
Examine this program and its output closely. First, notice that p and q are created at the start of main( ), but r is not created until its block is entered. As you know, in C++, local variables are not created until their block is entered. When r is created, the memory to which it points is given an initial value of 12. This value is then displayed, and the block ends. This causes r to go out of scope, which means that its destructor is called. This causes r’s reference count in gclist to be decremented to zero. Then collect( ) is called to collect garbage.
Because the display option is on, when collect( ) begins, it displays the contents of gclist. Notice that it has four entries. The first is the one that was previously linked to r. Notice that its refcount field is zero, indicating that the memory pointed to by the memPtr field is no longer in use by any program element. The next two entries are still active, and they are linked to p and q. Because they are still in use, the memory they point to is not freed at this time. The final entry represents the null pointer to which p and q originally pointed when they were created. Because it is no longer in use, it will be removed from the list by collect( ). (Of course, no memory is freed when the null pointer is removed.)
Because no other GCPtr points to the same memory as r, its memory can be released, as the Deleting: 12 line confirms. Once this is done, program execution continues after the block. Finally, p and q go out of scope when the program ends and their memory is released. In this case, q’s destructor is called first, meaning that it is collected first. Finally, p is destroyed and gclist is empty.
Allocating and Discarding Objects
It is important to understand that memory becomes subject to garbage collection as soon as its reference count drops to zero (which means that no GCPtr is pointing to it). It is not necessary for the GCPtr that originally pointed to that object to go out of scope. Thus, you can use a single GCPtr object to point to any number of allocated objects by simply assigning that GCPtr a new value. The discarded memory will eventually be collected. For example:
// Allocate and discard objects.
#include
#include
#include "gc.h"
using namespace std;
int main() {
try {
// Allocate and discard objects.
GCPtr
p = new int(2);
p = new int(3);
p = new int(4);
// Manually collect unused objects for
// demonstration purposes.
GCPtr
cout << "*p: " << *p << endl;
} catch(bad_alloc exc) {
cout << "Allocation failure!\n";
return 1;
}
return 0;
}
The output from this program, with the display option turned on, is shown here:
Constructing GCPtr.
Before garbage collection for gclist
memPtr refcount value
[002F1310] 1 4
[002F1300] 0 3
[002F12D0] 0 2
[002F12A0] 0 1
Deleting: 3
Deleting: 2
Deleting: 1
After garbage collection for gclist
memPtr refcount value
[002F1310] 1 4
*p: 4
GCPtr going out of scope.
Before garbage collection for gclist
memPtr refcount value
[002F1310] 0 4
Deleting: 4
After garbage collection for gclist
memPtr refcount value
-- Empty --
In the program, p, a GCPtr to int, is assigned a pointer to four separate chunks of dynamic memory, each being initialized with a different value. Next, a call is made to collect( ), which forces garbage collection to take place. Notice the contents of gclist: three of the entries are marked inactive, and only the entry that points to the memory that was allocated last is still in use. Next, the unused entries are deleted. Finally, the program ends, p goes out of scope, and the final entry is removed.
Notice that the first three chunks of dynamic memory to which p pointed have reference counts of zero. This is because of the way the overloaded assignment operator works. Recall that when a GCPtr is assigned a new address, the reference count for its original value is decremented. Thus, each time p is assigned the address of a new integer, the reference count for the old address is reduced.
One other point: because p was initialized when it was declared, no null-pointer entry was generated and put on gclist. Remember, a null-pointer entry is created only when a GCPtr is declared without an initial value.
A Simple Garbage Collector for C++ - Allocating Arrays
(Page 10 of 12 )
If you are allocating an array using new, then you must tell GCPtr this fact by specifying its size when the GCPtr pointer to that array is declared. For example, here is the way to allocate an array of five doubles:
GCPtr
The size must be specified for two reasons. First, it tells the GCPtr constructor that this object will point to an allocated array, which causes the isArray field to be set to true. When isArray is true, the collect( ) function frees memory by using delete[ ], which releases a dynamically allocated array, rather than delete, which releases only a single object. Therefore, in this example, when pda goes out of scope, delete[ ] is used and all five elements of pda are freed. Ensuring that the correct number of objects are freed is especially important when arrays of class objects are allocated. Only by using delete[ ] can you know that the destructor for each object will be called.
The second reason that the size must be specified is to prevent an out-of-bounds element from being accessed when an Iter is used to cycle through an allocated array. Recall that the size of the array (stored in arraySize) is passed by GCPtr to Iter’s constructor whenever an Iter is needed.
Be aware that nothing enforces the rule that an allocated array be operated on only through a GCPtr that has been specified as pointing to an array. This is solely your responsibility.
Once you have allocated an array, there are two ways you can access its elements. First, you can index the GCPtr that points to it. Second, you can use an iterator. Both methods are shown here.
Using Array Indexing
The following program creates a GCPtr to a 10-element array of ints. It then allocates that array and initializes it to the values 0 through 9. Finally, it displays those values. It performs these actions by indexing the GCPtr.
// Demonstrate indexing a GCPtr.
#include
#include
#include "gc.h"
using namespace std;
int main() {
try {
// Create a GCPtr to an allocated array of 10 ints.
GCPtr
// Give the array some values using array indexing.
for(int i=0; i < 10; i++)
ap[i] = i;
// Now, show the contents of the array.
for(int i=0; i < 10; i++)
cout << ap[i] << " ";
cout << endl;
} catch(bad_alloc exc) {
cout << "Allocation failure!\n";
return 1;
}
return 0;
}
The output, with the display option off, is shown here:
0 1 2 3 4 5 6 7 8 9
Because a GCPtr emulates a normal C++ pointer, no array bounds checking is performed, and it is possible to overrun or under run the dynamically allocated array. So, use the same care when accessing an array through a GCPtr as you do when accessing an array through a normal C++ pointer.
Using Iterators
Although array indexing is certainly a convenient method of cycling through an allocated array, it is not the only method at your disposal. For many applications, the use of an iterator will be a better choice because it has the advantage of preventing boundary errors. Recall that for GCPtr, iterators are objects of type Iter. Iter supports the full complement of pointer operations, such as ++. It also allows an iterator to be indexed like an array.
Here is the previous program reworked to use an iterator. Recall that the easiest way to obtain an iterator to a GCPtr is to use GCiterator, which is a typedef inside GCPtr that is automatically bound to the generic type T.
// Demonstrate an iterator.
#include
#include
#include "gc.h"
using namespace std;
int main() {
try {
// Create a GCPtr to an allocated array of 10 ints.
GCPtr
// Declare an int iterator.
GCPtr
// Assign itr a pointer to the start of the array.
itr = ap.begin();
// Give the array some values using array indexing.
for(unsigned i=0; i < itr.size(); i++)
itr[i] = i;
// Now, cycle through array using the iterator.
for(itr = ap.begin(); itr != ap.end(); itr++)
cout << *itr << " ";
cout << endl;
} catch(bad_alloc exc) {
cout << "Allocation failure!\n";
return 1;
} catch(OutOfRangeExc exc) {
cout << "Out of range access!\n";
return 1;
}
return 0;
}
On your own, you might want to try incrementing itr so that it points beyond the boundary of the allocated array. Then try accessing the value at that location. As you will see, an OutOfRangeExc is thrown. In general, you can increment or decrement an iterator any way you like without causing an exception. However, if it is not pointing within the underlying array, attempting to obtain or set the value at that location will cause a boundary error.
Using GCPtr with Class Types
GCPtr is used with class types in just the same way it is used with built-in types. For example, here is a short program that allocates objects of MyClass:
// Use GCPtr with a class type.
#include
#include
#include "gc.h"
using namespace std;
class MyClass {
int a, b;
public:
double val;
MyClass() { a = b = 0; }
MyClass(int x, int y) {
a = x;
b = y;
val = 0.0;
}
~MyClass() {
cout << "Destructing MyClass(" <<
a << ", " << b << ")\n";
}
int sum() {
return a + b;
}
friend ostream &operator<<(ostream &strm, MyClass &obj);
};
// An overloaded inserter to display MyClass.
ostream &operator<<(ostream &strm, MyClass &obj) {
strm << "(" << obj.a << " " << obj.b << ")";
return strm;
}
int main() {
try {
GCPtr
// Show value via overloaded inserter.
cout << *ob << endl;
// Change object pointed to by ob.
ob = new MyClass(11, 21);
cout << *ob << endl;
// Call a member function through a GCPtr.
cout << "Sum is : " << ob->sum() << endl;
// Assign a value to a class member through a GCPtr.
ob->val = 98.6;
cout << "ob->val: " << ob->val << endl;
cout << "ob is now " << *ob << endl;
} catch(bad_alloc exc) {
cout << "Allocation error!\n";
return 1;
}
return 0;
}
Notice how the members of MyClass are accessed through the use of the –> operator. Remember, GCPtr defines a pointer type. Thus, operations through a GCPtr are performed in exactly the same fashion that they are with any other pointer.
The output from the program, with the display option turned off, is shown here:
(10 20)
(11 21)
Sum is : 32
ob->val: 98.6
ob is now (11 21)
Destructing MyClass(11, 21)
Destructing MyClass(10, 20)
Pay special attention to the last two lines. These are output by ~MyClass( ) when garbage is collected. Even though only one GCPtr pointer was created, two MyClass objects were allocated. Both of these objects are represented by entries in the garbage collection list. When ob is destroyed, gclist is scanned for entries having a reference count of zero. In this case, two such entries are found, and the memory to which they point is deleted.
The following program shows a larger example that exercises all of the features of GCPtr:
// Demonstrating GCPtr.
#include
#include
#include "gc.h"
using namespace std;
// A simple class for testing GCPtr with class types.
class MyClass {
int a, b;
public:
double val;
MyClass() { a = b = 0; }
MyClass(int x, int y) {
a = x;
b = y;
val = 0.0;
}
~MyClass() {
cout << "Destructing MyClass(" <<
a << ", " << b << ")\n";
}
int sum() {
return a + b;
}
friend ostream &operator<<(ostream &strm, MyClass &obj);
};
// Create an inserter for MyClass.
ostream &operator<<(ostream &strm, MyClass &obj) {
strm << "(" << obj.a << " " << obj.b << ")";
return strm;
}
// Pass a normal pointer to a function.
void passPtr(int *p) {
cout << "Inside passPtr(): "
<< *p << endl;
}
// Pass a GCPtr to a function.
void passGCPtr(GCPtr
cout << "Inside passGCPtr(): "
<< *p << endl;
}
int main() {
try {
// Declare an int GCPtr.
GCPtr
// Allocate an int and assign its address to ip.
ip = new int(22);
// Display its value.
cout << "Value at *ip: " << *ip << "\n\n";
// Pass ip to a function
passGCPtr(ip);
// ip2 is created and then goes out of scope
{
GCPtr
}
int *p = ip; // convert to int * pointer'
passPtr(p); // pass int * to passPtr()
*ip = 100; // Assign new value to ip
// Now, use implicit conversion to int *
passPtr(ip);
cout << endl;
// Create a GCPtr to an array of ints
GCPtr
// Initialize dynamic array.
for(int i=0; i < 5; i++)
iap[i] = i;
// Display contents of array.
cout << "Contents of iap via array indexing.\n";
for(int i=0; i < 5; i++)
cout << iap[i] << " ";
cout << "\n\n";
// Create an int GCiterator.
GCPtr
// Now, use iterator to access dynamic array.
cout << "Contents of iap via iterator.\n";
for(itr = iap.begin(); itr != iap.end(); itr++)
cout << *itr << " ";
cout << "\n\n";
// Generate and discard many objects
for(int i=0; i < 10; i++)
ip = new int(i+10);
// Now, manually garbage collect GCPtr
// Keep in mind that GCPtr
// will not be collected by this call.
cout << "Requesting collection on GCPtr
GCPtr
// Now, use GCPtr with class type.
GCPtr
// Show value via overloaded insertor.
cout << "ob points to " << *ob << endl;
// Change object pointed to by ob.
ob = new MyClass(11, 21);
cout << "ob now points to " << *ob << endl;
// Call a member function through a GCPtr.
cout << "Sum is : " << ob->sum() << endl;
// Assign a value to a class member through a GCPtr.
ob->val = 19.21;
cout << "ob->val: " << ob->val << "\n\n";
cout << "Now work with pointers to class objects.\n";
// Declare a GCPtr to a 5-element array
// of MyClass objects.
GCPtr
// Allocate the array.
v = new MyClass[5];
// Get a MyClass GCiterator.
GCPtr
// Initialize the MyClass array.
for(int i=0; i<5; i++) {
v[i] = MyClass(i, 2*i);
}
// Display contents of MyClass array using indexing.
cout << "Cycle through array via array indexing.\n";
for(int i=0; i<5; i++) {
cout << v[i] << " ";
}
cout << "\n\n";
// Display contents of MyClass array using iterator.
cout << "Cycle through array through an iterator.\n";
for(mcItr = v.begin(); mcItr != v.end(); mcItr++) {
cout << *mcItr << " ";
}
cout << "\n\n";
// Here is another way to write the preceding loop.
cout << "Cycle through array using a while loop.\n";
mcItr = v.begin();
while(mcItr != v.end()) {
cout << *mcItr << " ";
mcItr++;
}
cout << "\n\n";
cout << "mcItr points to an array that is "
<< mcItr.size() << " objects long.\n";
// Find number of elements between two iterators.
GCPtr
mcItr = v.begin();
cout << "The difference between mcItr2 and mcItr is "
<< mcItr2 - mcItr;
cout << "\n\n";
// Can also cycle through loop like this.
cout << "Dynamically compute length of array.\n";
mcItr = v.begin();
mcItr2 = v.end();
for(int i=0; i < mcItr2 - mcItr; i++) {
cout << v[i] << " ";
}
cout << "\n\n";
// Now, display the array backwards.
cout << "Cycle through array backwards.\n";
for(mcItr = v.end()-1; mcItr >= v.begin(); mcItr--)
cout << *mcItr << " ";
cout << "\n\n";
// Of course, can use "normal" pointer to
// cycle through array.
cout << "Cycle through array using 'normal' pointer\n";
MyClass *ptr = v;
for(int i=0; i < 5; i++)
cout << *ptr++ << " ";
cout << "\n\n";
// Can access members through a GCiterator.
cout << "Access class members through an iterator.\n";
for(mcItr = v.begin(); mcItr != v.end(); mcItr++) {
cout << mcItr->sum() << " ";
}
cout << "\n\n";
// Can allocate and delete a pointer to a GCPtr
// normally, just like any other pointer.
cout << "Use a pointer to a GCPtr.\n";
GCPtr
*pp = new int(100);
cout << "Value at **pp is: " << **pp;
cout << "\n\n";
// Because pp is not a garbage collected pointer,
// it must be deleted manually.
delete pp;
} catch(bad_alloc exc) {
// A real application could attempt to free
// memory by collect() when an allocation
// error occurs.
cout << "Allocation error.\n";
}
return 0;
}
Here is the output with the display option turned off:
Value at *ip: 22
Inside passGCPtr(): 22
Inside passPtr(): 22
Inside passPtr(): 100
Contents of iap via array indexing.
0 1 2 3 4
Contents of iap via iterator.
0 1 2 3 4
Requesting collection on GCPtr
ob points to (10 20)
ob now points to (11 21)
Sum is : 32
ob->val: 19.21
Now work with pointers to class objects.
Destructing MyClass(0, 0)
Destructing MyClass(1, 2)
Destructing MyClass(2, 4)
Destructing MyClass(3, 6)
Destructing MyClass(4, 8)
Cycle through array via array indexing.
(0 0) (1 2) (2 4) (3 6) (4 8)
Cycle through array through an iterator.
(0 0) (1 2) (2 4) (3 6) (4 8)
Cycle through array using a while loop.
(0 0) (1 2) (2 4) (3 6) (4 8)
mcItr points to an array that is 5 objects long.
The difference between mcItr2 and mcItr is 3
Dynamically compute length of array.
(0 0) (1 2) (2 4) (3 6) (4 8)
Cycle through array backwards.
(4 8) (3 6) (2 4) (1 2) (0 0)
Cycle through array using 'normal' pointer
(0 0) (1 2) (2 4) (3 6) (4 8)
Access class members through an iterator.
0 3 6 9 12
Use a pointer to a GCPtr.
Value at **pp is: 100
Destructing MyClass(4, 8)
Destructing MyClass(3, 6)
Destructing MyClass(2, 4)
Destructing MyClass(1, 2)
Destructing MyClass(0, 0)
Destructing MyClass(11, 21)
Destructing MyClass(10, 20)
On your own, try compiling and running this program with the display option turned on. (That is, define DISPLAY in gc.h.) Next, walk through the program, matching the output against each statement. This will give you a good feel for the way the garbage collector works. Remember, garbage collection occurs whenever a GCPtr goes out of scope. This happens at various points in the program, such as when a function that receives a copy of a GCPtr returns. In this case, the copy goes out of scope and garbage collection takes place. Also remember that each type of GCPtr maintains its own gclist. Thus, collecting garbage from one list does not cause it to be collected from other types of lists.
The following program load tests GCPtr by repeatedly allocating and discarding objects until free memory is exhausted. When this occurs, a bad_alloc exception is thrown by new. Inside the exception handler, collect( ) is explicitly called to reclaim the unused memory, and the process continues. You can use this same technique in your own programs.
// Load test GCPtr by creating and discarding
// thousands of objects.
#include
#include
#include
#include "gc.h"
using namespace std;
// A simple class for load testing GCPtr.
class LoadTest {
int a, b;
public:
double n[100000]; // just to take up memory
double val;
LoadTest() { a = b = 0; }
LoadTest(int x, int y) {
a = x;
b = y;
val = 0.0;
}
friend ostream &operator<<(ostream &strm, LoadTest &obj);
};
// Create an inserter for LoadTest.
ostream &operator<<(ostream &strm, LoadTest &obj) {
strm << "(" << obj.a << " " << obj.b << ")";
return strm;
}
int main() {
GCPtr
int i;
for(i = 1; i < 20000; i++) {
try {
mp = new LoadTest(i, i);
} catch(bad_alloc xa) {
// When an allocation error occurs, recycle
// garbage by calling collect().
cout << "Last object: " << *mp << endl;
cout << "Length of gclist before calling collect(): "
<< mp.gclistSize() << endl;
GCPtr
cout << "Length after calling collect(): "
<< mp.gclistSize() << endl;
}
}
return 0;
}
A portion of the output from the program (with the display option off) is shown here. Of course, the precise output you see may differ because of the amount of memory available in your system and the compiler that you are using.
Last object: (518 518)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Last object: (1036 1036)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Last object: (1554 1554)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Last object: (2072 2072)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Last object: (2590 2590)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Last object: (3108 3108)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Last object: (3626 3626)
Length of gclist before calling collect(): 518
Length after calling collect(): 1
Some Restrictions
There are a few restrictions to using GCPtr:
1. You cannot create global GCPtrs. Recall that a global object goes out of scope after the rest of the program ends. When a global GCPtr goes out of scope, the GCPtr destructor calls collect( ) to try to release the unused memory. The trouble is that, depending on how your C++ compiler is implemented, gclist may have already been destroyed. In this case, executing collect( ) will cause a runtime error. Therefore, GCPtr should be used only when creating local objects.
2. When using dynamically allocated arrays, you must specify the size of the array when you declare a GCPtr that will point to it. There is no mechanism that enforces this, however, so be careful.
3. You must not attempt to release the memory pointed to by a GCPtr by explicitly using delete. If you need to immediately release an object, call collect( ).
4. A GCPtr object must point only to memory that is dynamically allocated via new. Assigning to a GCPtr object a pointer to any other memory will cause an error when the GCPtr object goes out of scope because an attempt will be made to free memory that was never allocated.
5. It is best to avoid circular pointer references for reasons described earlier in this chapter. Although all allocated memory is eventually released, objects containing circular references remain allocated until the program ends, rather than being released when they are no longer used by another program element.
Some Things to Try
It is easy to tailor GCPtr to the needs of your applications. As explained earlier, one of the changes that you might want to try is collecting garbage only after some metric has been reached, such as gclist reaching a certain size, or after a certain number of GCPtrs have gone out of scope.
An interesting enhancement to GCPtr is to overload new so that it automatically collects garbage when an allocation failure occurs. It is also possible to bypass the use of new when allocating memory for a GCPtr and use factory functions defined by GCPtr instead. Doing this lets you carefully control the dynamic allocation of memory, but it makes the allocation process fundamentally different than it is for C++’s built-in approach.
You might want to experiment with other solutions to the circular reference problem. One way is to implement the concept of a weak reference, which does not prevent garbage collection from occurring. You would then use a weak reference whenever a circular reference was needed.
Perhaps the most interesting variation on GCPtr is found in Chapter 3. There, a multithreaded version is created in which garbage collection takes place automatically, when free CPU time exists.
No comments:
Post a Comment