C - cache lines and association

Question

Context

Read papers about cache optimizations (association with a cache line in loops..)

The question is related to this context : array of 1024 integers.

Sizes : cpu cache 64k, cache line 32bytes, integer size : 4 bytes.

intel core 2 duo

Question

According to my cpu, 8 integers fit in a cache line.

[0,1,2,3,4,5,6,7,8,9,10,...,1023]
         ^
If I want to access 4 and go downward, 3,2,1 and 0 will be loaded already. 5,6,7 are loaded uselessly.

[0,1,2,3,4,5,6,7,8,..,1023]
               ^
If I want to access 7 and go downward, all the next elements will be in cache already. if I want to go upward, according to my cpu I will have to load another cache line immediatly after the arr[7] read.

Am I correct ?

Going further

But what tells me that arr[4] is not at an address that will cause a cache line load instead of arr[7] ? If my statement is true, we should not only consider the in-array alignment, but the whole memory alignment of the program to minimize the cache waste, right ?

Answer 1

But what tells me that arr[4] is not at an address that will cause a cache line load instead of arr[7] ?

int arrays are usually aligned on 4 byte borders (assuming int is 32 bits and byte 8 bits), so you won't know where the cache line border will be.

The lesson to learn is that you shouldn't worry about the occasional cached line being wasted (that is using 2 cache lines even though the data you need is less than 32 bytes), because that is mostly out of your hands when coding in C.

What you could worry about, if you are having performance problems, is choosing algorithms that reduces cache misses.

The typical example is loops:

int array[N][M];  // Assume N * M * sizeof (int) is much larger than the cache.

// Example 1
for (i=0; i<N; i++) {
  for (j=0; j<M; j++) {
    <do something with array[i][j]>
  }
}

// Example 2
int array[N][M];
for (j=0; j<M; j++) {
  for (i=0; i<N; i++) {
    <do something with array[i][j]>
  }
}

One of the examples will give around 8 times as many cache misses as the other because it accesses the elements in the wrong order.

Answer 2

As far as your main question is concerned, yes, you are correct in both cases.

In the second case, where arr[7] is loaded and might want to continue upwards, you should mind that probably either the compiler or some prefetching mechanism takes into account the spatial locality of this kind of data, thus improving the performance.

Going further, indeed reading some other address in the array could possibly cause a cache line load instead of arr[7] if the array isn't properly aligned in memory, but in this case alignment is not up to you, but up to compiler.