Hel - 1 year ago 86
C Question

# How to test efficiency of different algorithms

How to test efficiency of different algorithms, for example, sorting algorithms? I try it with

`clock_gettime`
. Is it accurate? Are there any ways to solve this problem?

``````#include <stdio.h>
#include <sys/time.h>
#include <time.h>

/* compute interval: end - start */
struct timespec diff(struct timespec start, struct timespec end);

/* tested algorithm, just an example. Print 10000 lines "hello" */
void testFunc(void);

int main(void)
{
struct timespec start;
struct timespec end;

struct timespec interval ;

clock_gettime(CLOCK_REALTIME, &start);

/* call the tested algorithm */
testFunc();

clock_gettime(CLOCK_REALTIME, &end);

interval = diff(start, end);
printf("%lld.%.9ld(seconds)\n", (long long)interval.tv_sec, interval.tv_nsec);

return 0;
}

/* compute interval: end - start */
struct timespec diff(struct timespec start, struct timespec end)
{
struct timespec temp;

if ((end.tv_nsec - start.tv_nsec) < 0) {
temp.tv_sec = end.tv_sec - start.tv_sec - 1;
temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
}
else {
temp.tv_sec = end.tv_sec - start.tv_sec;
temp.tv_nsec = end.tv_nsec - start.tv_nsec;
}

return temp;
}

/* tested algorithm, just an example. Print 10000 lines "hello" */
void testFunc(void)
{
int i;

for (i = 0; i < 10000; i++) {
printf("hello\n");
}
}
``````

When testing an algorithm, it is generally a good idea to eliminate all superfluous code except for the exact algorithm at issue (e.g. isolate the algorithm itself from program startup, file read, data initialization, except for what is part of the algorithm being tested itself). That is one limitation using `time` from the command line cannot do.

The `clock_gettime` function is nice because it allows nanosecond granularity. However, the `clock ()` function can also be of use in timing algorithms. The general use for `clock()` is:

``````#include <time.h>
...
int main () {
double t1 = 0.0, t2 = 0.0;
srand (time (NULL));
...
t1 = clock ();                  /* get start time (as double) */
quicksort (a, 0, TESTLIM - 1);  /* test whatever you need     */
t2 = clock ();                  /* get end time (as double)   */
printf ("\n quick1 (%lf sec)\n", (t2-t1)/CLOCKS_PER_SEC);
``````

The difference in time returned is a rough wall time for the code execution. It isn't an exact wall time as `CLOCKS_PER_SEC` is specified as a constant value regardless of what machine it is running on. (POSIX requires that `CLOCKS_PER_SEC` equals `1000000`)

Using either `clock_gettime` or `clock` will work, but as said in the other answers, don't expect to get a good approximation based solely on 2 runs, and use plenty of iterations.

Where `clock_gettime` provides a bit more flexibility is in allowing a choice of clocks to use, e.g. `CLOCK_MONOTONIC_RAW`, `CLOCK_PROCESS_CPUTIME_ID`, etc., that depending on your needs may help protect the timer from interruption. (see `man clock_gettime` for a full discussion of the behavior of the various clocks) You can use a similar implementation with `clock_gettime`, e.g.

``````#include <stdio.h>
#include <time.h>

typedef struct timespec timespec;

timespec diff (timespec start, timespec end);

int main (void) {
timespec time1, time2, tmp;
int temp;
clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &time1);
for (int i = 0; i < 242000000; i++)
temp += temp;
clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &time2);
tmp = diff (time1, time2);
printf (" timediff %ld:%ld\n", tmp.tv_sec, tmp.tv_nsec);
return 0;
}

timespec diff (timespec start, timespec end)
{
timespec temp;
if ((end.tv_nsec - start.tv_nsec) < 0) {
temp.tv_sec = end.tv_sec - start.tv_sec - 1;
temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec - start.tv_sec;
temp.tv_nsec = end.tv_nsec - start.tv_nsec;
}
return temp;
}
``````

(example courtesy of profiling-code-using-clock_gettime, disable optimization if testing this example)

Look both over and choose the one that works best for your needs.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download