sob.c

#include <err.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define CACHE_LINES 64

const char *PROG_NAME;

void usage(void) {
    fprintf(stderr,
            "usage: %s <array-fast | array-slow | linked-list> <size>\n",
            PROG_NAME);
    exit(1);
}


/* Get current time in micro-seconds */
int64_t timestamp(void) {
    struct timeval tv;
    if (gettimeofday(&tv, NULL) != 0)
        errx(1, "gettimeofday");
    return tv.tv_sec * 1000000 + tv.tv_usec;
}

/* Caller responsible for calling `free()`. */
int64_t* array_init(size_t size) {
    int64_t t1 = timestamp();
    int64_t *elems;

    /* Initialize an array [1, 2, 1, 2, 1, 2, ...] of length `size`. */
    {
        elems = malloc(sizeof(*elems) * size);
        if (elems == NULL)
            errx(1, "malloc");


        for (size_t i = 0; i < size; ++i) {
            elems[i] = 1 + (i % 2);
        }
    }

    int64_t t2 = timestamp();
    fprintf(stderr, "initialization: %" PRId64 " us\n", t2-t1);
    return elems;
}

void array_fast(size_t size) {
    int64_t *elems = array_init(size);

    /* Compute sum element-by-element sequentially. */
    {
        int64_t t1 = timestamp();
        int64_t sum = 0;
        for (size_t i = 0; i < size; ++i)
            sum += elems[i];
        int64_t t2 = timestamp();
        fprintf(stderr, "sum (%" PRId64 "): %" PRId64 " us\n", sum, t2-t1);
    }

    free(elems);
}

void array_slow(size_t size) {
    int64_t *elems = array_init(size);

    /* Compute sum element-by-element, but with cache-line-sized gaps
     * between array accesses. */
    {
        int64_t t1 = timestamp();
        int64_t sum = 0;

        for (size_t j = 0; j < CACHE_LINES; ++j)
            for (size_t i = j; i < size; i += CACHE_LINES)
                sum += elems[i];


        int64_t t2 = timestamp();
        fprintf(stderr, "sum (%" PRId64 "): %" PRId64 " us\n", sum, t2-t1);
    }

    free(elems);
}

void linked_list(size_t size) {
}

int main(int argc, char **argv) {
    PROG_NAME = argv[0];
    if (argc < 3)
        usage();

    size_t size = atoll(argv[2]);

    if (strcmp(argv[1], "array-fast") == 0)
        array_fast(size);
    else if (strcmp(argv[1], "array-slow") == 0)
        array_slow(size);
    else if (strcmp(argv[1], "array-unrolled") == 0)
        array_slow(size);
    else if (strcmp(argv[1], "linked-list") == 0)
        linked_list(size);
    else
        usage();

    return 0;
}