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.

Answer 2

STL containers are implemented using naked pointers.

You can specify a custom allocator when you instantiate them (so they they initialize their pointers using your allocator), but (because the allocated values are stored in naked pointers) you don't know where those pointers are, and therefore you can't change them later.

Instead, you might consider implementing a subset of the STL yourself: your versions of the STL containers could then be implemented with managed pointers.

Answer 3

An alternative technique which is fairly well known is the buddy system. You should take a look at that for additional inspiration.

Answer 4

If this is for console game programming it's a lot easier to forbid un-scoped dynamic memory allocations at runtime. And at startup time, but that's a bit difficult to achieve.

Answer 5

My take on this, is that if have to be afraid of fragmentation, that means you are juggling around with data pieces which are a huge fraction of your memory, and by this virtue alone, you cannot have many of them. Do you already know what these will be? Maybe it would be better to step down a level and make more specific decisions, thus impeding less on the other code and the general performance of your application?

A list is an exceptionally bad example to put into a defragmenting memory manager, because it's a bunch of tiny pieces, as are most other STL data structures. If you do this, it will have all kinds of obvious bad implications - including the performance of your defragmenter going down, also the indirection cost etc. The only structures where it makes sense IMO are contigious ones - array, deque, main chunk of hashtable, those things, and only beyond a certain size, and only after they are not gonna be resized any longer. These kind of things call, again, for specific solutions, instead of generic ones.

Comment back on how it all turns out.