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

다른 사람들이 말했듯이 문제는 배열의 메모리 위치에 대한 저장소 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가 메모리에 2 차원 배열을 배치하는 방식으로 인해 모든 곳을 뛰어 넘도록 요구하고 있습니다. 그러나 이제 키커에게 : 왜 이것이 문제가 되는가? 모든 메모리 액세스가 동일합니까?

아니요 : 캐시 때문입니다. 메모리의 데이터는 일반적으로 64 바이트 인 작은 청크 ( ‘캐시 라인’이라고 함)로 CPU로 가져옵니다. 4 바이트 정수가 있다면 깔끔한 작은 번들로 16 개의 연속 정수를 얻는다는 의미입니다. 실제로 이러한 메모리 덩어리를 가져 오는 것은 상당히 느립니다. CPU는 단일 캐시 라인을로드하는 데 걸리는 시간에 많은 작업을 수행 할 수 있습니다.

이제 액세스 순서를 다시 살펴보십시오. 두 번째 예는 (1) 16 개 덩어리 청크를 잡고 (2) 모두 수정하고, (3) 4000 * 4000 / 16 회 반복합니다. 훌륭하고 빠르며 CPU는 항상 작동해야합니다.

첫 번째 예는 (1) 16 개의 덩어리 청크를 잡고, (2) 그중 하나만 수정하고, (3) 4000 * 4000 번 반복합니다. 메모리에서 “페치”횟수의 16 배가 필요합니다. 실제로 CPU는 해당 메모리가 표시되기를 기다리는 데 시간을 소비해야하며, 앉아있는 동안 귀중한 시간을 낭비하고 있습니다.

중요 사항:

이제 답을 얻었으니 여기에 흥미로운 메모가 있습니다. 두 번째 예제가 빠른 이유는 없습니다. 예를 들어, 포트란에서 첫 번째 예는 빠르고 두 번째 예는 느립니다. 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의 레이아웃을 ‘행 전공’이라고하고 포트란을 ‘열 전공’이라고합니다. 보다시피 프로그래밍 언어가 행 전공인지 열 전공인지 아는 것이 매우 중요합니다! 자세한 내용은 다음 링크를 참조하십시오 : http://en.wikipedia.org/wiki/Row-major_order

답변

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

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

x[50000][50000];