c

Question

저는 C를 처음 접하는 상당히 유능한 Java 프로그래머입니다. 저는 4 가지 운영 모드를 가진 루틴을 최적화하려고합니다.

이미지의 모든 픽셀을 반복하고 통과 된 '모드'에 따라 새로운 픽셀 값을 계산합니다.

내 질문은 루프를 위해 중첩 된 두 개의 스위치 명령문의 오버 헤드와 관련이 있습니다. 기본 C 문, 수학 및 논리 작업의 상대적 효율성에 관한 문서에 대한 링크에 관심이 있습니다.

코드는 다음과 같이 진행됩니다.

for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             switch (mode)                  /* select the type of calculation */
             {
                case 0:
                weight = dCentre / maxDistanceEdge;
                case 1: 
                    weight = (float)x/width;             
                    break;
                case 2: 
                    weight = (float)y/height;
                    break;
                case 3: 
                    weight = dBottomLeft / maxDistanceCorner;
                    break;
                case 4: 
                    weight = dTopRight / maxDistanceCorner;
                    break;
                default: 
                weight = 1;
                break;
            }
             // Calculate the new pixel value given the weight
             ...
            }             

    }

이것이 5000 x 5000 픽셀 이미지를 초과하면 많은 오버 헤드를 볼 것으로 예상하십니까? 나는 약간의 테스트를 시도했지만 시스템 (모바일 장치)이 결과를 왜곡시킬 수있는 모든 종류의 물건을 가지고 있기 때문에 내 결과는 모든 곳에 있습니다.

다른 옵션은 각 모드마다 별도의 방법을 갖는 것입니다. 이것은 분명히 중복 코드를 소개하지만 효율성은 여기서 게임의 이름입니다.

미리 감사드립니다!

가브

Answer 1

스위치 명세서는 연속 값을 위해 점프 테이블과 희소 값에 대한 많은 if-ELSE 문으로 컴파일합니다. 어쨌든 성능에 관심이있는 경우 이미지 처리를 위해 내부 루프에서 스위치 문을 원하지 않습니다. 당신은 대신 아래에서 원합니다.

또한 내부 루프에서 중량 계산을 옮겼습니다 (이를 달성하기 위해 Case 2의 루프를 교체했습니다). 이 유형의 사고, 내부 루프에서 물건을 옮기면 C에서 원하는 성능을 얻을 수 있습니다.

switch (mode)                  /* select the type of calculation */
{
case 0:
    weight = dCentre / maxDistanceEdge;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 1:
    for (x = 0; x < width; x++) {
        weight = (float)x/width;
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 2:
    // note - the loops have been swapped to get the weight calc out of the inner loop
    for (y = 0; y < height; y++) {
        weight = (float)y/height;
        for (x = 0; x < width; x++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 3:
    weight = dBottomLeft / maxDistanceCorner;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
case 4:
    weight = dTopRight / maxDistanceCorner;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;
default:
    weight = 1;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             // Calculate the new pixel value given the weight
             ...
        }
    }
    break;

// etc..
}

Answer 2

효율성이 코드 크기보다 더 중요하다면 예, 중복 루틴을 만들어야합니다. 사례 진술은 C에서 할 수있는 더 낮은 오버 헤드 중 하나이지만 0은 아닙니다. 모드를 기반으로 분기해야하므로 시간이 걸립니다. 최대 성능을 원한다면 루프를 복제하는 비용으로도 루프에서 케이스를 제거하십시오.

Answer 3

스위치 문은 가능한 한 효율적입니다. 그들은 점프 테이블에 편집되어 있습니다. 사실, 스위치가 제한된 이유입니다. 스위치 만 쓸 수 있습니다. ~할 수 있다 고정 값에 따라 점프 테이블을 컴파일합니다.

Answer 4

루프에서 수행하는 수학과 비교할 때 스위치의 오버 헤드는 아마도 최소화 될 것입니다. 그러나 확실히 확실한 방법은 두 가지 다른 접근법에 대해 다른 버전을 만들고 시간을내는 것입니다.

Answer 5

스위치/케이스는 IF/else와 동등한 것과 비교하여 매우 빠릅니다. 일반적으로 점프 테이블로 구현됩니다. 그러나 여전히 비용이 있습니다.

사물을 최적화하는 동안 :

1) "루프의 경우 스위치 x 및 y"가 아닌 라인 위로 반복하려고 시도하면 캐시 메모리 관리로 인해 한 솔루션이 다른 솔루션보다 빠를 수 있습니다.

