3

基本的に、これを行うには 2 つの方法があります。

for (int x = 0; x < UPPER_X; x++)
    for (int y = 0; y < UPPER_Y; y++)
    {        
        arr1[x, y] = get_value();
        arr2[y, x] = get_value();
    }

唯一の違いは、内側のループで変更する変数 (最初または 2 番目) です。言語によって結果が異なると聞きました。

.NET の正しい順序は?

4

4 に答える 4

4

確実にするために、特定の状況をベンチマークする必要があります。

長方形の配列 (つまり、連続して割り当てられたメモリ) には違いはないと思うかもしれませんが、このMSDN の記事によると違いがあります。

多次元配列を 1 次元配列に変換すると、さらに良い結果が得られます。構文を気にしないのであれば、これは些細なことです。1 つのインデックスをオフセットとして使用するだけです。たとえば、次の例では、1 次元配列を 2 次元配列として使用することを宣言しています。

double[] myArray = new double[ROW_DIM * COLUMN_DIM];

この配列の要素にインデックスを付けるには、次のオフセットを使用します。

myArray[row * COLUMN_DIM + column];

これは、同等のギザギザまたは長方形の配列よりも間違いなく高速です。

于 2009-01-02T01:37:26.903 に答える
3

一方が他方よりも高速である理由は、プロセッサのキャッシュと、データがメモリに配置される方法に関係しています。

2 次元データを 1 次元アドレス空間に格納する通常の方法が 2 つあります。最初の行、2 番目の行などのすべてのデータを格納する方法 (別名、行優先順) と、列ごとに行うことができます（別名、列の主要な順序）。以下は、これら両方のオプションの 3x3 配列のメモリ位置です。

行:

1 2 3
4 5 6
7 8 9

列:

1 4 7
2 5 8
3 6 9

1 つのメモリ ロケーションにアクセスすると、キャッシュ ライン全体 (ウィキペディアによると、8 ～ 512 バイトになる可能性があります) がキャッシュに読み込まれます。したがって、次のメモリ ロケーションにアクセスすると、それは既にキャッシュ内にあります。したがって、アドレス空間内をジャンプするよりも、メモリに順次アクセスする方がはるかに高速です。したがって、大規模な 2 次元配列では、内部ループ変数として行または列を選択すると、速度に大きな違いが生じる可能性があります。

于 2009-01-02T03:28:49.440 に答える
1

そこでベンチマークを行ったところ、arr1 へのアクセスが 3 倍高速であるという結果が得られました。

于 2009-01-02T02:12:08.923 に答える
1

非常に興味深いことに、配列インデックスに「非連続的に」アクセスするだけで、これが非常に大きな違いになる可能性があると考えることをやめませんでした。私はそれを自分で試してみましたが、次のコードでは 2 番目のループが 2 ～ 3 倍長くかかることもわかりました。

// Hmmm, how to insert blank lines in the code formatter???
static void Main(string[] args)
{
    Stopwatch timer = new Stopwatch();
    int arraySize = 10000;

    // First array, access X by Y
    int[,] xbyy = new int[arraySize, arraySize];


    timer.Start();
    for (int x = 0; x < arraySize; x++)
        for (int y = 0; y < arraySize; y++)
        {
            xbyy[x, y] = 15;
        }
    timer.Stop();
    TimeSpan duration = timer.Elapsed;
    string realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
                    duration.Minutes, duration.Seconds, duration.Milliseconds);
    Console.WriteLine("X by Y took " + realTimeFormat);



    // Seecond array, access Y by X
    int[,] ybyx = new int[arraySize, arraySize];

    timer.Start();
    for (int x = 0; x < arraySize; x++)
        for (int y = 0; y < arraySize; y++)
        {
            ybyx[y, x] = 15;
        }
    timer.Stop();
    duration = timer.Elapsed;
    realTimeFormat = string.Format("{0:00} minutes {1:00} seconds {2:000} milliseconds",
                duration.Minutes, duration.Seconds, duration.Milliseconds);
    Console.WriteLine("Y by X took " + realTimeFormat);


    Console.ReadLine();
}

簡潔にするために、X by Y ループと Y by X ループの出力された IL スニペットを次に示します。

ループ前の初期コード、

