C++ allocates abnormally large amout memory for variables

Question

I recently got to know an integer takes 4 bytes from the memory.

First ran this code, and measured the memory usage:

int main()
{
   int *pointer;
}

• It took 144KB.

Then I modified the code to allocate 1000 integer variables.

int main()
{
   int *pointer;

   for (int n=0; n < 1000; n++)
     { 
       pointer = new int ; 
     }
}

• Then it took (168-144=) 24KB
  but 1000 integers are suppose to occupy (4bytes x 1000=) 3.9KB.

Then I decided to make 262,144 integer variables which should consume 1MB of memory.

int main()
{
   int *pointer;

   for (int n=0; n < 262144; n++)
     { 
       pointer = new int ; 
     }
}

Surprisingly, now it takes 8MB

Memory usage, exponentially grows respective to the number of integers.
Why is this happening?

I'm on Kubuntu 13.04 (amd64)
Please give me a little explanation. Thanks!

NOTE: sizeof(integer) returns 4

Answer 1

Memory for individually allocated dynamic objects is not required to be contiguous. In fact, due to the alignment requirements for new char[N] (namely to be aligned at alignof(std::maxalign_t), which is usually 16), the standard memory allocator might just never bother to return anything but 16-byte aligned memory. So each int allocation actually consumes (at least) 16 bytes. (And further memory may be required by the allocator for internal bookkeeping.)

The moral is of course that you should be using std::vector<int>(1000000) to get a sensible handle on one million dynamic integers.

Answer 2

Non-optimized allocations in common allocators go with some overhead. You can think of two "blocks": An INFO and a STORAGE block. The Info block will most likely be right in front of your STORAGE block.

So if you allocate you'll have something like that in your memory:

        Memory that is actually accessible
        vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
--------------------------------------------
|  INFO |  STORAGE                         |
--------------------------------------------
^^^^^^^^^
Some informations on the size of the "STORAGE" chunk etc.

Additionally the block will be aligned along a certain granularity (somewhat like 16 bytes in case of int).

I'll write about how this looks like on MSVC12, since I can test on that in the moment.

Let's have a look at our memory. The arrows indicate 16 byte boundaries.

If you allocate a single 4 byte integer, you'll get 4 bytes of memory at a certain 16 bytes boundary (the orange square after the second boundary). The 16 bytes prepending this block (the blue ones) are occupied to store additional information. (I'll skip things like endianess etc. here but keep in mind that this can affect this sort of layout.) If you read the first four bytes of this 16byte block in front of your allocated memory you'll find the number of allocated bytes.

If you now allocate a second 4 byte integer (green box), it's position will be at least 2x the 16 byte boundary away since the INFO block (yellow/red) must fit in front of it which is not the case at the rightnext boundary. The red block is again the one that contains the number of bytes.

As you can easily see: If the green block would have been 16 bytes earlier, the red and the orange block would overlap - impossible.

You can check that for yourself. I am using MSVC 2012 and this worked for me:

char * mem = new char[4096];
cout << "Number of allocated bytes for mem is: " << *(unsigned int*)(mem-16) << endl;
delete [] mem;


double * dmem = new double[4096];
cout << "Number of allocated bytes for dmem is: " << *(unsigned int*)(((char*)dmem)-16) << endl;
delete [] dmem;

prints

Number of allocated bytes for mem is: 4096
Number of allocated bytes for dmem is: 32768

And that is perfectly correct. Therefore a memory allocation using new has in case of MSVC12 an additional "INFO" block which is at least 16 bytes in size.