c++ title標籤 - 為什麼我的程序在循環8192個元素時很慢?





link元素 html中的meta (4)


元素訪問順序照顧在那裡仍然有一些低懸的水果。 積累可以通過一種方式完成,當向右迭代時,只需要從內存中提取3個新值並進行累加。 訣竅是知道如何放下最左邊的列; 添加新列時,請記住它的值,直到它退出採樣窗口。

費用前:9讀,9加,1分後費用:3讀,3加,1分

將採樣窗口視為3x3框,您需要分別跟踪每列(1x3)。 積累一個新的列並刪除最老的一個。

該部分是一個高延遲指令,所以隱藏延遲可能是有利的,但在去那里之前,如果按常量除法並且循環展開(由編譯器)已經做了一些延遲補償,應該檢查編譯器輸出。

但是,在正確使用緩存的最顯著優化之後,這些確實是小事。

這是來自該程序的摘錄。 矩陣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,但問題不在於使用的內存量,而僅僅是執行時間,所以我不知道這會有什麼幫助。




下面的測試已經用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的優秀答案中解釋的緩存問題。 一開始它只是偽代碼。 我被要求在評論中做測試...這是一個完全重構的測試版本。




這種差異是由以下相關問題中的同一個超級對齊問題引起的:

  • 為什麼轉置一個512x512的矩陣要比轉置513x513的矩陣慢得多?
  • 矩陣乘法:矩陣大小差異小,時序差異大

但那隻是因為代碼還有其他問題。

從原始循環開始:

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;
}

首先註意到兩個內部循環是微不足道的。 他們可以展開如下:

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

這樣就留下了我們感興趣的兩個外部循環。

現在我們可以看到問題在這個問題中是一樣的: 為什麼迭代遍歷二維數組時,循環的順序會影響性能?

您正在逐列迭代矩陣,而不是逐行迭代。

為了解決這個問題,你應該交換兩個循環。

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

這完全消除了所有的非順序訪問,因此您不再在大的二權位上隨機放慢速度。

Core i7 920 @ 3.5 GHz

原始代碼:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

互換外環:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds



你是否手寫程序並將其掃描到計算機中? 這就是“helloworld.png”所暗示的。 如果是這種情況,您需要知道C ++標準(即使在其最新版本中)不需要光學字符識別,不幸的是,它不作為任何當前編譯器的可選功能包含在內。

您可能需要考慮將圖形轉換為文本格式。 任何純文本編輯器都可以使用; 使用文字處理器雖然能夠生成漂亮的打印輸出,但很可能會導致您在嘗試掃描時遇到的相同錯誤。

如果你真的冒險,你可以嘗試將你的代碼寫入文字處理器。 打印它,最好使用像OCR-A這樣的字體。 然後,將您的打印輸出並重新掃描。然後可以通過第三方OCR包運行掃描以生成文本格式。 然後可以使用許多標準編譯器之一編譯文本表單。

然而,請注意,在調試階段會產生巨大的造紙成本。





c++ performance memory-management gcc