2) (사전 계산 된) 역의 곱셈으로 모든 부문을 대체하면 상당한 이익과 아마도 수용 가능한 정밀 손실이 생길 수 있습니다.

Answer 6

효율성을 위해 더 잘 움직입니다 switch 루프 밖.

다음과 같은 기능 포인터를 사용합니다.

double fun0(void) { return dCentre/maxDistanceEdge; }
double fun1(void) { return (float)x/width; }
/* and so on ... */

double (*fun)(void);

switch (mode)                  /* select the type of calculation */
{
    case 0: fun = fun0;
            break;
    case 1: fun = fun1;
            break;
    case 2: fun = fun2;
            break;
    case 3: fun = fun3;
            break;
    case 4: fun = fun3;
            break;
    default : fun = fun_default;
            break;
}

for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
             weight = fun();
             // Calculate the new pixel value given the weight
             ...
        }
}

함수 호출 오버 헤드를 추가하지만 함수에 매개 변수를 전달하지 않아서 너무 크지 않아야합니다. 나는 그것이 성능과 가독성 사이의 상충 관계라고 생각합니다.

편집하다: GCC를 사용하는 경우 기능 통화를 제거하면 사용할 수 있습니다. goto 그리고 값으로 레이블 : 스위치 내에서 올바른 레이블을 찾은 다음 매번 점프하십시오. 나는 그것이 더 많은 사이클을 절약해야한다고 생각합니다.

Answer 7

스위치는 상당한 오버 헤드를 생성해서는 안되며, 로우 엔드의 일종의 배열로 컴파일되면 효과적으로 다음과 같습니다.

jmp {baseaddress}+switchcasenum

Answer 8

이것은 아마도 CPU의 지점 예측기의 양과 컴파일러가 스위치의 코드를 생성하는 방법에 따라 다릅니다. 이러한 소수의 경우 의사 결정 트리를 생성 할 수 있으며,이 경우 일반 CPU 지점 예측은 대부분의 오버 헤드를 제거 할 수 있어야합니다. 스위치 테이블을 생성하면 상황이 조금 더 나빠질 수 있습니다 ...

즉, 알아내는 가장 좋은 방법은 그것을 프로필하고 보는 것입니다.

Answer 9

Jim의 조언 외에도 루프 순서를 교환하십시오. 루프 스무핑이 케이스 1에 이상적인지 여부는 테스트가 필요하지만, 나는 그럴 것 같습니다. 페이징 성능을 향상시키기 위해 거의 항상 X 좌표가 내부 루프 내부를 원합니다. 이로 인해 기능이 반복 각 동일한 일반 메모리 영역에 남아있는 경향이 더 높아집니다. 자원이 제한된 모바일 장치는이 차이를 강조 할만 큼 충분한 RAM을 가질 수 있습니다.

Answer 10

이 스레드를 부딪히서 죄송하지만 스위치가 문제와는 거리가 멀다.

이 경우 효율성의 실제 문제는 분열입니다. 분할 작업의 모든 분모가 상수 (폭, 높이, 최대 ...) 인 것 같습니다. 이미지 과정에서 변경되지 않습니다. 내 추측이 옳다면, 이들은 런타임에 모든 크기 이미지를 사용할 수 있도록로드 된 이미지를 기반으로 변경할 수있는 간단한 변수입니다. 이제 이미지 크기가로드 될 수 있지만 컴파일러가 최적화 할 수 없습니다. 훨씬 간단한 곱셈 작업으로 "Const"로 선언 된 경우 할 수 있습니다. 나의 제안은 이러한 상수의 수적을 사전 계산하고 곱하는 것입니다. 내가 기억할 수있는 한, 곱셈 작업은 약 10 클럭 사이클이 필요합니다. 1GHz CPU.

Answer 11

칩과 컴파일러 및 코드의 세부 사항에 따라 다르지만 ... 이는 종종 점프 테이블로 구현되며 매우 빠릅니다.

BTW-- 이런 종류의 것을 이해하는 것은 몇 주 동안 경력의 어느 시점에서 조립을 배우는 데 꽤 좋은 주장입니다 ...

Answer 12

스위치를 사용하는 것이 속도와 프로그래머 시간 모두에 더 좋습니다. 중복 코드가 덜 만들고 새로운 스택 프레임이 필요하지 않을 것입니다.

