c/c++ 컴파일러는 2의 거듭제곱 값에 의한 상수 분할을 시프트로 최적화합니까?

c/c++ 컴파일러는 2의 거듭제곱 값에 의한 상수 분할을 시프트로 최적화합니까?

질문이 모든 것을 말해줍니다.혹시 다음이...

size_t div(size_t value) {
    const size_t x = 64;
    return value / x;
}

...에 최적화되어 있습니까?

size_t div(size_t value) {
    return value >> 6;
}

컴파일러가 이것을 합니까?(제 관심은 GCC에 있습니다.)그럴 수 있는 상황과 그렇지 않은 상황이 있습니까?

저는 정말 알고 싶습니다. 왜냐하면 제가 이렇게 최적화될 수 있는 부서를 쓸 때마다 저는 정신적인 에너지를 소비합니다. 1초의 소중한 것이 전환이 가능한 부서에서 낭비되는 것이 아닌지에 대해 궁금해하기 때문입니다.

을 가지고도g++ -O0(예,-O0!), 이렇게 됩니다.기능은 다음으로 압축됩니다.

_Z3divm:
.LFB952:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        movq    %rdi, -24(%rbp)
        movq    $64, -8(%rbp)
        movq    -24(%rbp), %rax
        shrq    $6, %rax
        leave
        ret

참고:shrq $66자리 차이로 오른쪽으로 이동합니다.

와 함께-O1불필요한 정크가 제거됩니다.

_Z3divm:
.LFB1023:
        movq    %rdi, %rax
        shrq    $6, %rax
        ret

g++ 4.3.3, x64에 대한 결과입니다.

대부분의 컴파일러는 2의 거듭제곱을 시프트로 줄이는 것보다 더 나아가 CPU에 내장된 분할 명령(있는 경우)을 사용하는 대신 정수 분할을 상수로 일련의 곱셈, 시프트 및 추가 명령으로 변환하여 결과를 얻는 경우가 많습니다.

예를 들어 MSVC는 71로 나눗셈을 다음과 같이 변환합니다.

// volatile int y = x / 71;

8b 0c 24        mov ecx, DWORD PTR _x$[esp+8] ; load x into ecx

b8 49 b4 c2 e6  mov eax, -423447479 ; magic happens starting here...
f7 e9           imul ecx            ; edx:eax = x * 0xe6c2b449

03 d1           add edx, ecx        ; edx = x + edx

c1 fa 06        sar edx, 6          ; edx >>= 6 (with sign fill)

8b c2           mov eax, edx        ; eax = edx
c1 e8 1f        shr eax, 31         ; eax >>= 31 (no sign fill)
03 c2           add eax, edx        ; eax += edx

89 04 24        mov DWORD PTR _y$[esp+8], eax

그래서, 곱셈으로 71의 나눗셈을 얻고, 두 번 교대하고, 두 번 더하면 됩니다.

무슨 일이 일어나고 있는지에 대한 자세한 내용은 Henry Warren의 Hacker's Delight 책 또는 동반 웹 페이지를 참조하십시오.

• https://web.archive.org/web/20190515215157/http ://www.hackersdelight.org/

곱셈/쉬프트/추가 마법 번호를 사용한 상수별 분할에 대한 몇 가지 추가 정보를 제공하는 온라인 추가 장과 필요한 마법 번호를 계산할 수 있는 작은 JavaScript 프로그램이 있는 페이지가 있습니다.

이 책의 동반 사이트는 특히 비트 수준의 미세 최적화에 관심이 있다면 (책과 마찬가지로) 읽을 가치가 있습니다).

이 최적화에 대해 설명하는 또 다른 기사는 https://learn.microsoft.com/en-us/archive/blogs/devdev/integer-division-by-constants 입니다.

주장이 긍정적이라고 판단할 수 있을 때만.예를 들어 그렇습니다만, C99가 정수 분할에 대해 0을 향한 반올림 의미론을 지정한 이후로, 부정적인 인수에 대해 서로 다른 결과를 제공하기 때문에 시프트로 2의 거듭제곱에 의한 분할을 최적화하는 것이 더 어려워졌습니다.

하여, 의 한 과 같습니다.r=x/p;x의 거듭제곱으로.p컴파일러에 의해 실제로 번역될 수 있습니다.

if (x<0)
  x += p-1;
r = x >> (log2 p);

OP가 이러한 것들에 대해 생각해야 하는지를 물었기 때문에, 가능한 한 가지 대답은 "당신이 컴파일러보다 배당 기호를 더 잘 알고 있거나 결과가 0 또는 -0으로 반올림되어도 상관없다는 것을 알고 있는 경우에만"일 것입니다.

예, 컴파일러는 이러한 단순 계산에 가장 적합한 코드를 생성합니다.하지만, 왜 당신이 구체적으로 "전환"을 주장하는지는 저에게 명확하지 않습니다.주어진 플랫폼에 대한 최적의 코드는 쉽게 "이동"과 다른 것으로 밝혀질 수 있습니다.

일반적으로 "전환"이 2의 거듭제곱 곱셈과 나눗셈을 구현하는 가장 최적의 방법이라는 오래되고 치명적인 생각은 현대 플랫폼에서 실질적인 관련성이 거의 없습니다.이것은 신인들에게 "최적화"의 개념을 설명하는 좋은 방법이지만, 그 이상은 아닙니다.

원래 예제는 서명되지 않은 형식을 사용하므로 분할 작업 구현이 크게 단순화되므로 실제로 대표적인 예는 아닙니다.C 언어와 C++ 언어의 "제로를 향한 라운드" 요구사항은 피연산자가 서명된 경우 단순한 이동으로 나눗셈을 수행하는 것을 불가능하게 만듭니다.

언급URL : https://stackoverflow.com/questions/2580680/does-a-c-c-compiler-optimize-constant-divisions-by-power-of-two-value-into-shi