72

2D 配列を反復処理するネストされたループの次の順序のうち、時間 (キャッシュ パフォーマンス) の点でより効率的なのはどれですか? なんで？

int a[100][100];

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
       a[i][j] = 10;    
   }
}

また

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
      a[j][i] = 10;    
   }
}
4

10 に答える 10

64

最初の方法は、割り当てられているセルが互いに隣り合っているため、わずかに優れています。

最初の方法:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

2 番目の方法:

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment
于 2012-03-27T10:56:47.993 に答える
44

  1. array[100][100] の場合 - L1 キャッシュが 100*100*sizeof(int) == 10000*sizeof(int) == [通常] 40000 より大きい場合、どちらも同じです。Sandy Bridgeでの注意- L1 キャッシュは 32k しかないため、違いを確認するには 100*100 の整数で十分です。

  2. コンパイラはおそらくこのコードをすべて同じように最適化します

  3. コンパイラの最適化がなく、行列が L1 キャッシュに収まらないと仮定すると、[通常] キャッシュのパフォーマンスにより、最初のコードの方が優れています。要素がキャッシュ内で見つからないたびに -キャッシュ ミスが発生し、RAM または L2 キャッシュに移動する必要があります [はるかに遅い]。RAM からキャッシュへの要素の取り込み [キャッシュ フィル] は、ブロック [通常は 8/16 バイト] で行われます。つまり、最初のコードでは、最大で [16 バイトのキャッシュ ブロック、4 バイトの ints を想定] のミス率が得られますが、2 番目のコード1/4では2 番目のコード スナップでは、[隣接する要素のキャッシュ フィルに挿入された] 既にキャッシュにあった要素が削除され、冗長なキャッシュ ミスが発生します。

    • これは、キャッシュ システムを実装する際に使用される一般的な前提である局所性の原則と密接に関連しています。最初のコードはこの原則に従っていますが、2 番目のコードはそうではありません。したがって、最初のコードのキャッシュ パフォーマンスは 2 番目のコードよりも優れています。

結論: 私が認識しているすべてのキャッシュの実装について、最初のものは 2 番目のものより悪くはありません。それらは同じである可能性があります-キャッシュがまったくない場合、またはすべての配列が完全にキャッシュに収まる場合-またはコンパイラの最適化が原因です。

于 2012-03-27T10:58:42.790 に答える
13

この種のマイクロ最適化はプラットフォームに依存するため、妥当な結論を導き出すためにコードをプロファイリングする必要があります。

于 2012-03-27T10:57:44.863 に答える
10

2番目のスニペットではj、各反復での変化により、空間的な局所性が低いパターンが生成されます。舞台裏では、配列参照が以下を計算することを忘れないでください。

( ((y) * (row->width)) + (x) )

配列の50行だけに十分なスペースがある単純化されたL1キャッシュについて考えてみます。最初の50回の反復では、50回のキャッシュミスに対して避けられないコストを支払うことになりますが、その後はどうなりますか？50から99までの反復ごとに、ミスをキャッシュし、L2（および/またはRAMなど）からフェッチする必要があります。次に、x1に変更しyて最初からやり直し、配列の最初の行がキャッシュから削除されたため、別のキャッシュミスが発生します。

最初のスニペットにはこの問題はありません。これは、行優先の順序で配列にアクセスします。これにより、ローカリティが向上します。キャッシュミスの料金を支払う必要があるのは、行ごとに最大1回（ループの開始時に配列の行がキャッシュに存在しない場合）だけです。

そうは言っても、これはアーキテクチャに非常に依存する質問であるため、結論を出すには、詳細（L1キャッシュサイズ、キャッシュラインサイズなど）を考慮する必要があります。また、両方の方法を測定し、ハードウェアイベントを追跡して、結論を引き出すための具体的なデータを入手する必要があります。

于 2012-03-27T11:12:03.773 に答える
6

C++ が行優先であることを考えると、最初の方法は少し高速になると思います。メモリ内では、2D 配列は 1 次元配列で表され、パフォーマンスは行優先または列優先のいずれかを使用してアクセスするかによって異なります

于 2012-03-27T11:01:14.537 に答える
4

これは古典的な問題ですcache line bouncing

ほとんどの場合、最初の方が優れていますが、正確な答えは次のとおりだと思います。IT DEPENDS、アーキテクチャが異なると結果が異なる可能性があります。

于 2012-03-27T11:22:01.080 に答える
3

あなたの場合（すべての配列1の値を入力）、それはより速くなります：

   for(j = 0; j < 100 * 100; j++){
      a[j] = 10;
   }

aそれでも2次元配列として扱うことができます。

編集a：Binyamin Sharetが述べたように、あなたがそのように宣言されている場合、あなたはそれを行うことができます：

int **a = new int*[100];
for(int i = 0; i < 100; i++){
    a[i] = new int[100];
}
于 2012-03-27T10:54:18.883 に答える
1

最初のループ内に保存a[i] in a temp variableし、その中で j インデックスを検索できるため、最初のオプションの方が優れています。そういう意味では、キャッシュされた変数と言えます。

于 2015-03-25T16:31:13.877 に答える