0

1 次元配列がジャグ配列よりも高速であるかどうかに興味があり、次のコード ブロックのパフォーマンスを測定しました。

テスト 1: ギザギザの配列

double[][][][] jagged = ArrayExtensions.Get4DMatrix<double>(100, 100, 50, 50, 0);
for (int iter = 0; iter < 5; iter++)
{
    sw.Restart();
    for (i = 0; i < 100; i++)
    {
        for (j = 0; j < 100; j++)
        {
            for (k = 0; k < 50; k++)
            {
                for (l = 0; l < 50; l++)
                {
                    test = jagged[i][j][k][l];
                    jagged[i][j][k][l] = test;
                }
            }
        }
    }
    Console.WriteLine("Jagged Arrays, Test {0}: {1} ms", iter, sw.ElapsedMilliseconds);
}

テスト 2: 1 次元配列

double[] single = ArrayExtensions.Get1DArray<double>(25000000);
for (int iter = 0; iter < 5; iter++)
{
    sw.Restart();
    for (i = 0; i < 100; i++)
    {
        for (j = 0; j < 100; j++)
        {
            for (k = 0; k < 50; k++)
            {
                for (l = 0; l < 50; l++)
                {
                    test = single[i * 100 + j * 100 + k * 50 + l];
                    single[i * 100 + j * 100 + k * 50 + l] = test;
                }
            }
        }
    }
    Console.WriteLine("Single Arrays, Test {0}: {1} ms", iter, sw.ElapsedMilliseconds);
}

テストを実行すると、次の結果が得られます。

Jagged Arrays, Test 0: 1447 m
Jagged Arrays, Test 1: 1429 m
Jagged Arrays, Test 2: 1431 m
Jagged Arrays, Test 3: 1430 m
Jagged Arrays, Test 4: 1429 m

Single Arrays, Test 0: 386 ms
Single Arrays, Test 1: 387 ms
Single Arrays, Test 2: 386 ms
Single Arrays, Test 3: 387 ms
Single Arrays, Test 4: 387 ms

また、配列への割り当てのみでテストを実行し、次に配列からの読み取りのみでテストを実行しましたが、結果は同じ比率でした。

1 次元配列はジャグ配列よりも高速であると予想していましたが、最後のブロックが最初のブロックの実行時間の 27% しか実行されないことを知って非常に驚きました。

なぜこの大きな違いが生じるのか誰か説明できますか? また、1次元配列を使用することの欠点はありますか(コードの読みやすさ以外に、明らかに難しくなり、エラーを発生させるリスクが高くなる可能性があります)?

コードは最適化されていないビルドで実行されました。最適化されたビルドでは、両方のテストが各反復で 100 ミリ秒未満で実行されますが、これはループ内で実行されるコードにもっと関係があると思います。それでも、1 次元配列はジャグ配列よりも 50% 高速です。

4

3 に答える 3

0

おそらく、「ジャグ配列」は（配列への）ポインターの配列であるためです...あなたの例では、4つのレベルの間接性があります：

jagged[i][j][k][l]
  • 「ギザギザ」からのオフセット i を取得します
  • 前の結果からオフセット j を取得します
  • 前の結果からオフセット k を取得します
  • 前の結果からのオフセット l を取得します
于 2013-08-10T19:12:48.570 に答える
0

パフォーマンスの主要な要因の 1 つは、データ キャッシュ ミスの数です。メモリは、キャッシュ ラインと呼ばれるチャンクに分割されます。マシンによっては、16 ～ 256 バイト程度になる場合があります。キャッシュ ライン内のデータの任意のバイトにアクセスすると、その中のすべてにアクセスする場合とほぼ同じコストがかかります。ごく最近アクセスされたキャッシュ ラインは、CPU コア内の小さなキャッシュに保持され、非常に迅速に再度アクセスできます。1 番目のレベルのキャッシュに入れるほど最近アクセスされなかった行は、2 番目のレベルのキャッシュで検索されます。そこに見つからない行は、3 番目のレベルのキャッシュで検索される場合があります (理論的には、4 番目、5 番目、6 番目などですが、そこまで行くマシンはないと思います)。命令にはデータが必要です。

あなたのプログラムは、完全にシーケンシャルなアクセスを使用しているため、線形配列とジャグ配列の相対的なパフォーマンスの最適な指標ではない可能性があります。これは、ほとんどのアクセスが最速 (レベル 1) のキャッシュによって処理されることを意味します。pspet が指摘しているように、ネストされた 4 つのオブジェクトを逆参照すると、1 つのオフセットを計算してそれを使用するよりも多くの作業が必要になります。すべてがレベル 1 キャッシュから来ている場合、実際のデータ アクセスが安価であるという事実は、この余分な労力が支配的であることを意味します。

ループの順序を変えて遊んで、パフォーマンスを監視することをお勧めします。「リリース」モードでビルドし、デバッガーを接続せずに実行して、正確なタイミング結果を取得します。2 つの内部ループを交換すると、両方のバージョンのコードの速度がほぼ同じになると推測できます (ほとんどのデータ要求は、第 1 レベルのキャッシュでは満たされない可能性がありますが、内部レベルの参照に対する要求は満たされるでしょう)。相対時間がより近くなります。すべてのループを交換すると、線形配列バージョンのパフォーマンスがもう少し損なわれますが、ネストされたギザギザ配列のパフォーマンスが低下する可能性があります (外側の配列はおそらく第 1 レベルのキャッシュに残りますが、ネストされた参照はおそらくしません、

.NET で 85,000 バイトを超える配列を使用すると、特に寿命が短い場合にパフォーマンスが低下するため、多くの場合、2 レベルのギザギザ配列が最適な場合があります。たとえば、データ項目がそれぞれ 64 バイトの場合、64 ビット システムで 2 レベルのネストを使用すると、項目が 85K を超えることなく、それぞれ 1,024 項目の 10,000 配列を持つことができます。10,000,000 を超えるアイテムが必要な場合は、アクセス パターンによって、より大きな配列を使用するか、3 番目のレベルの入れ子を使用する方がよいかが決まりますが、上記のアプローチが最適な配列サイズにはさまざまなものがあります。

于 2013-08-10T19:47:13.490 に答える