.NET 직사각형 어레이 : 루프에서 액세스하는 방법?
https://stackoverflow.com/questions/405810
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
기본적으로이 작업을 수행하는 두 가지 방법이 있습니다.
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();
}
유일한 차이점은 내부 루프에서 변수를 변경하는 것이 첫 번째 또는 두 번째입니다. 결과가 언어마다 다르다는 말을 들었습니다.
.NET에 적합한 순서는 무엇입니까?
해결책
하나가 다른 것보다 빠른 이유는 프로세서의 캐시와 관련이 있으며 데이터가 메모리에 배치되는 방식.
2 차원 데이터를 저장하는 두 가지 일반적인 방법은 1 차원 주소 공간에 있는데, 첫 번째 행에 대한 모든 데이터를 저장 한 다음 두 번째 행 등 (일명 줄거리 주문) 또는 열로 할 수 있습니다 (일명 열 주요 순서). 아래는이 두 옵션 모두에 대한 메모리 위치가 3x3 배열에 대한 것입니다.
행 :
1 2 3
4 5 6
7 8 9
열 :
1 4 7
2 5 8
3 6 9
하나의 메모리 위치에 액세스하면 전체 캐시 라인 (Wikipedia에 따라 8 ~ 512 바이트 일 수 있음)이 캐시에로드됩니다. 따라서 다음 메모리 위치에 액세스하면 이미 캐시에 있습니다. 따라서 주소 공간에서 뛰어 다니는 것보다 순차적으로 메모리에 액세스하는 것이 훨씬 빠를 수 있습니다. 따라서 큰 2 차원 배열의 경우 행이나 열을 내부 루프 변수로 선택하는 것 사이에 상당한 속도 차이가있을 수 있습니다.
다른 팁
특정 상황을 확실히 벤치마킹해야합니다.
직사각형 배열에는 차이가 없다고 생각할 것입니다 (즉, 연속적으로 할당 된 메모리). MSDN 기사 차이가 있습니다 :
다차원 배열을 단일 차원 배열로 변환하여 더 나은 결과를 얻을 수 있습니다. 구문을 신경 쓰지 않으면 이것은 사소 할 수 있습니다. 하나의 색인을 오프셋으로 사용하십시오. 예를 들어, 다음은 단일 차원 배열을 2 차원 배열로 선언합니다.
double[] myArray = new double[ROW_DIM * COLUMN_DIM];
이 배열의 요소를 색인화하려면 다음 오프셋을 사용하십시오.
myArray[row * COLUMN_DIM + column];
이것은 의심 할 여지없이 동등한 들쭉날쭉하거나 직사각형 배열보다 빠릅니다.
그래서 나는 벤치 마크를했고 결과는 ARR1에 대한 액세스가 3 배 더 빠르다는 것입니다.
매우 흥미 롭습니다. 나는 배열 인덱스에 "비 순위행"에 액세스함으로써 그렇게 큰 차이가 될 수 있다고 생각하지 않았습니다. 나는 그것을 스스로 시도했고, 또한 다음 코드가 두 번째 루프가 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 루프에 대한 방출 된 IL 스 니펫과 y x x 루프가 있습니다.
루핑 전 초기 코드,
.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를 반복합니다
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
x에 의해 y
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 논리 흐름은 다소 비슷합니다. 내가 관찰 할 수있는 주요 차이점은 첫 번째 루프가 첫 번째 배열에 대한 위치 2 및 3에 STLOC 및 LDLOC를 사용하여 X 인덱스 변수를 사용하는 것입니다. 두 번째 루프에 올 때 Maxstack을 소비하여 Stloc.s 및 Ldloc.s 지침을 사용했습니다. 나는 이것이 스택의 참조 변수와 힙의 차이와 느린 성능에 기여한다고 생각합니다.
이제 루프가 테스트되는 순서를 바꾸면 x by x 루프가 먼저 실행되도록 스택 참조에 액세스 할 수 있습니다. 타이밍 지속 시간이 반전됩니다.
업데이트 : 스택 또는 힙 주소를 참조하는 것이 잘못되었습니다. 방법의 처음 네 가지 변수는 전용 STLOC.0, 1, 3, 4 및 LDLOC.0, 1, 3, 4 OPCODES와 참조하는 데 더 효율적 인 것 같습니다.
http://weblogs.asp.net/mnolton/archive/2004/01/09/48992.aspx
