C++ new memory allocation fragmentation

Question

I was trying to look at the behavior of the new allocator and why it doesn't place data contiguously.

My code:

struct ci {
    char c;
    int i;
}

template <typename T>
void memTest()
{
    T * pLast = new T();
    for(int i = 0; i < 20; ++i) {
         T * pNew = new T();
         cout << (pNew - pLast) << " ";
         pLast = pNew;
    }
}

So I ran this with char, int, ci. Most allocations were a fixed length from the last, sometimes there were odd jumps from one available block to another.

sizeof(char) : 1
Average Jump: 64 bytes

sizeof(int): 4
Average Jump: 16

sizeof(ci): 8 (int has to be placed on a 4 byte align)
Average Jump: 9

Can anyone explain why the allocator is fragmenting memory like this? Also why is the jump for char so much larger then ints and a structure that contains both an int and char.

Answer 1

There are two issues:

• most allocators store some additional data prior to the start of the block (typically block size and a couple of pointers)

• there are usually alignment requirements, e.g. Linux typically allocates to at least an 8 byte boundary, OS X allocates to at least a 16 byte boundary

So you'll nearly always get some kind of gap between successive allocations.

Of course you should never rely on any specific behaviour for something like this, where the implementation is free to do as it pleases.

Answer 2

Your code contains a bug, to know distance of pointers cast them to (char *), otherwise the deltas are in sizeof(T).

Answer 3

In general, you cannot depend on particular memory placement. The memory allocator's internal bookkeeping data and alignment requirements can both affect the placement of blocks. There is no requirement for blocks to be allocated contiguously.

Further, some systems will give you even "stranger" behavior. Many modern Linux systems have heap randomization enabled, where newly-allocated virtual memory pages are placed at random addresses to make certain types of security vulnerability exploits more difficult. With virtual memory, disparate allocated block addresses do not necessarily mean that the physical memory is fragmented, as there is no requirement for the virtual address space to be dense.

Answer 4

This isn't fragmentation, it's just rounding up the size of your allocation to a round block size.

In general programming you should not pay attention to the pattern of memory addresses returned by general purpose allocators like new. When you do care about allocation behaviour you should always use a special purpose allocator (boost::pool, something you write yourself, etc.)

The exception is if you are studying allocators, in which case you could do worse than pick up your copy of K&R for a simple allocator which might help you understand how new gets its memory.

Answer 5

As others have already said, basically you have no control over how the memory management system works. If you allocate many singular objects, that might result in fragmentation, and there's nothing you can do against this.

However, if you need your objects to be in contiguous order in memory, you can write your own memory allocator that operates on top of malloc() or new. One way to control fragmentation is to allocate a larger block of memory and to then construct your actual singular objects inside this block using placement new (link to the C++ FAQ Lite).

(This works of course because a call to malloc() or new T[] is guaranteed to return a contiguous block of memory. One singular allocated object cannot be fragmented; fragmentation can only results with several allocated objects.)

Answer 6

For small allocation, boost has a very simple allocator I've used called boost::simple_segregated_storage

It creates a copy of slists of free and used blocks, all the same size. As long as you only allocate to its set block size, you get no external fragmentation (though you can get some internal fragmentation if your block size is bigger than the requested size.) It also runs O(1) if you use it in this manner. Great for small allocation the likes of which are common with template programming.