General memory managers are quite complex and difficult to construct, because they have to be able to serve requests for blocks of memory of arbitrary size arriving in an unpredictable order. In C++, you can construct a general memory manager by overriding the global new and delete operators and replacing them with your own custom global memory manager. This is quite complex, and is rarely ever done in practice, as the default memory manager provided by the default global new and delete operators is quite capable.
An alternative scenario, which does sometimes arise in practice, is the need to construct a custom memory manager designed to handle the memory allocation needs of a single class. In the notes that follow I will discuss how to create such a custom memory manager.
The example these notes discuss is an example where I will implement a memory manager designed to serve up a single kind of object. Specifically, I will create a custom memory manager that handles requests to create and delete nodes for an AVL tree.
The first step in making such a custom memory manager is to override operators new and delete for the class whose memory we wish to manage. That looks something like the following:
template<class T>
class AVLNode {
public:
AVLNode() {
left = right = parent = 0;
balanceFactor = 0;
}
AVLNode(const T& el, AVLNode *p = 0, AVLNode *l = 0, AVLNode *r = 0) {
key = el; parent = p; left = l; right = r; balanceFactor = 0;
}
void* operator new (size_t size);
void operator delete (void *p);
T key;
int balanceFactor;
AVLNode *left, *right, *parent;
};
This is the old template AVLNode class familiar to you from the AVL tree assignment. The two new additions here are overloads of operator new and operator delete.
void* operator new (size_t size); void operator delete (void *p);
As in any case where one wants to override an existing operator and replace it with a new version, the first requirement is that the override have exactly the same signature as the original - the same list of parameters and the same return type. The generic new operator takes a single parameter that specifies the size in bytes of the block of memory needed and then returns a generic pointer to that block. In C++, the void* type is a generic pointer type that can be used to point to anything, hence all overrides of operator new return void*. The generic delete operator takes as its parameter a generic pointer to a block of memory to be deleted, and has the task of marking the block of memory that pointer points to as being freed and available for eventual reuse.
It is important to note that what we are doing here is overriding new and delete for the AVLNode class only. That is, only requests to create AVLNodes with new and requests to delete AVLNodes will get funneled through these two overrides. All other requests for new and delete operations in our program will continue to be handled by the global new and delete operators already present in C++.
Since our custom memory manager will only need to handle requests to allocate and free memory for a single type, we can greatly simplify the design of our memory manager. Here are some important aspects of the design.
The next important design decision is in how to implement the pool of blocks described above. Since this memory manager only serves requests for AVLNodes, one way to implement this pool would be as an array of AVLNodes:
AVLNode<T>* pool;
For reasons that will become clear in a moment, it is a little bit better to implement the pool as an array of ints:
int* pool;
To satisfy a request for an AVLNode, we will return a block of ints from the pool that is just large enough to contain an AVLNode. We can determine how large that block of ints needs to be via the computation
// Determine the block size int blockSize; int nodeSize = sizeof(AVLNode<T>); if(nodeSize % sizeof(int) == 0) blockSize = nodeSize/sizeof(int); else blockSize = nodeSize/sizeof(int) + 1;
The expression sizeof(AVLNode<T>) returns the size of an AVLNode in bytes. By dividing that by sizeof(int) we can determine the size of an AVLNode in ints instead of in bytes.
The int data type makes a good basic unit of measure for our pool because ints align nicely along CPU word boundaries in the memory.
Since the pool is an array of ints, one way to describe locations in the pool is via an integer index into that array. It is important to note the difference between this integer index and an actual memory location. The index measures locations relative to the start of the pool array in units of a single int. Memory locations measure locations relative to the start of the entire memory in units of bytes.
Here is how we can map between these two different measurement systems. To map an integer index n into the pool array to a memory location, we can use the following code:
void* p = &(pool[n]);
To map a memory location specified via a pointer void* p back to an index in the array, we use the logic
int n = reinterpret_cast<int*>(p) - pool;
The reason we use ints as the underlying data type for the pool array is that this guarantees that at the beginning of each block that represents an AVLNode we can find an int. That int will serve as the index linking together the blocks in the freed list. The only additional information we will need to implement the freed list is a static member variable
static int freeIndex;
to store the index of the last block in the chain of freed blocks. A second member variable
static int unusedIndex;
will record the index of beginning of the first of the unallocated blocks. Each time we have to give out one of the unallocated blocks we will increment this index to the next unallocated block.
The code for the memory manager consists of three methods. The first of these initializes the memory manager by allocating a pool with the requested number of blocks.
template <class T>
void AVLNode<T>::initMemoryManager(int desiredSize)
{
// Determine the block size
int nodeSize = sizeof(AVLNode<T>);
if(nodeSize % sizeof(int) == 0)
blockSize = nodeSize/sizeof(int);
else
blockSize = nodeSize/sizeof(int) + 1;
poolSize = blockSize*desiredSize;
pool = new int[poolSize];
// At start there is only one freed block in the pool, and all the
// other blocks are in the unallocated section.
freeIndex = 0;
pool[0] = -1; // Marks the end of the chain of freed blocks
unusedIndex = blockSize; // The first unused block starts blockSize spaces
// after the start of the only freed block
}
The code for operator new attempts to allocate a new block by using a block from the freed list if it is available. If no freed block is available, it tries next to use an unallocated block. If no blocks are available at all, operator new throws an exception of type bad_alloc, which is standard behavior for operator new.
template <class T>
void* AVLNode<T>::operator new (size_t size)
{
void* returnAddress = 0;
// If there is a freed block available, issue that first
if(freeIndex != 0) {
returnAddress = &(pool[freeIndex]);
freeIndex = pool[freeIndex];
} else if(unusedIndex < poolSize) {
// If no freed block is available, use an unallocated block instead.
returnAddress = &(pool[unusedIndex]);
unusedIndex += blockSize;
} else {
// To indicate an out of memory situation, throw a bad_alloc exception.
throw bad_alloc();
}
return returnAddress;
}
The code for operator delete simply computes the index corresponding to the address given for the freed AVLNode and adds the block starting at that index to the freed list.
template <class T>
void AVLNode<T>::operator delete (void *p)
{
// Compute the array index of the beginning of the block we
// have been given to delete.
int blockIndex = reinterpret_cast<int*>(p) - pool;
// Add this newly freed block to the chain of freed blocks.
pool[blockIndex] = freeIndex;
freeIndex = blockIndex;
}
In situations where a program is likely to need to allocate and free large numbers of objects of the same type, a custom memory manager as demonstrated here can give a performance boost over the standard versions of new and delete. Additionally, a custom memory manager can offer these benefits: