パフォーマンスが向上するのはなぜですか？

Question

私は基本的に2つの異なる配列（それぞれがピーク時に2〜4kのサイズを持つ）でルックアップし、これらの値に基づいて3番目の配列に値を設定するforループを2つ持っています。いくつかの奇妙な理由のために、コードのこの部分のパフォーマンスと、2つのループのための2つの順序とに依存する2つの違いがあります。

これが最初の設定です。それは私のPC上〜150ミリ秒で実行されます。私はこの

for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 
{ 
    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
{ 
     resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
    } 
} 

様ループの順序が、何も変わらない場合

public static int[] SchoolMultiplication(int[] a, int[] b, int numberBase) 
{ 
    List<double> times = new List<double>(); 
    TimeTest timeTest = new TimeTest(); 

    int aLen = a.Length; 
    int bLen = b.Length; 

    int[,] resultMatrix = new int[a.Length + b.Length, aLen]; 
    int[] result = new int[a.Length + b.Length]; 

    timeTest.Start(); 

    for (int horizontalIndex = 0; horizontalIndex < b.Length; horizontalIndex++) 
    { 
     for (int verticalIndex = 0; verticalIndex < a.Length; verticalIndex++) 

     { 
      resultMatrix[a.Length + b.Length - 1 - verticalIndex - horizontalIndex, verticalIndex] = a[a.Length - verticalIndex - 1] * b[b.Length - horizontalIndex - 1]; 
     } 
    } 

は今の方法の総運転時間は約〜400ミリ秒に低下します。単純なループ順序の交換は、パフォーマンスを約300％向上させますか？私はそれが何らかのキャッシュやポインタの性能のものだと思いますか？

Answer 1

データの整理物です。メモリは1次元配列と考えてください。これが実際にディスク上に配置される方法です（コンピュータに関する限り）。したがって、多次元配列を作成するときに、ループ順序を変更するときに、配列の移動方法を変更します。順番に読むのではなく、あなたはポジションからポジションにジャンプしています。

---

多次元配列はあなたに次のようになります。

そして、コンピュータに次のように。

ですから、配列をループあなたの配列を変更すると、このようにトラバースされています：

したがって、あなたがより多くのキャッシュミスと貧しい実行アルゴリズムを取得横断する最適な方法は、下の矢印以下のインデックスがあり。

Answer 2

キャッシュヒット/ミスに関連している可能性があります。この違いは、1つのキャッシュ・ラインのサイズを上回るサイズの逐次対分散アクセスにあります。

プレーンなC++ループでは、ループ上で少しのパフォーマンスを得るためにループを後方に作るのに役立ちます。それが.NETにどのように適合するかは不明です。

Answer 3

データの地域、地域、地域。 （私が持っているであろうよりもそれが良いと言う）ウィキペディアから：

リニアデータ構造：コードがインデックスによって配列やその他のデータ構造を参照する傾向があり、ループが含まれているため、局所性がよく発生します。連続的な局所性（空間的局所性の特別な場合）は、関連するデータ要素が配置され、線形的にアクセスされるときに生じる。例えば、基本アドレスから最高要素までの1次元配列の要素の単純なトラバースは、メモリ内の配列の連続的な局所性を利用するでしょう。[2]より一般的な等距離局所性は、直線的なトラバースが、同一の構造およびサイズを有する隣接するデータ構造のより長い領域上にあり、これに加えて構造全体がアクセスされるのではなく、構造の相互に対応する同じ要素のみに存在する場合に生じる。これは、行列が行の連続した行列として表され、その要件が行列の単一の列にアクセスする場合です。

Answer 4

これについてはCode Completeで覚えています。ほとんどの言語では、配列は最後のインデックスが順番に設定された状態で設定されているため、最初の配列を反復処理するときにスキップするのではなく、最後のインデックスを反復処理するときに行のバイトに直接アクセスします。

Answer 5

あなたの直感は正しいです、それはキャッシングの問題です。 @マイケルダニエルズの質問は、本質的にまったく同じ問題を説明しています。コードの2番目のビットは、より多くのキャッシュヒットを取得します。

Fastest way to loop through a 2d array?

しかし、shhhh我々はパフォーマンスの権利を気になっていませんか？ :)

Answer 6

また、配列aとbの相対的なサイズが違いを生むと私は考えるだろう。

a.lengthが大きく、b.lengthが小さい場合、2番目のオプションは高速にする必要があります。 逆に、a.lengthが小さく、b.lengthが大きければ、最初のオプションが高速になります。 問題は、内部ループのセットアップ/ティアダウンコストを避けることです。ところで

、なぜあなたは

int型アレン= a.Lengthを持っています。

しかし、a.Lengthを直接呼び出しますか？あなたはどちらか一方を選ぶべきようです。