2D 어레이에서 반복할 때 루프 순서가 성능에 영향을 미치는 이유는 무엇입니까?

2D 어레이에서 반복할 때 루프 순서가 성능에 영향을 미치는 이유는 무엇입니까?

는 두 개의 이 거의 한데, 제가 이 프로그램을 요.i ★★★★★★★★★★★★★★★★★」j변수를 설정합니다.이랬다누가 왜 이런 일이 일어나는지 설명해 줄 수 있나요?

버전 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

버전 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

말한 배열 내의 입니다.x[i][j]다음은 그 이유에 대한 간단한 설명입니다.

2차원 배열이 있지만 컴퓨터의 메모리는 본질적으로 1차원입니다.따라서 다음과 같은 어레이를 상상해 보십시오.

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

컴퓨터가 메모리에 한 줄로 저장합니다.

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

두 번째 예에서는 두 번째 번호로 먼저 루프하여 어레이에 액세스합니다.

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

순서대로 치고 있다는 뜻이죠이제 첫 번째 버전을 보세요.하고 있는 일:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

C가 2D 어레이를 메모리에 배치한 방식 때문에 여기저기 뛰어다니라고 하는군요.하지만 이제 킥커를 위해:이게 왜 중요하죠?모든 메모리 액세스는 동일하죠?

아니요: 캐시 때문입니다.메모리의 데이터는 작은 청크(일반적으로 64바이트)로 CPU에 전달됩니다.4바이트의 정수가 있다면 16개의 정수를 하나의 작은 묶음으로 연속해서 얻을 수 있습니다.이러한 메모리 청크를 가져오는 것은 실제로 매우 느립니다.CPU는 캐시 라인 1개를 로드하는 데 걸리는 시간 내에 많은 작업을 수행할 수 있습니다.

이제 액세스 순서를 다시 살펴보겠습니다.두 번째 예는 (1) 16개의 int의 청크를 취득하고 (2) 모든 int를 변경하며 (3) 4000*4000/16회 반복하는 것입니다.이 기능은 매우 빠르고 CPU는 항상 작업할 수 있는 기능이 있습니다.

첫 번째 예시는 (1) 16개의 int의 청크를 잡고 (2) 그 중 하나만 수정하고 (3) 4000*4000회 반복하는 것입니다.메모리로부터 「페치」의 16배가 필요하게 됩니다.실제로 CPU는 메모리가 표시되기를 기다리는 데 시간을 할애해야 하며, 메모리가 표시되기까지 기다리는 동안 귀중한 시간을 낭비하게 됩니다.

중요사항:

정답이 나왔으니, 여기 흥미로운 노트가 있습니다.두 번째 예가 빠른 것이어야 할 이유는 없습니다.예를 들어 Fortran의 경우 첫 번째 예는 고속이고 두 번째 예는 저속입니다.왜냐하면 Fortran은 C와 같이 개념적인 "행"으로 확장하는 대신 "열"로 확장하기 때문입니다.

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

C의 레이아웃을 '열 메이저', Fortran의 레이아웃을 '컬럼 메이저'라고 합니다.보시다시피 프로그래밍 언어가 줄자인지 열자인지 아는 것이 매우 중요합니다.상세한 것에 대하여는, http://en.wikipedia.org/wiki/Row-major_order 를 참조해 주세요.

조립과는 아무 관련이 없습니다.이는 캐시 누락이 원인입니다.

c 다차원 배열은 가장 빠른 마지막 차원으로 저장됩니다.따라서 첫 번째 버전은 반복할 때마다 캐시를 놓치는 반면 두 번째 버전은 캐시를 놓치지 않습니다.따라서 두 번째 버전은 훨씬 더 빨라야 합니다.

http://en.wikipedia.org/wiki/Loop_interchange 도 참조해 주세요.

범인은 다음과 같습니다.

x[j][i]=i+j;

두 번째 버전은 연속 메모리를 사용하기 때문에 상당히 빠릅니다.

로 시도했다.

x[50000][50000];

실행 시간은 버전 1의 경우 13초, 버전 2의 경우 0.6초입니다.

버전 2는 버전 1보다 컴퓨터의 캐시를 더 잘 사용하기 때문에 훨씬 빠르게 실행됩니다.생각해 보면 어레이는 메모리의 인접 영역일 뿐입니다.어레이 내의 요소를 요구하면 OS는 해당 요소를 포함하는 메모리 페이지를 캐시로 가져옵니다.다만, 다음의 몇개의 요소도 그 페이지상에 있기 때문에(이러한 요소는 연속되어 있기 때문에), 다음의 액세스는 이미 캐시에 있습니다.이것이 바로 버전 2가 속도를 높이기 위해 하고 있는 일입니다.

한편 버전 1은 요소의 컬럼 와이즈에 액세스하고 있으며 행 와이즈가 아닙니다.이러한 종류의 액세스는 메모리레벨에서는 연속되지 않기 때문에 프로그램은 OS 캐시를 충분히 이용할 수 없습니다.

캐시 적중률에 대한 다른 훌륭한 답변 외에 최적화 차이도 있을 수 있습니다.두 번째 루프는 컴파일러에 의해 다음과 같은 형태로 최적화될 수 있습니다.

for (j=0; j<4000; j++) {
  int *p = x[j];
  for (i=0; i<4000; i++) {
    *p++ = i+j;
  }
}

첫 번째 루프에서는 매번 포인터 "p"를 4000으로 증가시킬 필요가 있기 때문에 이것은 가능성이 낮습니다.

★★★★★★ p++그리고 심지어*p++ = ..할 수 .*p = ..; p += 4000최적화할 수 없기 때문에, 최적화의 메리트는 적다.컴파일러가 내부 어레이의 크기를 파악하고 사용해야 하기 때문에 더 어렵습니다.또한 일반 코드의 내부 루프에서는 그다지 자주 발생하지 않으므로(루프 내에서 마지막 인덱스가 일정하게 유지되고 두 번째에서 마지막 인덱스가 단계인 다차원 배열에서만 발생합니다), 최적화는 우선순위가 낮습니다.

_{나는 일반적인 대답을 하려고 한다.}

왜냐면i[y][x]의 줄임말이다*(i + y*array_width + x)C로 (클래스를 시험해 보다)int P[3]; 0[P] = 0xBEEF;).

반복할수록y, 사이즈의 청크로 반복한다.array_width * sizeof(array_element)만약 당신의 내부 루프에 그것이 있다면, 당신은 그것을 가지고 있을 것이다.array_width * array_height반복할 수 있습니다.

순서를 바꿈으로써, 당신은 단지array_height청크 반복 및 임의의 청크 반복 사이에서는,array_width의 반복만sizeof(array_element).

구식의 x86-CPU에서는 이것이 크게 문제가 되지 않았지만, 오늘날의 x86에서는 데이터의 프리페치와 캐싱이 많이 이루어집니다.느린 반복 순서에서 많은 캐시 누락이 발생할 수 있습니다.

그 이유는 캐시 로컬 데이터 액세스입니다.두 번째 프로그램에서는 캐싱과 프리페치의 이점을 얻을 수 있는 메모리를 통해 선형적으로 스캔합니다.첫 번째 프로그램의 메모리 사용 패턴은 훨씬 더 분산되어 있기 때문에 캐시 동작이 더 나빠집니다.

언급URL : https://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra