What would algorithms be without time. Efficiency. Sure, there will always be faster machines to run algorithms on, so efficiency may not be that big a deal. Or is it? Certainly resources on a mobile device, or a probe going into space are limited. More resources = more energy requirements = bigger batteries = less room for increased functionality (i.e. higher resolution cameras).
So how do we calculate how fast an algorithm runs? Firstly, what are the properties of the speed calculation – real/user/system time? seconds/milliseconds/microseconds?
THE MOST BASIC TIMING REGIME
The most basic timing uses the time.h library, and the clock_t structure. It allows timing using seconds, and the function clock(), which provides a minimum amount of feedback.
The function clock() returns the sum of user and system time represented as CPU time in cycles, but modern standards require CLOCKS_PER_SEC to be 1000000, giving a maximum possible precision of 1 µs. Here is a sample piece of code:
clock_t start, end;
double timeshift;
start = clock();
// Perform some operation
end = clock();
timeshift = (end - start) / CLOCKS_PER_SEC;
The variable timeshift will contain the timing for the algorithm in seconds. This works okay, but if the time resolution between algorithms is finer, then chances are this will produce the same time. To calculate the value in milliseconds:
timeshift = ((end - start)*1000) / CLOCKS_PER_SEC;
TIMING WITH FINER RESOLUTION
A better measure of timing can be had using the sys/time.h library and the timeval structure. The structure looks like this:
struct {
int32_t tv_sec; /* Seconds */
int32_t tv_usec; /* Microseconds */
} ut_tv; /* Time entry was made */
struct timeval ut_tv; /* Time entry was made */
The function gettimeofday() returns the current wall clock time.
struct timeval t1, t2;
long sec, msec, tmilli;
gettimeofday(&t1,NULL);
// Perform some operation
gettimeofday(&t2,NULL);
sec = (t2.tv_sec - t1.tv_sec);
msec = (t2.tv_usec - t1.tv_usec);
tmilli = (1000 * sec) + (msec * 0.001);
printf("%ld milliseconds\n", tmilli);
This timer has 1 microsecond resolution, where 1,000,000 microseconds = 1 second.
Are there problems with this approach? Yes, some to do with NTP (network time protocol) and the fact that processes on the system can potentially change the timer, making it jump backward and forward in time.
Sometimes it returns a negative value. That’s right, your program was *so* efficient it executed before you even ran it. The problem is that gettimeofday() still can’t really tell the difference between a 2 microseconds and 3 microseconds difference. The problem lies in deriving the code. If the difference in time is derived as above, the code will work as long as the relationship t2.tv_usec > t1.tv_usec holds. However although the relationship t2.tv_sec > t1.tv_sec holds, the same is not true for microseconds. For example consider the following two timestamps:
t1 = 1370282687 434738
t2 = 1370282711 289326
Calculating the differences results in 24 for seconds, and -145412 for microseconds. A better way is to convert both elements of the structure to microseconds, before calculating the difference.
long t1_msec, t2_msec, diff;
t1_msec = (1000000 * t1.tv_sec) + t1.tv_usec;
t2_msec = (1000000 * t2.tv_sec) + t2.tv_usec;
diff = t2_msec - t1_msec;
Or, even better, use the function timersub(), also found in sys/time.h. It basically works like this:
timersub(&t2, &t1, &tv);
tMilli = (1000000 * tv.tv_sec + tv.tv_usec) / 1000;
printf("%ld milliseconds\n", tMilli);
The difference is calculated and stored in the structure tv, which can then be output in microseconds. Note that microseconds may be too fine a resolution, however dividing by 1000 gives a measure in milliseconds.
Note that on some systems (Linux, BSD) gettimeofday() has been replaced with clock_gettime() (not OSX).
