[C++] 정확하게 8192 개 요소를 루핑 할 때 프로그램이 느려지는 이유는 무엇입니까?



Answers

다음 테스트는 Visual C ++ 컴파일러에서 수행되었습니다. 기본 Qt Creator 설치에서 사용되었으므로 (최적화 플래그가없는 것으로 추측합니다). GCC를 사용할 때 Mystical의 버전과 "최적화 된"코드 사이에는 큰 차이가 없습니다. 결론은 컴파일러 최적화가 인간보다 마이크로 최적화를 더 잘 처리한다는 것입니다 (마침내). 나머지 부분은 참고 용으로 남겨 둡니다.

이 방법으로 이미지를 처리하는 것은 효율적이지 않습니다. 단일 차원 배열을 사용하는 것이 좋습니다. 모든 픽셀을 처리하는 것은 하나의 루프에서 완료됩니다. 포인트에 대한 무작위 액세스는 다음을 사용하여 수행 할 수 있습니다.

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

이 특별한 경우에는 각 픽셀을 세 번 사용하기 때문에 세 픽셀 그룹의 합계를 계산하고 캐시하는 것이 좋습니다.

몇 가지 테스트를 해봤는데 공유 가치가 있다고 생각합니다. 각 결과는 평균 5 회의 테스트입니다.

user1615209의 원본 코드 :

8193: 4392 ms
8192: 9570 ms

신비의 버전 :

8193: 2393 ms
8192: 2190 ms

1D 배열을 사용하여 두 번 통과 : 첫 번째 합계는 가로 합계이고 두 번째는 세로 합계와 평균입니다. 3 개의 포인터를 가진 두 개의 통과 주소 지정과 다음과 같은 증가분 만 :

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

2D는 1D 배열을 사용하고 다음과 같이 주소 지정합니다.

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

8193: 932 ms
8192: 925 ms

캐싱 수평 한 패스는 한 행 앞을 합쳐서 캐시에 남습니다.

// 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

결론:

  • 몇 가지 포인터와 그냥 증분을 사용하여 이익 (나는 그것이 더 빨랐을 줄 알았는데)
  • 수평 합을 캐싱하는 것은 여러 번 계산하는 것보다 낫습니다.
  • 2 회 통과는 3 회 빨라지는데 2 회만 가능합니다.
  • 단일 패스와 중개 결과를 모두 사용하여 3.6 배 빠른 속도를 낼 수 있습니다.

훨씬 더 잘할 수있을 것이라고 확신합니다.

NOTE : Mystical의 뛰어난 대답에 설명되어있는 캐시 문제보다는 일반적인 성능 문제를 대상으로이 답변을 작성했습니다. 처음에는 의사 코드였습니다. 코멘트에서 테스트를 수행하라는 요청을 받았습니다. 여기 테스트를 통해 완전히 리팩토링 된 버전이 있습니다.

Question

다음은 문제의 프로그램에서 발췌 한 내용입니다. 행렬 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에 대해 알고 있지만, 문제는 사용 된 메모리의 양이 아니라 실행 시간 일 뿐이므로 도움이되는 방법을 모르겠습니다.




Links