Friday, June 11, 2010

What the Hell are Allocators ???

Writing this is like a compulsive need to understand wht the heck is all about Allocators in c++. I see these whenever I check a process core dump with vectors, maps etc , and they make the complete stack look so scary. And also not to mention the compilation errors. You do some teeny weeny mistake in vector or map or some crazy stl declaration and bammm the compilation error scares the hell out of you, and you wonder where did I declare with those allocators n all.

Here I will try to get over my fears and try to understand properly what are these things. And not embarrass my self because of the fact that being a 3.5 years experienced c++ programmer c++ allocators have eluded me for a long, and will now make an attempt to do it along with explaining to you guys.

The definition as understood by me is that an allocator is a class that handles the allocation/de-allocation of various STL, especially containers. For example take vector, its just a linked list. Whenever we call push_back() on a vector object, it has to allocate some memory for the entry and attache it to the existing linked list. This allocation of memory is hidden to us and is handled by a class specifically designed for the purpose i.e  the allocator.
Now what is the functionality  that we are looking for in the Allocator class
1. Allocation/Deallocation
2. Hopefully Thats it...

Lets take it forward and try to implement an allocator.

#include <iostream>

#include <vector>



using namespace std;



template<typename T>

class Allocator

{

        public:

                typedef T value_type;

                typedef value_type* pointer;





        public:

                inline explicit Allocator()

                {

                        cout << "Constructor of Allocator\n";

                }

                inline ~Allocator()

                {

                        cout << "destructor of Allocator\n";

                }

                inline explicit Allocator(Allocator const&) {}



};



int main()

{

        vector<int, Allocator<int> > vec;

}


Guess what when I compiled I got a really long list of errors. Probably these compilation errors will help us understand Allocators better. So, here is the listing.

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In instantiation of `std::vector<int, Allocator<int> >':

test_allocator.cxx:29:   instantiated from here

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:152: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:153: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:154: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:157: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:158: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:322: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:338: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:354: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:370: error: no type named `const_pointer' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:462: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:476: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:500: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:514: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:521: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:528: error: no type named `const_reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:535: error: no type named `reference' in `class Allocator<int>'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:542: error: no type named `const_reference' in `class Allocator<int>'

test_allocator.cxx: In function `int main()':

test_allocator.cxx:29: error: no matching function for call to `Allocator<int>::Allocator(Allocator<int>)'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182: error: in passing argument 1 of `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h: In member function `void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(_Tp*, size_t) [with _Tp = int, _Alloc = Allocator<int>]':

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:106:   instantiated from `std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = int, _Alloc = Allocator<int>]'

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:182:   instantiated from `std::vector<_Tp, _Alloc>::vector(const typename std::_Vector_base<_Tp, _Alloc>::allocator_type&) [with _Tp = int, _Alloc = Allocator<int>]'

test_allocator.cxx:29:   instantiated from here

/usr/local/lib/gcc/sparc-sun-solaris2.10/3.4.6/../../../../include/c++/3.4.6/bits/stl_vector.h:117: error: 'struct std::_Vector_base<int, Allocator<int> >::_Vector_impl' has no member named 'deallocate'



So, you can see there are various declarations/definitions missing in the allocator class. I hate to tell this, but its a fact that allocators follow some C++ standards guideline as per how the class should look like. 
(ISO C++ standard, section 20.4.1)
And it looks like the following. I have provided brief description next to each declaration.

//Template definition for allocator as it will be used to allocate 
// any pointer type
    template <class T>  class allocator {
    public:
            //Set of typedefs to be used in various

            //methods for allocation/deallocation/construction

            // destruction etc.


            typedef size_t    size_type;

            //Unsigned integral value that can represent the difference between two pointers
            typedef ptrdiff_t difference_type;

            // Pointer type for the class

            typedef T*        pointer;

            // Const pointer type for the class
            typedef const T*  const_pointer;

            //Reference type for the class 
            typedef T&        reference;

            //Const Reference for the class
            typedef const T&  const_reference;

            // Value type    
            typedef T         value_type;
      
            //template structure, which allows any allocator might allocate memory of another type indirectly.

            template <class U> struct rebind { typedef allocator<U>
                                         other; };

            allocator() throw();
            allocator(const allocator&) throw();
            template <class U> allocator(const allocator<U>&) throw();
            ~allocator() throw();

            pointer address(reference x) const;
            const_pointer address(const_reference x) const;

            // This function will be called, whenever a new memory 
            // allocation is required. As in vector push_back      
            pointer allocate(size_type,
                       allocator<void>::const_pointer hint = 0);

            // This function will be called when the memory location needs to be 

            // freed.

            void deallocate(pointer p, size_type n);
            size_type max_size() const throw();

            // Following are required to initialize/de-initialize the allocated
            // memory location.
            void construct(pointer p, const T& val);
            void destroy(pointer p);
    };


Now after we have understood how our Allocator class should look like, lets put some life into this class. Lets make it usable by defining atleast allocate/deallocate functions. 

Here is how I have defined it in my test program.
            pointer allocator::allocate(size_type sz, std::allocator<void>::const_pointer hint = 0)
            {
                     cout << "Allocating\n";
                     char* ch = (char*)malloc(sizeof(sz));
                     return (pointer)(ch);
            }
            void allocator::deallocate(pointer p, size_type n)
            {
                    cout << "De-Allocating\n";
                    free(p);
            

            }


Now lets see, how does it work in real use.

            int main()
            {
                vector<int> myVector;


                myVector.push_back(1);

  

            }

On compiling and running the program following out put is obtained.
            Allocating

            De-Allocating


At this point atleast we are aware of some internals of allocators, and we know "wht the hell allocators are" . Going further we can define our pool of memory and allocate from that pool and handle all allocations/deallocations in that chunk of memory using our own creative memory management algorithm. 

I hope I will cover that advanced topic some other day , till then cya .....