優化此代碼塊

Question

for (int i = 0; i < 5000; i++) 
    for (int j = 0; j < 5000; j++) 
    { 
     for (int ii = 0; ii < 20; ii++) 
      for (int jj = 0; jj < 20; jj++) 
      { 
       int num = matBigger[i+ii][j+jj]; 
       // Extract range from this. 
       int low = num & 0xff; 
       int high = num >> 8; 
       if (low < matSmaller[ii][jj] && matSmaller[ii][jj] > high) 
        // match found 
      } 
    } 

該機器是x86_64,32kb L1 cahce，256 Kb二級緩存。

任何關於如何可能優化此代碼的指針？

編輯一些背景原來的問題：Fastest way to Find a m x n submatrix in M X N matrix

Answer 1

一些基本的建議：

1. 簡介它，這樣你可以學到其中的熱點是。
2. 考慮緩存局部性以及由您的循環順序產生的地址。
3. 在最內層的範圍中使用更多const，以更多地向編譯器提示。
4. 試着分解它，所以如果low測試失敗，則不計算high。
5. 試着明確地保持偏移量爲matBigger和matSmaller，最後進入一個簡單的增量。

Answer 2

最好的事情是理解代碼應該做什麼，然後檢查是否存在其他算法。

從

除了：

• ，如果你是如果匹配存在只是感興趣，請務必在// match found的位置，打破了所有3個循環。
• 確保數據以最佳方式存儲。這一切都取決於您的問題，但是，只有一個大小爲5000 * 5000 * 20的數組和一個用於訪問元素的過載operator()(int,int,int)可能更有效。

Answer 3

我想嘗試的第一件事是移動i和j環路外的ii和jj循環。

for (int ii = 0; ii < 20; ii++) 
    for (int jj = 0; jj < 20; jj++) 
    int smaller = matSmaller[ii][jj]; 
    for (int i = 0; i < 5000; i++) 
     for (int j = 0; j < 5000; j++) { 
     int num = matBigger[i+ii][j+jj]; 
     int low = num & 0xff; 
     if (low < smaller && smaller > (num >> 8)) { 
      // match found 
     } 
     } 

：您正在使用的 matSmaller爲 i和 j循環2500萬次迭代相同的元素，這意味着你（或者如果你是幸運的編譯器）能吊起他們的環路外的訪問這樣

這可能會更快（感謝訪問matSmaller陣列的次數較少），或者它可能會更慢（因爲我已經改變了訪問matBigger陣列的模式，並且有可能我已經減少了對緩存友好）。一個類似的替代方案是將ii迴路移出i和j並提升matSmaller[ii]，但將jj迴路留在內部。經驗法則是，它比較早的索引更適合緩存，用於增加內部循環中多維數組的索引值的最後。所以我們更願意修改jj和j比我們要修改ii和i。

我想嘗試的第二件事 - matBigger的類型是什麼？看起來它的值只有16位，所以請試試它們爲int和(u)int16_t。前者可能會更快，因爲對齊int訪問速度很快。後者可能會更快，因爲更多的陣列在任何時候都適合緩存。

有一些，你可以用smaller一些早期的分析考慮更高層次的東西：例如，如果它是0，那麼你不需要檢查matBigger爲ii和jj該值，因爲num & 0xff < 0永遠是假的。

要做得比「猜測事情並看看它們是否更快」，您需要知道初學者哪一行最熱，這意味着您需要一個分析器。

Answer 4

什麼是matSmaller和matBigger？ 嘗試改變它們到matBigger[i+ii * COL_COUNT + j+jj]

Answer 5

我同意史蒂夫關於重新安排你的循環有更高的計數作爲內部循環。由於你的代碼只是進行加載和比較，我相信很大一部分時間用於指針算術。做一個實驗來改變史蒂夫的回答這個：

for (int ii = 0; ii < 20; ii++) 
    { 
    for (int jj = 0; jj < 20; jj++) 
    { 
    int smaller = matSmaller[ii][jj]; 
    for (int i = 0; i < 5000; i++) 
     { 
     int *pI = &matBigger[i+ii][jj]; 
     for (int j = 0; j < 5000; j++) 
     { 
     int num = *pI++; 
     int low = num & 0xff; 
     if (low < smaller && smaller > (num >> 8)) { 
      // match found 
     } // for j 
     } // for i 
    } // for jj 
    } // for ii 

即使是在64位模式下，C編譯器並不一定要做註冊藏在心裏的一個偉大的工作。通過將數組訪問權限改爲簡單的指針增量，可以使編譯器的工作更容易，從而生成高效的代碼。

編輯：我剛剛注意到@unwind提示基本上是一樣的東西。另一個要考慮的問題是你的比較統計。低或高的比較更可能嗎？安排條件陳述，以便首先進行不太可能的測試。

Answer 6

看起來這裏有很多重複。一種優化是減少重複工作量。使用筆和紙，我展示的matBigger「我」指標迭代：

[0 + 0], [0 + 1], [0 + 2], ..., [0 + 19], 
     [1 + 0], [1 + 1], ..., [1 + 18], [1 + 19] 
        [2 + 0], ..., [2 + 17], [2 + 18], [2 + 19] 

正如你可以看到有被多次存取的位置。 此外，乘以迭代計數表明訪問內部內容：20 * 20 * 5000 * 5000或10000000000（10E + 9）次。好多啊！

因此，不要試圖加速執行10E9指令（例如執行（管道）緩存或數據緩存優化），請嘗試減少迭代次數。

該代碼正在搜索矩陣中的某個範圍內的數字：大於最小值且小於最大範圍值。

在此基礎上，嘗試了不同的方法：

1. 找到並記住所有的座標，其中搜索值大於低值更大 。讓我們稱這些定位點。
2. 對於每個錨點，找到位於範圍之外的錨點之後的第一個值的座標。

目標是減少重複訪問次數。錨點允許進行一次掃描並允許其他決策，例如查找範圍或確定包含錨值的MxN矩陣。

另一個想法是創建包含matBigger和matSmaller被更多用於搜索優化的新數據結構。

例如，創建一個{值，座標列表}項爲每個唯一值matSmaller：

Value coordinate list 
    26 -> (2,3), (6,5), ..., (1007, 75) 
    31 -> (4,7), (2634, 5), ... 

現在你可以使用這個數據結構找到matSmaller值，並立即知道自己的位置。所以你可以搜索matBigger這個數據結構中的每個唯一值。這又減少了對矩陣的訪問次數。