After a sequence of new/delete on structs, I seem to have memory loss

Question

Hello All:

I have a linked list of structs each of which contains an integer and a pointer to the next struct. Before populating this struct by a sequence of new commands, I note down the memory used (say Mem_1) by this program in Windows Task Manager under "Mem Usage". The actual linked list creation occurs next. (See void populate(int i) function below). Then, I use a sequence of deletes to try and delete this linked list and hopefully reclaim the memory. After the deletes, I check the memory again in the Task Manager. This time the amount of memory used is, say, Mem_2. I notice that Mem_2 > Mem_1. Should not Mem_2 = Mem_1? Or is there some dangling pointer I am not properly taking care of.

Thanks for your help in advance...(The code is a console application/VS2008/Windows XP platform)

struct item_s{
int value;
item_s* next;
};

struct item_s* item = NULL;
struct item_s* last_item = NULL;
struct item_s* last_accessed = NULL;

void populate(int i){
     if(item == NULL){
    item = new item_s;
    item->value = i;
    item->next = NULL;
    last_item = item;
}
else{
    last_item->next = new item_s;
    last_item->next->value = i;
    last_item->next->next = NULL;
    last_item = last_item->next;
}
}

void main(){
for(i = 1; i <= 10000; i++){
    populate(i);
}
last_item = item;
last_accessed = last_item->next;
while(last_item!=NULL){
    delete last_item;
    last_item = last_accessed;
    if(last_item!=NULL){
        last_accessed = last_item->next;
    }
}
}

Answer 1

TwoThree big problems here:

1. Why are you newing structs anyway? You should probably use some form or RAII container instead. If you were, you wouldn't have to worry about memory leaks at all (unless there were bugs in the container of course) Examples include std::vector and std::auto_ptr. If you have access to C++0x there is also std::unique_ptr and std::shared_ptr. If you have access to TR1 only (or the boost libraries), similar containers available are std::tr1::shared_ptr, and std::tr1::scoped_ptr. (Which are in the boost:: namespace in the boost incarnations)
2. Windows' task manager reports virtual memory consumed by the process. The delete call merely returns the memory to the C runtime. The C runtime does not always immediately return the memory back to the operating system, because OS allocations (via VirtualAlloc) are extremely expensive.
3. It's int main() !

To determine whether memory is actually allocated, you would need that tool to operate at C runtime level, not at operating system level.

Answer 2

This is just not how the Windows memory manager works. After it went to the trouble of allocating and mapping virtual memory pages, it does not give up on them just because you stopped using them. That would be very inefficient. It just keeps a hold of them, adding the freed blocks of memory to a list of free blocks. Ready to be reused again when your program continues running.

Taskmgr.exe is quite insufficient to reverse-engineer how memory management works. Especially the "Mem Usage" column. Which only tells you how much RAM your program is currently using. A highly variable number. Minimize your app's main window for example to see a drastic change.

Windows Internals is a decent book to learn more about how this works.

Answer 3

The number you are looking at unfortunately does not reflect what you think it does: the net amount of memory that your program has allocated using new calls that are unmatched by delete is probably less than what the operating system (OS) thinks your process owns (that's the number you are viewing here).

This is because when you call new there is a layer called the heap manager between you and the OS. When you ask for a block of memory using new, the heap manager looks for an appropriate contiguous block of free bytes in its cache of OS memory, and only if there is none does it request another OS block. This results in the number you are watching increasing.

When you call delete, the heap manager does not always release that memory back to the OS (that would be expensive, and cause excessive contention between processes). Most often, it just adds the released block back to an internal free list for later reuse elsewhere in your program. Over time, this in-and-out process from free list to in use and back can result in contiguous blocks of free bytes becoming hard to find. Every so often therefore, the heap manager will perform a compaction operation to coalesce free space into larger contiguous blocks, which can then be partitioned more efficiently when the need arises (to satisfy more new calls).

To track your actual memory usage here, you could add global counters of new and delete calls and output at the end of your program whether they match up.

A better way to do this would be to encapsulate the counter of 'active' objects as a static member of your struct, and increment it on construction and copy construction, and decrement it on destruction. That way you always can tell just how many active instances you have. If you have multiple threads in your program, such a counter would need to be maintained using ++ and -- in a threadsafe way - most OSes have atomic ways to do this eg. InterlockedDecrement and InterlockedIncrement on Windows.