How to explicitly manage multiple pool allocators for heterogeneous types (and sizes)?
Scenario: I have a class G that consists (usually) of thousands of objects of type derived from class N. All of these objects have a well-defined lifecycle. First, the G object is built, then the N-derived objects are added, then some computation is done with G that does not change the N-derived objects, then G goes out of scope, and with it the constituent N-derived objects. Objects derived from an N-object, in turn, contain pointers or standard containers of pointers to other N-derived objects added to the same object G. G is a graph with heterogeneous nodes.
My goals:
- Minimize the cost of allocating each N-derived object.
- To maximize locality of references for N-derived objects belonging to the same G.
- To minimize the cost of freeing by freeing one block for all N-derived objects.
- Be able to define multiple independent G objects with independent lifecycles - potentially manage these independent G objects in parallel threads without thread synchronization.
To me, this seemed to require multiple pool allocators that allocate as if they were using the stack ... and only free the allocation pool when the pool is destroyed.
I looked at the pool pool generators - but couldn't find a way to set multiple independent pools for heterogeneous objects of different sizes.
I then defined my own allocator, but quickly found that although I can pass it as a template argument for standard containers like std :: vector, std :: set, std :: list et al. - Let me specify the type of allocator pool ... I come in - out because I can't easily specify that two other independent containers should share the same (non-global) allocator pool. I will admit that one solution would be to use static / global and be limited to only building G objects in a single thread. I also thought about using streaming local storage to associate my own allocator with the appropriate pool ... but found it ugly. Neither approach directly supports a mixed construction of two independent G objects in the same stream.
Am I missing out on an existing solution to my problem in Boost?
Is there a better idiom than using static / global or streaming local storage to achieve my goals?
Update
I've read the Stroustrup faq file - and the boost :: container documentation. I was very excited about Boost :: container at first - but disappointed that I didn't see a concrete example of how to use stateful controllers with these containers. I was able to simplify my original question to ask ... given the structure:
struct DataUnit { map<int,string> m; list<int> l; }
How can I ensure that there is one pool for each DataUnit instance from which the internal m and l are allocated? If I pass in a custom allocator for display and list, m and l get independent instances of that container. I originally thought I could use get_allocator () to initialize the allocator with my antenna / pool ... but unfortunately allocate () is called before the vector <...> default constructor returns, so I can't do it.
Even weirder, I found that I was pushing boost :: container for a while on the fact that vanilla std containers have get_allocator () (on MSVC 2010 and 2012 and g ++ 4.6.3), which suggests that the library standard in those contexts has similar stateful support for boost :: container.
Unfortunately, I still don't have a viable solution to my original problem (although I can now express it more eloquently).
Update 2
Thanks pmr, your last comment is that I would get a "correct answer" - if you classified it as an answer. :) My problem getting boost :: container was that I expected its documentation will be explicit about any new features like passing allocator objects during build ... and I haven't checked the source of boost :: container correctly. Boost :: container, I am now convinced, offers a very elegant and intuitive (if poorly documented) solution to all my problems above. Thanks again!
source to share
Warning: completely untested code. And I don't know what the "idiom" is - but 1.5 pages of code below should solve your problem.
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 The idea is borrowed from the Microsoft CAtlPlex class, which is the number one reason why most Microsoft template containers (lists, maps, hash maps) are usually 2 times faster than their STL counterparts. I have become a much happier person since I left using std :: vector, std :: set, std :: list, etc. in favor of ATL equivalents.
source to share