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

Question

我想提高 list 和 map 的特定用法的性能，其中项目的数量有大约 100000 的硬限制。在这种情况下，STL 默认分配器显然不是最佳选择，因为清理所有数千个小对象需要很长时间(> 10 秒!)。更不用说所有其他潜在问题。

很明显，为了改进这一点，我可以预先分配正确数量的内存以包含所有列表/ map 节点。到目前为止，我已经能够实现默认分配器的工作版本(通过从 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;}

我正在像这样实例化我的列表和 map :

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

MemPoolStack它本身并不是真正的问题，它可能有错误，但这只是为了举例。关键是 MemPoolStack类存储一个unique_ptr到预分配的内存，以及一些其他成员变量。

问题是我需要引用我的 MemPoolStack在MemPool类，以便 Visual C++11 映射或列表可以构造我的分配器的所有不同方式都以一个 MemPoolStack 结束。每个列表或 map 的实例。然后我可以使用 MemPoolStack::Pop()在 MemPool::allocate() , 和 MemPoolStack::Push()在 MemPool::deallocate() .

我还需要一种方法来初始构造我的分配器，指定大小。我试着放一个 shared_ptr<MemPoolStack>在 MemPool但是当列表决定调用分配器的默认构造函数时，它最终迷路了……

我也愿意放弃所有这些代码，以找到解决原始问题的良好替代方案。

Answer 1

由于您需要一个单一的底层池，并且可以复制和重新绑定(bind)分配器，因此您不能将状态直接存储在分配器中。

您可以做的是存储指向您的状态的指针(或 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));

将使用指定的后备池。