CODEWITHSUNDEEP
c++new-operatordynamic-memory-allocation
Jason T.
Jason T.

Reputation: 382

C++ new memory allocation fragmentation

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.

Upvotes: 4

Views: 1411

Answers (5)

Paul R
Paul R

Reputation: 212969

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 - modern operating systems typically allocate to at least an 8 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.

Upvotes: 10

Michael Dorgan
Michael Dorgan

Reputation: 12515

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.

Upvotes: 0

Matt Curtis
Matt Curtis

Reputation: 23624

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.

Upvotes: 3

Michael Ekstrand
Michael Ekstrand

Reputation: 29090

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.

Upvotes: 2

Drakosha
Drakosha

Reputation: 12155

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

Upvotes: 6

Related Questions