Hi, i 've recently done a university project requiring me to construct a data structure{ a heap}....
Now that i 've finished the programming task , i am thinking how can i measure the programm's performance.....
I will populate my data structure with 2 million random elements, and i will measure the time it takes to complete the varius operations on it....
The question is how can i do this...????
PS:: after the project gets marked i will post it online.
Which OS / Compiler / type of machine ?
use clock() to get the time before starting the algorithm and again afterwards, then subtract the two times. For example
clock_t start = clock();
// do something, such as call a function
clock_t end = clock();
clock_t diff = end - start;#include <algorithm>
#include <vector>
#include <iostream>
#include <ctime>
#include <iterator>
#include <boost/random.hpp>
#include <limits>
using namespace std ;
using namespace boost ;
inline double elapsed_msecs( clock_t start, clock_t end )
{ return double( end - start ) * 1000.0 / CLOCKS_PER_SEC ; }
int main()
{
// choose a reasonably good random number generator
// and a distribution that mirrors the intended use of the heap
mt19937 engine ; // mersene twister; fast with acceptable quality.
uniform_int<> distribution( 1, 1024*1024 ) ; // just as an example
variate_generator< mt19937&, uniform_int<> >
generator( engine, distribution ) ;
// measure performance for a your implementation and
// a reference implementation. this example measures
// performance of the reference implementation in libstdc++
// for two operations: make_heap O(N) and sort_heap O(N log N)
enum { HEAP_SIZE = 2*1024*1024, ITERATIONS = 32 };
double make_heap_total = 0.0 ;
double make_heap_min = numeric_limits<double>::max() ;
double make_heap_max = 0.0 ;
double sort_heap_total = 0.0 ;
double sort_heap_min = numeric_limits<double>::max() ;
double sort_heap_max = 0.0 ;
// run the test several times
for( int i=0 ; i<ITERATIONS ; ++i )
{
vector<int> vec ; vec.reserve(HEAP_SIZE) ;
generate_n( back_inserter(vec), size_t(HEAP_SIZE), generator ) ;
clock_t start = clock() ;
make_heap( vec.begin(), vec.end() ) ;
clock_t end = clock() ;
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 ) ;
start = clock() ;
sort_heap( vec.begin(), vec.end() ) ;
end = clock() ;
duration = elapsed_msecs( start, end ) ;
sort_heap_total += duration ;
sort_heap_min = min( sort_heap_min, duration ) ;
sort_heap_max = max( sort_heap_max, duration ) ;
}
cout << "resolution of libc clock: " << 1000.0 / CLOCKS_PER_SEC << " millisecs\n" ;
cout << "make_heap - min: " << make_heap_min << " max: " << make_heap_max
<< " avj: " << make_heap_total / ITERATIONS << " millisecs\n" ;
cout << "sort_heap - min: " << sort_heap_min << " max: " << sort_heap_max
<< " avj: " << sort_heap_total / ITERATIONS << " millisecs\n" ;
}
// compile with optimizations enabled and test
/*
>g++ -Wall -std=c++98 -O3 -march=pentium4 -I/usr/local/include perf_metric.cpp && ./a.out
resolution of libc clock: 7.8125 millisecs
make_heap - min: 54.6875 max: 62.5 avj: 60.0586 millisecs
sort_heap - min: 1328.12 max: 1335.94 avj: 1334.23 millisecs
*/i was concerned that if i used clock, it's output would compromised by the fact that it is run from inside the program....
I suppose you could use an external program to time it, but it would have a problem too in that it takes some time for one program to spawn another program so you would not be gaining anything. Calling the clock() function executes very quickly and would not throw off the timings very much if you execute the algorithm numerious times (such as a thousand times or so) before executing the clock() function again.
the time taken to call clock() would be much lower than the resolution of the clock provided by the library.
#include <iostream>
#include <ctime>
using namespace std ;
int main()
{
const double res = 1000.0 / CLOCKS_PER_SEC ;
cout << "resolution of libc clock: " << res << " millisecs\n" ;
int ncalls = 0 ;
enum { NTESTS = 1024 } ;
for( int i=0 ; i<NTESTS ; ++i )
{
clock_t t1 = clock(), t2 = t1+1 ;
while( clock() == t1 ) ;
while( clock() == t2 ) ++ncalls ;
}
cout << "time taken to call clock: " << NTESTS * res / ncalls << " millisecs\n" ;
}
/*
>g++ -O3 -march=pentium4 -Wall -std=c++98 clock_time.cpp && ./a.out
resolution of libc clock: 7.8125 millisecs
time taken to call clock: 0.00506795 millisecs
*/since the clock ticks are at discrete intervals, there can be an error of upto one clock tick in a single measurement. for example,
|--------|S+++++++|++++++++|++++++++|++++++++|++++++++|+++++++E|--------|--------| 5 ticks
|--------|-------S|++++++++|++++++++|++++++++|++++++++|++++++++|+++++E--|--------| 6 ticks
we can clearly make this out in the difference between the min and max times posted earlier. to minimize the statistical expectation of error
a. the time measured should be an order of magnitude higher than the resolution of the clock.
b. run the test several times; the average should then give a better indication
the time taken to call clock one or two times would be negigible in comparison.
if you are attempting to profile your code for identifying and removing performance bottlenecks, you should use a standard profiler. a good profiler would (approximately) adjust for the profiling overhead while reporting time information.
guys your posts are very helpful {specially with vijayan121's posts i try to follow...}
Some more questions:
1st) where can i find: mt19937
2nd) i just want to test a structure for a university project.... can a profiler help me?If yes, can you suggest me an easy-to-learn one....
3rd) except from the time taken is it possible to see how much space is consumed?
{because i have the following incident testing with 10 million elements it finishes the job rather fast, but when i go to 50 million elements the sytem stops repsonding... i guess it isn't a matter of computer power, but of ram space....
Thank you all for your help :)
Yet my request for basic information about your setup goes unheeded - oh well, enjoy.
n.aggel> where can i find: mt19937
the one i have used is from the boost libraries. http://www.boost.org/index.htm
n.aggel> ... can a profiler help me? If yes, can you suggest me an easy-to-learn one....
n.aggel> .. is it possible to see how much space is consumed? ...
Salem>> Which OS / Compiler / type of machine?
if you had given that information, Salem would have given you an answer.
Yet my request for basic information about your setup goes unheeded - oh well, enjoy.
oops sorry {didn't do it on purpose}:
OS:
ubuntu and windows {it depends on the solution proposed, i prefer to end up with platform neutral applications}
Compiler:
g++
type of machine:
intel p4 3.2GHz, 1GB of ram
thanks again!
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.