cache.c

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

// copied from http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#C
void insertion_sort (int *a, int n) {
    int i, j, t;
    for (i = 1; i < n; i++) {
        t = a[i];
        for (j = i; j > 0 && t < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = t;
    }
}

static void print_arr(int arr[], int l)
{
    for (int i = 0; i < l; ++i) {
        printf("%d ", arr[i]);
    }
    puts(".");
}

static const int rows = 1000;
static const int cols = 1000;
// static const int length = 1027*1027;
static const int length = 1027*8;
static int **arrs;

void row_by_row()
{
    clock_t start, end;
    double elapsed_time;
    start = clock();

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            insertion_sort(arrs[rows-i-1], length);
        }
    }

    end = clock();
    elapsed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
    printf("row-by-row: %f seconds\n", elapsed_time);
}

void col_by_col()
{
    clock_t start, end;
    double elapsed_time;
    start = clock();

    for (int j = 0; j < cols; ++j) {
        for (int i = 0; i < rows; ++i) {
            insertion_sort(arrs[rows-i-1], length);
        }
    }

    end = clock();
    elapsed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
    printf("col-by-col: %f seconds\n", elapsed_time);
}

int main(int argc, char **argv)
{

    arrs = malloc(sizeof *arrs * rows);
    for (int i = 0; i < rows; ++i) {
        arrs[i] = malloc(sizeof *arrs[i] * length);
        for (int j = 0; j < length; ++j) {
            // descending order; worst case for insertion sort
            arrs[i][j] = length - j;
        }
    }

    row_by_row();
    // col_by_col();

    return 0;
}