Crazy Leak...plz help

[n.aggel]

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...

[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.

[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.

[n.aggel]

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...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....

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

q.push(new LeftistHeap(vec[i]) );

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

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}

myNode::node_pool.purge_memory() ;

any other ideas?

[vijayan121]

>> 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 is80 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 >&) (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)

[n.aggel]

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....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...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 10valgrind 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:

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::Sorry, if i ask silly things, but i am kinda lost...

[vijayan121]

>> but why? i thaught that with this line the queue queue 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.

>> 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.

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!

[n.aggel]

Thank you for solving this problem!! :cool:

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.

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

:D , that couldn't be more true... but when you are frustated with a program, your comments include funny stuffnote 2: no one is going to accuse you of writing fiendishly efficient code!
sorry, my english don't help me...fiendishly efficient code?:confused: 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!

[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.

[n.aggel]

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?

[vijayan121]

you are right (read i was wrong). the technique you have used is indeed O(N).
you could improve the performance by avoiding the calls to new/delete. using a queue having leftist_heap by value (not pointer to dynamically allocated objects) would make it even faster. note that the copy/assignment/destroy of (your implementation of) leftist_heap are trivial operations. it would still be O(N), but you would not have to call new/delete N times.

[n.aggel]

first of all, i am sorry i didn't respond earlier , damned exams...

you could improve the performance by avoiding the calls to new/delete. using a queue having leftist_heap by value (not pointer to dynamically allocated objects) would make it even faster. ....... but you would not have to call new/delete N times.

Why the calls to new/delete harm the performance more than using by value passing?

I have an overloaded operator copy operator::

LeftistHeap::LeftistHeap(const LeftistHeap & rhs )
{
            root = NULL;
            *this = rhs;
}

It is ok for this purpose right?

i was thinking to begin something like this::

void LeftistHeap::initializeHeap(std::vector<int> & vec)
{
  
   queue<LeftistHeap> q;
 
 	
 LeftistHeap temp;
 
   for(int i=0; i<vec.size(); ++i)
   {
         q.push(temp(vec[i]) );
   }
 
 	//void LeftistHeap::merge( LeftistHeap & rhs )
   while ( q.size()!=1)
     {
           LeftistHeap temporal(	*(q.front())	);
           q.pop();
           //dld temp = merge(temp, q.front())
           temporal.merge( *(q.front()) );
 
           // delete the LeftistHeap which we have just merged in to temp
           q.pop();
 
           q.push(temporal);
     }
 
    //how to cahnge this line??
     root=merge(q.front()->root, NULL);
}

The way i see it, with value passing the queue will be responible for the elements, so if i pop one, it will also be deleted so how can i
assign it to root without having to copy the elements one by one?

Thanks again for your time,
Nick

[vijayan121]

>> Why the calls to new/delete harm the performance more than using by value passing?
this copy constructor does nothing more than the trivial bitwise copy that the compiler would have generated.

LeftistHeap::LeftistHeap(const LeftistHeap & rhs )
{
            root = NULL;
            *this = rhs;
}

as you have not declared an operator=, *this = rhs does a trivial bitwise assignment. (you can safely comment this constructor out; the inline bitwise copy that the compiler would generate would be faster than your out-of-line implementation and will do the same thing.) the same observation also holds for the do nothing destructor that you have.
since you are not using deep copy semantics, copying a LeftistHeap copies a pointer and an integer; destroying it would do nothing at all.new LeftistHeap on the other hand requires a call to operator new to allocate dynamic memory and delete LeftistHeap a call to operator delete to release the memory. these would typically require several dozen instructions to be executed. and you are doing this a very large number (several millions) of times.

>> ...so if i pop one, it will also be deleted so how can i ...
create a temporary copy (we have seen that this is inexpensive). and to avoid even this, try to use the object before popping it if possible. eg.

// note: added const to the input parameter to make it const-correct.
void LeftistHeap::initializeHeap( const std::vector<int>& vec )
{
      queue<LeftistHeap> q;
      for( int i=0; i<vec.size(); ++i ) q.push( LeftistHeap(vec[i]) );

     while ( q.size() > 1 )
     {
           LeftistHeap temp = q.front();
           q.pop();
           temp.merge( q.front() );
           q.pop();
           q.push(temp);
     }
     // the only LeftistHeap in the queue is still alive at this point. 
     root = merge( q.front().root, NULL );
}

[n.aggel]

this copy constructor does nothing more than the trivial bitwise copy that the compiler would have generated ....... times.

wow!!, i didn't know that...basically i was considering the new operator as a magic operator that returned memory! {i haven't read the part on stoursrup's book that explained what it really was..Now i have an idea, thank you!>> ...so if i pop one, it will also be deleted so how can i ...
create a temporary copy (we have seen that this is inexpensive). and to avoid even this, try to use the object before popping it if possible. eg.

// note: added const to the input parameter to make it const-correct.
void LeftistHeap::initializeHeap( const std::vector<int>& vec )
{
//....
     root = merge( q.front().root, NULL );  //this is were i think the problem is...
}

I still can't understand one thing, the same as yesterday, so i will rephrase the question. If i am inserting things to queue by value{so the queue has the ownership} and then return a pointer to that queue {with root=merge( q.front().root, NULL ); , when i leave the function scope (and the queue is destroyed) won't i have a problem?

Anyhow, i tested your code with 15 elements(it compiled) ,but when i run it{and made a printout on the heap), i got a core dumped-segmentation fault error...

Thanks again for your help!
Is there any way to bypass the error...because i liked the overall idea of dumping the new operator!

[vijayan121]

>> root = merge( q.front().root, NULL ); ..
that line is equivalent to root = q.front().root;

>> If i am inserting things to queue by value{so the queue has the ownership} and then return a pointer to that queue {with root=merge( q.front().root, NULL );, when i leave the function scope (and the queue is destroyed) won't i have a problem?
the destructor of the leftistheap does not delete it's nodes (infact it does nothing). so if we merge the root of a leftistheap into another leftistheap and destroy the original leftistheap, the nodes will remain.

>> i tested your code with 15 elements(it compiled) ,but when i run it{and made a printout on the heap), i got a core dumped-segmentation fault error...
i have not been able to reproduce that error even with a million elements; with a simulated printout of the entire heap. this is an extract of the valgrind output.

>valgrind --leak-check=yes -v --show-reachable=yes ./project
...
==19458== Command line
==19458==    ./project
==19458== Startup, with flags:
==19458==    --leak-check=yes
==19458==    -v
==19458==    --show-reachable=yes
...
==19458== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
==19458== malloc/free: in use at exit: 8192 bytes in 2 blocks.
==19458== malloc/free: 32802 allocs, 32800 frees, 54861840 bytes allocated.
==19458==
==19458== searching for pointers to 2 not-freed blocks.
==19458== checked 2456944 bytes.
==19458==
==19458== 8192 bytes in 2 blocks are still reachable in loss record 1 of 1
==19458==    at 0x3C03D183: malloc (in /usr/local/lib/valgrind/vgpreload_memcheck.so)
==19458==    by 0x3C20B099: __smakebuf (in /lib/libc.so.6)
==19458==    by 0x3C20AF64: __swsetup (in /lib/libc.so.6)
==19458==    by 0x3C1ECDE1: __swbuf (in /lib/libc.so.6)
==19458==
==19458== LEAK SUMMARY:
==19458==    definitely lost: 0 bytes in 0 blocks.
==19458==    possibly lost:   0 bytes in 0 blocks.
==19458==    still reachable: 8192 bytes in 2 blocks.
==19458==         suppressed: 0 bytes in 0 blocks.
...

i am attaching the code with the suggested modifications along with the complete valgrind output. you could have a look at it and identify the differences between that and your code.

ok, i tried, but daniweb does not seem to allow uploads of tar.gz or tar.bz2 files (gives an error 'invalid file'). surprising for a site that hosts a software forum. as a work-around, you could send me a test mail (not daniweb pm, i do not think that would work either) and i can attach the file in the reply.

[n.aggel]

>> i tested your code with 15 elements(it compiled) ,but when i run it{and made a printout on the heap), i got a core dumped-segmentation fault error... i have not been able to reproduce that error even with a million elements; with a simulated printout of the entire heap. this is an extract of the valgrind output.

once againmy mistake!, i 've put the print statement after the deletion of the structure....How absent minded can i be?---I can hear Salem making a comment on this :P -- void mainers and uncarefull programmers are doomed!! {just a joke!}>> If i am inserting things to queue by value{so the queue has the ownership} and then return a pointer to that queue {with root=merge( q.front().root, NULL );, when i leave the function scope (and the queue is destroyed) won't i have a problem?
the destructor of the leftistheap does not delete it's nodes (infact it does nothing). so if we merge the root of a leftistheap into another leftistheap and destroy the original leftistheap, the nodes will remain. I just understood what you are saying, but still it seems weird {that the destructor doesn't do anything} because if the nodes remain and there isn't any leftist heap to contain them{i.e. i didn't merge, but just created a queue and then deleted it...} then this is not considered as a memory leak?

