C에서 절대적으로 가장 빠른 for 루프는 무엇입니까?

Question

이미지 픽셀에 액세스하는 데 최적화 된 코드를 작성하려고 시도 중이므로 어셈블리 수준으로 내려 가지 않고 for 루프를 빠르게 처리해야합니다. 더 나아가 인덱싱은 행을 따라 수행되어 캐시 누락을 최소화합니다. 은 "dostuff는"같은 행에이 arent 요소를 액세스 포함되어 있기 때문에

가

for (indr=0;indr<(height-1)*width;indr+=width) { 
     for (indc=0;indc<width;indc++){ 
      I[indr+indc]= dostuff ; 
     } 
    } 

나는 그것을 하나의 루프를 만들 캔트 :

이 내가 가진 것입니다.

더 빠른 방법이 있나요?

편집 내 이전 게시물이 약간 불분명하기 때문에 여기에 전체 코드를 추가하십시오. 꽤 읽을 수는 없지만 일반적인 아이디어는 Im이 완전한 이미지를 사용하여 간단한 상자로 컨볼 루션을 수행한다는 것입니다. 이미지의 왼쪽과 아래쪽에 ws + 1이 채워지고 오른쪽과 상단에는 ws가 0으로 채워집니다. 그런 다음 그것은 적분 영상 Ii로 만들어진다. 다음 함수는 적분 이미지를 취해 결과 Ic가 원본 이미지와 동일한 크기의 회선을 추출합니다.

void convI(float *Ic,float *Ii,int ws, int width, int height) 
{ 
    int W=width+ws*2+1,indR; 
    int H=height+ws*2+1,indC; 
    int w=width, indr; 
    int h=height, indc; 
    int jmpA=W*(ws+1),jmpC=W*ws,jmpB=ws+1,jmpD=ws; 

    for (indR=W*(ws+1),indr=0;indr<width*(height-1);indR+=W,indr+=width) { 
     for (indC=ws+1,indc=0;indc<width;indC++,indc++){ 
      //Performs I[indA]+I[indD]-I[indB]-I[indC]; 
      Ic[indr+indc]= 
      Ii[indR-jmpA+indC-jmpB]+ 
      Ii[indR+jmpC+indC+jmpD]- 
      Ii[indR+jmpC+indC-jmpB]- 
      Ii[indR-jmpA+indC+jmpD]; 
     } 
    } 
} 

그래서 "dostuff"부분입니다. 루프가 느립니다.

Answer 1

모든 최적화 수준을 설정하면 다른 코드가 제공 한 성능보다 성능이 향상 될 이유는별로 없습니다.

왜 루프 자체가 병목 현상이 의심 스럽습니까? 당신이 실제로하고있는 것을 알지 못해도 말할 수있는 것이별로 없습니다. 코드를 벤치 마크하고, 의심이 들더라도 이것이 생성하는 어셈블러를 살펴보십시오.

편집 : 루프의 내부 부분을 보여 준 후에.

루프 밖에서 가능한 한 인덱스 계산식을 표현할 가능성이 조금 있습니다. 루프 변수와 섞이기 때문에 이것은 아마도 최적화 될 수 없습니다. (또는 인덱스의 계산 순서를 변경하여 컴파일러에서이를 볼 수 있도록 가능한 한 많이 미리 계산할 수 있습니다.)

대부분의 경우 성능에 문제가있는 것은 벡터 액세스로 인한 것입니다. 인덱스를 더 잘 계산할 수 있다면 컴파일러/시스템이 실제로 벡터에 정규 패턴으로 액세스하는 것을 실제로 볼 수 있으므로이 방법도 향상 될 수 있습니다.

그래도 도움이되지 않으면 벡터의로드가 저장소가 아니라 증분이되도록 루프를 다시 구성하십시오. 로드는 항상 데이터가 작업을 수행 할 때까지 기다려야 만합니다. 저장소는 그 작업에 덜 민감합니다.

Answer 2

SSE와 같은 벡터화 명령을 사용하지 않으려면 수행 할 수있는 작업이 많지 않습니다.

Answer 3

바깥 쪽 루프의 height-1을 루프 앞의 할당으로 들어 올리면 승리 할 수 ​​있습니다. 그러나, 나는 표준 컴파일러가 요즘 표준 최적화로 그렇게 할 것이라고 생각합니다. 그것은 또한 다른 포인터를 가지고, 내가 [indr]로 설정 한 다음 그 인덱스를 이 될 수 있습니다 작은 승리가 될 수 있습니다.

두 가지 모두주의 깊게 벤치마킹해야합니다.

Answer 4

당신이 뭘 좋아 보여.어셈블리를하지 않으려면 간단한 루프를 간단하게 유지하는 것이 가장 좋습니다. GCC는 똑똑합니다. 코드가 원하는 것을 명확하게 알고 있다면 일반적으로 코드를 최적화하는 것이 좋습니다. 그러나 프로덕션 코드에서 공통적이지 않은 멋진 기술을 사용하면 "실제로 의미하는 바가 무엇인지 추론하는 데 어려움이있을 수 있습니다. 그래서 당신의 코드가 어떤 모습

dostuff이 실제로 무엇을하는지에 따라, 당신은 당신이에 있다고 가정 (

char t = I[indr+indc]; 
// do stuff 
I[indr+indc] = t; 

이

이 코드는 더 수행하지 않습니다 ... 임시 캐싱 I[indr+indc]에서 일부 승리를 찾을 수 있습니다 최소한 기본적인 최적화는 켜져 있지만, do stuff이 충분히 화려하면 더 잘 수행 될 수 있습니다 (원하는 경우 정교 할 수 있음).

다른 사람들이 간단한 수학을 들었을 때 듣지 마십시오. 정말로 필요는 없습니다. -O1에서 생성 된 어셈블리를 보면 매번이 작업이 완료되었음을 알 수 있습니다. 가장 저렴한 최적화 중 하나입니다.

Answer 5

가장 안쪽 루프를 풀 수 있습니다. 가독성을 잃지 만 CPU 캐시와 프리 페치 큐가 더 잘 수행됩니다. 이것은 항상 사실이지만 나는 당신이 얼마나 많은 속도를 얻을지 모르겠다. indc과 indr을 모두 레지스터 변수로 선언하고 (height-1)*width을 다시 계산하지 않으려 고 임시 변수에 보관하십시오. 당신은 당신이 루프 내부 indr 사용할 필요가, 또는 postdecrementing 대신 predecrementing하지 않는 경우

Answer 6

// DragonLord style: 
float *ic_p = I + (width * height) - 1; // fencepost 
// Start at the end, and work backwards 
// assumes I is 0-based and wraps, is contiguous 

for (indr=(height -1) * width; indr>=0; indr-=width) { 
// Sadly cannot test on indr -= width here 
// as the 0 pass is needed for the loop 
     for (indc=width; indc--;){ 
     // Testing on postdecrement 
     // allows you to use the 0 value one last time before testing it FTW 
      // indr and indc are both 0-based inside the loop for you 
      // e.g. indc varies from (width-1) down to 0 
      // due to postdecrement before usage 
      printf("I[ %d + %d ] == %f \n", indr, indc, *ic_p); 
      // always use pointers in C/C++ for speed, we are not Java 
      *ic_p-- = dostuff ; 
     } 
    } 

성능은 약간 공을 향해 높이에서 카운트 다운에 의해 개선 될 수있다 ... 곱셈은 클럭 사이클을 많이 먹고, 알고 indc는 1's 기반 indc로 얻을 수있는 경우 indc는 (너비 +1)에서 초기화해야합니다.

for (indc=(width+1); --indc;){