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

(Edit: sorry, misread your question; previous answer removed.)

You can use any memory pool for your objects. Usually you group together same (or similar) sized objects in the same pool. Since you usually have to call a special delete function on the pool I suggest you use a shared_ptr with a custom deleter. You can then use this shared_ptr with any standard container you like.

Edit: It seems like an example is needed. Warning: this is totally untested and from the top of my head. Don't expect it to compile.

#include <boost/pool.hpp>
#include <memory>

class A;
class B; // B inherits from A

int main() {
  // could be global
  boost::object_pool<A> a_pool;
  boost::object_pool<B> b_pool;

  std::vector<std::shared_ptr<A>> v;

  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));
  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));
  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));

  v[2] = std::shared_ptr<B>(b_pool.construct(), [&](B*p) { b_pool.free(p); });

  return 0;
}

This will work even is B is much larger than A. It also does not rely on the automatic freeing of the pool which is IMHO dangerous. The memory layout is not tight because the pool will always overallocate, but it will have no fragmentation and this is what you want if I understood your question.

Answer 2

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

Answer 3

The fragmentation occurs not because of the use of the boost container. It will happen when you frequently allocate and deallocate objects of different sizes with new and delete. The ptr_array simply stores the pointers to these allocated objects and will probably not notably contribute to the fragmentation.

If you want to counter memory fragmentation, you can overload your objects operator new and implement your own memory management system. I suggest you read into the subjects of memory pools and free lists.