緩存堆陣列性能

Question

我遇到了奇怪的內存訪問性能問題，有什麼想法？

int* pixel_ptr = somewhereFromHeap; 

int local_ptr[307200]; //local 

//this is very slow 
for(int i=0;i<307200;i++){ 
    pixel_ptr[i] = someCalculatedVal ; 
} 

//this is very slow 
for(int i=0;i<307200;i++){ 
    pixel_ptr[i] = 1 ; //constant 
} 

//this is fast 
for(int i=0;i<307200;i++){ 
    int val = pixel_ptr[i]; 
    local_ptr[i] = val; 
} 

//this is fast 
for(int i=0;i<307200;i++){ 
    local_ptr[i] = someCalculatedVal ; 
} 

試圖鞏固值本地掃描線

int scanline[640]; // local 

//this is very slow 
for(int i=xMin;i<xMax;i++){ 
    int screen_pos = sy*screen_width+i; 
    int val = scanline[i]; 
    pixel_ptr[screen_pos] = val ; 
} 

//this is fast 
for(int i=xMin;i<xMax;i++){ 
    int screen_pos = sy*screen_width+i; 
    int val = scanline[i]; 
    pixel_ptr[screen_pos] = 1 ; //constant 
} 

//this is fast 
for(int i=xMin;i<xMax;i++){ 
    int screen_pos = sy*screen_width+i; 
    int val = i; //or a constant 
    pixel_ptr[screen_pos] = val ; 
} 

//this is slow 
for(int i=xMin;i<xMax;i++){ 
    int screen_pos = sy*screen_width+i; 
    int val = scanline[0]; 
    pixel_ptr[screen_pos] = val ; 
} 

任何想法？我用cflags -01 -std = C++ 11 -fpermissive使用mingw。

update4： 我不得不說，這些是我的程序中的代碼片段，並且前後都會運行繁重的代碼/函數。掃描線塊在退出之前確實在函數結束時運行。

現在有了適當的測試程序。這是@Iwillnotexist。

#include <stdio.h> 
#include <unistd.h> 
#include <sys/time.h> 

#define SIZE 307200 
#define SAMPLES 1000 

double local_test(){ 
    int local_array[SIZE]; 

    timeval start, end; 
    long cpu_time_used_sec,cpu_time_used_usec; 
    double cpu_time_used; 

    gettimeofday(&start, NULL); 
    for(int i=0;i<SIZE;i++){ 
     local_array[i] = i; 
    } 
    gettimeofday(&end, NULL); 
    cpu_time_used_sec = end.tv_sec- start.tv_sec; 
    cpu_time_used_usec = end.tv_usec- start.tv_usec; 
    cpu_time_used = cpu_time_used_sec*1000 + cpu_time_used_usec/1000.0; 

    return cpu_time_used; 
} 

double heap_test(){ 
    int* heap_array=new int[SIZE]; 

    timeval start, end; 
    long cpu_time_used_sec,cpu_time_used_usec; 
    double cpu_time_used; 

    gettimeofday(&start, NULL); 
    for(int i=0;i<SIZE;i++){ 
     heap_array[i] = i; 
    } 
    gettimeofday(&end, NULL); 
    cpu_time_used_sec = end.tv_sec- start.tv_sec; 
    cpu_time_used_usec = end.tv_usec- start.tv_usec; 
    cpu_time_used = cpu_time_used_sec*1000 + cpu_time_used_usec/1000.0; 

    delete[] heap_array; 

    return cpu_time_used; 
} 


double heap_test2(){ 
    static int* heap_array = NULL; 

    if(heap_array==NULL){ 
     heap_array = new int[SIZE]; 
    } 

    timeval start, end; 
    long cpu_time_used_sec,cpu_time_used_usec; 
    double cpu_time_used; 

    gettimeofday(&start, NULL); 
    for(int i=0;i<SIZE;i++){ 
     heap_array[i] = i; 
    } 
    gettimeofday(&end, NULL); 
    cpu_time_used_sec = end.tv_sec- start.tv_sec; 
    cpu_time_used_usec = end.tv_usec- start.tv_usec; 
    cpu_time_used = cpu_time_used_sec*1000 + cpu_time_used_usec/1000.0; 

    return cpu_time_used; 
} 


