Memory leak (I think)

[dobby156]

Hi

I have made a binary tree collection, and am having a bit of oddity.

I have tried populating the tree with 4000 int then calling my clear method (recursive).

Memory usage
Before populate with 4000 ints 572k,
after Populate 856k,
after delete 1624k,
after re-population 1856k,
after delete 1624k;

Is there a leak or does (as I suspect) the current stack capacity not shrink once it has been grown?

This is the delete method, getGreater() and getLesser() return a pointer to the next node respectively.

void removeTreeFromPoint (BinaryTreeNode<T>* current)
{
	if(current)
	{
		removeTreeFromPoint(current->getLesser());
		removeTreeFromPoint(current->getGreater());
		delete current;
	}
}

Thank You

[kbw]

The algorithm looks ok.

How did you make those measurements?

What type T is in your tree? Are they being deleted correctly?

[dobby156]

I took the measurements just using task manager, I am not sure how accurate it is but it was very responsive to changing of the heap size and the growing of the stack.

on the tests T is just an int. populate-depopulation isn't leaving anything behind i don't think because after the second clear() call the program return the to the size as before.

Thanks.

[simeonz]

dobby156 wrote:

Is there a leak or does (as I suspect) the current stack capacity not shrink once it has been grown?

Sounds very probable (not the leak). Stack, heap, any reserved address range probably gets committed to physical memory as needed. Heap memory can return to the system when entire pages of memory become free, but it is not guaranteed. It just makes sense.

Here is my VERY improvised interpretation.

Memory usage
Before populate with 4000 ints 572k,
after Populate 856k,

I think that the stack have grown already here. I mean, the implementation of the populating method could be recursive.

after delete 1624k,

I think that the heap's internal structure also grows here. In trivial implementation, the heap will maintain a set of free memory blocks. As you return the blocks of allocated memory back to the heap, such a set/list/whatever could grow unless the freed address ranges get consolidated. The management is actually in two layers - heap (malloc) and free store (new). The latter may be lightweight, but who knows.

after re-population 1856k,
after delete 1624k;

The memory is returned to the system in entire memory pages. This is the only explicable thing.

Regards

[dobby156]

Thank you that's kind of put my mind at rest a little, the population method is NOT recursive to loop driven. I try to avoid recursion, seeing as by default I get stack over flows at about level 4000. (each in I added was 1 greater than the last).

	
void add(T value)
{
	BinaryTreeNode<T> *cur = strt;
	T val;
	
	if(!strt) strt = new BinaryTreeNode<T>(value); 
	else while(cur)
	{
		val = cur->getValue();
		if(killDuplicates && value == val) cur = 0;
		else if(value >= val)
		{
			if (!cur->getGreater() )
			{
				cur->setGreater(new BinaryTreeNode<T>(value));
				cur = 0;
			}
			else cur = cur->getGreater();
		}
		else
		{
			if(!cur->getLesser())
			{
				cur->setLesser(new BinaryTreeNode<T>(value));
				cur = 0;
			}
			else cur = cur->getLesser();
		}
	}
}

That said, I think the initial growth when populated is from the tree its self with a small amount of stack.

Then on clear() you get the massive growth which massively increases the stack, which then seams to remain the same after execution. How I believe the dynamic memory has returned to the same size.

because you see the program expand by roughly them same amount as the first run through on the second then shrink down to the same size on delete I am confident that the dynamic memory frees up all the memory it uses afterwards.

Thanks again

PS: I think I will try recompile this next week with g++ on a *nix box and see whether top displays the same result.

[kfmfe04]

I recommend that you use valgrind:

http://valgrind.org/

You don't even need to relink your program. Just run valgrind on your executable.
It's especially useful if you are rolling your own data structures/non-trivial algorithms.

[kbw]

I took the measurements just using task manager

You need to use PerfMon and measure Private Bytes.