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.

Answer 2

OK, so I've gotten this working, once my brain cells were fired into action thanks to Useless.

Here's the code of the allocator (I've omitted the MemPoolStack here since it hasn't changed and probably is broken anyway, that's my next task - but the issue here was to get a working stateful allocator):

template <class T> struct MemPool
{
    typedef T value_type;
    shared_ptr<MemPoolStack> Stack; //My allocator's state goes here!
    template <class U> MemPool (const MemPool<U>& p) throw()
    {
        if(p.Stack->Mult!=sizeof(U))
        {
            throw runtime_error("Can't rebind MemPool to another size object. Sorry.");
        }
        Stack = p.Stack; //interestingly, this constructor is used by std::map but not std::list
    }
    template <class U> struct rebind { typedef MemPool<U> other; }; //off-topic: maybe they fixed this one in VS2019?
    MemPool(size_t count) :
        Stack(new MemPoolStack(count, sizeof(T))) //I can allocate the memory here!
    {
    }
    T* allocate (size_t n) 
    {
        //Now I can return Stack->Pop() here instead of using malloc!
        if(n!=1) throw runtime_error("MemPool can only allocate one item at a time. Sorry.");
        return static_cast<T*>(Stack->Pop());
        //return static_cast<T*>(malloc(n*sizeof(T)));  
    }
    void deallocate (T* p, size_t n) 
    { 
        ///Can use Stack->Push() here instead of free!
        if(n!=1) throw runtime_error("MemPool can only deallocate one item at a time. Sorry.");
        Stack->Push(static_cast<void*>(p));
        //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;}

However, my instantiation of all this is now a little more long-winded:

typedef pair<size_t, typename list<TKey>::iterator> MapType;
typedef MemPool<_Tree_node<pair<TKey,MapType>,void*>> MapPoolType;
typedef MemPool<_List_node<TKey,void*>> ListPoolType;

list<TKey, ListPoolType> Keys(ListPoolType(capacity+10));
map<TKey, MapType, less<TKey>, MapPoolType> Map(MapPoolType(capacity+10));
//I use list/map capacity+10 because the containers like a few free nodes to themselves.
//Probably should investigate further as to what these numbers actually need to be.

Setting a breakpoint in MemPool::allocate() shows that the Stack member is now always populated.

Great, Hooray for C++11!