Which OS / Compiler / type of machine ?
Salem
Posting Sage
11,531 posts since Dec 2005
Reputation Points: 5,862
Solved Threads: 953
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;
Ancient Dragon
Retired & Loving It
30,046 posts since Aug 2005
Reputation Points: 5,662
Solved Threads: 2,342
#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
*/
vijayan121
Posting Virtuoso
1,606 posts since Dec 2006
Reputation Points: 1,159
Solved Threads: 287
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.
Ancient Dragon
Retired & Loving It
30,046 posts since Aug 2005
Reputation Points: 5,662
Solved Threads: 2,342
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.
vijayan121
Posting Virtuoso
1,606 posts since Dec 2006
Reputation Points: 1,159
Solved Threads: 287
Yet my request for basic information about your setup goes unheeded - oh well, enjoy.
Salem
Posting Sage
11,531 posts since Dec 2005
Reputation Points: 5,862
Solved Threads: 953
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.
vijayan121
Posting Virtuoso
1,606 posts since Dec 2006
Reputation Points: 1,159
Solved Threads: 287
vijayan121
Posting Virtuoso
1,606 posts since Dec 2006
Reputation Points: 1,159
Solved Threads: 287
