Tuesday, April 3, 2012

Funky Memory

Allocators.  They are terrifying, difficult to understand, and easy to misunderstand.  They do not seem to be coded often, and few articles are written about them.  There is little to go on to figure out what exactly those handy little tools do or even how to use them.

I do not consider myself an expert on the topic, but I have read many articles, perused thousands of lines of code that uses them, and read the C++ standard1's sections about them. I am not an expert, but I know a little about allocators, and a little more information on the Web is much better than none at all!


Where are allocators used?

Most of the C++ STL containers have an optional template parameter and an optional contructor parameter for allocators, but those are seldom used.  By default, the template parameter is std::allocator<T>, and the constructor parameter is std::allocator<T>().  The STL containers use allocators.


What are allocators?

Allocators are objects that manage memory allocation.  The idea is similar to the new and delete operators.  In STL containers, when you add data to them, they do not use new; instead, they use an allocator to do the exact same thing.  The same is true when removing data (instead of delete, an allocator deletes the data).

The reason why containers go this round-about way of managing memory is so that you, the user, can change how exactly memory is allocated and deallocated.  Most of the time, the default allocator suffices, and I personally have never seen any code that uses anything else.  The option, however, is still there, just in case.


What is an example of a custom allocator?

Let us suppose that you want to output a log of all of the memory operations.  This could be handy for debugging a container to make certain that there are no memory leaks.  Nothing speaks better than code itself, so take a look at the example code that I have whipped up.

#include <iostream>
#include <memory>
#include <vector>


// My allocator class
template<typename T>
struct myAllocator :
public std::allocator<T>
{
// Typedefs
typedef typename std::allocator<T>::pointer pointer;


// Constructors
myAllocator() :
std::allocator<T>()
{} 
myAllocator( const myAllocator & src ) :
std::allocator<T>( src )
{}


template<typename U>
myAllocator( const myAllocator<U> & src ) :
std::allocator<T>( src )
{} 
// Allocation
pointer allocate(
size_t c,
std::allocator<void>::const_pointer hint = 0 )
{
std::cout << "===> allocate: "
<< c << "*" << sizeof(T) << std::endl;
return std::allocator<T>::allocate(c, hint);
// Deallocation
void deallocate( pointer p, size_t c )
{
std::cout << "===> deallocate: "
<< c << "*" << sizeof(T) << std::endl;
std::allocator<T>::deallocate(p, c);
// Rebind (we'll look at this in another blog post)
template <typename U>
struct rebind { typedef myAllocator<U> other; };
};


// Let's test it
int main()
{
std::cout << "creating vector..." << std::endl;
std::vector<int, myAllocator<int> > test; 
std::cout << "inserting 1-10..." << std::endl;
for( int i = 0; i != 10; ++i )
test.push_back( i ); 
std::cout << "erasing one element..." << std::endl;
test.pop_back(); 
std::cout << "ending..." << std::endl;
return 0;
}
The output of the above is:
creating vector...
inserting 1-10...
===> allocate: 1*4
===> allocate: 2*4
===> deallocate: 1*4
===> allocate: 4*4
===> deallocate: 2*4
===> allocate: 8*4
===> deallocate: 4*4
===> allocate: 16*4
===> deallocate: 8*4
erasing one element...
ending...
===> deallocate: 16*4
And that, dear readers, is how allocators work.  The STL uses them to manage their memory, and we can define our own allocators that do just a bit more than allocate and deallocate memory.  Plug them into that [previously] mysterious template parameter, and off we go!


Footnotes:

1. Working Draft, Standard for Programming Language C++, document #N3225=10-0215, dated 2010-11-27

No comments:

Post a Comment