DaniWeb Forum Index > Software Development > C++

C++ RSS

Crazy Leak...plz help

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

Last »

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

Crazy Leak...plz help

Sep 6th, 2007

this is the final version of the priority queue i implemented {with some of your help!}...

the problem is that when i profile the code with valgrind, it shows that i have a memory leak....

i can also see that, if in my code i make certain test_points{where i pause the execution} and then check out the process manager....It seems that although i clean the memory, something stays behind...

i've used simple segregated storage scheme that vijayan121 suggested.. i also have a version where i visit every node to deleting it... using a preorder tree walk, or the method Hamrick suggested {with a stack}

all versions, have the exact same problem, that tells me that memory leak is not in the structure .....but where else can it be??

I attach the version with the segregated scheme along with the makefile i used to test the structure with valgrind

thank you in advance for your time...

Attached Files

vi.zip (4.4 KB, 10 views)

•

Join Date: Aug 2005

Posts: 15,340

Reputation: Ancient Dragon has a reputation beyond repute

Solved Threads: 1458

Ancient Dragon Ancient Dragon is offline

Offline

Still Learning

Re: Crazy Leak...plz help

Sep 6th, 2007

If this is for a school assignment then you probably should not use the boost library without your instructor's prior permission because he (or she) may not be able to compile it on school computers.

Don't PM me with questions -- you might get a nasty PM in response. If you have a question then post it in one of the forums.

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Crazy Leak...plz help

Sep 6th, 2007

check the function LeftistHeap::initializeHeap. valgrind is reporting 80 bytes in 10 unreachable blocks of memory allocated in this function. this is a leak.
the 2 reachable blocks are not memory allocated from your code (they are allocations by libc.so and will be released on program exit) and do not constitute a leak.

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

Re: Crazy Leak...plz help

Sep 6th, 2007

•

Originally Posted by Ancient Dragon

If this is for a school assignment then you probably should not use the boost library without your instructor's prior permission because he (or she) may not be able to compile it on school computers.

it begun as a university project, now the addons are basically for fun and learn...

•

Originally Posted by vijayan121

check the function LeftistHeap::initializeHeap. valgrind is reporting 80 bytes in 10 unreachable blocks of memory allocated in this function. this is a leak.
the 2 reachable blocks are not memory allocated from your code (they are allocations by libc.so and will be released on program exit) and do not constitute a leak.

This is what LeftistHeap::initializeHeap does:
In orderd to get a linear time initialization i create n heaps with each containing one of the n elements. Then i place these heaps on a FIFO queue. Then the heaps are deleted from this queue in pairs, merged, and added to the end of the queue until only one heap remains.This heap assign to root pointer....

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
void LeftistHeap::initializeHeap(std::vector<int> & vec)
{
 	 queue<LeftistHeap *> q;
 
 	 for(int i=0; i<vec.size(); ++i)
 	 {
	    q.push(new LeftistHeap(vec[i]) );
	 }
 
	 LeftistHeap *temp;
 
	 while ( q.size()!=1)
     	{
           temp = q.front();
           q.pop();
           //the line below equals to :: temp = merge(temp, q.front())
           temp->merge( *(q.front()) );
           q.pop();
 
           q.push(temp);
     	}
 
     // assign final heap.....
     root=merge(q.front()->root, NULL);
 
}
void LeftistHeap::initializeHeap(std::vector<int> & vec)
{
 	 queue<LeftistHeap *> q;
 	 
 	 for(int i=0; i<vec.size(); ++i)
 	 {
	    q.push(new LeftistHeap(vec[i]) );
	 }
	 
	 LeftistHeap *temp;
	 
	 while ( q.size()!=1)
     	{
           temp = q.front();
           q.pop();
           //the line below equals to :: temp = merge(temp, q.front())
           temp->merge( *(q.front()) );
           q.pop();

           q.push(temp);
     	}
     
     // assign final heap.....
     root=merge(q.front()->root, NULL);

}

here is the only line where i allocate space in the program

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
q.push(new LeftistHeap(vec[i]) );
q.push(new LeftistHeap(vec[i]) );

So to see if this has any problems i created a new ain that does only this::

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int main(int argc, char *argv[])
{
	LeftistHeap init(5);
 
    return 0;
}
int main(int argc, char *argv[])
{
	LeftistHeap init(5);
    	
    return 0;
}

if i test this programm with valgrind, i don't get any errors.... which is weird because i shoud inlcude this line to have it empty the pool{if i have understand correctly the operation of the pool}

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
myNode::node_pool.purge_memory() ;
myNode::node_pool.purge_memory() ;

any other ideas?

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Crazy Leak...plz help