int main (int argc, char** argv){ 
    double cpu_time_used = 0; 

    for(int i=0;i<SAMPLES;i++) 
     cpu_time_used+=local_test(); 

    printf("local: %f ms\n",cpu_time_used); 

    cpu_time_used = 0; 

    for(int i=0;i<SAMPLES;i++) 
     cpu_time_used+=heap_test(); 

    printf("heap_: %f ms\n",cpu_time_used); 

    cpu_time_used = 0; 

    for(int i=0;i<SAMPLES;i++) 
     cpu_time_used+=heap_test2(); 

    printf("heap2: %f ms\n",cpu_time_used); 

} 

未遵照優化。

地方：577.201000毫秒

heap_：826.802000毫秒

heap2：686.401000毫秒

與新的第一堆測試和刪除是2倍速度較慢。 （建議分頁？）

第二堆與重用堆數組仍然是1.2倍慢。 但我想第二個測試不是那麼實際，因爲其他代碼至少在我的情況下會運行。對於我的情況，我的pixel_ptr當然只在 程序初始化期間分配一次。

但是，如果有人有解決方案/想法加快速度，請回復！

我仍然困惑爲什麼堆寫入比堆棧段慢得多。 當然，必須有一些技巧，使堆更多的CPU /緩存flavourable。

最後更新?:

我重新審視，再次反彙編，這個時候，我突然有一個想法，爲什麼我的一些斷點 的不激活。該程序看起來可疑地更短，因此我懷疑編譯器可能會刪除我放入的冗餘僞代碼，這就解釋了爲什麼本地陣列神奇地快了許多倍。

Answer 1

下面的兩個代碼示例在運行時應該不會因編譯器設置不同而有所不同。可能您的編譯器會生成相同的代碼：

//this is fast 
for(int i=0;i<307200;i++){ 
    int val = pixel_ptr[i]; 
    local_ptr[i] = val; 
} 

//this is fast 
for(int i=0;i<307200;i++){ 
    local_ptr[i] = pixel_ptr[i]; 
} 

請嘗試增加優化設置。

Answer 2

我有點好奇，所以我做了測試，實際上我可以測量堆棧和堆訪問之間的區別。

第一個猜測是生成的程序集是不同的，但在看過之後，堆棧和堆棧實際上是相同的（這是有道理的，不應區分內存）。

如果裝配是相同的，那麼區別必須來自paging mechanism。猜測是，在堆棧上，頁面已經被分配，但是在堆上，第一次訪問會導致頁面錯誤和頁面分配（不可見，全部發生在內核級別）。爲了驗證這一點，我做了相同的測試，但首先我會在測量之前訪問一次堆。該測試給出了堆棧和堆的相同時間。可以肯定的是，我還做了一個測試，我首先訪問堆，但每隔4096個字節（每1024個int），然後是8192，因爲一個頁面通常是4096個字節長。結果是隻訪問每4096個字節也給堆和堆棧提供相同的時間，但訪問每個8192會產生差異，但不會像以前沒有訪問那麼多。這是因爲事先只有一半的頁面被訪問和分配。

所以答案是，在堆棧上，內存頁已經被分配了，但是在堆上，頁面被即時分配。這取決於OS分頁策略，但所有主要的PC操作系統可能都有類似的操作系統。

對於我使用Windows的所有測試，MS編譯器定位爲x64。

編輯：對於測試，我測量了一個較大的循環，因此每個存儲單元只有一個訪問。因爲delete ing內存可能不會取消分配頁面，並且它們已經分配給下一個循環（如果分配給下一個循環的new相同的空間）。