Extreme memory usage for individual dynamic allocation

Question

Hi folks, here's a simple test I did on MSVC++ 2010 under windows 7:

// A struct with sizeof(s) == 4, e.g 4 bytes
struct s
{
    int x;
};

// Allocate 1 million structs
s* test1 = new s[1000000];

// Memory usage show that the increase in memory is roughly 4 bytes * 1000000 - As expected
// NOW! If I run this:
for (int i = 0; i < 1000000; i++)
    new s();

// The memory usage is disproportionately large. When divided by 1000000, indicates 64 bytes per s!!!

Is this a common knowledge or am I missing something? Before I always used to create objects on the fly when needed. For example new Triangle() for every triangle in a mesh, etc.

Is there indeed order of magnitude overhead for dynamic memory allocation of individual instances?

Cheers

EDIT:

Just compiled and ran same program at work on Windows XP using g++: Now the overhead is 16 bytes, not 64 as observed before! Very interesting.

Answer 1

Is that for a debug build? Because in a debug build msvc will allocate "guards" around objects to see if you overwrite past your object boundary.

Answer 2

Not necessarily, but the operating system will usually reserve memory on your behalf in whatever sized chunks it finds convenient; on your system, I'd guess it gives you multiples of 64 bytes per request.

There is an overhead associated with keeping track of the memory allocations, after all, and reserving very small amounts isn't worthwhile.

Answer 3

There is usually overhead with any single memory allocation. Now this is from my knowledge of malloc rather than new but I suspect it's the same.

A section of the memory arena, when carved out for an allocation of (say) 30 bytes, will typically have a header (e.g., 16 bytes, and all figures like that are examples only below, they may be different) and may be padded to a multiple of 16 bytes for easier arena management.

The header is usually important to allow the section to be re-integrated into the free memory pool when you're finished with it.

It contains information about the size of the block at a bare minimum and may have memory guards as well (to detect corruption of the arena).

So, when you allocate your one million structure array, you'll find that it uses an extra 16 bytes for the header (four million and sixteen bytes). When you try to allocate one million individual structures, each and every one of them will have that overhead.

I answered a related question here with more details. I suspect there will be more required header information for C++ since it will probably have to store the number of items over and above the section size (for proper destructor calls) but that's just supposition on my part. It doesn't affect the fact that accounting information of some sort is needed per allocated item.

If you really want to see what the space is being used for, you'll need to dig through the MSVC runtime source code.

Answer 4

You should check the malloc implementation. Probably this will clear things up.

Not sure though if MSVC++'s malloc can be viewed somewhere. If not, look at some other implementation, they are probably similar to some degree.

Don't expect the malloc implementation to be easy. It needs to search for some free space in the allocated virtual pages or allocate a new virtual page. And it must do this fast. As fast as possible. And it must be multithreading safe. Maybe your malloc implementation has some sort of bitvector where it safes which 64 bit chunks are free in some page and it just takes the next free chunk.