944,126 Members | Top Members by Rank

Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 1774
  • C++ RSS
You are currently viewing page 1 of this multi-page discussion thread
Aug 11th, 2007
0

Measuring Performance...

Expand Post »
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.
Similar Threads
Reputation Points: 23
Solved Threads: 12
Posting Whiz in Training
n.aggel is offline Offline
202 posts
since Nov 2006
Aug 11th, 2007
0

Re: Measuring Performance...

Which OS / Compiler / type of machine ?
Team Colleague
Reputation Points: 5862
Solved Threads: 950
Posting Sage
Salem is offline Offline
7,164 posts
since Dec 2005
Aug 11th, 2007
0

Re: Measuring Performance...

use clock() to get the time before starting the algorithm and again afterwards, then subtract the two times. For example
C++ Syntax (Toggle Plain Text)
  1. clock_t start = clock();
  2. // do something, such as call a function
  3. clock_t end = clock();
  4. clock_t diff = end - start;
Sponsor
Team Colleague
Featured Poster
Reputation Points: 5608
Solved Threads: 2283
Retired and Enjoying Life
Ancient Dragon is online now Online
21,961 posts
since Aug 2005
Aug 11th, 2007
0

Re: Measuring Performance...

C++ Syntax (Toggle Plain Text)
  1. #include <algorithm>
  2. #include <vector>
  3. #include <iostream>
  4. #include <ctime>
  5. #include <iterator>
  6. #include <boost/random.hpp>
  7. #include <limits>
  8. using namespace std ;
  9. using namespace boost ;
  10.  
  11. inline double elapsed_msecs( clock_t start, clock_t end )
  12. { return double( end - start ) * 1000.0 / CLOCKS_PER_SEC ; }
  13.  
  14. int main()
  15. {
  16. // choose a reasonably good random number generator
  17. // and a distribution that mirrors the intended use of the heap
  18. mt19937 engine ; // mersene twister; fast with acceptable quality.
  19. uniform_int<> distribution( 1, 1024*1024 ) ; // just as an example
  20. variate_generator< mt19937&, uniform_int<> >
  21. generator( engine, distribution ) ;
  22.  
  23. // measure performance for a your implementation and
  24. // a reference implementation. this example measures
  25. // performance of the reference implementation in libstdc++
  26. // for two operations: make_heap O(N) and sort_heap O(N log N)
  27. enum { HEAP_SIZE = 2*1024*1024, ITERATIONS = 32 };
  28. double make_heap_total = 0.0 ;
  29. double make_heap_min = numeric_limits<double>::max() ;
  30. double make_heap_max = 0.0 ;
  31. double sort_heap_total = 0.0 ;
  32. double sort_heap_min = numeric_limits<double>::max() ;
  33. double sort_heap_max = 0.0 ;
  34.  
  35. // run the test several times
  36. for( int i=0 ; i<ITERATIONS ; ++i )
  37. {
  38. vector<int> vec ; vec.reserve(HEAP_SIZE) ;
  39. generate_n( back_inserter(vec), size_t(HEAP_SIZE), generator ) ;
  40.  
  41. clock_t start = clock() ;
  42. make_heap( vec.begin(), vec.end() ) ;
  43. clock_t end = clock() ;
  44. double duration = elapsed_msecs( start, end ) ;
  45. make_heap_total += duration ;
  46. make_heap_min = min( make_heap_min, duration ) ;
  47. make_heap_max = max( make_heap_max, duration ) ;
  48.  
  49. start = clock() ;
  50. sort_heap( vec.begin(), vec.end() ) ;
  51. end = clock() ;
  52. duration = elapsed_msecs( start, end ) ;
  53. sort_heap_total += duration ;
  54. sort_heap_min = min( sort_heap_min, duration ) ;
  55. sort_heap_max = max( sort_heap_max, duration ) ;
  56. }
  57.  
  58. cout << "resolution of libc clock: " << 1000.0 / CLOCKS_PER_SEC << " millisecs\n" ;
  59. cout << "make_heap - min: " << make_heap_min << " max: " << make_heap_max
  60. << " avj: " << make_heap_total / ITERATIONS << " millisecs\n" ;
  61. cout << "sort_heap - min: " << sort_heap_min << " max: " << sort_heap_max
  62. << " avj: " << sort_heap_total / ITERATIONS << " millisecs\n" ;
  63. }
  64.  
  65. // compile with optimizations enabled and test
  66. /*
  67. >g++ -Wall -std=c++98 -O3 -march=pentium4 -I/usr/local/include perf_metric.cpp && ./a.out
  68. resolution of libc clock: 7.8125 millisecs
  69. make_heap - min: 54.6875 max: 62.5 avj: 60.0586 millisecs
  70. sort_heap - min: 1328.12 max: 1335.94 avj: 1334.23 millisecs
  71. */
