trick

locality.c

// Locality test.
//
// See:
// http://en.wikipedia.org/wiki/Locality_of_reference#Matrix_multiplication

#include <string.h>

#define N 1000

int a[N][N], b[N][N], c[N][N];


void m1()
{
    int i, j, k;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            for (k = 0; k < N; k++)
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
}

void m2()
{
    int i, j, k;

    for (i = 0; i < N; i++)
        for (k = 0; k < N; k++)  // <- b[k][j] can be cached.
            for (j = 0; j < N; j++)
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
}


int main(int argc, char *argv[])
{
    int i, j;

    memset(c, 0, N * N);

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++) {
            a[i][j] = 3;
            b[i][j] = 5;
        }

    if (argc > 1 && argv[1][0] == '1')
        m1();
    else
        m2();

    return 0;
}