How to test efficiency of different algorithms

Question

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");
    }
}

score 2 · Answer 1 · edited May 23 '17 at 10:29

2

Well you can use the time command. A good explanation can be found here. First compile the source code into executable binary. Then run time ./executable_code and do not take your decision based on one or two tests. Good luck!

edited May 23 '17 at 10:29

Community

1
1

answered Aug 14 '16 at 06:52

Parnab Sanyal

749
5
19

Emilien · Answer 2 · 2016-08-14T07:14:24.067

There are many ways to test depending on what you mean with efficiency. The simplest is Parnab's advice to use the time command. However if you really want to understand what happens it might not be enough.

The perf tool allows you to access much more metrics such as the number of cycles, the number of cache hit/miss for the different level of caches, the number of mispredicted branches and so on. There is also an API to access perf tools from C but it's not very well documented. Other tools exist such as PAPI but I don't know how they differ from each other.

Moreover, since sorting algorithms are (I guess) data-dependent (which means they do not execute the same number of instructions depending on which array they sort) you need to compare them on the same inputs and it might not be very easy since some may be better at sorting almost sorted arrays for instance.

The most important point is execution time. And it's much better to access more metrics as you say. — Hel, Aug 14 '16 at 07:13

David C. Rankin · Accepted Answer · 2016-08-14T07:52:28.447

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.

How to test efficiency of different algorithms

3 Answers3