Visual C++11堆栈分配器用于std::list和std::map

Question

我想提高列表和地图的特定用法的性能，其中条目的数量限制在100000左右。在这种情况下，STL默认分配程序显然不是最佳选择，因为清理所有数千个小对象需要很长时间(>10秒！)。更别提其他潜在的问题了。

因此，显然，为了改进这一点，我可以预先分配正确的内存量，以包含所有的列表/映射节点。到目前为止，我已经能够实现默认分配程序的工作版本(从std：：allocator_traits派生)，该版本对每个节点使用alloc/free。但是，我很难找到如何修改它以允许“有状态”使用，例如，我非常简单的堆栈：

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;}

我正在实例化我的列表并绘制如下地图：

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

MemPoolStack本身并不是真正的问题，它可能有but，但它只是为了例如目的。重点是MemPoolStack类将一个unique_ptr存储到预先分配的内存和一些其他成员变量。

存在的问题是，我需要在MemPoolStack类中引用我的MemPool，以便VisualC++11映射或列表可以构造我的分配程序的所有不同方式都会在每个列表或映射中得到一个MemPoolStack实例。然后，我可以使用MemPoolStack::Pop()在MemPool::allocate()，MemPoolStack::Push()在MemPool::deallocate()。

我还需要一种方法来构造我的分配器，指定大小。我试图在shared_ptr<MemPoolStack>中添加一个MemPool，但是当列表决定调用分配程序的默认构造函数时，它就会丢失.

我也愿意抛开所有这些代码，作为原始问题的一个好的替代解决方案。

Answer 1

因为您需要一个基础池，并且可以复制和重新绑定分配器，所以不能将状态直接存储在分配器中。

您可以做的是存储指向状态的指针(或shared_ptr)，这样就可以将分配器的副本浅拷贝到指针，引用相同的底层池。

请注意，您需要为分配器编写一个默认构造函数，并让它创建一个新的支持池，或者您需要创建一个具有特定支持池的分配器实例，并将其传递给容器构造函数。

所以这个：

list<TKey, MemPool<TKey>> Keys;

默认情况下将构造一个分配器(类似于MemPool<list<TKey>::node>)，而该分配器实例必须创建自己的支持状态；同时：

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

将通过您必须提供的select_on_container_copy_construction() const方法复制原始分配器实例(这样您就可以使两个容器与它们各自的分配器实例共享相同的池)；最后，如下所示：

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

将使用指定的支持池。

Answer 2

好吧，所以我已经开始工作了，一旦我的脑细胞被激活，因为没用。

下面是分配器的代码(我在这里省略了MemPoolStack，因为它没有更改，而且可能无论如何都坏了，这是我的下一个任务--但这里的问题是如何获得一个工作的有状态分配器)：

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;}

然而，我对这一切的实例化现在有点冗长了：

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.

在MemPool::allocate()中设置断点显示，Stack成员现在总是被填充。

太好了，C++11万岁！