Visual C++11 stack allocator for std::list and std::map

Question

I'd like to increase the performance of a specific usage of list and map, where the number of items has a hard limit in the order of 100000. The STL default allocator obviously isn't the best choice in this situation, since cleaning up all the thousands of small objects takes a very long time (>10sec!). Not to mention all the other potential issues.

So obviously to improve this I can preallocate the correct amount of memory to contain all of the list/map nodes. So far I've been able to implement a working version of the default allocator (by deriving from std::allocator_traits), that uses alloc/free for each node. But I'm struggling to find out how to modify this to allow for the "stateful" use of, for example, my very simple stack:

using namespace std;
class MemPoolStack
{
public:
    size_t Size;
    size_t Mult;
    size_t Total;
    size_t Top;
    size_t Last;
    unique_ptr<byte[]> Data;
    unique_ptr<size_t[]> Nexts;

    MemPoolStack(size_t size, size_t mult) :
        Size(size),
        Mult(mult),
        Total(size * mult),
        Top(0),
        Last(0),
        Data(new byte[Total]),
        Nexts(new size_t[Size])
    {
    }
    size_t& Next(size_t i)
    {
        return *(Nexts.get() + i);
    }
    void* Pop()
    {
        byte* p = nullptr;
        if(Top<Size)
        {
            p = Data.get() + (Top * Mult);
            bool last = (Top==Last);
            size_t next = last ? Top+1 : Next(Top);
            if(last) Next(Top) = next;
            Top = next;
            if(Top>Last) Last=Top;
        }
        else
        {
            p = nullptr;
        }
        return p;
    }
    bool Push(void* p)
    {
        ptrdiff_t diff = (byte*)p - Data.get();
        size_t index = ((size_t)diff / Mult);
        if(diff>=0 && index<Size)
        {
            Next(index) = Top;
            Top = index;
            return true;
        }
        return false;
    }
};

template <class T> struct MemPool
{
    typedef T value_type;
    MemPool() throw() {}
    template <class U> MemPool (const MemPool<U>&) throw() {}
    template <class U> struct rebind { typedef MemPool<U> other; }; //off-topic: why doesn't allocator_traits define this?
    T* allocate (size_t n) 
    {
        return static_cast<T*>(malloc(n*sizeof(T))); 
    }
    void deallocate (T* p, size_t n) 
    { 
        free(p); 
    }
};

template <class T, class U>
bool operator== (const MemPool<T>&, const MemPool<U>&) throw()
{return true;}

template <class T, class U>
bool operator!= (const MemPool<T>&, const MemPool<U>&) throw()
{return false;}

And I'm instantiating my list and map like this:

list<TKey, MemPool<TKey>> Keys;
map<TKey, MapType, less<TKey>, MemPool<MapType>> Map;

The MemPoolStack itself isn't really the issue here, it probably has bugs but it's just for example purposes. The point is that the MemPoolStack class stores a unique_ptr to the preallocated memory, and some other member variables.

The problem there is that I need to have some reference to my MemPoolStack in the MemPool class, so that all the different ways that a Visual C++11 map or list can construct my allocator all end up with one MemPoolStack instance per list or map. Then I could use MemPoolStack::Pop() in MemPool::allocate(), and MemPoolStack::Push() in MemPool::deallocate().

I also need a way to initially construct my allocator, specifying the size. I tried putting a shared_ptr<MemPoolStack> in MemPool but it ended up getting lost when the list decided to call the allocator's default constructor...

I'm also open to throwing away all of this code for a good alternative solution to the original problem.

Answer 1

Since you want a single underlying pool, and allocators can be copied and re-bound, you can't store your state directly in the allocator.

What you can do is store a pointer (or a shared_ptr) to your state, such that copies of your allocator shallow-copy the pointer, referring to the same underlying pool.

Note that you either need to write a default constructor for your allocator, and have it create a new backing pool, or you need to create an allocator instance with a specific backing pool and pass it to the container constructor.

So this:

list<TKey, MemPool<TKey>> Keys;

will default construct an allocator (which will be something like MemPool<list<TKey>::node>), and that allocator instance will have to create its own backing state; while this:

list<TKey, MemPool<TKey>> MoreKeys(Keys);

will copy that original allocator instance via a select_on_container_copy_construction() const method you must provide (so you can make both containers, with their separate allocator instances, share the same pool); and finally this:

map<TKey, MapType, less<TKey>, MemPool<MapType>> Map(MemPool<MapType>(my_pool));

will use the specified backing pool.