c - loop - 為什麼迭代遍歷2D數組時循環的順序會影響性能?




loop tiling (5)

我試圖給出一個通用的答案。

因為i[y][x]是C中的*(i + y*array_width + x)的簡寫形式(嘗試使用經典的int P[3]; 0[P] = 0xBEEF; )。

在迭代y ,您將遍歷大小為array_width * sizeof(array_element) 。 如果你在你的內部循環中有那個,那麼你將在這些塊上進行array_width * array_height迭代。

通過翻轉順序,你將只​​有array_height塊迭代,並且在任何塊迭代之間,你將只有sizeof(array_element) array_width迭代。

雖然在真正舊的x86-CPU上這並不重要,但現在的x86做了大量的數據預取和緩存。 您可能會在較慢的迭代次序中產生很多緩存未命中

可能重複:
這兩個for循環中的哪一個在時間和高速緩存性能方面更高效

下面是兩個幾乎相同的程序,只是我切換了ij變量。 他們都跑了不同的時間。 有人能解釋為什麼發生這種情況?

版本1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

版本2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

原因是緩存本地數據訪問。 在第二個程序中,您可以通過內存進行線性掃描,從緩存和預取中受益。 您的第一個程序的內存使用模式更加分散,因此緩存行為更差。


版本2的運行速度要快得多,因為它使用計算機的緩存優於版本1.如果仔細考慮,陣列只是連續的內存區域。 當你請求一個數組中的元素時,你的操作系統可能會將一個內存頁面帶入包含該元素的緩存中。 但是,由於接下來的幾個元素也在該頁面上(因為它們是連續的),下一個訪問將已經在緩存中! 這是版本2正在做的事情,以加快速度。

另一方面,版本1正在逐列訪問元素,而不是行列式。 這種訪問在內存級不是連續的,所以程序不能充分利用操作系統緩存。



除了緩存命中的其他優秀答案之外,還有一個可能的優化差異。 您的第二個循環可能會被編譯器優化為等同於:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

這對第一個循環來說不太可能,因為它需要每次增加4000個指針“p”。

編輯: p++甚至*p++ = ..可以被編譯為大多數CPU中的單個CPU指令。 *p = ..; p += 4000 *p = ..; p += 4000不能,因此優化它的好處較少。 這也比較困難,因為編譯器需要知道並使用內部數組的大小。 並且它在正常代碼的內部循環中並不經常出現(它只出現在多維數組中,最後一個索引在循環中保持不變,而倒數第二個被分步),所以優化不是優先級。





cpu-cache