headerphoto

Sample Application

Below you see a demo we prepared for the International Conference on Compiler Construction (CC) 2012, and the full source code of the program used in this demonstration.

/*
 * Linked List Hash (ll_hash)
 *
 * ll_hash is a demo application that demonstrates some of the parallelization capabilities of
 * the sambamba framework for runtime adaptive parallelization (http://www.sambamba.org).
 *
 * It constructs two singly linked lists of lengths chosen by the user. Each element of the
 * list contains an integer, also chosen by the user (each element contains the same value).
 * A hash value is then computed for the whole list by combining the hash values of the nodes.
 *
 * The integer value in the nodes controls the runtime of the hash computation for a single node,
 * which grows exponentially in the given value.
 *
 * */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>

// =========================================================================================

typedef struct list {
    struct list *next;
    int data;
} list;

list* makeList(int elemSize, int num) {
    list *newNode = malloc(sizeof(list));
    newNode->next = num ? makeList(elemSize, num-1) : 0;
    newNode->data = elemSize;
    return newNode;
}

void freeList(list *x) {
    if (!x)
        return;

    x->data = 0;
    list *tmp = x->next;
    free(x);
    freeList(tmp);
}

// =========================================================================================

long hashElem(list *elem) {
    long n = (1 << elem->data);
    long res = 0;
    while (--n)
        res = 31 * res + n;
    return res;
}

long hashList(list *x) {
    if (!x)
        return 0;

    return hashElem(x) + 31 * hashList(x->next);
}

// =========================================================================================

long performTask(int elemSize, int listSize) {
    list *x = makeList(elemSize, listSize);
    list *y = makeList(elemSize, listSize);

    long hashX = hashList(x);
    long hashY = hashList(y);

    freeList(x);
    freeList(y);

    return hashX * hashY;
}

// =========================================================================================

struct timeval start, end;

int main(int argc, const char **argv) {
    unsigned int iterations, wpn, size;
    char lineBuf[128];

    printf("Please specify: <iterations> <work per node> <length of list>\n");

    do {
        printf(" -> ");
        if (!fgets(lineBuf, 128, stdin))
            if (feof(stdin))
                break;
            else
                continue;

        int read = sscanf(lineBuf, "%u %u %u", &iterations, &wpn, &size);

        if (read < 1) {
            printf("!!! You have to specify an iteration count...\n");
            continue;
        }

        if (read < 2) wpn = 21;
        if (read < 3) size = 10;

        double secSum = 0.0;
        printf("    ---------------------------------------------------\n");

        unsigned int i;
        for (i = 1; i <= iterations; ++i) {
            gettimeofday(&start, 0);
            long result = performTask(wpn, 1 << size);
            gettimeofday(&end, 0);
            double secs = (end.tv_sec - start.tv_sec) + 1e-6 * (end.tv_usec - start.tv_usec);
            secSum += secs;
            printf("    %2u: result: %ld, took %7.3f s\n", i, result, secs);
        }

        printf("    ---------------------------------------------------\n");
        double avgSecSum = secSum / iterations;
        printf("    Average of %u iterations: %7.3f s\n", iterations, avgSecSum);
        printf("    ---------------------------------------------------\n");
    } while (1);

    printf("\n");

    return 0;
}