정확히 8192 개 요소를 반복 할 때 내 프로그램이 느린 이유는 무엇입니까?

정확히 8192 개 요소를 반복 할 때 내 프로그램이 느린 이유는 무엇입니까?

---

다음은 문제의 프로그램에서 발췌 한 것입니다. 행렬 img[][]의 크기는 SIZE × SIZE이며 다음 위치에서 초기화됩니다.

img[j][i] = 2 * j + i

그런 다음 행렬을 만들고 res[][]여기에있는 각 필드는 img 행렬에서 주변 9 개 필드의 평균이됩니다. 단순함을 위해 테두리는 0으로 유지됩니다.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

그게 프로그램의 전부입니다. 완전성을 위해, 여기에 이전에 오는 것이 있습니다. 뒤에 코드가 없습니다. 보시다시피 초기화 일뿐입니다.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

기본적으로이 프로그램은 SIZE가 2048의 배수 일 때 느립니다 (예 : 실행 시간).

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

컴파일러는 GCC입니다. 제가 아는 바에 따르면 이것은 메모리 관리 때문입니다.하지만 저는 그 주제에 대해 너무 많이 알지 못합니다. 이것이 제가 여기서 묻는 이유입니다.

또한 이것을 고치는 방법도 좋지만 누군가가 이러한 실행 시간을 설명 할 수 있다면 이미 충분히 행복 할 것입니다.

나는 malloc / free에 대해 이미 알고 있지만 문제는 사용 된 메모리 양이 아니라 실행 시간 일 뿐이므로 어떻게 도움이 될지 모르겠습니다.

---

차이는 다음과 같은 관련 질문의 동일한 수퍼 정렬 문제로 인해 발생합니다.

• 512x512 행렬을 전치하는 것이 513x513 행렬을 전치하는 것보다 훨씬 느린 이유는 무엇입니까?
• 행렬 곱셈 : 행렬 크기의 작은 차이, 타이밍의 큰 차이

그러나 그것은 코드에 또 다른 문제가 있기 때문입니다.

원래 루프에서 시작 :

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

먼저 두 개의 내부 루프가 사소하다는 점에 유의하십시오. 다음과 같이 펼칠 수 있습니다.

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

그래서 우리가 관심있는 두 개의 외부 루프가 남습니다.

Now we can see the problem is the same in this question: Why does the order of the loops affect performance when iterating over a 2D array?

You are iterating the matrix column-wise instead of row-wise.

---

To solve this problem, you should interchange the two loops.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

This eliminates all the non-sequential access completely so you no longer get random slow-downs on large powers-of-two.

---

Core i7 920 @ 3.5 GHz

Original code:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Interchanged Outer-Loops:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds

---

The following tests have been done with Visual C++ compiler as it is used by the default Qt Creator install (I guess with no optimization flag). When using GCC, there is no big difference between Mystical's version and my "optimized" code. So the conclusion is that compiler optimizations take care off micro optimization better than humans (me at last). I leave the rest of my answer for reference.

---

It's not efficient to process images this way. It's better to use single dimension arrays. Processing all pixels is the done in one loop. Random access to points could be done using:

pointer + (x + y*width)*(sizeOfOnePixel)

In this particular case, it's better to compute and cache the sum of three pixels groups horizontally because they are used three times each.

I've done some tests and I think it's worth sharing. Each result is an average of five tests.

Original code by user1615209:

8193: 4392 ms
8192: 9570 ms

Mystical's version:

8193: 2393 ms
8192: 2190 ms

Two pass using a 1D array: first pass for horizontal sums, second for vertical sum and average. Two pass addressing with three pointers and only increments like this:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Two pass using a 1D array and addressing like this:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

One pass caching horizontal sums just one row ahead so they stay in cache:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Conclusion:

• No benefits of using several pointers and just increments (I thought it would have been faster)
• Caching horizontal sums is better than computing them several time.
• Two pass is not three times faster, two times only.
• It's possible to achieve 3.6 times faster using both a single pass and caching an intermediary result

I'm sure it's possible to do much better.

NOTE Please, note that I wrote this answer to target general performance issues rather than the cache problem explained in Mystical's excellent answer. At the beginning it was just pseudo code. I was asked to do tests in the comments... Here is a completely refactored version with tests.

참고URL : https://stackoverflow.com/questions/12264970/why-is-my-program-slow-when-looping-over-exactly-8192-elements