Reputation Points: 1159
Solved Threads: 285
Posting Virtuoso
vijayan121 is offline Offline
1,606 posts
since Dec 2006
Aug 11th, 2007
0

Re: Measuring Performance...

i was concerned that if i used clock, it's output would compromised by the fact that it is run from inside the program....
Reputation Points: 23
Solved Threads: 12
Posting Whiz in Training
n.aggel is offline Offline
202 posts
since Nov 2006
Aug 11th, 2007
0

Re: Measuring Performance...

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.
Sponsor
Team Colleague
Featured Poster
Reputation Points: 5608
Solved Threads: 2283
Retired and Enjoying Life
Ancient Dragon is online now Online
21,961 posts
since Aug 2005
Aug 12th, 2007
0

Re: Measuring Performance...

the time taken to call clock() would be much lower than the resolution of the clock provided by the library.
C++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. #include <ctime>
  3. using namespace std ;
  4.  
  5. int main()
  6. {
  7. const double res = 1000.0 / CLOCKS_PER_SEC ;
  8. cout << "resolution of libc clock: " << res << " millisecs\n" ;
  9. int ncalls = 0 ;
  10. enum { NTESTS = 1024 } ;
  11. for( int i=0 ; i<NTESTS ; ++i )
  12. {
  13. clock_t t1 = clock(), t2 = t1+1 ;
  14. while( clock() == t1 ) ;
  15. while( clock() == t2 ) ++ncalls ;
  16. }
  17. cout << "time taken to call clock: " << NTESTS * res / ncalls << " millisecs\n" ;
  18. }
  19. /*
  20. >g++ -O3 -march=pentium4 -Wall -std=c++98 clock_time.cpp && ./a.out
  21. resolution of libc clock: 7.8125 millisecs
  22. time taken to call clock: 0.00506795 millisecs
  23. */
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.
Last edited by vijayan121; Aug 12th, 2007 at 12:47 am.
Reputation Points: 1159
Solved Threads: 285
Posting Virtuoso
vijayan121 is offline Offline
1,606 posts
since Dec 2006
Aug 12th, 2007
0

Re: Measuring Performance...

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
Last edited by n.aggel; Aug 12th, 2007 at 6:53 am.
Reputation Points: 23
Solved Threads: 12
Posting Whiz in Training
n.aggel is offline Offline
202 posts
since Nov 2006
Aug 12th, 2007
0

Re: Measuring Performance...

Yet my request for basic information about your setup goes unheeded - oh well, enjoy.
Team Colleague
Reputation Points: 5862
Solved Threads: 950
Posting Sage
Salem is offline Offline
7,164 posts
since Dec 2005
Aug 12th, 2007
0

Re: Measuring Performance...

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.
Reputation Points: 1159
Solved Threads: 285
Posting Virtuoso
vijayan121 is offline Offline
1,606 posts
since Dec 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Two questions from a new member
Next Thread in C++ Forum Timeline: Help Me Plz!!





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC