sumtree/OpenMP

/*
 * The sleep command (marked  with **********************) makes all the difference with OpenMP.
 * If sleep is there, we get reasonable speedups with more threads:
 *
 * ❯ gcc -fopenmp ./sumtree.c -o sumtree
 *
 * ❯ OMP_NUM_THREADS=1 ./sumtree
 * time: 1213.934000 ms.
 * res:  16384⏎
 *
 * ❯ OMP_NUM_THREADS=16 ./sumtree
 * time: 113.490000 ms.
 * res:  16384⏎
 *
 * But without the sleep, we get major slowdowns:
 *
 * ❯ OMP_NUM_THREADS=1 ./sumtree
 * time: 2.258000 ms.
 * res:  16384⏎
 *
 * ❯ OMP_NUM_THREADS=16 ./sumtree
 * time: 39.863000 ms.
 * res:  16384⏎
 *
 * This is not true with CilkPlus (see the other file).
 */
#include <stdlib.h>
#include <stdio.h>
#include <omp.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;
        #pragma omp task shared(sl)
        sl = sumtree(t->l);

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

        #pragma omp taskwait

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


int main() {
    struct timeval t1, t2;
    double elapsedTime;
    #pragma omp parallel
    {
    #pragma omp single
    {
    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);
    }}
}