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

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

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

私の教授は、2 次元配列を最初の方法で初期化する方が、2 番目の方法よりもはるかにコストがかかると言いました。ボンネットの下で何が起こっているのか、誰かが説明できますか? または、2 つの初期化手段のパフォーマンスは同じですか?

4

4 に答える 4

23

@dlev が述べたように、これは参照の局所性によるものであり、コンピューター内の物理ハードウェアの動作に関係しています。

パソコンの内部には、さまざまな種類のメモリがあります。通常、特定のメモリ位置 (レジスタ) のみが実際の操作を実行できます。残りの時間、データに対して操作を実行している場合は、データをメモリからレジスタにロードし、計算を実行してから書き戻す必要があります。

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

コードが必要以上に遅い理由は、配列要素に順番にアクセスしないためです。C では、2D 配列は行優先順で配置されます。つまり、メモリは次のように配置されます。

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] ...

したがって、これを for ループに使用すると、次のようになります。

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

次に、メモリに表示される順序で配列要素にアクセスするため、優れた局所性が得られます。これにより、メイン メモリの読み取り回数が非常に少なくなります。これは、通常、すべてがキャッシュにあり、すぐに使用できるためです。

ただし、これまで行ったようにループを交換すると、アクセスがメモリ内でジャンプし、必ずしも連続するとは限りません。これは、次に読み取るメモリ アドレスがキャッシュにないキャッシュ ミスが多数発生することを意味します。これにより、キャッシュの読み込み回数が増加し、プログラムの速度が大幅に低下する可能性があります。

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

お役に立てれば！

于 2012-06-22T00:13:33.133 に答える
4

私はパーティーに少し遅れましたが、すでに優れた答えがあります。しかし、プロファイリング ツール (Linux 上) を使用して実験的にこの質問に答える方法を示すことで貢献できると思いました。

perfUbuntu 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を実行することで、利用可能なパフォーマンス統計を一覧表示できますperf list。この場合、イベントであるキャッシュ ミスに関心があります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% )

そして今、「行マイナー」バージョンでは実際に 2 桁多くのキャッシュ ミスが発生することが実験的に確認されました。

于 2012-07-10T14:38:08.193 に答える
4

私はおそらくこれに反対票を投じるでしょうが、C をプログラミングしている場合は、「最高」の可能性が最も高いでしょう。

memset(配列、0、sizeof(配列));

次に、最適化のすべての責任 (明らかに心配している) を memset の実装に任せることができます。特定のハードウェアの利点はそこで行うことができます。

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

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

もう 1 つの観察結果は、ゼロに初期化している場合は、その理由を自問することです。配列が静的である場合 (これほど大きいのはおそらく?)、cstartup はゼロに初期化します。繰り返しますが、これはおそらくハードウェアにとって最も効率的な方法を使用します。

于 2012-06-22T01:26:46.463 に答える
2

各手法でアクセスされるメモリ位置を見ると、2 番目は連続するバイトにアクセスするのに対し、1 番目は 100 バイトの跳躍でホップします。2 番目の方法を使用すると、メモリ キャッシュがより効率的に機能します。

于 2012-06-22T00:13:54.387 に答える