C++代碼的緩存優化

這似乎是一種開放式的，但我在爲多個處理器和緩存優化一塊C++代碼時遇到了問題。C++代碼的緩存優化

比多處理器更重要的是緩存：我遍歷2嵌套循環

for(int i=0; i<n; i++){ 
    //do a little something here with a single array 
    for(int j=0; j<whoaAnotherArray[n].size(); j++){ 
    * access array[i][j] and otherArray[i][j] and store in a variable 
     - an example is: "int x = array[i][j] + otherArray[i][j]" 
    * compare variable to some other array[index calculated from i and j] 
     - an example is: "if (x < yetAnotherArray[i*n+j]){ //do something to yetAnotherArray }" 
    } 
}

我的陣列（陣列和otherArray）是非常大大小。 n是它們的大小。

有沒有辦法讓這個緩存更友好？我已經開始使用鏈接列表，這對緩存來說很糟糕。我在某處讀到我的訪問命令[i] [j]也是緩存有效的。

FWIW，這是一個負重循環檢測算法的一部分。

我在想也許因爲我的數組非常龐大（它們是整數btw數組），最好是將它們打散一點以便它們更好地適應緩存？但我不確定這是對的還是如果是，如何去做。

我也開始使用openmp。我一直在做的唯一事情是加入

#pragma omp parallel for

之前的權利for循環，我得到體面的利用。我想了解如何更好地使用並行性，但除了代碼中的循環之外，我不確定我能做什麼。而且一直都是這樣：我試圖保持緩存的友好。

來源

2010-12-02 Sam

究竟是什麼你想在這裏實現什麼？我相當確信有一個比O（N²）更有效的解決方案。 – jwueller 2010-12-02 22:16:48

通常一個好的編譯器（特別是當你明確地問他時）在循環中插入* precache *指令。 – ruslik 2010-12-02 22:17:35

@elusive道歉，它不是O（N^2），但O（N），因爲我的內部循環不是N.我將解決這個問題... @ruslik我使用g ++，我該怎麼做？ – Sam 2010-12-02 22:19:04

緩存使用改進的一種可能性是修改訪問模式array和otherArray。當您讀取array[i][j]時，您的機器當然會將一行「內存」移動到緩存中。當你讀otherArray[i][j]時，你的機器當然會將一行「內存」移動到緩存中。有可能讀取第二行'第一行必須從緩存刷新到RAM中。然後，通過讀取yetAnotherArray中的值，可以使情況更糟（可能）。

實際發生的事情很大程度上取決於同時發生了什麼，高速緩存和其他任何正在執行的操作還有什麼。這可能非常難以弄清楚。

如果您的（主導）數組訪問模式要求同時從兩個（或全部3個）數組中請求element[i][j]，那麼您希望安排一些事物，使它們位於同一行內存中，。一種方法是將3個陣列合併爲一個m*n*3陣列，其中superArray[i][j][1]與superArray[i][j][2]相鄰，其位於superArray[i][j][3]的旁邊，其中陣列的3個平面各代表一個原始陣列。當然，這隻有在索引訂購權的時候纔有用，所以給它比我更多的思考。

最後：

這可能會改變你的優雅程序轉換成意大利麪條爛攤子 - 但這是一個很小的代價爲提高速度！
''我的意思是無論您的平臺從內存加載到高速緩存一次去塊。
谷歌周圍循環平鋪 和條帶開採。編譯器是不是很好，在這個還沒有和任何幫助，你可以提供應該獎勵改善執行速度。

來源

2010-12-02 23:08:30

有一個名爲Cachegrind（Valgrind插件）的程序，可以幫助您分析代碼對虛擬緩存的執行情況。我會和你一起看看你的代碼如何處理你的CPU的緩存。（我已經使用它一段時間了，所以我不記得它是否可以自動檢測你的CPU的緩存屬性，你可能需要給它確切的CPU緩存參數。）

你也可以嘗試一些優化，理想情況下，你的編譯器或應該做的事情：

1）更換這行：

for(int j=0; j<whoaAnotherArray[n].size(); j++){

有：

2）創建的指針進入該陣列在外環：在循環的第一指針訪問

int* pArray = array[i] - 1; 
int* pOtherArray = pOtherArray[j] - 1;

和使用preincrements：

int x = *(++pArray) + *(++pOtherArray);

（是的，我知道這是醜陋的。 我知道編譯器應該爲你做這個。但是在幾個月前，我發現這對Linux上的gcc 4.3（？）有所幫助。 YMMV）

3）如果有什麼方法可以重構代碼，以便一次循環遍歷array，然後在第二遍循環遍歷otherArray，然後嘗試執行此操作。似乎不太可能在你的情況下，但我不知道。重點是，您希望一次將內存訪問儘量集中到一個數組。

祝你好運。

來源

2010-12-02 22:55:44

閱讀香草薩特這2篇文章特別是第一個

http://www.ddj.com/go-parallel/article/showArticle.jhtml?articleID=217500206

http://ddj.com/architect/208200273

來源

2010-12-02 23:40:42 David

C++代碼的緩存優化

回答

相關問題