本文轉載自徐飛翔的“C語言中內循環和外循環的位置可能產生性能上的區別”
版權聲明：本文為博主原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
在圖像處理相關的代碼中，我們經常有類似于以下的代碼，去遍歷多維數組（張量）的每一個元素：
#define LENGTH 10000
void proc(){
uint8 datas[LENGTH][LENGTH];
int i, j;
long long sum = 0;
for (i = 0; i < LENGTH; i++){
for (j = 0; j < LENGTH; j++){
sum += datas[i][j];
}
}
}其中的sum += datas[i][j];從語義上是和sum += datas[j][i];效果一致的，然而從性能上來說是否是一致的呢？答案是不是的，要看程序的編譯優化程度。我們會發現，當循環變量處于內循環和外循環時，其性能是不一樣的，即便是運算結果一致。
我們知道不管是一維數組還是多維數組，在內存中都是線性排列的，以二維數組為例子，為了能將二維的數組拉成一維的，一般需要考慮編譯器在編譯代碼時，其在內存中是行優先（row-major）排列還是列優先（colum-major）排列的。如下圖所示，如果一個數組是行優先排列的，那么其在連續內存上的排列順序如紅色線的順序。舉個例子，比如現在有個數組int vars[3][3]，如果是行優先排列的，那么有：（===的意思是等價， (vars+i)表示對以vars作為數組指針的前提下，偏移i個元素的地址，而*(vars+i)是對其進行取內容。）
vars[0, 0] === *(vars+0);
vars[0, 1] === *(vars+1);
vars[1, 0] === *(vars+3);
==>
vars[i, j] === *(vars+3*i+j)如果是列優先排列呢，則是
vars[0, 0] === *(vars+0);
vars[0, 1] === *(vars+1*3+1);
vars[1, 0] === *(vars+0*3+1);
==>
vars[i, j] === *(vars+3*j+i)
到這里為止都好理解，不過后續我們需要理解的一點是，我們現在跑得程序很多都不是在裸機上跑的。這里指的裸機就是沒有操作系統的計算機，比如單片機等，或者是沒有任何操作系統的其他CPU。在操作系統上跑程序，那么我們的程序的內存空間其實都是虛擬內存空間，是一種邏輯地址，其和物理的內存位置是沒有必然關聯的，需要受到操作系統的控制。采用虛擬內存有很多好處，其中最明顯的就是：
- 不需要考慮不同程序之間的相對地址偏移，每個程序都有其獨自的內存空間，其地址范圍都是從0到系統定義的最大值
max_mem。 - 虛擬內存可以看成是一個巨大的線性內存空間，不需要考慮內存不足的情況，因為當內存不足的情況或者需要訪問的數據不在內存上時，就發生了缺頁錯誤（page fault），操作系統會自動進行“換頁”（paging），將物理內存暫時不用了的內存頁保存到存儲空間巨大的硬盤上，然后把需要讀取的內存加載到內存上。在這種情況下，可以把整個硬盤都看成是一個可以換入和切出的內存（雖然速度很慢，沒法和真正的內存比）
虛擬內存的細節太多，是操作系統設計的一個主要概念，其他細節需要參考其他書籍，比如[1,2]。我們在這里需要知道的是，我們程序中隨時可能遇到數據在內存中找不到的事情發生，這個時候就會發生換頁的操作，從硬盤中加載數據到內存（IO操作）是非?；〞r間的，因此很多程序的瓶頸都會在此。我們這里的關鍵點也正是在此。
在一個以行優先排序的編譯器上，每一行的數據在內存地址上都是比較接近的，而列數據的地址總是相差著sizeof(data_type) * N，其中N NN是每一行的元素數量。這就導致每一行的數據可能是處于同一個內存頁幀（page frame）上的，而每一個列的數據處于不同的頁幀上。在以行優先排序的編譯器上，如果外循環是列索引，內循環是行索引，有可能會發生頻繁地進行缺頁，換頁的操作（準確地說是n*m次），嚴重影響程序的性能。當然，這里只是可能，具體情況和你的數組大小，系統的頁大小設置等有關。（這里的缺頁特別在物理內存比較小的時候更為嚴重）
這里舉個代碼例子，說明性能上的差別。
考慮代碼：
# code 1
#define LENGTH 20000
int main(){
float vector[LENGTH][LENGTH];
int i, j;
float sum = 0.0f;
for (i = 0; i < LENGTH; i++){
for (j = 0; j < LENGTH; j++){
sum += datas[i][j];
}
}
return 0;
}# code 2
#define LENGTH 20000
int main(){
float vector[LENGTH][LENGTH];
int i, j;
float sum = 0.0f;
for (i = 0; i < LENGTH; i++){
for (j = 0; j < LENGTH; j++){
sum += datas[j][i];
}
}
return 0;
}這兩個代碼除了索引的順序不同（相當于內外循環調換）之外，其他別無差別。我們為了防止編譯器對代碼進行優化，影響分析，我們采用-O0編譯參數以去掉任何gcc的優化。（其實用其他優化等級效果也是類似的，讀者可以自行嘗試，并且用指令gcc -O0 -S code1.c觀察分析其匯編代碼。）
gcc -O0 code1.c
/usr/bin/time -v ./a.out我們用/usr/bin/time分析程序的運行時間，我們有這兩者的運行時間分別為：
code 1的運行時間為2.05s
而code 2的時間則變成了5.68s，性能明顯差code 1很多。
但是如果我們把數組的大小從20000改成200會怎么樣呢？我們發現其性能將不會有明顯區別了，就是因為尺寸大小的不同影響了頁幀的換頁過程。
Reference
[1]. Bryant R E, David Richard O H, David Richard O H. Computer systems: a programmer’s perspective[M]. Upper Saddle River: Prentice Hall, 2003.
[2]. Tanenbaum A S. Structured computer organization[M]. Pearson Education India, 2016.