나는 형태의 표현 최적화하는 데 필요한 최적화

Question

논리/관계식 :

(a * 2) > (b + c) 

최적화는 것이 아닌 다음과 같이 I 중 하나는 여러 가지 최적화 된 형태를 시도

(a > b) || (a > c) 

을 컴파일러의 관점. 나는 두 가지를 하나로 줄이고 싶다.

이는 가정에 기초하는 1 < = (를 A, B, C) = 26 <

하지만,이 경우에만 작동한다. 내가하려고하는 최적화가 실제로 가능합니까? 그렇다면 시작이 정말 도움이 될 것입니다.

Answer 1

내가 가지고 올 수있는 최선이이 입력 값의 제약을 활용

40072e:  29 c8     sub %ecx,%eax 
400730:  29 ca     sub %ecx,%edx 
400732:  09 d0     or  %edx,%eax 
400734:  a8 80     test $0x80,%al 
400736:  74 17     je  40074f <main+0x3f> 

하나의 조건 분기를 생성 gcc -O2이

char a, b, c; 
std::cin >> a >> b >> c; 

if (((b-a) | (c-a)) & 0x80) { 
    // a > b || a > c 
} 

입니다 26보다 작 으면 b에서 a을 뺀 값은 a > b 일 때 음수 값을, 두 번째 값은 7이되도록 설정합니다. 같은 경우 0으로 적용됩니다.. 그 다음에 또는 비트 모두 7은 a > b || a > c인지 여부를 나타냅니다. 마지막으로 비트 7은 이고,은 0x80이고 분기점은 검사합니다.

업데이트 : 호기심에서 벗어난이 4 가지 코딩 방법으로 시간을 조정했습니다. 테스트 데이터를 생성하기 위해 간단한 선형 합동 의사 난수 생성기를 사용했습니다. 나는 1 억회 반복을 위해 루프를 수행했다.단순함을 가정 할 때 조건이 true이면 카운터에 5를 더하고, 그렇지 않으면 아무것도하지 않겠다고 가정했습니다. 나는 -O2 최적화 수준을 사용하여 Intel Xeon X5570 @ 2.93GHz에 g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)을 사용하여 시간을 측정했습니다. 우리는 하나입니다 마스크를 생성하는 부호 확장을 사용하여 내 대답에 제안에 수정 가장 빠른

#include <iostream> 
unsigned myrand() { 
    static unsigned x = 1; 
    return (x = x * 1664525 + 1013904223); 
} 

int main() { 
    size_t count = 0; 
    for(size_t i=0; i<100000000; ++i) { 
     int a = 1 + myrand() % 26; 
     int b = 1 + myrand() % 26; 
     int c = 1 + myrand() % 26; 

     count += 5 & (((b-a) | (c-a)) >> 31);  // 0.635 sec 
     //if (((b-a) | (c-a)) & 0x80) count += 5;  // 0.660 sec 
     //if (a > std::max(b,c)) count += 5;   // 0.677 sec 
     //if (a > b || a > c) count += 5;   // 1.164 sec 
    } 
    std::cout << count << std::endl; 
    return 0; 
} 

됩니다 : 여기

코드 (조건부 변형 중 하나를 제외한 모든 주석)의 32 1s 또는 32 0s이 있으며 조건이 거짓인지 여부에 따라 다르며이를 사용하여 5을 마스크하여 5 또는 0을 추가합니다.이 변형에는 분기가 없습니다. 시간은 각 행에 주석으로 표시됩니다. 가장 느린 것은 원래 식 (a > b || a > c)입니다.

Answer 2

대답은 아마도 : 당신은 그것을 최적화하고 싶지 않을 것입니다. 더욱이이를 더 효율적으로 작성하는 방법이 없다는 점은 의심 스럽습니다. 만약 a, b, c가 1과 26 사이의 값이라면, 어쨌든 최적의 크기가되고 싶다면 정수 (정수는 필요 없다)를 사용하면 안된다.

a> b 인 경우 a> c 표현은 어쨌든 실행되지 않습니다. 따라서 최대 2 개 (및 최소 1 개)의 조건부 연산을 수행 할 수 있습니다. 이는 최적화할만한 가치가 없습니다.

Answer 3

저는 이것이 대부분의 경우에도 최적화라고 의심합니다.

compare a b 
jump not greater 
compare a c 
jump not greater 

a * 2 > b + c 

주는 곳 :

shift a left 1 (in temp1) 
add b to c (in temp2) 
compare temp1 temp2 
jump if not greater 

을 항상 성능과 실제에 대한 결정을 기반으로하는 것이 훨씬 낫다에

a > b || a > c 

평가한다 성능 측정법 (프로세서 아키텍처를 선택하는 것이 바람직 함). 값이 클 수 없습니다 때문에