Cache effects
- C course
- Advanced
- Lesson 74/83
- 5 min
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]).
Practice 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", ...).
Starter code
#include <stdio.h>
#define N 4
// Write sum_row_major: outer i inner j, sum a[i][j]
// Write sum_col_major: outer j inner i, sum a[i][j]
// main: declare 4x4 array, call both and print results
int main(void) {
return 0;
}Sample 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;
}Expected output
satır: 136 sütun: 136
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Match cache concepts
| Term | Meaning |
|---|---|
cache line |
Consecutive data |
row-major |
Cache friendly |
column-major |
Cache hostile |
locality |
Near access |
2 Which access pattern is cache friendly?
- Column-major
- Row-major Correct answer
- Random access
- Reverse order
Explanation: Row-major accesses consecutive memory; it uses cache well.
3 Row-major access
for (int j = 0; j < N; j++) sum += a[____][j];for (int j = 0; j < N; j++) sum += a[i][j];Explanation: a[i][j] is row-major access; cache friendly.