Crazy Leak...plz help - Page 2

[n.aggel]

The article on memory was very informing....

it would also be a good idea to modify the second rule to

.PHONY : clean # do not get confused by an actual file called clean
clean : # clean is a 'phony' target
<tab>rm -f $(NAME) $(objs)

this will prevent gmake from going mad if there happens to be a file called clean in the current directory.

i noticed that you erased the part where i deleted the precompiled header file
"LeftistHeap.h.gch", shouldn't i delete it?

however, keep in mind that If you already use an open source operating system, and you are happy with it, there is probably no good reason to change. to me, even one buntu is one buntu too many; it need not be so for you.

i think i will try desktopBSD first chance i get... i understand what you are saying{one of the reasons i settled with ubuntu is that it gave me everything i needed}, but when i see people {that i highly regard} use something else, it is a great motivation for me to try new things...:)

Thread solved!

[vijayan121]

>> noticed that you erased the part where i deleted the precompiled header file "LeftistHeap.h.gch", shouldn't i delete it?
it was an oversight. if you want to use precompiled headers, it would be a good idea to make sure that they are recreated as and when required. eg.

CC = g++
CFLAGS = -Wall -std=c++98 -O3 
LD = $(CC)
 
PROGRAM = zoo
ANIMALS = puma.c tiger.c meerkat.c zebra.c
SOURCES =  $(ANIMALS) main.c
HEADERS = $(ANIMALS:.c=.h)
ANIMAL_OBJECTS = $(ANIMALS:.c=.o)
OBJECTS = $(SOURCES:.c=.o)
PRECOMPILED = $(HEADERS:.h=.h.gch)

$(PROGRAM) : $(OBJECTS) 
    $(LD) -o $(PROGRAM) $(OBJECTS)

main.o : main.c $(PRECOMPILED) 
    $(CC) $(CFLAGS) -o main.o -c main.c 
$(ANIMAL_OBJECTS): %.o : %.c %.h.gch
    $(CC) $(CFLAGS) -o $@ -c $<

$(PRECOMPILED): %.h.gch : %.h
    $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"


.PHONY : clean
clean :
    rm -f $(OBJECTS) $(PRECOMPILED) $(PROGRAM)

>> i think i will try desktopBSD first chance i get...
you could try out both DesktopBSD and PC-BSD and see which one suits you better; both are FreeBSDs. PC-BSD has the larger user base, the community is very active and does seem to have more momentum at the moment. DesktopBSD is closer to FreeBSD; stable, light on resources and fast. for a comparison between the two from a newbie perspective, see: http://www.dailykos.com/story/2007/7/5/63728/62134.

[n.aggel]

It turns out that make is pretty sofisticated as a tool{and convienient!}...

i started reading tha manual http://www.gnu.org/software/make/manual/make.html...

i liked the whole phony target thing .PHONY and the trick with the substititions $(SOURCES:.c=.o) .

Seeing the makefile you posted i decided to mimic it, so i made this::

# Project: PQ
#Add -g option to use with valgrind and with gdb!

CC = g++
CFLAGS = -Wall -std=c++98 -O3
LD = $(CC)

PROGRAM = priority_queue
STRUCTURE = LeftistHeap.cpp
SOURCES = main.cpp $(STRUCTURE)
HEADERS = $(STRUCTURE:.c=.h)
OBJECTS = $(SOURCES:.c=.o)
STRUCTURE_OBJECTS = $(STRUCTURE:.c=.o)
PRECOMPILED = $(HEADERS:.h=.h.gch)

$(PROGRAM): $(OBJECTS)
	$(LD) -o $(PROGRAM) $(OBJECTS)

$(STRUCTURE_OBJECTS): %.o : %.c %.h.gch
    $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"

main.o : main.c $(PRECOMPILED) 
    $(CC) $(CFLAGS) -o main.o -c main.c

$(PRECOMPILED): %.h.gch : %.h
    $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"

	
# do not get confused by an actual file called clean
#When one phony target is a prerequisite of another, it serves as a subroutine of the other	
.PHONY: cleanall cleanobj
     
cleanall : cleanobj
	rm -f $(PROGRAM)

cleanobj :
	rm -f $(OBJECTS) $(PRECOMPILED) # or rm *.o

