[c++] 為什麼我的程序在循環8192個元素時很慢?



Answers

下面的測試已經用Visual C ++編譯器完成了,因為它被默認的Qt Creator安裝使用(我猜沒有優化標誌)。 當使用GCC時,Mystical的版本和我的“優化”代碼沒有太大的區別。 因此,結論是編譯器優化比人類更關心微觀優化(最後是我)。 我留下我的答案的其餘部分供參考。

以這種方式處理圖像效率不高。 最好使用單維數組。 處理所有像素是在一個循環中完成的。 隨機訪問點可以使用:

pointer + (x + y*width)*(sizeOfOnePixel)

在這種情況下,最好計算並緩存三個水平像素組的總和,因為它們每次使用三次。

我做了一些測試,我認為這是值得分享的。 每個結果是五次測試的平均值。

user1615209的原始代碼:

8193: 4392 ms
8192: 9570 ms

神秘的版本:

8193: 2393 ms
8192: 2190 ms

兩次使用一維數組:第一次為水平和,第二次為總和和平均。 用三個指針進行兩遍尋址,只有這樣的增量:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

兩次使用一維數組並進行如下處理:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

一次通過緩存水平只提前一行,所以他們留在緩存中:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

結論:

  • 沒有使用幾個指針和增量的好處(我認為它會更快)
  • 緩存水平和數比計算它們好幾次。
  • 兩次通過不是三倍,只有兩次。
  • 同時使用單個傳遞和緩存中間結果可以達到3.6倍的速度

我相信可以做得更好。

注意請注意,我寫了這個答案來解決一般性能問題,而不是Mystical的優秀答案中解釋的緩存問題。 一開始它只是偽代碼。 我被要求在評論中做測試...這是一個完全重構的測試版本。

Question

這是來自該程序的摘錄。 矩陣img[][]的大小為SIZE×SIZE,初始化為:

img[j][i] = 2 * j + i

然後,你創建一個矩陣res[][] ,並且這裡的每個字段都是img矩陣中圍繞它的9個字段的平均值。 為簡單起見,邊框保留為0。

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

這就是這個程序的全部內容。 為了完整起見,以下是以前的內容。 之後沒有代碼。 正如你所看到的,這只是初始化。

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

基本上,當SIZE是2048的倍數時,這個程序很慢,例如執行時間:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

編譯器是GCC。 據我所知,這是因為內存管理,但我對這個主題並不太了解,這就是我在這裡問的原因。

如何解決這個問題會很好,但如果有人能解釋這些執行時間,我已經夠快樂了。

我已經知道malloc / free,但問題不在於使用的內存量,而僅僅是執行時間,所以我不知道這會有什麼幫助。




Related