Hel Hel - 3 months ago 8
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");
}
}

Answer

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.