[解決済み] 2次元配列の反復処理において、ループの順序がパフォーマンスに影響するのはなぜですか？

質問

以下の2つのプログラムは、私が "Space "と "Space "を入れ替えた以外はほとんど同じです。 i と 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; }
   }
}

解決方法は？

他の方もおっしゃっているように、配列のメモリ位置へのストアが問題なのです。 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は、1つのキャッシュラインがロードされる間に、多くの作業を行うことができます。

では、アクセスの順番を振り返ってみましょう。2番目の例は、(1)16個のintの塊を取得し、(2)それらすべてを変更し、(3)4000*4000/16回繰り返しています。これなら高速で、CPUは常に何か作業をすることができます。

最初の例は、（1）16個のintの塊をつかみ、（2）そのうちの1つだけを変更し、（3）4000*4000回繰り返すというものです。これには、メモリから16倍の"fetch"が必要になります。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/Row-major_order