PS::for the record your technique had actual results because i could create 1million elements in about 60-70 milliseconds and now i can do the same in just 43ms !!!!

thanks again for all your help vijayan121....

[n.aggel]

I deleted the implementations of the copy constructor and destructor...let the compiler do the job...and the results:::

1million elements 38 ms!!!

[vijayan121]

>> 1 million elements, 38 ms
that seems reasonable. what were the compiler switches? and i suppose it with the use of boost.pool?

>> it seems weird {that the destructor doesn't do anything} because if the nodes remain and there isn't any leftist heap to contain them{i.e. i didn't merge, but just created a queue and then deleted it...} then this is not considered as a memory leak
not really. the heaps are merged in pairs and put back into the queue till only one node remains. the pointer to the root node of the last heap in the queue (the one that contains the fully merged heap) is copied to the member variable root of the heap pointed to by the this pointer. so even if the queue (and the heap that it contains) are destroyed, the nodes remain. till you call boost::pool::purge_memory().

>>> daniweb does not seem to allow uploads of tar.gz or tar.bz2 files
let me try something. great, this works! note: fool_daniweb.txt is *not* a text file; it is really a tar.bz2

[n.aggel]

Thank you for all your help!

PS::i haven't used any particular compiler switch..

[n.aggel]

i marked this thread as unsolved ,again. because unfortunately i found a new error ,that i have never seen before}.

The application works like it should, but if i increase the number of iterations from 1 to {lets say 9} i get a weird behaviour....

First of all the application gets too slow, from the fifth iteration and above...If the desktop environment downs't get stack i get a core dumped error...

If i run the application with valgrind i get the following warnings::

==6837== Warning: set address range perms: large range 134217736 (undefined)
==6837== Warning: set address range perms: large range 134217768 (noaccess)
==6837== Warning: set address range perms: large range 268435464 (undefined)
==6837== Warning: set address range perms: large range 268435496 (noaccess)
==6837== Warning: set address range perms: large range 536870920 (undefined)

Plus some more that look like the ones above...

note:: i haven't managed to finish a whole run of valgrind...

I also tried to compile with the -Wall option enabled and i get the following warnings::

LeftistHeap.cpp: In member function ‘LeftistHeap* LeftistHeap::createHeap(std::vector<int, std::allocator<int> >&)’:
LeftistHeap.cpp:166: warning: comparison between signed and unsigned integer expressions
LeftistHeap.cpp: In member function ‘void LeftistHeap::initializeHeap(std::vector<int, std::allocator<int> >&)’:
LeftistHeap.cpp:193: warning: comparison between signed and unsigned integer expressions

Any ideas? What can it be...i mean with fewer iterations i don't get any problem, and everything works like it should, also valgrind reports that i don't have any memory leak... Why i get these results with some more iterations?

Thanks for your help in advance...:)