스위치는 매우 효율적이어서 정말 이상하고 혼란스러운 마법.

Answer 13

그러나 효율성은 여기서 게임의 이름입니다.

새로운 픽셀 값을 계산하기 위해 이미지 버퍼 위에 반복하면 일반적인 창피한 평행 문제처럼 들립니다. 이러한 의미에서는 일부 작업을 작업자 스레드로 푸시하는 것을 고려할 수 있습니다. 이는 미세 최적화보다 작업 속도를 높여야합니다. 스위치/케이스 문제와 같은.

또한 매번 분기 지침을 수행하는 대신 인덱스가 모드 식별자 역할을하는 기능 포인터에서 함수 포인터를 호출 할 수 있습니다.

다음과 같은 통화로 끝납니다.

computeWeight[mode](pixel);

5000x5000 픽셀을 사용하면 개별 픽셀이 아닌 다양한 픽셀의 기능을 호출하여 기능 호출 오버 헤드를 줄일 수 있습니다.

이를 최적화하기 위해 Loop Unrolling 및 Parameter를 사용하여 참조/포인터로 전달할 수도 있습니다.

Answer 14

많은 좋은 점이 이미 주어졌습니다. 내가 이것에 추가 할 수있는 유일한 것은 스위치에서 가장 빈번한 경우와 가장 빈번한 경우를 옮기는 것입니다.

따라서 사례 4가 사례 1보다 자주 발생하면 그 이상이어야합니다.

switch (mode) {
    case 4:
        // ..
        break;
    case 1:
        // ..
        break;
}

C ++를 사용하지 않는 것이 너무 나쁘다. 왜냐하면 스위치 명령문은 다형성으로 대체 될 수 있기 때문이다.

건배 !

Answer 15

이 스레드에는 5 개의 개별 기능을 작성하지 않아도되는 창의적인 제안이 많이 있습니다.

파일이나 입력 된 입력에서 '모드'를 읽지 않으면 계산 방법을 컴파일 시간에 결정할 수 있습니다. 일반적으로 계산을 컴파일 시간에서 실행 시간으로 이동하고 싶지 않습니다.

어느 쪽이든 코드는 읽기가 더 쉬우 며, 첫 번째 경우에 브레이크 진술을 할 것인지 여부에 대해 아무도 혼란스러워하지 않을 것입니다.

또한 주변 코드에서 버그를 받으면 열거가 잘못된 값으로 설정되었는지 여부를 찾을 필요가 없습니다.

Answer 16

내부 루프와 관련하여 ... 0-> var는 var--------------------------------- var-- 이 접근법은 또한 "너비"가 x로로드되었으며 잊을 수 있으며 "높이"도 마찬가지입니다. 또한 메모리의 픽셀은 일반적으로 왼쪽-> 오른쪽, 상단> 하단이므로 x를 내부 루프로 분명히 가지고 있습니다.

for (y = height; y--;) {
    for (x = width; x--;) {
         weight = fun();
         // Calculate the new pixel value given the weight
         ...
    }
}

또한 ... 그리고 스위치 문에는 x 또는 y를 사용하는 2 개의 사례 만 있습니다. 나머지는 상수입니다.

 switch (mode)                  /* select the type of calculation */
 {
     case 0:
        weight = dCentre / maxDistanceEdge;
        break;
     //case 1: 
     //  weight = (float)x/width;             
     // break;
     //case 2: 
     //     weight = (float)y/height;
     //     break;
     case 3: 
          weight = dBottomLeft / maxDistanceCorner;
          break;
      case 4: 
           weight = dTopRight / maxDistanceCorner;
           break;
      default: 
           weight = 1;
           break;
 }

따라서 기본적으로 루프 전에 모드 1 또는 2 가중치가 계산되지 않는 한.

... Y loop code here

    if (mode == 2) { weight = (float)y/height; } // calc only once per Y loop

    ... X loop here

        if (mode == 1) { weight = (float)x/width; } // after this all cases have filled weight
        calc_pixel_using_weight(weight);

데이터가 드물다면 스위치 명세서가 매우 불친절하다는 것을 알았습니다. <4 요소의 경우 if-then-else로 가서 가장 일반적인 사례가 맨 위에 있는지 확인하십시오. 첫 번째 조건이 사례의 90%를 잡으면 기본적으로 홈런을 쳤다. 마찬가지로 다른 조건이 <1% 인 경우 마지막으로 넣습니다.