以下の 2 つのプログラムは、変数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
あなたのコンピュータはそれを単一の行としてメモリに保存します:
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 個の int のチャンクを取得し、(2) そのうちの 1 つだけを変更し、(3) 4000*4000 回繰り返します。これには、メモリからの「フェッチ」回数の 16 倍が必要になります。CPU は実際には、そのメモリが表示されるのを待つために時間を費やす必要があります。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
組み立てには関係ありません。これはキャッシュ ミスによるものです。
C 多次元配列は、最後の次元が最速として格納されます。したがって、最初のバージョンはすべての反復でキャッシュを失いますが、2 番目のバージョンはそうではありません。したがって、2 番目のバージョンは大幅に高速になるはずです。
バージョン 2 は、バージョン 1 よりもコンピューターのキャッシュをより適切に使用するため、はるかに高速に実行されます。考えてみれば、配列はメモリの連続した領域にすぎません。配列内の要素を要求すると、OS はおそらくその要素を含むメモリ ページをキャッシュに取り込みます。ただし、次のいくつかの要素もそのページにあるため (連続しているため)、次のアクセスは既にキャッシュされています! これは、バージョン 2 が速度を上げるために行っていることです。
一方、バージョン 1 は、行単位ではなく列単位で要素にアクセスしています。この種のアクセスはメモリ レベルで連続していないため、プログラムは OS のキャッシュをあまり利用できません。
その理由は、キャッシュ ローカル データ アクセスです。2 番目のプログラムでは、キャッシュとプリフェッチの恩恵を受けるメモリを直線的にスキャンしています。最初のプログラムのメモリ使用パターンははるかに分散しているため、キャッシュの動作が悪化します。
キャッシュヒットに関する他の優れた回答に加えて、最適化の違いも考えられます。2 番目のループは、コンパイラによって次のようなものに最適化される可能性があります。
for (j=0; j<4000; j++) {
int *p = x[j];
for (i=0; i<4000; i++) {
*p++ = i+j;
}
}
最初のループでは、ポインタ「p」を毎回 4000 ずつインクリメントする必要があるため、この可能性は低くなります。
編集： p++ほとんどのCPUで単一のCPU命令にコンパイルすることさえ*p++ = ..できます。*p = ..; p += 4000できないため、最適化するメリットが少なくなります。コンパイラは内部配列のサイズを認識して使用する必要があるため、これもより困難です。また、通常のコードの内側のループでは頻繁に発生しないため (ループ内で最後のインデックスが一定に保たれ、最後から 2 番目のインデックスがステップ実行される多次元配列でのみ発生します)、最適化の優先度は低くなります。 .
この行の犯人:
x[j][i]=i+j;
2 番目のバージョンは連続メモリを使用するため、大幅に高速になります。
で試しました
x[50000][50000];
実行時間は、バージョン 1 では 13 秒、バージョン 2 では 0.6 秒です。
私は一般的な答えを出すようにしています。
i[y][x]は C の省略形であるため*(i + y*array_width + x)( classy を試してくださいint P[3]; 0[P] = 0xBEEF;)。
を反復処理するyと、 size のチャンクを反復処理しますarray_width * sizeof(array_element)。内側のループにそれがある場合、array_width * array_heightそれらのチャンクを反復します。
順序を反転することで、チャンク イテレーションのみarray_heightになり、チャンク イテレーション間では のarray_widthイテレーションのみになりsizeof(array_element)ます。
非常に古い x86-CPU ではこれはあまり問題ではありませんでしたが、最近の x86 では多くのデータのプリフェッチとキャッシュが行われます。遅い反復順序では、多くのキャッシュ ミスが発生する可能性があります。