なぜこのような2次元配列を初期化するのが悪いですか？

Question

for(int i = 0; i<100; i++) 

    for(int j = 0; j<100; j++) 

     array[j][i] = 0; 
     // array[i][j] = 0; 

私の教授は、第2の方法とは対照的に、第1の方法で2次元配列を初期化する方がはるかに高価だと言いました。誰かがその事件を起こすフードの下で起こっていることを説明することができますか？または、初期化の2つの手段は同等のパフォーマンスを持っていますか？

Answer 1

@dlevが述べたように、これはlocality of referenceが原因であり、コンピュータの物理ハードウェアの仕組みと関係があります。

コンピュータ内部には、さまざまな種類のメモリがあります。通常、特定のメモリ位置（レジスタ）のみが実際の操作を実行できます。それ以外の場合は、データ操作を実行する場合は、メモリからレジスタにロードし、計算を実行してから書き戻す必要があります。

メインメモリ（RAM）は、レジスタよりはるかに遅く、しばしば数百から数千倍です。したがって、可能な限りメモリからの読み取りは避けるべきです。これに対処するために、ほとんどのコンピュータは通常、cachesと呼ばれる特別なメモリ領域を持っています。キャッシュの仕事は、メモリから最近アクセスされたデータを保持することであり、同じメモリ領域が再びアクセスされた場合、その値は主メモリからではなく（高速）キャッシュから引き出すことができる（遅い）。通常、キャッシュは、ある値がメモリから読み込まれると、その値に加えて隣接する値の束がキャッシュに取り込まれるように設計されています。こうすることで、配列全体を反復処理すると、最初の値を読み取った後、配列の残りの値がキャッシュに格納され、より効率的にアクセスできます。

コードが遅くなる理由は、配列要素に順番にアクセスしないためです。あなたがするので、

for (int i = 0; i < N; i++) { 
    for (int j = 0; j < M; j++) { 
     // Do something with A[i][j] 
    } 
} 

その後、あなたは優れた局所性を得る：Cでは、2次元の配列を使用すると、ループのためにこれを使用する場合

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ... 

が結果としてメモリが配置されていることを意味し、row-major orderにレイアウトされていますメモリ内に現れる順に配列要素にアクセスすることができます。これにより、すべてが通常キャッシュに入っていて準備ができているため、メインメモリの読み込み回数は非常に少なくなります。

しかし、ループを交換すると、アクセスはメモリ内でジャンプし、必ずしも連続しているとは限りません。これは、キャッシュミスが多いことを意味します。次に読み取るメモリアドレスはキャッシュにありません。これにより、キャッシュ負荷が増加し、プログラムが大幅に遅くなる可能性があります。

コンパイラはこのようなループを自動的に交換するほどスマートになり始めていますが、これらの詳細を無視することはできません。原則として、多次元配列用のCまたはC++コードを記述するときは、列優先順位ではなく行優先順位で反復処理を実行してください。あなたのプログラムでは、顕著なスピードアップを得ることができます。

希望すると便利です。

Answer 2

各テクニックでアクセスされるメモリの場所を見ると、2番目のバイトは連続するバイトにアクセスし、最初のバイトは100バイトの飛び跳ねでジャンプします。メモリキャッシュは、それを2番目の方法で実行すると、より効率的に動作します。

Answer 3

私はおそらくこのためdownvoted取得しますが、あなたがCをプログラミングしている場合は、 "最良の" は最も可能性が高いです。

のmemset（配列、0、はsizeof（配列））;

次に、memsetの実装に対して、（あなたが心配している）最適化の責任をすべて延期することができます。特定のハードウェアの利点をそこで実行することができます。

http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/

http://www.cplusplus.com/reference/clibrary/cstring/memset/

別の観察は、あなたがゼロにinit'ingされている場合、なぜあなた自身に尋ねることですか？あなたの配列が静的であれば（これはおそらく？）、cstartupは0に初期化されます。ここでも、これはおそらくあなたのハードウェアにとって最も効率的な方法を使用します。

Answer 4

私はパーティーに少し遅れましたが、すでに素晴らしい回答があります。しかし、私は、プロファイリングツール（Linux上）を使ってこの質問に実験的にどのように答えられるかを実証することで貢献できると考えました。

perfツールは、Ubuntu 10.10パッケージlinux-tools-commonで使用します。ここで

が、私はこの質問に答えるために書いた小さなCプログラムです：

// test.c 
#define DIM 1024 

int main() 
{ 
    int v[DIM][DIM]; 
    unsigned i, j; 

    for (i = 0; i < DIM; i++) { 
     for (j = 0; j < DIM; j++) { 
#ifdef ROW_MAJOR_ORDER 
      v[i][j] = 0; 
#else 
      v[j][i] = 0; 
#endif 
     } 
    } 

    return 0; 
} 

次に、2つの異なるバージョンでコンパイル：

$ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj 
$ gcc test.c -O0 -o row-min 

注意を私は-O0で無効な最適化をしたので、gccがチャンスを持っていませんより効率的にループを再編成することができます。

perf listを実行すると、perfで利用可能なパフォーマンス統計を表示できます。この場合、私たちはキャッシュミスに興味があります。これはイベントcache-missesです。

$ perf stat -e cache-misses -r 100 ./row-min 

Performance counter stats for './row-min' (100 runs): 

      286468 cache-misses    (+- 0.810%) 

     0.016588860 seconds time elapsed (+- 0.926%) 

$ perf stat -e cache-misses -r 100 ./row-maj 

Performance counter stats for './row-maj' (100 runs): 

       9594 cache-misses    (+- 1.203%) 

     0.006791615 seconds time elapsed (+- 0.840%) 

そして今、我々は実験的に、あなたが実際にして二桁以上のキャッシュ・ミスを見ないことを確認しました：

今では、プログラムの各バージョンに何度も実行して平均を取るのと同じくらい簡単です「行マイナー」バージョン