c - 文字列 - 2D配列を反復処理するときに、ループの順序がパフォーマンスに影響するのはなぜですか?




perl while 文字列 (5)

私は一般的な答えを出そうとします。

なぜなら、 i[y][x]はCの中の*(i + y*array_width + x)省略形であるからです*(i + y*array_width + x) classy int P[3]; 0[P] = 0xBEEF;試してください）。

yを繰り返し処理するときには、 array_width * sizeof(array_element)サイズのチャンクを反復処理します。 あなたが内部ループにある場合は、それらのチャンクに対してarray_width * array_height繰り返しがあります。

順序を反転することで、 array_heightチャンク・イテレーションのみを持ち、任意のチャンク・イテレーションの間にsizeof(array_element)だけのarray_width反復をarray_widthます。

実際に古いx86-CPUではこれはあまり重要ではありませんでしたが、今日のx86では多くのデータのプリフェッチとキャッシュが行われています。 おそらく、より遅い反復順序で多くのキャッシュミスを生成します。

可能な重複：
これらの2つのforループのどれが時間とキャッシュのパフォーマンスの面でより効率的か

以下は、 i変数とj変数の切り替えを除いて、ほぼ同じ2つのプログラムです。 それらはどちらも異なる時間で実行されます。 誰かがなぜこれが起こるのか説明できますか？

バージョン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; }
   }
}

これは犯人を示しています： 

x[j][i]=i+j;

2番目のバージョンは連続的なメモリを使用するため、大幅に高速化されます。

私は一緒に試みた 

x[50000][50000];

実行時間はバージョン1では13秒、バージョン2では0.6秒です。

バージョン2はコンピュータのキャッシュをバージョン1よりも使いやすくなるため、はるかに高速に動作します。それについて考えると、配列はメモリの連続した領域です。 配列内の要素を要求すると、OSはおそらくその要素を含むキャッシュにメモリページを持ち込みます。 しかし、次のいくつかの要素もそのページにあります（連続しているため）、次のアクセスはすでにキャッシュに入っています！ これは、速度を上げるためにバージョン2がやっていることです。

一方、バージョン1は、要素を列にアクセスし、行にはアクセスしません。 この種のアクセスはメモリレベルでは連続していないため、プログラムはOSキャッシュを利用できません。

他の人が言っているように、問題は配列内のメモリ位置へのストアです： x[i][j] 。 ここで少しの洞察があります：

あなたは2次元の配列を持っていますが、コンピュータのメモリは本質的に1次元です。 だからあなたはあなたの配列をこのように想像しています： 

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

あなたのコンピュータは、それを1行としてメモリに保存します。 

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

2番目の例では、最初に2番目の番号をループして配列にアクセスします。 

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

あなたがそれらをすべて順番に叩いているという意味。 今、第1版を見てください。 あなたはやっている： 

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Cがメモリー内に2次元配列を配置する方法のために、あなたはそれをどこにでも飛び越そうとしています。 しかし今キッカーのために：なぜこれは問題なのですか？ すべてのメモリアクセスは同じですか？

いいえ：キャッシュのため。 メモリからのデータは、通常は64バイトの小さなチャンク（「キャッシュライン」と呼ばれます）でCPUに引き継がれます。 4バイトの整数を持っている場合は、ちょっとした小さな束で16個の連続した整数を得ることになります。 実際には、これらのメモリの断片を取得するのはかなり遅いです。 あなたのCPUは単一のキャッシュラインがロードされるまでに多くの作業を行うことができます。

2番目の例は、（1）16個のintのチャンクを取り、（2）それらすべてを修正し、（3）4000 * 4000/16回繰り返すというものです。 これは素早く素早く、CPUには常に何かがあります。

最初の例は、（1）16の整数のチャンクを取り、（2）それらのうちの1つだけを変更し、（3）4000 * 4000回繰り返す。 それはメモリからの「フェッチ」の数の16倍を必要とするでしょう。 あなたのCPUは実際にそのメモリが現れるのを待っている間に座っていなければならず、周りに座っている間に貴重な時間を無駄にしています。

重要な注意点：

今、あなたは答えを持っています、興味深いメモがあります：あなたの2番目の例が速いものでなければならないという固有の理由はありません。 たとえば、Fortranでは、最初の例は速く、次の例は遅くなります。 これは、Cのように概念的な「行」に展開するのではなく、「列」に展開するためです。 

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

Cのレイアウトは「row-major」と呼ばれ、Fortranは「column-major」と呼ばれます。 ご覧のとおり、プログラミング言語が行優先か主列かを知ることは非常に重要です！ 詳細はこちらのリンクをご覧ください： http://en.wikipedia.org/wiki/Row-major_order : http://en.wikipedia.org/wiki/Row-major_order

組立とは関係ありません。 これはキャッシュミスによるものです。

C多次元配列は、最後の次元が最速として格納されます。 したがって、最初のバージョンではすべての反復でキャッシュが失われますが、2番目のバージョンではキャッシュが失われます。 したがって、2番目のバージョンは大幅に高速化する必要があります。

http://en.wikipedia.org/wiki/Loop_interchangeも参照してhttp://en.wikipedia.org/wiki/Loop_interchange 。




配列   文字列   while   loop   last   2次元配列   c   performance   for-loop   optimization   cpu-cache  


cpu-cache