Timing Algorithms

How to Time a Running Program

If you are trying to measure accurately how long it takes a program or a part of a program to run, you really can't use a watch or anything like that. It takes some time for a program to start up, or even for it to notice when you have pressed the enter key. You need to make the program time itself.
Fortunately, that isn't very difficult. Unix and Windows both provide a little function that reads the system clock, and tells you the time down to the microsecond. At least, that is what it claims, but it is usually lying. The system clock does not tick 1,000,000 times per second, and the computer tells time by counting ticks, so the maximum accuracy of computer generated times is less than you might imagine.

Here's how it works:

Unix/BSD version (as on rabbit)

(windows is below)

You must include the library files sys/time.h and sys/resource.h to get access to the timing functions, and you need to declare a strange variable whose type is struct timeval and another whose type is struct rusage to receive the answer from the system clock. It is best to define a little function that reads the system clock, and never worry about its details again:

        #include <sys/time.h>
        #include <sys/resource.h>

        double getcputime(void)
         { struct timeval tim;
           struct rusage ru;
           getrusage(RUSAGE_SELF, &ru);
           tim=ru.ru_utime;
           double t=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;   
           tim=ru.ru_stime;
           t+=(double)tim.tv_sec + (double)tim.tv_usec / 1000000.0;   
           return t; }

Then a program that times some operation is very easy to write:

void main(void)
 { int Array[100000];
   int nitems=0;

   // read all the data into the array

   double begintime=getcputime();

   // sort the array

   double endtime=getcputime();

   printf("To sort %d ints, it took %.3f seconds\n", nitems, endtime-begintime); }

Of course, C++ programmers can use cout<< instead of printf. If you use printf, you must also #include <stdio.h>

Remember

That you share the computer with everyone else in the class. Do not ruin everything by deliberately running programs that will take more than just a couple of seconds to complete.

Windows version

(unix is above)

The idea is the same, but the function required to read the clock is much simpler. Generally this is a dis-advantage, because less information is available (for example, windows can not distinguish between time spent on system tasks and time spent directly on your program code)

#include <time.h>

double getcputime(void)
{ return clock()/(double)CLOCKS_PER_SEC; }

At the time of writing, CLOCKS_PER_SEC is defined to be 1000.