.method private hidebysig static void  Main(string[] args) cil managed
{
  .entrypoint
  // Code size       290 (0x122)
  .maxstack  4
  .locals init ([0] class [System]System.Diagnostics.Stopwatch timer,
           [1] int32 arraySize,
           [2] int32[0...,0...] xbyy,
           [3] int32 x,
           [4] int32 y,
           [5] valuetype [mscorlib]System.TimeSpan duration,
           [6] string realTimeFormat,
           [7] int32[0...,0...] ybyx,
           [8] int32 V_8,
           [9] int32 V_9)
  IL_0000:  newobj     instance void [System]System.Diagnostics.Stopwatch::.ctor()
  IL_0005:  stloc.0
  IL_0006:  ldc.i4     0x2710
  IL_000b:  stloc.1

X による Y のループ

  IL_000c:  ldloc.1
  IL_000d:  ldloc.1
  IL_000e:  newobj     instance void int32[0...,0...]::.ctor(int32,
                                                             int32)
  IL_0013:  stloc.2
  IL_0014:  ldloc.0
  IL_0015:  callvirt   instance void [System]System.Diagnostics.Stopwatch::Start()
  IL_001a:  ldc.i4.0
  IL_001b:  stloc.3
  IL_001c:  br.s       IL_003d
  IL_001e:  ldc.i4.0
  IL_001f:  stloc.s    y
  IL_0021:  br.s       IL_0034
  IL_0023:  ldloc.2
  IL_0024:  ldloc.3
  IL_0025:  ldloc.s    y
  IL_0027:  ldc.i4.s   15
  IL_0029:  call       instance void int32[0...,0...]::Set(int32,
                                                           int32,
                                                           int32)
  IL_002e:  ldloc.s    y
  IL_0030:  ldc.i4.1
  IL_0031:  add
  IL_0032:  stloc.s    y
  IL_0034:  ldloc.s    y
  IL_0036:  ldloc.1
  IL_0037:  blt.s      IL_0023
  IL_0039:  ldloc.3
  IL_003a:  ldc.i4.1
  IL_003b:  add
  IL_003c:  stloc.3
  IL_003d:  ldloc.3
  IL_003e:  ldloc.1
  IL_003f:  blt.s      IL_001e
  IL_0041:  ldloc.0

Y による X のループ 

  IL_0090:  ldloc.1
  IL_0091:  ldloc.1
  IL_0092:  newobj     instance void int32[0...,0...]::.ctor(int32,
                                                             int32)
  IL_0097:  stloc.s    ybyx
  IL_0099:  ldloc.0
  IL_009a:  callvirt   instance void [System]System.Diagnostics.Stopwatch::Start()
  IL_009f:  ldc.i4.0
  IL_00a0:  stloc.s    V_8
  IL_00a2:  br.s       IL_00c7
  IL_00a4:  ldc.i4.0
  IL_00a5:  stloc.s    V_9
  IL_00a7:  br.s       IL_00bc
  IL_00a9:  ldloc.s    ybyx
  IL_00ab:  ldloc.s    V_9
  IL_00ad:  ldloc.s    V_8
  IL_00af:  ldc.i4.s   15
  IL_00b1:  call       instance void int32[0...,0...]::Set(int32,
                                                           int32,
                                                           int32)
  IL_00b6:  ldloc.s    V_9
  IL_00b8:  ldc.i4.1
  IL_00b9:  add
  IL_00ba:  stloc.s    V_9
  IL_00bc:  ldloc.s    V_9
  IL_00be:  ldloc.1
  IL_00bf:  blt.s      IL_00a9
  IL_00c1:  ldloc.s    V_8
  IL_00c3:  ldc.i4.1
  IL_00c4:  add
  IL_00c5:  stloc.s    V_8
  IL_00c7:  ldloc.s    V_8
  IL_00c9:  ldloc.1
  IL_00ca:  blt.s      IL_00a4
  IL_00cc:  ldloc.0

IL ロジック フローは多少似ています。私が観察できる主な違いは、最初のループが最初の配列と X インデックス変数の位置 2 と 3 に stloc と ldloc を使用することに成功したことです。2 番目のループに到達するまでに、maxstack が消費されたため、stloc.s および ldloc.s 命令が使用されました。これが、スタック上の変数とヒープ上の変数の参照の違いであり、パフォーマンスの低下に寄与していると思います。

ここで、スタック参照にアクセスするために Y by X ループが最初に実行されるように、ループがテストされる順序を入れ替えると、タイミング期間が逆になることがわかります。

更新: スタックまたはヒープ アドレスの参照について間違っていました。メソッドの最初の 4 つの変数は、専用の stloc.0、1、3、4 および ldloc.0、1、3、4 オペコードで参照する方が効率的であるように思われます。

http://weblogs.asp.net/mnolton/archive/2004/01/09/48992.aspx

于 2009-01-02T03:54:22.773 に答える