5

リストとマップの特定の使用方法のパフォーマンスを向上させたいと考えています。この場合、アイテムの数には 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自体はここでは実際の問題ではありません。おそらくバグがありますが、これは単なる例です。ポイントは、MemPoolStackクラスunique_ptrが事前に割り当てられたメモリと他のいくつかのメンバー変数に a を格納することです。

問題は、Visual C++11 マップまたはリストがアロケーターを構築できるさまざまな方法がすべて、リストまたはマップごとに 1 つのインスタンスになるようMemPoolStackに、クラス内に my への参照が必要なことです。次に、 in 、およびinを使用できます。MemPoolMemPoolStackMemPoolStack::Pop()MemPool::allocate()MemPoolStack::Push()MemPool::deallocate()

サイズを指定して、アロケータを最初に構築する方法も必要です。を入れてみshared_ptr<MemPoolStack>ましMemPoolたが、リストがアロケーターのデフォルトコンストラクターを呼び出すことを決定したときに失われました...

また、元の問題に対する優れた代替ソリューションを得るために、このコードをすべて破棄することにもオープンです。

4

2 に答える 2

1

よし、役に立たないおかげで脳細胞が活動を開始したら、これが機能するようになった。

アロケーターのコードは次のとおりです (MemPoolStack変更されておらず、おそらく壊れているため、here を省略しました。それが私の次のタスクです。ただし、ここでの問題は、動作するステートフル アロケーターを取得することでした)。

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 万歳！

于 2013-12-18T15:19:12.627 に答える