Code demonstrating the impact of memory access patterns on program performance

access_patterns.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#include <mach/mach_time.h>

void random_fill(int *array, int dim)
{
    for (int i = 0; i < dim; i++)
        for (int j = 0; j < dim; j++)
            array[i*dim + j] = rand();
}

int main(int argc, char *argv[])
{
    int SIZE = 10000;

    if (argc > 1) {
        SIZE = atoi(argv[1]);
    }

    srand(time(NULL));

    int *array = malloc(SIZE * SIZE * sizeof(int));

    printf("Initializing %dx%d matrix\n", SIZE, SIZE);
    random_fill(array, SIZE);

    mach_timebase_info_data_t info;
    if (mach_timebase_info(&info) != KERN_SUCCESS) return 1;

    long accum;
    int i, j;
    uint64_t start, end;

    printf("Testing access pattern A\n");

    accum = 0;

    start = mach_absolute_time();
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            accum += array[i * SIZE + j];
    end = mach_absolute_time();

    printf("Accumulator value is %ld\n", accum);
    printf("Took %.3f seconds\n", (((float)(end-start)) * info.numer / info.denom) / NSEC_PER_SEC);

    printf("Testing access pattern B\n");

    accum = 0;
    start = mach_absolute_time();
    for (j = 0; j < SIZE; j++)
        for (i = 0; i < SIZE; i++)
            accum += array[i * SIZE + j];
    end = mach_absolute_time();

    printf("Accumulator value is %ld\n", accum);
    printf("Took %.3f seconds\n", (((float)(end-start)) * info.numer / info.denom) / NSEC_PER_SEC);

    return 0;
}