Preventing Memory Fragmentation in Polymorphic Container

Question

This question requires some explaning, so thumbs up if you don't skip the example :)

I recently read a book describing memory fragmentation (on the heap) in some detail and it got me thinking about my own projects. For example, when using a ptr_container (from Boost) in the following way

ptr_array<A> arr;       // 
arr.push_back(new A()); // a1.
arr.push_back(new A()); // a2.
arr.push_back(new A()); // a3.
....

it will quite fast lead to some memory fragmentation when replacing elements. For the sake of argument, lets say that the actual container can hold all pointers we give to it. The heap will look something like:

[arr_array][a1][a2][a3]...[aN]

When we start to replace pointers with a subtype (that has a larger size) this situation changes, lets say we replace all objects referenced by odd pointers (a1, a3, ...) to a larger type, then it'll look like:

[arr_array][xx][a2][xx][a4]...[aN][b1][b3]...[bN]

where [xx] denotes unused space and b1...bN are the new objects.

So what I'd like is a container that stores the objects (like in STL-containers) but supports polymorphic storage. I do know how to implement this kind of container but I prefer to use "expert" libraries (Boost, STL, ...). To sum it up, my question:

Is there a container that supports (dynamically allocated) polymorphic objects saved in a continuous sequence of memory?

For example, the memory layout could look like this:

[arr_array] = [ptr_lookup_table][storage]
            = [p1, p2, ..., pn][b1, a2, b3, ..., aN]

Thank you for your answers / comments!

Answer 1

Memory fragmentation requires foreknowledge about memory allocation, so I'll need to set some concepts first.

Memory Allocation

When you call operator new (which by default will often call malloc behind the scenes), you do not directly request memory from the OS, instead what happens (generally) is that:

• you call malloc for 76 bytes, it looks if such is available:
  • if it is not, it request a page (usually 4KB) from the OS, and prepare it
• it then serves you the 76 bytes you asked for

Memory fragmentation may happen at two levels:

• You may exhaust your virtual address space (not so easy with 64bits platforms)
• You may have nearly empty pages that cannot be reclaimed and yet cannot serve the requests you make

Generally, since malloc should call pages 4KB at a time (unless you ask for a bigger chunk in which case it will choose a bigger multiple of 4KB), you should never exhaust your address space. It happened on 32bits machine (limited to 4GB) for unusually large allocations though.

On the other hand, if your implementation of malloc is too naive, you may end up with fragmented memory blocks and thus have a much higher memory footprint than what you really use. This is usually what the term memory fragmentation refers to nowadays.

Typical Strategy

When I say naive I refer to, for example, your idea of allocating everything continuously. This is a bad idea. This is typically not what happens.

Instead, the good malloc implementations today use pools.

Typically, they will have pools per size:

• 1 byte
• 2 bytes
• 4 bytes
• ...
• 512 bytes
• ...
• 4KB and more are handled specially (directly)

And when you make a request, they will find the pool with the minimum size that can satisfy it, and this pool will serve you.

Because in a pool all requests are served with the same size, there is no fragmentation within the pool as a free cell can be used for any incoming request.

So, fragmentation ?

Nowadays, you should not observe fragmentation per se.

However you can still observe memory holes. Suppose that a pool is handling objects of 9 to 16 bytes and you allocate say 4,000,000 of them. This requires at least 16,000 pages of 4KB. Now suppose that you deallocate all but 16,000 of them, but deviously so that one object still lives for each page. The pages cannot be reclaimed by the OS, as you still use them, however since you only use 16 bytes out of 4KB, the space is quite wasted (for now).

Some languages with Garbage Collection may handle those cases with compaction, however in C++, relocating an object in memory cannot be done because user has direct control over object addresses.

Magic container

I do not know of any such beast. I do not see why it would be useful either.

TL;DR

Don't worry about fragmentation.

Note: "experts" may want to write their own pool allocation mechanism, I would like to remind them not to forget about alignment