CS:APP -「第 6 章：記憶體階層」 Cache Locality: 「在處理大數據陣列時，Row-major 和 Column-major 的存取順序對效能有什麼影響？」

Q

Cache Locality: 「在處理大數據陣列時，Row-major 和 Column-major 的存取順序對效能有什麼影響？」

A 

• Row-major (連續): 當 CPU 讀取 arr[0][0] 時，會把後面的 arr[0][1], arr[0][2] 一起放進 Cache Line (通常 64 bytes)。下一次迴圈要用時，資料已經在 Cache 裡了（Cache Hit）。

• Column-major (跳躍): 存取 arr[0][0] 後，下一個要拿 arr[1][0]。這兩個元素在記憶體中隔了 $10000 \times 4$ bytes，遠超過 Cache Line 的長度。CPU 必須重新去主記憶體抓資料（Cache Miss），導致速度大幅下降。

什麼順序會有差？

在現代 CPU 架構中，當你從記憶體讀取一個位元組時，硬體並不會只抓那一個位元組，而是抓取一整塊連續的資料，這被稱為 Cache Line（通常是 64 Bytes）。

## 1. Row-major (列優先) 存取：Cache Friendly

C 語言的二維陣列在記憶體中是橫向連續存放的。如果你用 row-major 順序存取（外迴圈是 i, 內迴圈是 j）

## 2. Column-major (行優先) 存取：Performance Killer

如果你把迴圈順序對調（外迴圈是 j, 內迴圈是 i）：

每次存取 array[i][j] 之後，下一個要抓的是 array[i+1][j]。在記憶體中，這兩個位址隔了「一整列」的距離。Cache Line 抓進來的資料還沒用到就被踢出去了。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N 10000 // 10000 x 10000 的矩陣，約佔 400MB 記憶體

// 分配在 Heap 以免 Stack Overflow

int (*arr)[N];

int main() {

arr = malloc(sizeof(int[N][N]));

if (!arr) return 1;

struct timespec start, end;

double cpu_time_used;

// --- 測試 1: Row-major (順著記憶體位址存取) ---

clock_gettime(CLOCK_MONOTONIC, &start);

long long sum = 0;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

sum += arr[i][j];

}

}

clock_gettime(CLOCK_MONOTONIC, &end);

cpu_time_used = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("Row-major (順向) 耗時: %f 秒\n", cpu_time_used);

// --- 測試 2: Column-major (跳躍記憶體位址存取) ---

clock_gettime(CLOCK_MONOTONIC, &start);

sum = 0;

for (int j = 0; j < N; j++) { // 注意：這裡迴圈對調了

for (int i = 0; i < N; i++) {

sum += arr[i][j];

}

}

clock_gettime(CLOCK_MONOTONIC, &end);

cpu_time_used = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("Column-major (跳向) 耗時: %f 秒\n", cpu_time_used);

free(arr);

return 0;

}

r@ubuntu-server:~/leaarning$ gcc -O0 cache_test.c -o cache_test

r@ubuntu-server:~/leaarning$ ./cache_test 

Row-major (順向) 耗時:   0.260539 秒

Column-major (跳向) 耗時: 0.429585 秒