How to come up with a high cache miss rate example?

Question

I'm trying to come up with an example program which would have a high cache-miss rate. I thought I could try accessing a matrix column by column like so:

#include <stdlib.h>

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

    int w = 1000;
    int h = 1000;

    int **block = malloc(w * sizeof(int*));
    for (i = 0; i < w; i++) {
        block[i] = malloc(h * sizeof(int));
    }

    for (k = 0; k < 10; k++) {
        for (i = 0; i < w; i++) {
            for (j = 0; j < h; j++) {
                block[j][i] = 0;
            }
        }
    }

    return 0;
}

when I compile this with -O0 flag and run using perf stat -r 5 -B -e cache-references,cache-misses ./a.out it gives me:

 Performance counter stats for './a.out' (5 runs):

    715,463 cache-references                                      ( +-  0.42% )
    527,634 cache-misses          #   73.747 % of all cache refs  ( +-  2.53% )

0.112001160 seconds time elapsed                                  ( +-  1.58% )

which is good enough for my purposes. However if I go ahead and change the matrix size to 2000x2000 it gives:

 Performance counter stats for './a.out' (5 runs):

  6,364,995 cache-references                                      ( +-  2.32% )
  2,534,989 cache-misses          #   39.827 % of all cache refs  ( +-  0.02% )

0.461104903 seconds time elapsed                                  ( +-  0.92% )

and if I increase it even further to 3000x3000 I get:

 Performance counter stats for './a.out' (5 runs):

 59,204,028 cache-references                                      ( +-  1.36% )
  5,662,629 cache-misses          #    9.565 % of all cache refs  ( +-  0.11% )

1.116573625 seconds time elapsed                                  ( +-  0.32% )

which is strange because I would expect to get more cache miss rate as the size increases. I need something that will be as platform independent as possible. computer architecture class was long ago so any insight would be welcomed..

Notes

I said I need something relatively platform independent but still these are my specs:

• Intel® Core™ i5-2467M
• 4 GiB RAM
• 64 bit ubuntu 12.04

Answer 1

Beware of automatic prefetch in modern CPUs - it can often detect strided accesses. Perhaps try a random access pattern, e.g.:

int main(void)
{
    int i;

    int n = 1000 * 1000;

    int *block = malloc(n * sizeof(int));

    for (i = 0; i < n / 10; i++) {
         int ri = rand() % n;
         block[ri] = 0;
    }

    return 0;
}