本文轉(zhuǎn)載自徐飛翔的“C語言中內(nèi)循環(huán)和外循環(huán)的位置可能產(chǎn)生性能上的區(qū)別”
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。
在圖像處理相關(guān)的代碼中，我們經(jīng)常有類似于以下的代碼，去遍歷多維數(shù)組（張量）的每一個(gè)元素：
#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];效果一致的，然而從性能上來說是否是一致的呢？答案是不是的，要看程序的編譯優(yōu)化程度。我們會(huì)發(fā)現(xiàn)，當(dāng)循環(huán)變量處于內(nèi)循環(huán)和外循環(huán)時(shí)，其性能是不一樣的，即便是運(yùn)算結(jié)果一致。
我們知道不管是一維數(shù)組還是多維數(shù)組，在內(nèi)存中都是線性排列的，以二維數(shù)組為例子，為了能將二維的數(shù)組拉成一維的，一般需要考慮編譯器在編譯代碼時(shí)，其在內(nèi)存中是行優(yōu)先（row-major）排列還是列優(yōu)先（colum-major）排列的。如下圖所示，如果一個(gè)數(shù)組是行優(yōu)先排列的，那么其在連續(xù)內(nèi)存上的排列順序如紅色線的順序。舉個(gè)例子，比如現(xiàn)在有個(gè)數(shù)組int vars[3][3]，如果是行優(yōu)先排列的，那么有：（===的意思是等價(jià)， (vars+i)表示對(duì)以vars作為數(shù)組指針的前提下，偏移i個(gè)元素的地址，而*(vars+i)是對(duì)其進(jìn)行取內(nèi)容。）
vars[0, 0] === *(vars+0);
vars[0, 1] === *(vars+1);
vars[1, 0] === *(vars+3);
==>
vars[i, j] === *(vars+3*i+j)如果是列優(yōu)先排列呢，則是
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)
到這里為止都好理解，不過后續(xù)我們需要理解的一點(diǎn)是，我們現(xiàn)在跑得程序很多都不是在裸機(jī)上跑的。這里指的裸機(jī)就是沒有操作系統(tǒng)的計(jì)算機(jī)，比如單片機(jī)等，或者是沒有任何操作系統(tǒng)的其他CPU。在操作系統(tǒng)上跑程序，那么我們的程序的內(nèi)存空間其實(shí)都是虛擬內(nèi)存空間，是一種邏輯地址，其和物理的內(nèi)存位置是沒有必然關(guān)聯(lián)的，需要受到操作系統(tǒng)的控制。采用虛擬內(nèi)存有很多好處，其中最明顯的就是：
- 不需要考慮不同程序之間的相對(duì)地址偏移，每個(gè)程序都有其獨(dú)自的內(nèi)存空間，其地址范圍都是從0到系統(tǒng)定義的最大值
max_mem。 - 虛擬內(nèi)存可以看成是一個(gè)巨大的線性內(nèi)存空間，不需要考慮內(nèi)存不足的情況，因?yàn)楫?dāng)內(nèi)存不足的情況或者需要訪問的數(shù)據(jù)不在內(nèi)存上時(shí)，就發(fā)生了缺頁錯(cuò)誤（page fault），操作系統(tǒng)會(huì)自動(dòng)進(jìn)行“換頁”（paging），將物理內(nèi)存暫時(shí)不用了的內(nèi)存頁保存到存儲(chǔ)空間巨大的硬盤上，然后把需要讀取的內(nèi)存加載到內(nèi)存上。在這種情況下，可以把整個(gè)硬盤都看成是一個(gè)可以換入和切出的內(nèi)存（雖然速度很慢，沒法和真正的內(nèi)存比）
虛擬內(nèi)存的細(xì)節(jié)太多，是操作系統(tǒng)設(shè)計(jì)的一個(gè)主要概念，其他細(xì)節(jié)需要參考其他書籍，比如[1,2]。我們?cè)谶@里需要知道的是，我們程序中隨時(shí)可能遇到數(shù)據(jù)在內(nèi)存中找不到的事情發(fā)生，這個(gè)時(shí)候就會(huì)發(fā)生換頁的操作，從硬盤中加載數(shù)據(jù)到內(nèi)存（IO操作）是非?；〞r(shí)間的，因此很多程序的瓶頸都會(huì)在此。我們這里的關(guān)鍵點(diǎn)也正是在此。
在一個(gè)以行優(yōu)先排序的編譯器上，每一行的數(shù)據(jù)在內(nèi)存地址上都是比較接近的，而列數(shù)據(jù)的地址總是相差著sizeof(data_type) * N，其中N NN是每一行的元素?cái)?shù)量。這就導(dǎo)致每一行的數(shù)據(jù)可能是處于同一個(gè)內(nèi)存頁幀（page frame）上的，而每一個(gè)列的數(shù)據(jù)處于不同的頁幀上。在以行優(yōu)先排序的編譯器上，如果外循環(huán)是列索引，內(nèi)循環(huán)是行索引，有可能會(huì)發(fā)生頻繁地進(jìn)行缺頁，換頁的操作（準(zhǔn)確地說是n*m次），嚴(yán)重影響程序的性能。當(dāng)然，這里只是可能，具體情況和你的數(shù)組大小，系統(tǒng)的頁大小設(shè)置等有關(guān)。（這里的缺頁特別在物理內(nèi)存比較小的時(shí)候更為嚴(yán)重）
這里舉個(gè)代碼例子，說明性能上的差別。
考慮代碼：
# 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;
}這兩個(gè)代碼除了索引的順序不同（相當(dāng)于內(nèi)外循環(huán)調(diào)換）之外，其他別無差別。我們?yōu)榱朔乐咕幾g器對(duì)代碼進(jìn)行優(yōu)化，影響分析，我們采用-O0編譯參數(shù)以去掉任何gcc的優(yōu)化。（其實(shí)用其他優(yōu)化等級(jí)效果也是類似的，讀者可以自行嘗試，并且用指令gcc -O0 -S code1.c觀察分析其匯編代碼。）
gcc -O0 code1.c
/usr/bin/time -v ./a.out我們用/usr/bin/time分析程序的運(yùn)行時(shí)間，我們有這兩者的運(yùn)行時(shí)間分別為：
code 1的運(yùn)行時(shí)間為2.05s
而code 2的時(shí)間則變成了5.68s，性能明顯差code 1很多。
但是如果我們把數(shù)組的大小從20000改成200會(huì)怎么樣呢？我們發(fā)現(xiàn)其性能將不會(huì)有明顯區(qū)別了，就是因?yàn)槌叽绱笮〉牟煌绊懥隧搸膿Q頁過程。
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.