#i also added this command...although i haven't used it yet....
TAGS : $(SOURCES) $(HEADERS)
	etags -t $(SOURCES) $(HEADERS)

but i do have some questions {like usual:P}

1) why do you use this::

CC = g++
LD = $(CC)

in the end LD equals g++, right?

2) the makefile above doesn't work.... i get this error::

makefile:22: target `LeftistHeap.cpp' doesn't match the target pattern
makefile:23: *** missing separator.  Stop.

i can't fix it because, i don't understand this line:: $(CC) $(CFLAGS) -o $@ -c $< || echo ...
i read section 10.5.3 Automatic Variables in the manual, but stil i can't decipher the meaning of it...

3)in the manual i found the following rule::

print: foo.c bar.c
	lpr -p $?
	touch print

what's the practical use of it?

thanks in advance for your time,
nicolas

[vijayan121]

>> ... in the end LD equals g++, right?...
usually yes, for C++ programmers. g++ invokes ld (unless invoked with the -c switch). but this may not always be what you require. for example, you may want to use g++ to compile your code on a solaris machine, but want to link with the native solaris (unix) ld instead of the gnu ld. defining LD seperately would aid portability. also, if the linker is invoked via a compiler-driver, passing switches to the linker is somewhat awkward: eg. g++ -std=c++98 -Wall -Wl, --print-map -Wl, --cref foo.cc bar.cc >> the makefile above doesn't work.... i get this error...
the makefile is written with the assumption that source files have a .c suffix. the source files you use have a .cpp suffix. the substitution (.c to .h) is failing.

>> i can't fix it because, i don't understand .. automatic variables
play around with the following toy makefile; that should give you a basic understanding of using variables in makefiles.

PROGRAM := zoo

SOURCE_SUFFIX ?= .cpp
HEADER_SUFFIX ?= .h
OBJECT_SUFFIX := .o
PRECOMPILED_SUFFIX := $(HEADER_SUFFIX).gch

ANIMALS = puma tiger meercat zebra
MAIN := main
ANIMAL_SOURCES = $(foreach ANIMAL,$(ANIMALS),$(ANIMAL)$(SOURCE_SUFFIX))
SOURCES = $(ANIMAL_SOURCES) $(MAIN)$(SOURCE_SUFFIX)
HEADERS = $(ANIMAL_SOURCES:$(SOURCE_SUFFIX)=$(HEADER_SUFFIX))
ANIMAL_OBJECTS = $(ANIMAL_SOURCES:$(SOURCE_SUFFIX)=$(OBJECT_SUFFIX))
OBJECTS = $(SOURCES:$(SOURCE_SUFFIX)=$(OBJECT_SUFFIX))
PRECOMPILED = $(HEADERS:$(HEADER_SUFFIX)=$(PRECOMPILED_SUFFIX))

CC = g++
PROCESSOR ?= pentium4
OPTIMIZE ?= -O3
override CFLAGS += -Wall -std=c++98 $(OPTIMIZE) -march=$(PROCESSOR)

the_target : one two three four three two
    @echo
    @echo automatic variables
    @echo -------------------
    @echo rule  \'$@ : $+\'
    @echo target \$$\@ : $@
    @echo first prerequisite \$$\< : $<
    @echo prerequisites \$$\^ : $^
    @echo prerequisites with dups \$$\+ : $+

    @echo
    @echo variables
    @echo ---------
    @echo ANIMAL_SOURCES $(ANIMAL_SOURCES)
    @echo SOURCES $(SOURCES)
    @echo HEADERS $(HEADERS)
    @echo ANIMAL_OBJECTS $(ANIMAL_OBJECTS)
    @echo OBJECTS $(OBJECTS)
    @echo PRECOMPILED $(PRECOMPILED)
    @echo CFLAGS $(CFLAGS)

one two three four :
    @echo making target $@

#invoke gmake (on unix, make is not gnu make)
#try out the following invocations of gmake:

#gmake
#gmake SOURCE_SUFFIX='.cc'
#gmake SOURCE_SUFFIX='.cc' HEADER_SUFFIX='.hpp'
#gmake SOURCE_SUFFIX='.cpp' HEADER_SUFFIX='.hpp' CFLAGS='-g'
#gmake SOURCE_SUFFIX='.cxx' HEADER_SUFFIX='.hxx' CFLAGS='-g' OPTIMIZE='-O2'

>> in the manual i found the following rule ... what's the practical use of it?
the automatic variable $? gives the names of prerequisites which are newer than the target. touch updates the timestamp of the target. (the target print is an empty target file). the net effect is to print those prerequisites (files) that have been modified since the last time gmake print was invoked.

also, use a construct of this kind as a command only if the make should not fail if the first part of the command fails: $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers" the comand is passed to the shell (usually /bin/sh) to execute; &, &&, || have their usual meanings and are interpreted by the shell. the above line means: if the attemt to precompile the header fails, echo a message to that effect. the shell command (atleast echo) will always succeed and make will continue. this would not be ok for catastrophic errors (in this case, we can carry on with make even if no precompiled headers are available. they are not essential).

[n.aggel]

also, use a construct of this kind as a command only if the make should not fail if the first part of the command fails: $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers" the comand is passed to the shell (usually /bin/sh) to execute; &, &&, || have their usual meanings and are interpreted by the shell. the above line means: if the attemt to precompile the header fails, echo a message to that effect. the shell command (atleast echo) will always succeed and make will continue. this would not be ok for catastrophic errors (in this case, we can carry on with make even if no precompiled headers are available. they are not essential).

That's interesting but when i invoke gmake i get among others this::

g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp || echo "not using precompiled headers"

but if i understand what you are telling i should only get this::: g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp...correct?

[n.aggel]

Another weird thing vijayan121... i want to time the performance of the merge operation so i change main.cpp to this::

int main(int argc, char *argv[])
{

	

    enum { HOW_MANY_ELEMENTS = 1000000, TEST_ITERATIONS = 1, DISTRIBUITION_AREA=1024*1024 };
	
	
	
		mt19937 engine ; // mersene twister; fast with acceptable quality.
		uniform_int<> distribution( 1, DISTRIBUITION_AREA ) ; // just as an example
		variate_generator< mt19937&, uniform_int<> > 
				generator( engine, distribution ) ;
     
     
	double make_heap_total = 0.0 ;
	double make_heap_min = numeric_limits<double>::max() ;
	double make_heap_max = 0.0 ;
     
     
     
     
     cout<<endl;
     cout<<"#############################################"<<endl;
     cout<<"Start of Priority Queue testbench  "<<endl;
     cout<<"#############################################"<<endl;
     cout<<endl;	
	
	for( int i=0 ; i<TEST_ITERATIONS ; ++i )
	{
		LeftistHeap init1;	//The test structures
		LeftistHeap init2;
		
		
		static vector<int> vec(HOW_MANY_ELEMENTS) ;
		
		cout<<"Initialization of init1 Priotity Queue"<<endl;
		generate_n( vec.begin(), size_t(HOW_MANY_ELEMENTS), generator ) ;
		init1.initializeHeap(vec);
		//init1.print(1);
    		
    		cout<<"Initialization of init2 Priotity Queue"<<endl;
    		generate_n( vec.begin(), size_t(HOW_MANY_ELEMENTS), generator ) ;
    		init2.initializeHeap(vec);
    		//init2.print(1);
    		
    		clock_t start = clock() ;
		init1.merge(init2);
    		clock_t end = clock() ;
    		
    		
    		myNode::node_pool.pool<>::~pool<>() ;
		::new( &myNode::node_pool ) pool<>(  sizeof(myNode) ) ;
    		
    		//cout<<"\t\tEnd of Initialization phase"<<endl;
    		
    		//initial statistics
    		double duration = elapsed_msecs( start, end ) ;
    		make_heap_total += duration ;
    		make_heap_min = min( make_heap_min, duration ) ;
    		make_heap_max = max( make_heap_max, duration ) ;
    		
    			

	
	}
	cout<<endl<<endl;
	cout <<"Results analysis:"<<endl;
	cout << HOW_MANY_ELEMENTS <<" number of elements"<<endl;
	cout << "resolution of libc clock: " << 1000.0 / CLOCKS_PER_SEC << " millisecs\n" ;
	cout << "make_heap - min: " << make_heap_min << "\t  max: " << make_heap_max
        << "\t average: " << make_heap_total / TEST_ITERATIONS << " millisecs\n" ;
     

	cout<<endl;
	cout<<endl;
	cout<<"#############################################"<<endl;
	cout<<"END of Structure"<<endl;
	cout<<"#############################################"<<endl;
    	
    return 0;
}

Running with this the merge operation takes 0 seconds....although if i print the initials and the final structure everything seems to be ok....

any idea why this is happening?

[vijayan121]

>> but if i understand what you are telling i should only get this::: g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp...correct?

correct. if the compilation of LeftistHeap.cpp fails, the error is catastrophic and make should fail.

>> the merge operation takes 0 seconds....although if i print the initials and the final structure everything seems to be ok....any idea why this is happening?

the resolution of the libc clock is 7.8125 millisecs (on my machine). creating a heap of one million elements involves
a. dynamic allocation and initialization of one million nodes (this is what we optimized by means of a pool allocator)
b. creation of two million temporary heap objects (N + N/2 + N/4 + ... + 2 + 1)
c. two million pushes ino the queue
d. one million calls to merge (half the number of pushes)
e. two million pops from the queue
and all this takes 12 clock ticks or so. this is C++, not java.

the advantage of using leftist heaps is because of their ability to merge quickly; in O(log N) time. so merging two leftist heaps containing one million elements will (recursively) call merge about 25 times or so (on the average).
it is no surprise that the time taken is not measurable using the libc clock.
you could instrument your code (or use a profiler) to verify that these are the call counts.

[n.aggel]

>> but if i understand what you are telling i should only get this::: g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp...correct?

correct. if the compilation of LeftistHeap.cpp fails, the error is catastrophic and make should fail.

yes but i don't get output g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp but g++ -Wall -std=c++98 -O3 -o LeftistHeap.o -c LeftistHeap.cpp || echo "not using precompiled headers"

[vijayan121]

>> yes but i don't get output ... but ...
that must be because of the way you wrote the command in the make file. could tell you what is happening if you post the contents of your makefile. your makefile may contain something like this (this was there in an earlier version which you posted; it gave make errors and you must have modified it since then):

$(STRUCTURE_OBJECTS): %.o : %.c %.h.gch
    $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"

[n.aggel]

....you post the contents of your makefile....

yes i forgot this step, here is my makefile::

# Project: PQ
#Add -g option to use with valgrind and with gdb!

CC = g++
CFLAGS = -Wall -std=c++98 -O3
LD = $(CC)

PROGRAM = priority_queue
STRUCTURE = LeftistHeap.cpp
SOURCES = main.cpp $(STRUCTURE)
HEADERS = $(STRUCTURE:.cpp=.h)
OBJECTS = $(SOURCES:.cpp=.o)
STRUCTURE_OBJECTS = $(STRUCTURE:.cpp=.o)
PRECOMPILED = $(HEADERS:.h=.h.gch)

$(PROGRAM): $(OBJECTS)
	$(LD) -o $(PROGRAM) $(OBJECTS)

$(STRUCTURE_OBJECTS): %.o : %.cpp %.h.gch
	$(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"

main.o : main.cpp $(PRECOMPILED) 
	$(CC) $(CFLAGS) -o main.o -c main.cpp

$(PRECOMPILED): %.h.gch : %.h
	$(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"

	
# do not get confused by an actual file called clean
#When one phony target is a prerequisite of another, it serves as a subroutine of the other	
.PHONY: clean cleanobj
     
clean : cleanobj
	rm -f $(PROGRAM)

cleanobj :
	rm -f $(OBJECTS) $(PRECOMPILED) # or rm *.o

TAGS : $(SOURCES) $(HEADERS)
	etags -t $(SOURCES) $(HEADERS)

[vijayan121]

modify as follows.

# ....
# ....
$(PROGRAM): $(OBJECTS)
    $(LD) -o $(PROGRAM) $(OBJECTS)

$(STRUCTURE_OBJECTS): %.o : %.cpp %.h.gch
    $(CC) $(CFLAGS) -o $@ -c $< 

main.o : main.cpp $(PRECOMPILED) 
    $(CC) $(CFLAGS) -o main.o -c main.cpp

$(PRECOMPILED): %.h.gch : %.h
    $(CC) $(CFLAGS) -o $@ -c $< || echo "not using precompiled headers"
#...
#...

[n.aggel]

thanks fo pointing this out!