5

intという名前の s の行列がありA、行ではなく列で繰り返し処理すると、実行速度が約 50 ミリ秒遅くなります。

for(int i=0;i<n;i++)  
    for(int j=0;j<n;j++)  
        cout<<A[j][i];    //slower than of A[i][j]

なぜこれが起こるのか誰にも分かりますか？数人に聞いてみましたが、誰も理由を知りませんでした。コンピューターのメモリでアドレスがどのように表現されるかに関係していると確信していますが、それでも、より具体的な答えを見つけたいと思います。

4

5 に答える 5

7

行列を行ごとに反復する方が、キャッシュ メモリがあるため高速です。

にアクセスするA[i][j]と、1 つの要素よりも多くのメモリがキャッシュに読み込まれます。マトリックスの各行は連続したメモリ ブロック内に格納されるため、メモリ「アラウンド」 A[i][j]がまだキャッシュにある場合、同じ行内の次の要素にアクセスすると、メイン メモリではなくキャッシュから読み取られる可能性が高くなります。 (キャッシュミスを参照)。

関連する質問も参照してください:
2D 配列を反復処理するとき、ループの順序がパフォーマンスに影響するのはなぜですか?
これら 2 つの for ループのうち、時間とキャッシュ パフォーマンスの点でより効率的なのは
どれですか? キャッシュ メモリはどのように機能しますか?
行列乗算: 行列サイズの小さな違い、タイミングの大きな違い

于 2013-02-25T08:07:47.537 に答える
3

他の人が指摘しているように、これはキャッシュの問題です。これを一方向に使用すると、配列要素にアクセスするたびにキャッシュミスが発生する可能性があります。

キャッシュの問題は、実際には最適化にとって非常に重要な要素です。これが、構造体の配列ではなく、配列の構造体を実行する方がよい場合がある理由です。これら2つを比較してください。

struct StructOfArrays {
  int values[100];
  char names[100][100];
}

struct StructOfArrays values;

struct NormalValStruct {
  int val;
  char name[100];
}

struct NormalValStruct values[100];

値を反復処理するStructOfArraysと、おそらくキャッシュにロードされ、効率的に読み取られます。繰り返してNormalValStruct値メンバーを取得すると、1回おきにキャッシュミスが発生します。

このトリックは、高性能アプリケーションでよく使用されます。多くの場合、これはゲームです。

于 2013-02-25T08:40:47.097 に答える
3

2D 配列は、(行/列) メジャーで1D 配列 としてメモリに格納されます。これが意味することは、5 列の配列が次々に 5 列として格納される可能性があることです。したがって、アクセス方法とこの順序に基づいて、アクセスがキャッシュされるか、すべてのアクセスでキャッシュが失敗する可能性があり、性能差が大きい。

于 2013-02-25T08:07:29.133 に答える
3

キャッシュラインの読み取りメカニズムについてです。空間的局所性について読んでください。

確認するには、このアプリケーションの実行中にキャッシュを無効にしてみてください。（やり方は忘れましたが、できます。）

于 2013-02-25T08:08:19.887 に答える
2

最初のループはメモリに線形にアクセスするため、間にギャップがあります。したがって、最初のループはキャッシュに適しています。

于 2013-02-25T08:06:25.470 に答える