Defragmenting C++ Heap Allocator & STL

Question

I'm looking to write a self defragmenting memory manager whereby a simple incrementing heap allocator is used in combination with a simple compacting defragmenter.

The rough scheme would be to allocate blocks starting at the lowest memory address going upwards and keeping book-keeping information starting at the highest memory address working downwards.

The memory manager would pass back smart pointers - boost's intrusive_ptr's seems the most obvious to the book-keeping structs that would then themselves point to the actual memory block thus giving a level of indirection so that the blocks can be easily moved around.

The defragmenter would compact down the heap starting at 'generation' bookmarks to speed up the process and only defragmenting a fixed amount of memory at a time. Raw pointers to the blocks themselves would be valid until the next defrag pass and so could be passed around freely until such a time improving performance.

The specific application for this is console game programming and so at the beginning or end of each frame a defrag pass could be done relatively safely.

So my question is has anybody used this kind of allocation scheme in combination with STL would it just completely blow STL apart as I suspect. I can see std::list< intrusive_ptr > working at the intrusive_ptr level but what about the allocation of the stl list nodes themselves is there anyway to override the next/prev pointers to be intrusive_ptr's themselves or am I just going to have to have a standard heap allocator along side this more dynamic one.

Answer 1

If you're going to be moving objects around in memory then you can't do this fully generically. You will only be able to do this with objects that know that they might be moved. You also will need a locking mechanism. When a function is being called on an object, then it can't be moved.

The reason is that the whole C++ model relies on objects sitting at fixed points in memory, so if a thread was calling a method on an object, this thread was paused and the object moved, disaster would strike when the thread resumed.

Any object which held a raw memory pointer to another object that might be moved (including a sub-object of itself) would not work.

Such a memory management scheme may work but you have to be very careful. You need to be strict about implementing handles, and the handle->pointer locking semantics.

For STL containers, you can customize the allocator, but it still needs to return fixed raw memory pointers. You can't return an address that might move. For this reason, if you're using STL containers, they must be containers of handles, and the nodes themselves will be ordinary dynamically allocated memory. You may find that you too much in overhead in the handle indirection and still have problems in the fragmentation of the handle collections than you gain by using STL.

Using containers that understand your handles directly might be the only way forward, and even then there may still be a lot of overhead compared to a C++ application that uses traditional objects fixed in memory.