2D 배열을 반복하는 중첩 루프의 순서가 더 효율적입니다.

2D 배열을 반복하는 중첩 루프의 순서가 더 효율적입니다.

---

이 질문에 이미 답변이 있습니다.

• 2D 배열을 반복 할 때 루프의 순서가 성능에 영향을 미치는 이유는 무엇입니까? 7 답변

2D 배열을 반복하는 중첩 루프의 다음 순서 중 시간 (캐시 성능) 측면에서 더 효율적인 것은 무엇입니까? 왜?

int a[100][100];

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
       a[i][j] = 10;    
   }
}

또는

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
      a[j][i] = 10;    
   }
}

---

첫 번째 방법은 할당되는 셀이 서로 옆에 놓이기 때문에 약간 더 좋습니다.

첫 번째 방법 :

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^2nd assignment
[ ][ ][ ][ ][ ] ....
^101st assignment

두 번째 방법 :

[ ][ ][ ][ ][ ] ....
^1st assignment
   ^101st assignment
[ ][ ][ ][ ][ ] ....
^2nd assignment

---

1. array [100] [100]의 경우-L1 캐시가 100 * 100 * sizeof (int) == 10000 * sizeof (int) == [보통] 40000보다 크면 둘 다 동일합니다. Sandy Bridge의 참고 사항 - L1 캐시는 32k에 불과하므로 100 * 100 정수는 차이를 확인하기에 충분한 요소 여야합니다.

2. 컴파일러는 아마도이 코드를 똑같이 최적화 할 것입니다.

3. 컴파일러 최적화가없고 행렬이 L1 캐시에 맞지 않는다고 가정하면 첫 번째 코드는 [보통] 캐시 성능으로 인해 더 좋습니다. 캐시에서 요소를 찾을 수 없을 때마다- 캐시 미스 가 발생하고 RAM 또는 L2 캐시로 이동해야합니다 (훨씬 느림). RAM에서 캐시 [캐시 채우기]로 요소를 가져 오는 작업은 [보통 8/16 바이트] 블록 단위로 수행됩니다. 따라서 첫 번째 코드에서는 [16 바이트 캐시 블록, 4 바이트 정수라고 가정] 의 최대 미스 비율 을 얻 습니다.1/4 코드는 제한되지 않으며 1 일 수도 있습니다. 두 번째 코드 스냅에서 이미 캐시에 있던 요소 [인접한 요소에 대한 캐시 채우기에 삽입 됨]가 제거되고 중복 캐시 미스가 발생합니다.

   • 이는 캐시 시스템을 구현할 때 사용되는 일반적인 가정 인 지역성 원칙 과 밀접한 관련이 있습니다. 첫 번째 코드는이 원칙을 따르지만 두 번째 코드는 그렇지 않습니다. 따라서 첫 번째 코드의 캐시 성능이 두 번째 코드보다 더 좋습니다.

결론 : 내가 아는 모든 캐시 구현에 대해 첫 번째가 두 번째보다 나쁘지는 않습니다. 캐시가 전혀 없거나 모든 배열이 캐시에 완전히 맞는 경우 또는 컴파일러 최적화로 인해 동일 할 수 있습니다.

---

이러한 종류의 마이크로 최적화는 플랫폼에 따라 다르므로 합리적인 결론을 도출하기 위해 코드를 프로파일 링해야합니다.

---

두 번째 스 니펫 j에서 각 반복 의 변경 으로 인해 공간 지역성이 낮은 패턴이 생성됩니다. 배후에서 배열 참조는 다음을 계산합니다.

( ((y) * (row->width)) + (x) ) 

배열의 50 개 행에만 충분한 공간이있는 단순화 된 L1 캐시를 고려하십시오. 처음 50 번 반복하는 동안 50 번의 캐시 미스에 대해 피할 수없는 비용을 지불하게되지만, 그러면 어떻게됩니까? 50에서 99까지 반복 할 때마다 여전히 캐시 미스가 발생하고 L2 (및 / 또는 RAM 등)에서 가져와야합니다. 그런 다음 x1로 변경하고 y다시 시작하면 어레이의 첫 번째 행이 캐시에서 제거 되었기 때문에 또 다른 캐시 누락이 발생합니다.

첫 번째 스 니펫에는이 문제가 없습니다. 더 나은 지역성을 달성 하기 위해 row-major 순서로 배열에 액세스합니다. 한 행당 캐시 누락에 대해 최대 한 번만 지불하면됩니다 (루프가 시작될 때 배열의 행이 캐시에없는 경우).

즉, 이것은 매우 아키텍처에 의존적 인 질문이므로 결론을 도출하려면 세부 사항 (L1 캐시 크기, 캐시 라인 크기 등)을 고려해야합니다. 또한 두 가지 방법을 모두 측정하고 하드웨어 이벤트를 추적하여 결론을 도출 할 구체적인 데이터를 가져야합니다.

---

C ++이 행 메이저라는 점을 고려하면 첫 번째 방법이 조금 더 빠를 것이라고 생각합니다. 메모리에서 2D 배열은 단일 차원 배열로 표시되며 성능은 주 행 또는 주 열을 사용하여 액세스하는 데 달려 있습니다.

---

이것은 다음에 대한 고전적인 문제입니다. cache line bouncing

In most time the first one is better, but I think the exactly answer is: IT DEPENDS, different architecture maybe different result.

---

In second method, Cache miss, because the cache stores contigous data. hence the first method is efficient than second method.

---

In your case (fill all array 1 value), that will be faster:

   for(j = 0; j < 100 * 100; j++){
      a[j] = 10;
   }

and you could still treat a as 2 dimensional array.

EDIT: As Binyamin Sharet mentioned, you could do it if your a is declared that way:

int **a = new int*[100];
for(int i = 0; i < 100; i++){
    a[i] = new int[100];
}

---

In general, better locality (noticed by most of responders) is only the first advantage for loop #1 performance.

The second (but related) advantage, is that for loops like #1 - compiler is normally capable to efficiently auto-vectorize the code with stride-1 memory access pattern (stride-1 means there is contiguous access to array elements one by one in every next iteration). On the contrary, for loops like #2, auto-vectorizations will not normally work fine, because there is no consecutive stride-1 iterative access to contiguos blocks in memory.

Well, my answer is general. For very simple loops exactly like #1 or #2, there could be even simpler aggressive compiler optimizations used (grading any difference) and also compiler will normally be able to auto-vectorize #2 with stride-1 for outer loop (especially with #pragma simd or similar).

---

First option is better as we can store a[i] in a temp variable inside first loop and then lookup for j index in that. In this sense it can be said as cached variable.

참고URL : https://stackoverflow.com/questions/9888154/which-ordering-of-nested-loops-for-iterating-over-a-2d-array-is-more-efficient