Why is deleted memory unable to be reused

Question

I am using C++ on Windows 7 with MSVC 9.0, and have also been able to test and reproduce on Windows XP SP3 with MSVC 9.0.

If I allocate 1 GB of 0.5 MB sized objects, when I delete them, everything is ok and behaves as expected. However if I allocate 1 GB of 0.25 MB sized objects when I delete them, the memory remains reserved (yellow in Address Space Monitor) and from then on will only be able to be used for allocations smaller than 0.25 MB.

This simple code will let you test both scenarios by changing which struct is typedef'd. After it has allocated and deleted the structs it will then allocate 1 GB of 1 MB char buffers to see if the char buffers will use the memory that the structs once occupied.

struct HalfMegStruct
{
    HalfMegStruct():m_Next(0){}

    /* return the number of objects needed to allocate one gig */
    static int getIterations(){ return 2048; }

    int m_Data[131071];
    HalfMegStruct* m_Next;
};

struct QuarterMegStruct
{
    QuarterMegStruct():m_Next(0){}

    /* return the number of objects needed to allocate one gig */
    static int getIterations(){ return 4096; }

    int m_Data[65535];
    QuarterMegStruct* m_Next;
};

// which struct to use
typedef QuarterMegStruct UseType;

int main()
{
    UseType* first = new UseType;
    UseType* current = first;

    for ( int i = 0; i < UseType::getIterations(); ++i )
        current = current->m_Next = new UseType;

    while ( first->m_Next )
    {
        UseType* temp = first->m_Next;
        delete first;
        first = temp;
    }

    delete first;

    for ( unsigned int i = 0; i < 1024; ++i )
        // one meg buffer, i'm aware this is a leak but its for illustrative purposes. 
        new char[ 1048576 ]; 

    return 0;
}

Below you can see my results from within Address Space Monitor. Let me stress that the only difference between these two end results is the size of the structs being allocated up to the 1 GB marker.

This seems like quite a serious problem to me, and one that many people could be suffering from and not even know it.

• So is this by design or should this be considered a bug?
• Can I make small deleted objects actually be free for use by larger allocations?
• And more out of curiosity, does a Mac or a Linux machine suffer from the same problem?

Answer 1

I cannot positively state this is the case, but this does look like memory fragmentation (in one of its many forms). The allocator (malloc) might be keeping buckets of different sizes to enable fast allocation, after you release the memory, instead of directly giving it back to the OS it is keeping the buckets so that later allocations of the same size can be processed from the same memory. If this is the case, the memory would be available for further allocations of the same size.

This type of optimization, is usually disabled for big objects, as it requires reserving memory even if not in use. If the threshold is somewhere between your two sizes, that would explain the behavior.

Note that while you might see this as weird, in most programs (not test, but real life) the memory usage patterns are repeated: if you asked for 100k blocks once, it more often than not is the case that you will do it again. And keeping the memory reserved can improve performance and actually reduce fragmentation that would come from all requests being granted from the same bucket.

You can, if you want to invest some time, learn how your allocator works by analyzing the behavior. Write some tests, that will acquire size X, release it, then acquire size Y and then show the memory usage. Fix the value of X and play with Y. If the requests for both sizes are granted from the same buckets, you will not have reserved/unused memory (image on the left), while when the sizes are granted from different buckets you will see the effect on the image on the right.

I don't usually code for windows, and I don't even have Windows 7, so I cannot positively state that this is the case, but it does look like it.