4

シナリオ: クラス N から派生した型の (通常) 何千ものオブジェクトで構成されるクラス G があります。これらのオブジェクトはすべて、明確に定義されたライフサイクルを持っています。まず、オブジェクト G が構築され、次に N 派生オブジェクトが追加されます。次に、N 派生オブジェクトを変更しない G で何らかの計算が行われます。次に、G は範囲外になり、それとともに構成要素N 派生オブジェクト。次に、N 派生オブジェクトには、同じ G オブジェクトに追加された他の N 派生オブジェクトへのポインターまたはポインターの標準コンテナーが含まれます。G は異種ノードを持つグラフを表します。

私の目標は次のとおりです。

  1. 各 N 派生オブジェクトを割り当てるコストを最小限に抑えます。
  2. 同じ G オブジェクトに属する N 派生オブジェクトの参照の局所性を最大化します。
  3. すべての N 派生オブジェクトに対して 1 つのブロックの割り当てを解除することにより、割り当て解除のコストを最小限に抑えます。
  4. 独立したライフサイクルを持つ複数の独立した G オブジェクトを定義できるようにする - これらの独立した G オブジェクトをスレッド同期なしで並行スレッドで管理する可能性があります。

私には、これは複数のプールアロケーターを必要とするように見えました-スタックを使用しているかのように割り当てます...そしてプールが破棄されたときにのみプールされた割り当てを解放します。

ブースト プール アロケータを調べましたが、サイズの異なる異種オブジェクトに対して複数の独立したプールを確立する方法が見つかりませんでした。

次に、独自のカスタム アロケーターを定義しましたが、std::vector、std::set、std::list などの標準コンテナーにテンプレート引数として渡すことができる一方で、すぐにそれを発見しました。- プール アロケータのタイプを指定できるようにする... 2 つの別の方法では独立したコンテナーが同じ (非グローバル) アロケーター プールを共有する必要があることを簡単に指定できないため、行き詰まります。1 つの解決策は、静的/グローバルを使用し、1 つのスレッドで G オブジェクトのみを構築するように制限することだと認識しています。カスタム アロケータを関連するプールに関連付けるために thread-local-storage を使用することも考えましたが、それは見苦しいと考えました。どちらのアプローチも、同じスレッド内の 2 つの独立した G オブジェクトのインターリーブ構造を直接サポートしていません。

Boost の問題に対する既存の解​​決策を見落としていませんか?

私の目的を達成するために、静的/グローバルまたはスレッドローカルストレージを使用するよりも優れたイディオムはありますか?

アップデート

Stroustrup のよくある質問と、boost::container のドキュメントを読みました。最初は、Boost::container に非常に勇気づけられましたが、これらのコンテナーでステートフル アロケーターを使用する方法の具体的な例を見ていないことに失望しました。元の質問を単純化して尋ねることができました...構造が与えられました：

struct DataUnit { map<int,string> m; list<int> l; }

DataUnit の各インスタンスに対して、m と l の内部構成要素が割り当てられる単一のプールがあることを確認するにはどうすればよいですか? map と list にカスタム アロケーターを渡すと、m と l はこのコンテナーの独立したインスタンスを取得します。最初は get_allocator() を使用して aerena/pool でアロケーターを初期化できるのではないかと考えていました...しかし、悲しいことに、vector<...> のデフォルトのコンストラクターが返される前に allocate() が呼び出されます..だから私はそれはできません。

さらに奇妙なことに、boost::container をしばらく試してみたところ、バニラの std コンテナーには get_allocator() (MSVC 2010 および 2012 および g++ 4.6.3) があることがわかりました。コンテキストには、boost::container と同様のステートフル アロケーター サポートがあります。

残念ながら、元の問題に対する実行可能な解決策はまだありません (ただし、より雄弁に表現できるようになりました)。

更新 2

ありがとう、pmr、あなたの最後のコメントは、私が「正解」を授与するものです-あなたがそれを答えとして分類した場合。:) boost::containerを見つけた私の問題は、そのドキュメントが新しい機能について明示的であることを期待していたことです-構築時にアロケーターオブジェクトを渡すなど...そしてboost::containerソースをチェックしていませんでした適切にコーディングします。Boost::container は、上記のすべての懸念事項に対して、非常にエレガントで直感的な (文書化されていない場合) ソリューションを提供すると確信しています。再度、感謝します！

4

1 に答える 1

1

警告: 完全にテストされていないコードです。そして、それがどの「イディオム」なのかはわかりませんが、以下の 1.5 ページのコードで問題が解決するはずです。

class GraphNodeAllocator
{
    struct CMemChunk
    {
        CMemChunk* pNext;
        BYTE* data()
        {
            return static_cast<BYTE*>( static_cast<void*>( this + 1 ) );
        }
    };

    CMemChunk* m_pChunk; // Most recently allocated a.k.a. current chunk
    BYTE* m_pFirstByte;  // First free data byte within the current chunk
    size_t m_freeBytes;  // Count of free bytes within the current chunk

    static const size_t cbChunkAlloc = 0x10000; // 65536 bytes per single allocation
    static const size_t cbChunkPayload = cbChunkAlloc - sizeof( CMemChunk );

    void* Allocate( size_t sz )
    {
        if( sz > cbChunkPayload )
            return NULL;

        if( m_freeBytes >= sz )
        {
            // Current chunk has the space
            m_freeBytes -= sz;
            void* res = m_pFirstByte;
            m_pFirstByte += sz;
            return res;
        }

        // Need a new chunk
        CMemChunk* pChunk = static_cast< CMemChunk* >( malloc( cbChunkAlloc ) );
        if( NULL == pChunk )
            return NULL;
        pChunk->pNext = m_pChunk;
        m_pChunk = pChunk;
        m_pFirstByte = m_pChunk->data();
        m_freeBytes = cbChunkPayload;
        return Allocate( sz );
    }

public:
    inline GraphNodeAllocator(): m_pChunk( NULL ), m_pFirstByte( NULL ), m_freeBytes( 0 ) { }

    inline ~GraphNodeAllocator()
    {
        while( NULL != m_pChunk )
        {
            CMemChunk* pNext;
            pNext = m_pChunk->pNext;
            free( m_pChunk );
            m_pChunk = pNext;
        }
    }

    template<typename E>
    inline E* newNode()
    {
        void* ptr = Allocate( sizeof( E ) );
        if( NULL == ptr ) return NULL;
        return ::new( ptr ) E();
    }
};

PS アイデアは Microsoft の CAtlPlex クラスから借用されています。これが、ほとんどの Microsoft のテンプレート コンテナー (リスト、マップ、ハッシュマップ) が STL の対応するものと比較して通常 2 倍高速である最大の理由です。std::vector、std::set、std::list などの使用をやめて、ATL と同等のものを使用するようになって以来、私はずっと幸せな人間になりました。

于 2013-02-19T05:08:13.123 に答える