2016-10-18 172 views
5

我正在測試兩個幾乎相同的代碼,其中一個for循環的差異很小。第一個使用三個循環迭代索引y,z,x而第二次迭代x,z,y具有不同運行時間的幾乎相同的代碼 - 爲什麼?

我的問題是爲什麼在用戶時間和掛鐘時間的差異?是因爲一個代碼和另一個代碼中的內存位置?

test_1.c時:

#define N 1000 

// Matrix definition 
long long int A[N][N],B[N][N],R[N][N]; 

int main() 
{ 
    int x,y,z; 
    char str[100]; 

/*Matrix initialization*/ 
    for(y=0;y<N;y++) 
     for(x=0;x<N;x++) 
     { 
      A[y][x]=x; 
      B[y][x]=y; 
      R[y][x]=0; 
     } 
/*Matrix multiplication*/ 
    for(y=0;y<N;y++) 
     for(z=0;z<N;z++) 
      for(x=0;x<N;x++) 
      { 
       R[y][x]+= A[y][z] * B[z][x]; 
      } 
exit(0); 
} 

在第二個代碼(test_2.c)的差異及其對持續循環:

for(x=0;x<N;x++) 
    for(z=0;z<N;z++) 
     for(y=0;y<N;y++) 
     { 
      R[y][x]+= A[y][z] * B[z][x]; 
     } 

如果我打印/用戶/斌/時間 - v ./test_1我得到以下數據:

Command being timed: "./test_1" 
User time (seconds): 5.19 
System time (seconds): 0.01 
Percent of CPU this job got: 99% 
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.22 

雖然/用戶/ bin/time會-v ./test_2提供了以下數據:

Command being timed: "./test_2" 
User time (seconds): 7.75 
System time (seconds): 0.00 
Percent of CPU this job got: 99% 
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:07.76 
+2

這可能是因爲您使用一種方法獲取的緩存未命中次數高於另一種。 Google「緩存數據區域」。 –

+0

嘗試使用['cachegrind'](http://valgrind.org/docs/manual/cg-manual.html)等緩存分析工具運行您的代碼。 –

回答

17

基本上,你所訪問的內存在不同的模式 - 你的第一種方法是更加友好的內存緩存,因爲你所訪問大量的數據在同一個區域,然後移動到下一塊內存等等。

如果你想要一個現實世界的比喻,想象你正在爲10條不同的道路(AJ)提供傳單,其中每個道路都有房屋號1-10。您可以交付A1,A2,A3 ... A10,B1,B2,B3 ... B10等等,或者您可以交付A1,B1,C1 ... J1,A2,B2,C2 ...等。顯然,第一種方法將會更有效率。就像在計算機內存中一樣 - 訪問最近訪問的內存「接近」的內存比跳過內存效率更高。

相關問題