Expert: Ralph McArdell - 9/20/2010

Question
I have to make efiiciency check for diffrent traversal like
preorder,inorder and postorder.

I have make a switch case for user selection and difffrent
proceducers for the traversal and these procedurers are
recursive.

My Problem is that when i calculate time in the procedure
they calculate and print in vrious time i.e how many time it
does recurstion. And i calculate it in switch case it gives
start time and end time same can u help me out to solve this
??

Answer
I cannot answer this for sure as you fail to mention what you are using to obtain the times, nor the code in case you made a silly mistake. Note also that timing function execution times is a trickier business than you would think.

First off you need to consider the characteristics of the start and end times you are obtaining:

- what is the returned times' resolution?

If the timed code takes less than the resolution of the time values to execute then the difference between end and start times will be zero.

For example the C/C++ library time function returns an unsigned integer value that is typically the number of seconds elapsed since some starting point called the epoch. A modern computer can execute a heck of a lot of code in one second. The C/C++ library clock function returns a value with a resolution of CLOCKS_PER_TICK - which may have values of say 1000 (millisecond resolution) or 1000000 (microsecond resolution) or some other value, depending on the library implementation.

Anther point here is that just because you have some supposed resolution, what is the effective useful resolution? If say the value returned by a clock library function implementation with a CLOCKS_PER_TICK value of 1000000 jumps by a minimum of 1000 each time then it effectively only has millisecond resolution and not the supposed microsecond resolution indicated by the CLOCKS_PER_TICK value.

- what does the time measure?

There are two main things a time function can measure - real elapsed time - ticks since machine or process or thread started, actual date and time - sometimes called wall clock time. Or it can measure time used by a process or thread - that is it does not count the time the process or thread is suspended for some reason - waiting for a signal or I/O or because some other thread or process was scheduled to execute. Note that different implementations of the clock C/C++ library function measure different things - for an example see the code and results at the end of an old AllExperts answer of mine at:

   http://en.allexperts.com/q/C-1040/time-milliseconds-Windows.htm

Next we have to consider the sort of time your code would take to execute. Very often single executions of functions are short, especially for small data sets, and so may not take enough time to register for the effective resolution of your timing functions. Even if the calls do register a time then unless they are quite large values they are likely to fluctuate significantly if you are measuring elapsed, wall clock style times as such things as other threads executing will be counted, Even if you are measuring thread or process running time you will get variations due to issues such as memory access times differing due to differing states of system memory caches.

To make function call times more significant repeat them - say 1000 or 1000000 or more times. If your functions' execution times depend on data set size then use a larger data set. However if you are testing various algorithms then maybe you need to use several data set sizes for each algorithm to see how they perform as data set size increases. You might like to vary the number of iterations for tests so that quick running small data set tests have a significant time and large data sets do not take too long to execute. You can of course calculate the time per iteration by dividing the duration for all iterations by the number of iterations.

Be careful if you are using optimised code that the compiler does not remove any such loops entirely - this is probably less likely if you call a function in the loop as the compiler is less likely to know of any side effects the call may perform such as writing output or updating a global variable.

To try and mitigate the effects of caching run the tests more than once and ignore the first (couple maybe?) set of figures.

Finally collect many sets of timing data over many executions and average the results.

Oh, here is a useful thread of discussion on nanosecond timing resolution:

   http://stackoverflow.com/questions/275004/c-timer-function-to-provide-time-in-na...

If you need more serious code profiling then you should look at using profiling tools such as gprof (for GCC/ G++) or those that may be provided for your compiler or operating system (and possibly processor).

   http://en.wikipedia.org/wiki/List_of_performance_analysis_tools

Hope you find this of use.