Sep 7th, 2007

>> here is the only line where i allocate space in the program
q.push(new LeftistHeap(vec[i]) );

the leak is because of that line; sizeof(LeftistHeap) == sizeof(pointer) + sizeof(int), adds up to 8 bytes on i386. the leak reported by valgrind is

•

80 bytes in 10 blocks are definitely lost in loss record 1 of 2
==1599== at 0x3C03D2F3: operator new(unsigned) (in /usr/local/lib/valgrind/vgpreload_memcheck.so)
==1599== by 0x804936E: LeftistHeap::initializeHeap(std::vector<int, std::allocator<int> >&) (LeftistHeap.cpp:206)

and in main.cpp we have
enum { HOW_MANY_ELEMENTS = 10, TEST_ITERATIONS = 1, DISTRIBUITION_AREA=1024*1024 };
the blocks lost are the 10 LeftistHeap objects that you allocate using new and never delete.

change HOW_MANY_ELEMENTS to 1000 and valgrind will report 8000 bytes in 1000 blocks as definitely lost.
the dynamically allocated LeftistHeap objects are leaking; not the nodes

>> if i test this programm with valgrind, i don't get any errors.... which is weird...

valgrind automagically knows about memory that is still reachable. node_pool (has a static storage duration; still not destroyed at the point main returns) has references the the blocks it has allocated; so the memory is not *definitely* lost. in fact, the destructor of node_pool will free this memory.
you could verify this by using the valgrind switch --show-below-main=yes (continue stack traces below main)

Last edited by vijayan121; Sep 7th, 2007 at 10:29 am.

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

Re: Crazy Leak...plz help

Sep 7th, 2007

•

Originally Posted by vijayan121

q.push(new LeftistHeap(vec[i]) );
the leak is because of that line;

but why? i thaught that with this line the queue queue<LeftistHeap *> q; would be made responsible for desposing the elements....

•

Originally Posted by vijayan121

sizeof(LeftistHeap) == sizeof(pointer) + sizeof(int), adds up to 8 bytes on i386. the leak reported by valgrind is
and in main.cpp we have
enum { HOW_MANY_ELEMENTS = 10, TEST_ITERATIONS = 1, DISTRIBUITION_AREA=1024*1024 };
the blocks lost are the 10 LeftistHeap objects that you allocate using new and never delete.

something irrelevant: why the size of leftistheap is just sizeof(pointer) + sizeof(int)??I also have three pointers in the leftistheap class...

•

Originally Posted by vijayan121

change HOW_MANY_ELEMENTS to 1000 and valgrind will report 8000 bytes in 1000 blocks as definitely lost.
the dynamically allocated LeftistHeap objects are leaking; not the nodes

I had observed this behaviour, thats why i thaught it was the nodes leaking and also set the size to 10

•

Originally Posted by vijayan121

valgrind automagically knows about memory that is still reachable. node_pool (has a static storage duration; still not destroyed at the point main returns) has references the the blocks it has allocated; so the memory is not *definitely* lost. in fact, the destructor of node_pool will free this memory.
you could verify this by using the valgrind switch --show-below-main=yes (continue stack traces below main)

this i didn't know!thank you

here is what i did... if the queue isn't responsible then i am, so i did something like this:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
LeftistHeap *a=new LeftistHeap(vec[i]);
q.push(a);
delete a;
LeftistHeap *a=new LeftistHeap(vec[i]);
q.push(a);
delete a;

The program compiles but the structure doesn't work afterwards...as i would expect,because i delete where the queue elements point and logically valgrind reports Invalid read of size 4...

So, the question remains , how can i deallocate something that i a not in control, because when i push the pointer in the queue i lose all control on that memory....

thanks again for your time,
nick

PS:

orry, if i ask silly things, but i am kinda lost...

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Crazy Leak...plz help

Sep 7th, 2007

>> but why? i thaught that with this line the queue queue<LeftistHeap *> q; would be made responsible for desposing the elements....

the queue owns pointers to LeftistHeaps, not the LeftistHeaps themselves. so it would release what it owns, ie. the pointer, not the pointed object. the behaviour would have been different for a queue<LeftistHeap>.

>> why the size of leftistheap is just sizeof(pointer) + sizeof(int)??I also have three pointers in the leftistheap class...

the size of an object would include the size of its non-static member variables ( + a vptr if there are virtual functions + one vbaseptr for each virtual base class + any padding; however for yourLeftistHeap none of these apply). the only non-static member variables of a LeftistHeap are myNode *root; int emptyFlag;

>> here is what i did... if the queue isn't responsible then i am, so i did something like this:
>> .....
>> doesn't work afterwards...as i would expect...
>> how can i deallocate something that i a not in control, because when i push the pointer in the queue i lose all control on that memory....

the queue will safely keep (a copy of) anything that you push into it. and give it back to you on demand.
do something like this instead.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void LeftistHeap::initializeHeap(std::vector<int> & vec)
{
   //prey to work!!!     
   queue<LeftistHeap *> q;
 
 
   for(int i=0; i<vec.size(); ++i)
   {
         q.push(new LeftistHeap(vec[i]) );
   }
 
   LeftistHeap *temp;
 
   while ( q.size()!=1)
     {
           temp = q.front();
           q.pop();
           //dld temp = merge(temp, q.front())
           temp->merge( *(q.front()) );
 
           // delete the LeftistHeap which we have just merged in to temp
           delete q.front() ; // *** this was added to the original code ***
           q.pop();
 
           q.push(temp);
     }
 
     //kanoume assign to teliko heap.....
     root=merge(q.front()->root, NULL);
    // delete the one temporary LeftistHeap remaning
     delete q.front() ; // *** this was added to the original code ***
}
void LeftistHeap::initializeHeap(std::vector<int> & vec)
{
   //prey to work!!!     
   queue<LeftistHeap *> q;


   for(int i=0; i<vec.size(); ++i)
   {
         q.push(new LeftistHeap(vec[i]) );
   }

   LeftistHeap *temp;

   while ( q.size()!=1)
     {
           temp = q.front();
           q.pop();
           //dld temp = merge(temp, q.front())
           temp->merge( *(q.front()) );

           // delete the LeftistHeap which we have just merged in to temp
           delete q.front() ; // *** this was added to the original code ***
           q.pop();

           q.push(temp);
     }

     //kanoume assign to teliko heap.....
     root=merge(q.front()->root, NULL);
    // delete the one temporary LeftistHeap remaning
     delete q.front() ; // *** this was added to the original code ***
}

note 1: i do not think that prayer is an effective antidote to problems in software.
note 2: no one is going to accuse you of writing fiendishly efficient code!

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

Re: Crazy Leak...plz help

Sep 8th, 2007

Thank you for solving this problem!!

•

Originally Posted by vijayan121

the queue owns pointers to LeftistHeaps, not the LeftistHeaps themselves. so it would release what it owns, ie. the pointer, not the pointed object. the behaviour would have been different for a queue<LeftistHeap>.

that makes sense!

•

Originally Posted by vijayan121

note 1: i do not think that prayer is an effective antidote to problems in software.

, that couldn't be more true... but when you are frustated with a program, your comments include funny stuff

•

Originally Posted by vijayan121

note 2: no one is going to accuse you of writing fiendishly efficient code!

sorry, my english don't help me...fiendishly efficient code?

that means that the code is efficient or not?

if there are more corrections that can be made, it would be great if you could point them out vijayan!

•

Join Date: Dec 2006

Posts: 1,089

Reputation: vijayan121 is a name known to all

Solved Threads: 164

vijayan121 vijayan121 is offline

Offline

Veteran Poster

Re: Crazy Leak...plz help

Sep 8th, 2007

clearly the code (creating, merging, destroying a lot of heaps) you have is not very efficient. an alternative would be
1. write a function to add one element to an existing heap (push_heap).
2. to create a heap of N elements, start with an empty heap and iteratively call push_heap for each of the N elements.
this will do away with the need for creation/destruction of N heap objects.
i do not know the leftist heap data structure, but like in the standard heap (make_heap), there could be a faster algorithm to do this in linear time.

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

Re: Crazy Leak...plz help

#10

Sep 8th, 2007

•

Originally Posted by vijayan121

clearly the code (creating, merging, destroying a lot of heaps) you have is not very efficient. an alternative would be
1. write a function to add one element to an existing heap (push_heap).
2. to create a heap of N elements, start with an empty heap and iteratively call push_heap for each of the N elements.
this will do away with the need for creation/destruction of N heap objects.
i do not know the leftist heap data structure, but like in the standard heap (make_heap), there could be a faster algorithm to do this in linear time.

I was thinking something like you said but then i read this in wikipedia http://en.wikipedia.org/wiki/Leftist_tree ::

•

Initializing a height biased leftist tree is primarily done in one of two ways. The first is to merge each node one at a time into one HBLT. This process is inefficient and takes O(nlogn) time. The other approach is to use a queue to store each node and resulting tree. The first two items in the queue are removed, merged, and placed back into the queue. This can initialize a HBLT in O(n) time. This approach is detailed in the three diagrams supplied. A min height biased leftist tree is shown.

you think that the above could be implemented in a more efficient way?