[[354803]]

 在我們的觀念當(dāng)中，數(shù)組成員訪問(wèn)的時(shí)間復(fù)雜度是O(1)，每個(gè)成員都可以一次定位，因此訪問(wèn)時(shí)間應(yīng)該是一樣的。

那如果我說(shuō)，現(xiàn)在有一個(gè)一千萬(wàn)元素的數(shù)組，那么訪問(wèn)第一個(gè)元素與訪問(wèn)最后一樣元素的時(shí)間是一樣的嗎?這個(gè)時(shí)候你會(huì)不會(huì)有所猶豫呢?

實(shí)際動(dòng)手驗(yàn)證

實(shí)踐是檢驗(yàn)真理的唯一手段。空想沒(méi)用，我們動(dòng)手實(shí)際測(cè)試一下。我們實(shí)現(xiàn)如下所示的代碼，在該代碼中我們創(chuàng)建一個(gè)全局的數(shù)組，數(shù)組的大小是一千萬(wàn)個(gè)元素。然后分別對(duì)第一個(gè)元素和最后一個(gè)元素賦值，并在賦值前后記錄時(shí)間。

#define BUF_SIZE 10000000 //一千萬(wàn)個(gè)元素 
 
int test_array[BUF_SIZE] = {}; 
 
int main( int argc, char* argv[] ) 
 
{ 
 
long time1; 
 
long time2; 
 
time1 = get_time(); //獲取時(shí)間，單位是納秒 
 
test_array[0] = 1; //訪問(wèn)第一個(gè)元素 
 
time2 = get_time(); 
 
printf("access first item time: %ld\n", time2-time1); 
 
time1 = get_time(); 
 
test_array[BUF_SIZE-1] = 1; //訪問(wèn)最后一個(gè)元素 
 
time2 = get_time(); 
 
printf("access last item time: %ld\n", time2- time1); 
 
return(0); 
 
} 

 完成代碼后，我們編譯運(yùn)行一下。為了得到穩(wěn)定可靠的結(jié)果，我們多運(yùn)行幾次。得到的結(jié)果如下所示。

從測(cè)試結(jié)果可以看出，訪問(wèn)最后一個(gè)元素的性能明顯要比訪問(wèn)第一個(gè)元素慢得多，有幾十倍的性能差異!

原因分析

要想搞清楚上述問(wèn)題的原因，需要更加深入的理解計(jì)算機(jī)的原理，包括可執(zhí)行程序的內(nèi)存布局、操作系統(tǒng)進(jìn)程的原理以及硬件層面的一些知識(shí)。接下來(lái)我們將逐步介紹相關(guān)內(nèi)容，抽絲剝繭，搞清楚為什么有如此明顯的性能差異。

我們知道用戶態(tài)的程序都是運(yùn)行在虛擬空間的，每個(gè)程序都有自己4GB的虛擬空間。這個(gè)虛擬空間又稱為虛擬內(nèi)存。程序的虛擬內(nèi)存并不是即刻分配的，而是按需分配。也就是說(shuō)，只有在用戶訪問(wèn)該部分內(nèi)存的數(shù)據(jù)的時(shí)候，操作系統(tǒng)才會(huì)分配對(duì)應(yīng)的物理內(nèi)存，然后將數(shù)據(jù)加載到內(nèi)存中。顯然，這種從硬盤再讀取數(shù)據(jù)的速度肯定要比直接訪問(wèn)內(nèi)存慢的多。

 

現(xiàn)代的CPU為了提高系統(tǒng)采用了多級(jí)緩存和流水線技術(shù)。CPU會(huì)根據(jù)程序的指令運(yùn)行情況將部分?jǐn)?shù)據(jù)或者指令預(yù)加載到緩存當(dāng)中，這樣接下來(lái)就可以直接從從緩存讀取數(shù)據(jù)了。

 

根據(jù)存儲(chǔ)性能金字塔的數(shù)據(jù)，從緩存讀取數(shù)據(jù)的性能是從內(nèi)存讀取性能的10倍以上。因此，如果代碼沒(méi)有規(guī)律，CPU無(wú)法預(yù)取數(shù)據(jù)和指令，那么程序的運(yùn)行效率肯定會(huì)很低。

扯了這么遠(yuǎn)，讓我們回到題目本身。由于這里數(shù)組比較大，因此當(dāng)訪問(wèn)第一個(gè)元素的時(shí)候，第一千萬(wàn)個(gè)元素肯定是沒(méi)有被預(yù)讀的，之后訪問(wèn)該數(shù)據(jù)大概率會(huì)發(fā)生缺頁(yè)中斷。所以，訪問(wèn)第一個(gè)元素和最后一個(gè)元素在性能上是有差異的。

進(jìn)一步的驗(yàn)證

有了上面的分析，我們可以再做進(jìn)一步的驗(yàn)證。比如我們可以連續(xù)兩次訪問(wèn)最后一個(gè)元素，看看兩者的區(qū)別。

int main( int argc, char* argv[] ) 
 
{ 
 
long time1; 
 
long time2; 
 
time1 = get_time(); 
 
test_array[0] = 1; 
 
time2 = get_time(); 
 
printf("access first item time: %ld\n", time2-time1); 
 
time1 = get_time(); 
 
test_array[BUF_SIZE-1] = 1; // 第一次訪問(wèn)最后一個(gè)元素 
 
time2 = get_time(); 
 
printf("access last item time: %ld\n", time2- time1); 
 
time1 = get_time(); 
 
test_array[BUF_SIZE-1] = 1; // 第二次訪問(wèn)最后一個(gè)元素 
 
time2 = get_time(); 
 
printf("access last item time: %ld\n", time2- time1); 
 
return(0); 
 
} 

 修改完代碼之后，執(zhí)行該程序。同樣，我們多次執(zhí)行該程序，確保結(jié)果穩(wěn)定。通過(guò)下面執(zhí)行結(jié)果可以看到，在第二次執(zhí)行是其時(shí)間與訪問(wèn)第一個(gè)元素相當(dāng)，已經(jīng)沒(méi)有那么明顯的差異了。

通過(guò)上面的學(xué)習(xí)，大家是不是覺(jué)得深入學(xué)習(xí)計(jì)算機(jī)原理層面的重要性了。關(guān)于更多計(jì)算機(jī)深層次的內(nèi)容，我們后面會(huì)繼續(xù)分享給大家。