When comparing C and C++ to other popular programming languages like Java, C#, and python one of the big issues people bring up is that you “have to” manage dynamic memory manually. Aside from manual memory management not being nearly as big a deal as their detractors would make it seem, it is also not the whole story. While it’s true that manual memory management is the default behavior for these languages, and the vast majority of programs developed in these languages are developed in this fashion there is absolutely nothing to say that you aren’t free to use some kind of automatic memory management scheme.
When it comes to non-manual memory management as you find in languages such as Java, Perl, and Lisp, it generally falls into one of two broad categories: Garbage Collection and Reference Counting. Some people consider Reference Counting its self to be a form of garbage collection and while its mostly a matter of semantics, they work in fundamentally different ways. Ultimately they are both forms of automatic dynamic memory management with different positives and negatives.
Dynamic Memory and Garbage Collection: Why it matters
Anyone who has done any non trivial programming with C has encountered malloc(), the C language equivalent to C++’s operator new. It is used to allocate objects on the heap. These objects are different than objects which are allocated on the stack, in that when these object go out of scope their memory is not automatically returned to the system. Returning the memory used by an object that is allocated on the heap must be done explicitly either through the use of free() in C, or operator delete in C++.
Failure to free an objects memory when it goes out of scope is the cause of memory leaks – one of the major arguments for using garbage collected programming languages since this step is handled for you. If you have experience using both C++ and Java then I’m sure you noticed that creating an object is done the same way in both languages: through the use of operator new. When you are done with an object in C++ however you need to do the extra step of deleting that object, where in Java you don’t have to do anything. This is because Java uses a Garbage Collector.
“But computers are stupid!” you might be thinking “how would they know when an object isn’t being used anymore?”. There are many different types of garbage collectors, each with their own algorithms for reclaiming unused memory. The algorithm I will be discussing falls into the category of “tracing garbage collectors”.
Tracing Garbage Collectors
The purpose of a garbage collector is to offload the work of freeing unused memory back to the system. With that being said, “Garbage Collector” is somewhat of a misnomer. Object’s don’t magically appear, and neither do they magically become “garbage”. Object’s have a life time, from object creation, to while it is in use, and when it is no longer needed. Garbage collectors are involved through the entire life cycle – not just when the objects become garbage.
Appropriately named or otherwise, there is another matter of more importance: automatic memory management is not free, there is a cost to be paid in both time and space complexities. Each object managed by a tracing garbage collector needs some kind of “in use” flag. Additionally, the GC manages a list of pointers to each object created.
Aside from this additional memory usage, tracing garbage collectors periodically block normal program execution to perform their various GC tasks, which can impact overall program performance.
To determine when objects become garbage, the collector will periodically inspect all objects that have been created and compare them to all objects that are in use. The set difference of the two groups are the objects that can be freed. This is possible because because of the list of created objects the allocator/garbage collector maintains. How the “objects in use set” is determined is application specific. Let’s create a basic garbage collected Binary Search Tree to make these ideas a bit more concrete.
A Garbage Collected Binary Search Tree
To implement our GC’d BST we first need to implement our Garbage Collected Allocator, and the BST Node type who’s lifetime the allocator/garbage collector will be managing for us. As you can see, we’ve added the _gc_mark field to the node, this will be used for flagging garbage to be freeed.
template <class T>
struct GC_BTNode {
//Normal Binary Tree Node members
T info;
GC_BTNode* left;
GC_BTNode* right;
//for GC use
bool _gc_mark; //Is this object in use?
};
The next data structure is going to be for a “Roots” list. Since our GC’d objects are BST nodes, we can determine which of them are still in use by traversing any BST’s created starting from their root which we ill conveniently keep handy for just such purposes!
Now we can focus on the allocator. The allocator will also perform the garbage collection, but we have to create objects before we can worry about deleting them.
template <class T>
class GC_Allocator {
private:
vector<GC_BTNode<T>*> rootList; //list of roots of tree's in use
vector<GC_BTNode<T>*> nodeList; //objects created list
public:
GC_Allocator() {
}
GC_BTNode<T>* allocNode(T info, GC_BTNode<T>* left, GC_BTNode<T>* right) {
GC_BTNode<T>* tmpNode = new GC_BTNode<T>;
tmpNode->info = info;
tmpNode->left = left;
tmpNode->right = right;
//all nodes start with mark set false.
//and are immediately added to nodesList
tmpNode->_gc_mark = false;
nodeList.push_back(tmpNode);
return tmpNode;
}
void addRoot(GC_BTNode<T>* root) {
rootList.push_back(root);
}
};
As you can see we have methods for allocating nodes, and adding trees to the in use list. allocNode() will be replacing the use of operator new in our BST class.
template <class T>
class BST {
private:
GC_Allocator<T>* allocator;
using nodeptr = GC_BTNode<T>*;
nodeptr root;
int count;
nodeptr put(nodeptr h, T info) {
if (h == nullptr) {
count++;
return allocator->allocNode(info, nullptr, nullptr);
}
if (info < h->info) h->left = put(h->left, info);
else h->right = put(h->right, info);
return h;
}
/* additional code for
BST traversal, and for erasing elements
goes here */
public:
BST(GC_Allocator<T>* alloc) {
allocator = alloc;
root = nullptr;
}
void insert(T info) {
if (root == nullptr) {
root = allocator->allocNode(info, nullptr, nullptr);
allocator->addRoot(root);
count++;
} else {
root = put(root, info);
}
}
void traverse();
void erase(T info);
};
I’ve only shown the code for class definition so you can see that the allocator is passed as a pointer to the BST class, and that BST specific code is no different from normal except that we are using our custom allocator to create nodes, as well as adding the root of the tree to the root list when it is established.
Speaking of our custom allocator, we’re now ready to add the garbage collection code. Garbage Collection will take place in two phases: the mark phase, which finds all reachable nodes. And the sweep phase, which free’s the memory used by any nodes found to no longer be in use.
template <class T>
class GC_Allocator {
private:
vector<GC_BTNode<T>*> rootList;
vector<GC_BTNode<T>*> nodeList;
void mark_node(GC_BTNode<T>* node);
void mark();
void sweep();
public:
/*
Allocator specific code shown previously
*/
void gc() {
cout<<"[GC START]"<<endl;
mark();
sweep();
cout<<"[GC END]"<<endl;
}
};
The mark phases begins with a call to the aptly named mark() method, which traverses the rootList of created binary search tree’s. It then calls mark_node() on each of those BST’s which does a preorder traversal, of the tree to set each nodes _gc_mark flag.
void mark_node(GC_BTNode<T>* node) {
if (node != nullptr) {
node->_gc_mark = true;
mark_node(node->left);
mark_node(node->right);
}
}
void mark() {
for (GC_BTNode<T>* x : rootList) {
mark_node(x);
}
}
Pretty straight forward, right? Implementing sweep is just as simple. Sweep is a simple traversal of the nodeList, removing any node who wasn’t found to be reachable in the previous phase. The rest of the nodes get to live on in the next generation.
void sweep() {
int freedCnt = 0;
vector<GC_BTNode<T>*> nextGen;
for (auto& node : nodeList) {
if (node->_gc_mark)
nextGen.push_back(std::move(node));
else delete node;
}
freedCnt = nodeList.size() - nextGen.size();
nodeList = nextGen;
std::for_each(nodeList.begin(), nodeList.end(), [&](GC_BTNode<T>* h) { h->_gc_mark = false; });
cout<<freedCnt<<" items freed."<<endl;
}
And that’s it! All thats left to do is create a BST, delete some nodes without manually managing their memory, and watch the GC manage it for us!
int main() {
GC_Allocator<char> alloc;
BST<char> bst(&alloc);
string str = "GarbageCollectedBST";
for (char c : str)
bst.insert(c);
bst.print();
bst.erase('c');
bst.erase('S');
bst.print();
alloc.gc();
bst.print();
return 0;
}
max@MaxGorenLaptop:~$ g++ MarkSweep.cpp -o ms
max@MaxGorenLaptop:~$ ./ms
G C B a S T r b a g e c d e e o l l t
Delete 'c'
Delete 'S'
G C B a T r b a g e d e e o l l t
[GC START]
S is unreachable, freeing memory.
c is unreachable, freeing memory.
2 items freed.
[GC END]
G C B a T r b a g e d e e o l l t
max@MaxGorenLaptop:~$
Pretty Nifty, eh? Until next time, Happy Hacking!
