Why calculation of fibonacci with cilk took longer?

[amit_l_]

I'm running on Linux (ubuntu) Intel I7 1600Mhz, with 4 cores. I'm using Intel compiler V14 I measured the time it tooks to calculate fibonacci with or without cilk:

int fib(int n) {

    if (n < 2) {
        return n;
    }
    else {
        int x = cilk_spawn fib(n-1);
        int y = fib(n-2);
        cilk_spawn;
        return (x+y);
    }
}


inf seqFib(int n) {

    if (n < 2) {
        return n;
    }
    else {
        int x = fib(n-1);
        int y = fib(n-2);
        return (x+y);
    }

}


long long getNanoTime() {

    struct timespec currTod;
    long long curT = 0;
    long long billion = 1000000000;

    clock_gettime(CLOCK_REALTIME, &currTod);
    curT  = currTod.tv_sec * billion ;
    curT += currTod.tv_nsec;

    return curT; 


}


int main() {
    int x = 40;
    long long start = getNanoTime();
    int res = fib(x);
    long long end = getNanoTime();
    cout << "\n cilk: " << res;


    start = getNanoTime();
    res = seqFib(x);
    end = getNanoTime();
    cout << "\n seq:" << res;

    return 0;


}

But the results are weired: With cilk the result is 427 nano and without cilk it tooks 281 nano

I run it for several times, and same results ...

[ARCH_R_Intel]

There's two errors in the listing that probably came from typing them into the forum editor (which I have trouble with too).

• There's a type "inf" that should be "int" in the declaration of seqFib.
• Function fib has cilk_spawn where it should be cilk_sync. 

Another problem is that seqFib is calling fib when it recurses, so it's essentially fully parallel.

The amount of work per cilk_spawn is extremely small, just a few integer operations, so parallel scheduling overheads will dwarf any gains from parallelism.  It's better to use seqFib for small n, something like this:

int seqFib(int n) {
    if (n < 2) {
        return n;
    }
    else {
        int x = seqFib(n-1);
        int y = seqFib(n-2);
        return (x+y);
    }
}

int fib(int n) {
    if (n < 20) {
        return seqFib(n);
    }
    else {
        int x = cilk_spawn fib(n-1);
        int y = fib(n-2);
        cilk_sync;
        return (x+y);
    }
}

The variable x in main should be declared volatile, or input from the command line.  Otherwise the compiler might optimize the entire seqFib(x) call away.  When I declared x as volatile, times got more believable.  (I'm using icc 16.0.0 Beta, because that's what was handy.)

By the way, n=40 is a bit small, and the time for the parallel run includes Cilk library startup.  Consider using n big enough that the run takes a second.