Why is memory not reusable after allocating/deallocating a number of small objects?

Question

While investigating a memory link in one of our projects, I've run into a strange issue. Somehow, the memory allocated for objects (vector of shared_ptr to object, see below) is not fully reclaimed when the parent container goes out of scope and can't be used except for small objects.

The minimal example: when the program starts, I can allocate a single continuous block of 1.5Gb without problem. After I use the memory somewhat (by creating and destructing an number of small objects), I can no longer do big block allocation.

Test program:

#include <iostream>
#include <memory>
#include <vector>
using namespace std;

class BigClass
{
private:
    double a[10000];
};

void TestMemory() {
    cout<< "Performing TestMemory"<<endl;
    vector<shared_ptr<BigClass>> list;
    for (int i = 0; i<10000; i++) {
        shared_ptr<BigClass> p(new BigClass());
        list.push_back(p);
    };
};

void TestBigBlock() {
    cout<< "Performing TestBigBlock"<<endl;
    char* bigBlock = new char [1024*1024*1536];
    delete[] bigBlock;
}

int main() {
    TestBigBlock();
    TestMemory();
    TestBigBlock();
}

Problem also repeats if using plain pointers with new/delete or malloc/free in cycle, instead of shared_ptr.

The culprit seems to be that after TestMemory(), the application's virtual memory stays at 827125760 (regardless of number of times I call it). As a consequence, there's no free VM regrion big enough to hold 1.5 GB. But I'm not sure why - since I'm definitely freeing the memory I used. Is it some "performance optimization" CRT does to minimize OS calls?

Environment is Windows 7 x64 + VS2012 + 32-bit app without LAA

Answer 1

Sorry for posting yet another answer since I am unable to comment; I believe many of the others are quite close to the answer really :-)

Anyway, the culprit is most likely address space fragmentation. I gather you are using Visual C++ on Windows.

The C / C++ runtime memory allocator (invoked by malloc or new) uses the Windows heap to allocate memory. The Windows heap manager has an optimization in which it will hold on to blocks under a certain size limit, in order to be able to reuse them if the application requests a block of similar size later. For larger blocks (I can't remember the exact value, but I guess it's around a megabyte) it will use VirtualAlloc outright.

Other long-running 32-bit applications with a pattern of many small allocations have this problem too; the one that made me aware of the issue is MATLAB - I was using the 'cell array' feature to basically allocate millions of 300-400 byte blocks, causing exactly this issue of address space fragmentation even after freeing them.

A workaround is to use the Windows heap functions (HeapCreate() etc.) to create a private heap, allocate your memory through that (passing a custom C++ allocator to your container classes as needed), and then destroy that heap when you want the memory back - This also has the happy side-effect of being very fast vs delete()ing a zillion blocks in a loop..

Re. "what is remaining in memory" to cause the issue in the first place: Nothing is remaining 'in memory' per se, it's more a case of the freed blocks being marked as free but not coalesced. The heap manager has a table/map of the address space, and it won't allow you to allocate anything which would force it to consolidate the free space into one contiguous block (presumably a performance heuristic).

Answer 2

There is absolutely no memory leak in your C++ program. The real culprit is memory fragmentation.

Just to be sure(regarding memory leak point), I ran this program on Valgrind, and it did not give any memory leak information in the report.

//Valgrind Report
mantosh@mantosh4u:~/practice$ valgrind ./basic
==3227== HEAP SUMMARY:
==3227==     in use at exit: 0 bytes in 0 blocks
==3227==   total heap usage: 20,017 allocs, 20,017 frees, 4,021,989,744 bytes allocated
==3227== 
==3227== All heap blocks were freed -- no leaks are possible

Please find my response to your query/doubt asked in original question.

The culprit seems to be that after TestMemory(), the application's virtual memory stays at 827125760 (regardless of number of times I call it). Yes, real culprit is hidden fragmentation done during the TestMemory() function.Just to understand the fragmentation, I have taken the snippet from wikipedia

" when free memory is separated into small blocks and is interspersed by allocated memory. It is a weakness of certain storage allocation algorithms, when they fail to order memory used by programs efficiently. The result is that, although free storage is available, it is effectively unusable because it is divided into pieces that are too small individually to satisfy the demands of the application. For example, consider a situation wherein a program allocates 3 continuous blocks of memory and then frees the middle block. The memory allocator can use this free block of memory for future allocations. However, it cannot use this block if the memory to be allocated is larger in size than this free block."

The above explains paragraph explains very nicely about memory fragmentation.Some allocation patterns(such as frequent allocation and deal location) would lead to memory fragmentation,but its end impact(.i.e. memory allocation 1.5GBgets failed) would greatly vary on different system as different OS/heap manager has different strategy and implementation. As an example, your program ran perfectly fine on my machine(Linux) however you have encountered the memory allocation failure.

Regarding your observation on VM size remains constant: VM size seen in task manager is not directly proportional to our memory allocation calls. It mainly depends on the how much bytes is in committed state. When you allocate some dynamic memory(using new/malloc) and you do not write/initialize anything in those memory regions, it would not go committed state and hence VM size would not get impacted due to this. VM size depends on many other factors and bit complicated so we should not rely completely on this while understanding about dynamic memory allocation of our program.

As a consequence, there's no free VM regrion big enough to hold 1.5 GB.

Yes, due to fragmentation, there is no contiguous 1.5GB memory. It should be noted that total remaining(free) memory would be more than 1.5GB but not in fragmented state. Hence there is not big contiguous memory.

But I'm not sure why - since I'm definitely freeing the memory I used. Is it some "performance optimization" CRT does to minimize OS calls?

I have explained about why it may happen even though you have freed all your memory. Now in order to fulfil user program request, OS will call to its virtual memory manager and try to allocate the memory which would be used by heap memory manager. But grabbing the additional memory does depend on many other complex factor which is not very easy to understand.

Possible Resolution of Memory Fragmentation

We should try to reuse the memory allocation rather than frequent memory allocation/free. There could be some patterns(like a particular request size allocation in particular order) which may lead overall memory into fragmented state. There could be substantial design change in your program in order to improve memory fragmentation. This is complex topic and require internal understanding of memory manager to understand the complete root cause of such things.

However there are tools exists on Windows based system which I am not much aware. But I found one excellent SO post regarding the which tool(on windows) can be useful to understand and check the fragmentation status of your program by yourself.

https://stackoverflow.com/a/1684521/2724703