☰

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

tag-icon • tag-icon c performance for-loop optimization cpu-cache
2D 配列を反復処理するときに、ループの順序がパフォーマンスに影響するのはなぜですか? 質問する

i以下は、変数と変数を入れ替えた以外はほぼ同じ 2 つのプログラムですj。どちらも実行時間が異なります。なぜこのようなことが起こるのか説明していただけますか?

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

ベストアンサー1

他の人が言っているように、問題は配列内のメモリ位置への格納にあります。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...

つまり、順番にすべて実行しているということです。では、最初のバージョンを見てみましょう。次の操作を実行しています:

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

C が 2 次元配列をメモリ内にレイアウトする方法により、あちこちジャンプするように要求しています。しかし、ここで重要な点があります。なぜこれが重要なのでしょうか。すべてのメモリ アクセスは同じですよね?

いいえ、キャッシュのためです。メモリのデータは、通常 64 バイトの小さなチャンク (「キャッシュ ライン」と呼ばれる) で CPU に渡されます。4 バイトの整数がある場合、16 個の連続した整数が小さな束で取得されることになります。これらのメモリ チャンクを取得するのに実際はかなり時間がかかります。CPU は、1 つのキャッシュ ラインをロードするのにかかる時間で多くの作業を実行できます。

ここで、アクセスの順序をもう一度見てみましょう。2 番目の例は、(1) 16 個の int のチャンクを取得し、(2) それらすべてを変更し、(3) 4000*4000/16 回繰り返します。これは素晴らしく高速で、CPU は常に処理するものがあります。

最初の例は、(1) 16 個の int のチャンクを取得し、(2) そのうちの 1 つだけを変更し、(3) 4000*4000 回繰り返すというものです。これは、メモリからの「フェッチ」回数の 16 倍を必要とします。CPU は実際には、そのメモリが表示されるのを待つために時間を費やす必要があり、その間、貴重な時間を無駄にしていることになります。

重要な注意点：

答えがわかったところで、興味深い点があります。2 番目の例が必ずしも高速である必要はないということです。たとえば、Fortran では、最初の例は高速で、2 番目の例は低速になります。これは、C のように概念的な「行」に展開するのではなく、Fortran では「列」に展開するためです。つまり、

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 のレイアウトは「行優先」と呼ばれ、Fortran のレイアウトは「列優先」と呼ばれます。おわかりのように、プログラミング言語が行優先か列優先かを知ることは非常に重要です。詳細については、次のリンクを参照してください。http://en.wikipedia.org/wiki/行の順序

おすすめ記事