How to write your own allocator?

[Juha Nieminen]

This code compiles and runs, but it doesn't print anything. I'm
completely puzzled about why. (I'm using linux gcc 4.1.2.)
How can I write allocators which the STL containers will actually use?

#include <memory>
#include <list>
#include <iostream>

template<typename T>
class MyAlloc: public std::allocator<T>
{
public:
typename std::allocator<T>:ointer allocate
(typename std::allocator<T>::size_type count,
typename std::allocator<void>::const_pointer *hint = 0)
{
std::cout << "Allocation request: count = " << count
<< ", hint = " << hint << std::endl;
return std::allocator<T>::allocate(count, hint);
}

void deallocate(typename std::allocator<T>:ointer ptr,
typename std::allocator<T>::size_type count)
{
std::cout << "Deallocation request: count = " << count
<< std::endl;
std::allocator<T>::deallocate(ptr, count);
}
};

int main()
{
typedef std::list<int, MyAlloc<int> > List_t;

List_t l;
l.push_back(5);
l.push_back(10);
}

 

[Antoine Mathys]

This code compiles and runs, but it doesn't print anything. I'm
completely puzzled about why. (I'm using linux gcc 4.1.2.)
How can I write allocators which the STL containers will actually use?

Your allocator fails to overload two declarations. If you add this to
the public part of the interface, it will work:
MyAlloc () {}
template <class U> MyAlloc (const MyAlloc<U>&) {}
template <class U> struct rebind { typedef MyAlloc<U> other; };

In general, you shouldn't derive from std::allocator. It is better to
copy the entire interface and change the implementation.

 

[Kai-Uwe Bux]

This code compiles and runs, but it doesn't print anything. I'm
completely puzzled about why. (I'm using linux gcc 4.1.2.)
How can I write allocators which the STL containers will actually use?

#include <memory>
#include <list>
#include <iostream>

template<typename T>
class MyAlloc: public std::allocator<T>
{
public:
typename std::allocator<T>:ointer allocate
(typename std::allocator<T>::size_type count,
typename std::allocator<void>::const_pointer *hint = 0)
{
std::cout << "Allocation request: count = " << count
<< ", hint = " << hint << std::endl;
return std::allocator<T>::allocate(count, hint);
}

void deallocate(typename std::allocator<T>:ointer ptr,
typename std::allocator<T>::size_type count)
{
std::cout << "Deallocation request: count = " << count
<< std::endl;
std::allocator<T>::deallocate(ptr, count);
}
};

Add at least the rebind member template. As it stands, your allocator

int main()
{
typedef std::list<int, MyAlloc<int> > List_t;

List_t l;
l.push_back(5);
l.push_back(10);
}

The list container in this example will not use MyAlloc<int> but something
like

MyAlloc<int>::rebind<list_node>:ther

since it does not allocate integers but list_nodes. The only container that
possibly could use the allocator directly is std::vector, and even that
container will not necessarily do so.


Best

Kai-Uwe Bux

 

[zhangyw80]

I compiled the code snippet above in VC6, it doesn't compile because
the
prototype of function deallocate is wrong: the first argument should
be
void *, not pointer. linux gcc may be a little diffenrent.
however, you should implement the construct, _Charalloc and deallocate
(or their counterparts in linux gcc). when list allocates a new Node,
it calls _Charalloc for memory and construct to init a object T.
when list delete a Node, it calls deallocate. you can replace
allocate<T>::xxx with your own code to implement a custom memory
management
policy(e.g. private heap)

sample code(in VC6):
#include <memory>
#include <list>
#include <iostream>

using namespace std;

template<typename T>
class MyAlloc: public allocator<T>
{
public:

char _FARQ *_Charalloc(size_type _N)
{
cout << "alloc requst size:" << _N << endl;
return allocator<T>::_Charalloc(_N);
}

void construct(pointer p, const T& val)
{
cout << "constuct object:" << val << endl;
allocator<T>::construct(p, val);

}

void deallocate( allocator<void>:ointer ptr,
allocator<T>::size_type count)
{
cout << "Deallocation request: count = " << count
<< endl;
allocator<T>::deallocate(ptr, count);
}



};


int main()
{
typedef list<int, MyAlloc<int> > List_t;

List_t l;
l.push_back(5);
l.push_back(10);

return 1;
}

 

[Juha Nieminen]

Interesting. Three replies, three completely different answers...

I compiled the code snippet above in VC6, it doesn't compile because
the
prototype of function deallocate is wrong: the first argument should
be
void *, not pointer.

Is that standard? At least according to
http://www.dinkumware.com/manuals/default.aspx?manual=compleat&page=memory.html#allocator
the return value should indeed be 'pointer'.

 

[Juha Nieminen]

Add at least the rebind member template. As it stands, your allocator
inherits the rebind from std::allocator<> and therefore, rebound allocators
will not use the given allocate and deallocate functions.

This sounds like the most logical cause for the problem. I added this
to MyAlloc:

template<class Other>
struct rebind
{
typedef MyAlloc<Other> other;
};

but now I'm getting completely weird error messages. (Man, I wish the
new C++ standard would finally be released and compilers updated to take
full advantage of it so that template-related error messages would start
making some sense...)

/usr/include/c++/4.1.2/bits/stl_list.h:334: error: no matching function

::_List_impl::_List_impl(const MyAlloc<int>&)'

/usr/include/c++/4.1.2/bits/stl_list.h:327: error: conversion from
'const MyAlloc<std::_List_node<int> >' to non-scalar type 'MyAlloc<int>'
requested

 

[Juha Nieminen]

MyAlloc () {}
template <class U> MyAlloc (const MyAlloc<U>&) {}
template <class U> struct rebind { typedef MyAlloc<U> other; };

That solved the problem, thanks.

 

[Erik Wikström]

Interesting. Three replies, three completely different answers...



Is that standard? At least according to
http://www.dinkumware.com/manuals/default.aspx?manual=compleat&page=memory.html#allocator
the return value should indeed be 'pointer'.

zhangyw80 was talking about the first argument to the deallocate
function (not allocate) but either way, this is what the standard has to
say about it:

template <class T> class allocator {
public:
typedef size_t size_type;
// ...
typedef T* pointer;
// ...
pointer allocate(
size_type, allocator<void>::const_pointer hint = 0);
void deallocate(pointer p, size_type n);
// ...
};

 

[Kai-Uwe Bux]

This sounds like the most logical cause for the problem. I added this
to MyAlloc:

template<class Other>
struct rebind
{
typedef MyAlloc<Other> other;
};

but now I'm getting completely weird error messages. (Man, I wish the
new C++ standard would finally be released and compilers updated to take
full advantage of it so that template-related error messages would start
making some sense...)

/usr/include/c++/4.1.2/bits/stl_list.h:334: error: no matching function


/usr/include/c++/4.1.2/bits/stl_list.h:327: error: conversion from
'const MyAlloc<std::_List_node<int> >' to non-scalar type 'MyAlloc<int>'
requested

Right. I forgot that you also need a cross-type capable constructor. The
list wants to store an allocator object of type MyAlloc< list_node >. The
list constructor takes an argument of type MyAlloc< int >, which defaults
to MyAlloc< int >(). The internal MyAlloc< list_node > object is to be
initialized from there. Therefore, you need a constructor:

template < typename T >
class MyAlloc {

template < typename U >
MyAlloc ( MyAlloc<U> const & other ),

};


Best

Kai-Uwe Bux

 

[Juha Nieminen]

I performed some tests about creating memory allocators. It's actually
quite incredible how much, for example, std::list speeds up by using
your own efficient allocator instead of relying on the one in libc.

I actually made a library and a webpage on this subject:

http://warp.povusers.org/FSBAllocator/

For example with std::list<int>, performing the type of test I detail
in that page, the test program sped up from 1 min 12 seconds (using the
gcc's default allocator) to a mere 16 seconds (using my own allocator).
It also probably uses less memory overall (although this is a bit
difficult to measure in linux, but if my measures were correct, using my
own allocator reduced the peak memory usage to almost a half).

It's no wonder C++ may sometimes lose to other languages in speed, at
least if containers such as std::list or std::set are used with the
default allocator. 'new' is a rather slow operation.

 

[joseph cook]

[email protected]:

I would guess that most speedup comes from the fact that the general
allocator is thread-safe and yours is not (according to the web page),

Do compilers in general have a flag to tell it "SINGLE THREADS HERE!"
to optimize away and mutexes, etc ?

Thanks

 

[Stefan Ram]

Unfortunately we cannot use the code in our
production software because of the GPL license.

You can always ask the owner of the rights
for another license (agreement).