So, it turns out that memory *is* a long piece of magnetic tape.

cache.cpp

// c++ -O3 -std=c++11 cache.cpp

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

using namespace std;

const int n_cachelines=65536;
const int bytes_cacheline=64;

int main(int argc, const char * argv[]) {
    printf("Randomising...\n");
    int size = n_cachelines * bytes_cacheline;
    int* line_order_seq = new int[n_cachelines];
    int* rand_src_markers = new int[n_cachelines];
    int* line_order_rand = new int[n_cachelines];
    char* memory = (char*)malloc(size);
    
    for (int n=0; n<n_cachelines; n++) {
        line_order_seq[n] = n;
        rand_src_markers[n] = n;
    }
    
    int rand_src_id = 0;
    for (int n=0; n<n_cachelines; n++) {
        int remaining = n_cachelines-n;
        int skips_this_time=(rand()%remaining) + 1;
        for (int skips=0; skips<skips_this_time; skips++) {
            rand_src_id++;
            if (rand_src_id==n_cachelines) rand_src_id=0;
            while (rand_src_markers[rand_src_id] == -1) { // used already
                rand_src_id++;
                if (rand_src_id==n_cachelines) rand_src_id=0;
            }
        }
        line_order_rand[n]=rand_src_id;
        rand_src_markers[rand_src_id]=-1;
    }
//    for (int n=0;n<n_cachelines;n++) {
//        printf("%d -> %d\n", line_order_seq[n], line_order_rand[n]);
//    }
    printf("Go!\n");
    
    clock_t start = clock();
    for (int iter=0;iter<128;iter++) {
        for (int idx=0;idx<n_cachelines;idx++) {
            char* start = memory+line_order_seq[idx]*bytes_cacheline;
            char* working = start;
            for (int i=0; i<bytes_cacheline;i++) {
                *working = (*working)+1;
                ++working;
            }
        }
    }
    printf("Worst case, sequential: %f\n", (float(clock())-float(start))/CLOCKS_PER_SEC);
    
    start = clock();
    for (int iter=0;iter<128;iter++) {
        for (int idx=0;idx<n_cachelines;idx++) {
            char* start = memory+line_order_rand[idx]*bytes_cacheline;
            char* working = start;
            for (int i=0; i<bytes_cacheline;i++) {
                *working = (*working)+1;
                ++working;
            }
        }
    }
    printf("Worst case, random: %f\n", (float(clock())-float(start))/CLOCKS_PER_SEC);
    
    start = clock();
    for (int idx=0;idx<n_cachelines;idx++) {
        char* start = memory+line_order_seq[idx]*bytes_cacheline;
        char* working = start;
        for (int i=0; i<bytes_cacheline;i++) {
            for (int iter=0;iter<128;iter++) {
                *working = (*working)+1;
            }
            ++working;
        }
    }
    printf("Best case, sequential: %f\n", (float(clock())-float(start))/CLOCKS_PER_SEC);
    
    start = clock();
    for (int idx=0;idx<n_cachelines;idx++) {
        char* start = memory+line_order_rand[idx]*bytes_cacheline;
        char* working = start;
        for (int i=0; i<bytes_cacheline;i++) {
            for (int iter=0;iter<128;iter++) {
                *working = (*working)+1;
            }
            ++working;
        }
    }
    printf("Best case, random: %f\n", (float(clock())-float(start))/CLOCKS_PER_SEC);

}