4

场景：我有一个类 G，它包含（通常）数千个从类 N 派生的类型的对象。所有这些对象都有一个明确定义的生命周期。首先，构造一个对象 G，然后添加 N 个派生的对象，然后用 G 完成一些计算，这不会改变 N 个派生的对象，然后 G 超出范围，组成部分N 派生对象。N 派生对象又包含指向添加到同一 G 对象的其他 N 派生对象的指针或指针的标准容器。G 表示具有异构节点的图。

我的目标是：

  1. 最小化分配每个 N 派生对象的成本。
  2. 最大化属于同一 G 对象的 N 派生对象的参考局部性。
  3. 通过为所有 N 派生对象释放单个块来最小化释放成本。
  4. 为了能够定义多个具有独立生命周期的独立 G 对象 - 可能在没有线程同步的情况下在并发线程中管理这些独立 G 对象。

对我来说，这似乎需要多个池分配器 - 就像使用堆栈一样分配......并且只有在池被销毁时才释放池分配。

我查看了提升池分配器——但没有找到为不同大小的异构对象建立多个独立池的方法。

接下来，我定义了自己的自定义分配器——但很快发现，虽然我可以将它作为模板参数传递给标准容器，如 std::vector、std::set、std::list 等。- 允许我指定池分配器的类型...我来不及，因为我不能轻易指定两个独立的容器应该共享相同的（非全局）分配器池。我认识到一种解决方案是使用静态/全局并将自己限制为仅在一个线程中构造 G 对象。我还考虑过使用 thread-local-storage 将自定义分配器与相关池相关联......但认为这很难看。这两种方法都没有直接支持在同一线程中交叉构造两个独立的 G 对象。

我是否忽略了 Boost 中问题的现有解决方案？

有没有比使用静态/全局或线程本地存储更好的习惯来实现我的目标？

更新

我已经阅读了 Stroustrup 的常见问题和 boost::container 文档。起初，Boost::container 给了我很大的鼓舞——但很失望没有看到一个具体的例子来说明如何在这些容器中使用有状态分配器。我已经能够简化我原来的问题来问......给定一个结构：

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

如何确保对于 DataUnit 的每个实例都有一个单独的池，从中分配 m 和 l 的内部成分？如果我将自定义分配器传递给映射和列表，m 和 l 将获得此容器的独立实例。我最初认为我可能能够使用 get_allocator() 来用我的 aerena/pool 初始化分配器......但遗憾的是，在 vector<...> 的默认构造函数返回之前调用了 allocate() ......所以我不能那样做。

更奇怪的是，我发现，已经涉足了 boost::container 一段时间...... vanilla 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 这个想法是从微软的 CAtlPlex 类中借用的，这也是为什么大多数微软的模板容器（列表、地图、哈希图）通常比 STL 对应物快 2 倍的第一个原因。自从我放弃使用 std::vector、std::set、std::list 等支持 ATL 的等价物后，我变得更快乐了。

于 2013-02-19T05:08:13.123 回答