sumtree/CilkPlus

/*
 * You need GCC 7 to get CilkPlus for free. With the sleep, we get a predictable speedup:
 *
 * $ gcc -fcilkplus ./sumtree_cilk.c -o sumtree
 *
 * $ CILK_NWORKERS=1 ./sumtree
 * time: 1209.847000 ms.
 * res:  16384
 *
 * $ CILK_NWORKERS=16 ./sumtree
 * time: 74.009000 ms.
 * res:  16384
 *
 * Without the sleep we still get a (modest) speedup!

 * $ CILK_NWORKERS=1 ./sumtree
 * time: 3.223000 ms.
 * res:  16384

 * $ CILK_NWORKERS=16 ./sumtree
 * time: 2.498000 ms.
 * res:  16384
 *
 */
#include <stdlib.h>
#include <stdio.h>
#include <cilk/cilk.h>
#include <unistd.h>
#include <sys/time.h>

typedef struct treeS tree;
struct treeS {
    tree* l;
    tree* r;
    int i;
};

tree * mktree(int i) {
    if (i<=0) {
        tree* res = (tree*) malloc(sizeof(tree));
        res->l=NULL;res->r=NULL;res->i=1;
        return res;
    }
    else {
        tree* l=mktree(i-1);
        tree* r=mktree(i-1);
        tree* res = (tree*) malloc(sizeof(tree));
        res->l=l;res->r=r;res->i=1;
        return res;
    }
}

int sumtree(tree* t) {
    if (t->l == NULL)
        return t->i;
    else {
        int sl;
        sl = cilk_spawn sumtree(t->l);

        int sr;
        sr = sumtree(t->r);

        cilk_sync;

        int res = sl + sr;
        //sleep(0.1); /*            **********************           */
        return res;
    }
}


int main() {
    struct timeval t1, t2;
    double elapsedTime;
    tree* t = mktree(14);

    gettimeofday(&t1, NULL);
    int res = sumtree(t);
    gettimeofday(&t2, NULL);

    elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0;      // sec to ms
    elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0;   // us to ms
    printf("time: %f ms.\n", elapsedTime);
    printf("res:  %d", res);
}