new and delete[] are worse than malloc and free? (c++ / VS2012)

Question

OK, so, I wrote some code to check, how much memory is available at runtime. A whole (minimal) cpp file is below.

NOTE: The code is not perfect and not best practice, but I hope that you can focus on the memory management rather than the code.

What it does (part I):

• (1) Allocate as much memory as possible in one block. Clear that memory
• (2) Allocate as many medium sized blocks (16MB) as possible. Clear that memory.

--> This works fine

What it does (part II):

• (1) Allocate as much memory as possible in one block. Clear that memory
• (2) Allocate as many tiny blocks (16kb) as possible. Clear that memory.

--> This behaves weird!

The problem is: If I repeat that, I can only allocate 522kb for the secons run onward ---> ?

It does not happen, if the allocated blocks have e.g. 16MB of size.

Do you have any ideas, why this happens?

// AvailableMemoryTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <vector>
#include <list>
#include <limits.h>
#include <iostream>


int _tmain(int argc, _TCHAR* argv[])
{


    auto determineMaxAvailableMemoryBlock = []( void ) -> int
    {
        int nBytes = std::numeric_limits< int >::max();

        while ( true )
        {
            try
            {
                std::vector< char >vec( nBytes );
                break;
            }
            catch ( std::exception& ex )
            {
                nBytes = static_cast< int >( nBytes * 0.99 );
            }
        }
        return nBytes;
    };

    auto determineMaxAvailableMemoryFragmented = []( int nBlockSize ) -> int
    {

        int nBytes = 0;

        std::list< std::vector< char > > listBlocks;

        while ( true )
        {
            try
            {
                listBlocks.push_back( std::vector< char >( nBlockSize ) );
                nBytes += nBlockSize;
            }
            catch ( std::exception& ex )
            {
                break;
            }
        }
        return nBytes;
    };


    std::cout << "Test with large memory blocks (16MB):\n";
    for ( int k = 0; k < 5; k++ )
    {
        std::cout << "run #" << k << "   max  mem block          = " << determineMaxAvailableMemoryBlock() / 1024.0 / 1024.0 << "MB\n";
        std::cout << "run #" << k << "   frag mem blocks of 16MB = " << determineMaxAvailableMemoryFragmented( 16*1024*1024 ) / 1024.0 / 1024.0 << "MB\n";
        std::cout << "\n";
    } // for_k
    

    std::cout << "Test with small memory blocks (16k):\n";
    for ( int k = 0; k < 5; k++ )
    {
        std::cout << "run #" << k << "   max  mem block          = " << determineMaxAvailableMemoryBlock() / 1024.0 / 1024.0 << "MB\n";
        std::cout << "run #" << k << "   frag mem blocks of 16k  = " << determineMaxAvailableMemoryFragmented( 16*1024 ) / 1024.0 / 1024.0 << "MB\n";
        std::cout << "\n";
    } // for_k

    std::cin.get();


    return 0;
}

OUTPUT with large memory blocks (this works fine)

Test with large memory blocks (16MB):
run #0   max  mem block          = 1023.67MB     OK
run #0   frag mem blocks of 16MB = 1952MB        OK

run #1   max  mem block          = 1023.67MB     OK
run #1   frag mem blocks of 16MB = 1952MB        OK

run #2   max  mem block          = 1023.67MB     OK
run #2   frag mem blocks of 16MB = 1952MB        OK

run #3   max  mem block          = 1023.67MB     OK
run #3   frag mem blocks of 16MB = 1952MB        OK

run #4   max  mem block          = 1023.67MB     OK
run #4   frag mem blocks of 16MB = 1952MB        OK

OUTPUT with small memory blocks (memory allocation is weird from the second run onwards)

Test with small memory blocks (16k):
run #0   max  mem block          = 1023.67MB     OK
run #0   frag mem blocks of 16k  = 1991.06MB     OK

run #1   max  mem block          = 0.493021MB    ???
run #1   frag mem blocks of 16k  = 1991.34MB     OK

run #2   max  mem block          = 0.493021MB    ???
run #2   frag mem blocks of 16k  = 1991.33MB     OK

run #3   max  mem block          = 0.493021MB    ???
run #3   frag mem blocks of 16k  = 1991.33MB     OK

run #4   max  mem block          = 0.493021MB    ???
run #4   frag mem blocks of 16k  = 1991.33MB     OK

UPDATE:

This happels as well with new and delete[] instead of STL's internal memory allocation.

UPDATE:

It works for 64 bit (I limited the memory that both functions are allowed to allocate to 12GB). Really weird. Here is an image of that version's RAM usage:

UPDATE: It works with malloc and free, but not with new and delete[] (or STL as described above)

Answer 1

As I mentioned in the comment above, this is most likely a heap fragmentation issue. The heap will maintain lists of different sized chunks to satisfy different memory requests. Larger memory chunks are broken into smaller chunks for smaller memory requests to avoid wasting the difference between the chunk size and request size, which reduces the number of larger chunks. So, when a larger chunk is requested, the heap may not have enough large chunks to satisfy the request.

Fragmentation is a major issue with heap implementations since it effectively reduces usable memory. However, some heap implementations are able to coalesce smaller chunks back into larger chunks, and are better able to satisfy large requests even after a number of smaller requests.

I ran your above code, very slightly modified, using glibc's malloc (ptmalloc) and I got the following results...

Test with large memory blocks (16MB):
run #0   max  mem block          = 2048MB
run #0   frag mem blocks of 16MB = 2032MB

run #1   max  mem block          = 2048MB
run #1   frag mem blocks of 16MB = 2032MB

run #2   max  mem block          = 2048MB
run #2   frag mem blocks of 16MB = 2032MB

run #3   max  mem block          = 2048MB
run #3   frag mem blocks of 16MB = 2032MB

run #4   max  mem block          = 2048MB
run #4   frag mem blocks of 16MB = 2032MB

Test with small memory blocks (16k):
run #0   max  mem block          = 2048MB
run #0   frag mem blocks of 16k  = 2047.98MB

run #1   max  mem block          = 2048MB
run #1   frag mem blocks of 16k  = 2047.98MB

run #2   max  mem block          = 2048MB
run #2   frag mem blocks of 16k  = 2047.98MB

run #3   max  mem block          = 2048MB
run #3   frag mem blocks of 16k  = 2047.98MB

run #4   max  mem block          = 2048MB
run #4   frag mem blocks of 16k  = 2047.98MB

So, ptmalloc at least seems to handle fragmentation well for this particular scenario.