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.

Brunner

I don't understand. You have small smart_ptr handle that allows you to move the underlying block. But what happens if the underlying block has pointers? How do you force those ptrs to be smart_ptrs? – Sunflower

@jmucchiello: The allocator purely returns blocks of memory its up to the user to make sure the if your creating a class with that peice of memory that it uses smart_ptrs for any pointers it may contain. This is perfectly fine in my case as I have control over classes and use intrusive_ptrs to 'own' other objects anyway. – Brunner

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.

Worship

"You will only be able to do this with objects that know that they might be moved." -- And/or with objects which contain objects which know they might be moved: i.e. you could have a "managed pointer" class, and you'd OK with classes which use/contain instances the "managed pointer" class instead of using naked pointers. – Foucquet

He doesn't need to lock because he'll only be defragging 'between frames', i.e. while the objects which contain managed pointers aren't being run at all. – Foucquet

Yes fortunately we've got quite a tight control over how the application behaves and how programmers use the game SDK and so we can enforce certain restrictions within reason i.e you can pass around raw pointers in any one update of the application but that they will be invalid in the next frame; if you want a pointer to anything that is to be kept over many frames you have to use our custom intrusive_ptr type. We do this type of thing anyway with standard intrusive_ptr's. – Brunner

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.

Foucquet

For this I'd recommend having a look into Boost.Interprocess, where an offset_ptr is used for shared memory regions. – Kataway

I had suspected a custom STL implementation would be necessary which is a real shame. I suppose a properly done STL implementation such as EASTL wouldn't be so bad but would take a fair amount of time to write and test. Do you or anybody else know of someone having written such an STL implementation? I seem to remember Palm having a memory allocation scheme like this I wonder whether they've done anything related... – Brunner

I usually use only a small subset of the STL, i.e. (apart from I/O) I use std::string and one or two container types (and only a subset of the functionality of those types); so a custom STL implementation wouldn't be that hard for my purposes. – Foucquet

No I don't know of a publicly-available EASTL. – Foucquet

"I seem to remember Palm having a memory allocation scheme like this I wonder whether they've done anything related" -- Now I'm wondering (out of idle curiosity) whether this could be handled in hardware: 1) Your allocator returns pointers to invalid memory 2) Naive code (including any standard STL implementation) tries to use those pointer values 3) There's a hardware trap on the invalid pointer access, and a ring 0 trap handler of yours then does some kind of fixup to let the application access the corresponding non-invalid memory. – Foucquet

This does sound interesting! Good thinking, I'll have to look into the performance implications of this relating to latencies of data storage/segment interrupts and how debuggable this would be if things went wrong. It would seem the target hardware would suspend both hardware threads when an exception occured so that could be plus (from a locking perspective) and negative (from a performance perspective). I'm not so sure what the security issues involved in this also would be with respect to the hypervisor. Something similar is being done with ID software's tech 5 I believe. – Brunner

I have severe doubts that EASTL wants such memory management. :) If you want to hack your own STL, i may suggest starting off uSTL, it's simple, compact and readable. Does it work? Well, apparently, i heard it was used on Project:Snowblind by Crystal Dynamics on PS2. Shaved 'em more than a meg on template instantiations. However, as i mention elsewhere, i don't think it's the right direction. – Mosquito

I also have severe doubts about Palm having such high-end C++ abuse stuff. I don't know Palm, i only know Epoc->Symbian, and i know they haven't, although they were good at maxing out the systems without crashing. – Mosquito

Answer 3

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

Ecker

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.

Evin

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.

Mosquito