Home arrow C++ arrow Page 9 - A Simple Garbage Collector for C++
C++

A Simple Garbage Collector for C++


The use of dynamically allocated memory must be managed, because it has a tremendous effect on the performance of your programs. The current trend in handling dynamic memory seems to be shifting toward an automated approach. While C++ uses the manual approach for managing dynamic memory, this does not mean that it can't be automated in that language -- thus giving the C++ programmer the best of both worlds. This article explains how to do it. It is excerpted from chapter two of The Art of C++, written by Herbert Schildt (McGraw-Hill/Osborne, 2004; ISBN: 0072255129).

Author Info:
By: McGraw-Hill/Osborne
Rating: 4 stars4 stars4 stars4 stars4 stars / 73
June 21, 2005
TABLE OF CONTENTS:
  1. · A Simple Garbage Collector for C++
  2. · Comparing the Two Approaches to Memory Management
  3. · Choosing a Garbage Collection Algorithm
  4. · What About auto_ptr?
  5. · An Overview of the Garbage Collector Classes
  6. · GCPtr In Detail
  7. · The Overloaded Assignment Operators
  8. · GCInfo
  9. · How to Use GCPtr
  10. · Allocating Arrays
  11. · A Larger Demonstration Program
  12. · Load Testing

print this article
SEARCH DEVARTICLES

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<int> p; // p can point to int objects

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<int> p = new int(88); // declare and initialize

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 <iostream>
#include <new>
#include "gc.h"
using namespace std;
int main() {
  GCPtr<int> p;
 
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<int, 0>:
memPtr        refcount      value
[002F12C0]        0         88
[00000000]        0         ---
Deleting: 88
After garbage collection for gclist<int, 0>:
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 <iostream>
#include <new>
#include "gc.h"
using namespace std;
int main() {
  GCPtr<int> p;
  GCPtr<int> q;
 
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<int> r = new int(12);
      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<int, 0>:
memPtr      refcount    value
[002F31D8]      0       12
[002F12F0]      1       11
[002F12C0]      1       10
[00000000]      0       ---
Deleting: 12
After garbage collection for gclist<int, 0>:
memPtr      refcount    value
[002F12F0]      1       11
[002F12C0]      1       10
After exiting block.
Done
GCPtr going out of scope.
Before garbage collection for gclist<int, 0>:
memPtr      refcount    value
[002F12F0]      0       11
[002F12C0]      1       10
Deleting: 11
After garbage collection for gclist<int, 0>:
memPtr      refcount    value
[002F12C0]      1       10
GCPtr going out of scope.
Before garbage collection for gclist<int, 0>:
memPtr      refcount    value
[002F12C0]      0       10
Deleting: 10
After garbage collection for gclist<int, 0>:
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 <iostream>
#include <new>
#include "gc.h"
using namespace std;
int main() {
  try {
    // Allocate and discard objects.
    GCPtr<int> p = new
int(1);
    p = new int(2);
    p = new int(3);
    p = new int(4);
   
// Manually collect unused objects for
    // demonstration purposes.
    GCPtr<int>::collect();
    
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<int, 0>:
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<int, 0>:
memPtr      refcount    value
[002F1310]      1        4
*p: 4
GCPtr going out of scope.
Before garbage collection for gclist<int, 0>:
memPtr      refcount    value
[002F1310]      0        4
Deleting: 4
After garbage collection for gclist<int, 0>:
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.


blog comments powered by Disqus
C++ ARTICLES

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials