C
Cache effects
Learn CPU cache effects and data locality.
Cache effects
The CPU cache is much faster than memory; data in the same row stays in cache. Data locality keeps consecutively accessed data in the same cache line; this boosts performance.
In a two-dimensional array, row-major access (row first, then column) benefits from cache; column-major access loads a new cache line each time and is slower. In this lesson we write both methods and print the same result (136); the difference is only in speed.
Row and column sum
We define a 4x4 integer array: {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}. The sum is 1+2+...+16 = 136.
Row-major: for (i) for (j) sum += a[i][j]; — each a[i][j] is consecutive in memory. Column-major: for (j) for (i) sum += a[i][j]; — a new cache line each step. In this lesson both give 136; the real difference appears with millions of elements. Function signatures: int sum_row_major(int a[N][N]) and int sum_col_major(int a[N][N]).
Exercise Row and column sum
Define #define N 4. Write int sum_row_major(int a[N][N]) with outer i inner j and sum += a[i][j]. Write int sum_col_major(int a[N][N]) with outer j inner i and sum += a[i][j]. In main declare the array {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; call both functions and print printf("satır: %d\n", ...), printf("sütun: %d\n", ...).
Show example solution
#include <stdio.h>
#define N 4
int sum_row_major(int a[N][N]) {
int sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += a[i][j];
return sum;
}
int sum_col_major(int a[N][N]) {
int sum = 0;
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += a[i][j];
return sum;
}
int main(void) {
int a[N][N] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
printf("satır: %d\n", sum_row_major(a));
printf("sütun: %d\n", sum_col_major(a));
return 0;
}
Test yourself
-
Match cache concepts
- cache line
- Consecutive data
- row-major
- Cache friendly
- column-major
- Cache hostile
- locality
- Near access
-
Which access pattern is cache friendly?
- Column-major
- Row-major
- Random access
- Reverse order
Show answer
Row-major — Row-major accesses consecutive memory; it uses cache well.
-
Row-major access
for (int j = 0; j < N; j++) sum += a[____][j];
Show answer
for (int j = 0; j < N; j++) sum += a[i][j];
Next lesson: Loop optimization
