컴파일러가 예측 가능한 덧셈 루프를 곱셈에 최적화할 수 없는(또는 그렇지 않은) 이유는 무엇입니까?

컴파일러가 예측 가능한 덧셈 루프를 곱셈에 최적화할 수 없는(또는 그렇지 않은) 이유는 무엇입니까?

이 질문은 Mysticial의 훌륭한 답변을 읽으면서 떠오른 질문입니다.왜 정렬된 배열이 정렬되지 않은 배열보다 더 빠를까요?

관련된 유형의 컨텍스트:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

그는 인텔 컴파일러(ICC)가 이를 최적화하고 있다고 답변했습니다.

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

...이것에 상당하는 무엇인가가 됩니다.

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

옵티마이저는 이들 값이 동등함을 인식하고 루프를 교환하여 브런치를 내부 루프 밖으로 이동합니다.똑똑해!

근데 왜 이렇게 안 되지?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

미스테리컬(또는 다른 사람)도 마찬가지로 훌륭한 답변을 할 수 있기를 바랍니다.지금까지 그 질문에서 설명한 최적화에 대해 배운 적이 없기 때문에 정말 감사합니다.

컴파일러는 일반적으로 변환할 수 없습니다.

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

안으로

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

왜냐하면 후자는 부호 있는 정수를 넘치게 할 수 있지만 전자는 그렇지 않거든요서명된 두 개의 보완 정수의 오버플로에 대한 랩 어라운드 동작이 보장되더라도 결과는 변경됩니다(이 경우).data[c]3만개면 제품이 3만개면-1294967296표준 32비트의 경우int랩 어라운드를 사용하여30,000을 100,000배로 추가합니다.sum만약 그것이 넘쳐나지 않는다면,sum3000000000).다른 숫자의 부호 없는 수량, 오버플로에 대해서도 동일한 값이 유지된다는 점에 유의하십시오.100000 * data[c]전형적으로 감소모듈로를 도입할 것이다.2^32최종 결과에는 나타나지 않아야 합니다.

변형이 될 수도 있어

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

하지만, 만약, 평소처럼,long long보다 충분히 크다int.

왜 그렇게 하지 않는지는 알 수 없습니다.미스티컬이 말한 "루프 인터체인지 후에 루프 콜랩핑 패스를 실행하지 않는 것 같습니다.

루프 교환 자체는 일반적으로 유효하지 않습니다(서명된 정수).

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

넘쳐흐를 수 있다

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

하지 않을.여긴 조용해 왜냐면 모든 게 보장되니까data[c]추가되는 부호는 같기 때문에 하나의 부호가 오버플로우하면 둘 다 오버플로우됩니다.

컴파일러가 그것을 고려했을지는 잘 모르겠습니다만(@Mysticial, 다음과 같은 조건으로 시도해 주시겠습니까?data[c] & 0x80또는 양수 및 음수 값에 대해 해당될 수 있습니다.컴파일러에게 무효 최적화를 의뢰했습니다(예를 들어, 몇 년 전에 ICC(11.0, iirc)는 부호화된 32비트의 int-to-double 변환을 실시했습니다).1.0/n어디에n였다unsigned intgcc 출력보다 약 2배 빠릅니다.하지만 틀렸습니다. 많은 값이 더 컸습니다.2^31, ohs.)

이 답변은 링크된 특정 케이스에는 적용되지 않지만 질문 제목에는 적용되며 향후 독자들에게 흥미로운 내용이 될 수 있습니다.

한정된 정밀도로 인해 부동 소수점 덧셈을 반복하는 것은 곱셈에 해당하지 않습니다.고려사항:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

데모

적어도 쨍그랑거리는 다음과 같은 일을 하고 있습니다.

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

-O1과 컴파일하여 ~로 하다

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

---

정수 오버플로와는 관계가 없습니다.정의되지 않은 동작을 일으키는 정수 오버플로가 있는 경우 어느 경우든 발생할 수 있습니다.다음은 대신 을 사용하는 동일한 종류의 함수를 나타냅니다.

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

-O1과 컴파일하여 ~로 하다

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

컴파일러를 개발 및 관리하는 사람들은 작업에 소비하는 시간과 에너지가 한정되어 있기 때문에 일반적으로 사용자가 가장 신경 쓰는 것, 즉 잘 작성된 코드를 빠른 코드로 바꾸는 것에 초점을 맞추고 싶어합니다.그들은 바보 같은 코드를 빠른 코드로 바꾸는 방법을 찾는데 시간을 낭비하고 싶지 않다.그것이 코드 리뷰의 목적이다.높은 수준의 언어에서는 중요한 아이디어를 표현하는 "멍청한" 코드가 있을 수 있습니다.예를 들어, 숏컷 삼림 벌채와 스트림 퓨전(stream fusion)을 통해 Haskell 프로그램은 메모리를 할당하지 않는 엄격한 루프로 컴파일할 수 있습니다.그러나 이러한 인센티브는 단순히 반복 덧셈을 곱셈으로 바꾸는 것에는 적용되지 않습니다.빨리 하고 싶으면 곱셈으로 쓰면 돼요.

음, 일부 컴파일러는 정수 산술에 대해 이야기한다고 가정할 때 이러한 최적화를 수행할 수 있습니다.

동시에 일부 컴파일러는 반복 덧셈을 곱셈으로 대체하면 코드의 오버플로 동작이 변경될 수 있기 때문에 이를 거부할 수 있습니다.부호 없는 정수 유형의 경우 오버플로 동작이 언어로 완전히 지정되므로 차이가 없습니다.그러나 서명된 경우에는 (아마도 2의 보완 플랫폼에는 없을 것입니다)서명된 오버플로는 실제로 C에서 정의되지 않은 동작을 초래하는 것은 사실이며, 이는 오버플로의 의미를 완전히 무시해도 된다는 것을 의미하지만 모든 컴파일러가 그렇게 할 만큼 용감한 것은 아닙니다.이것은 종종 "C는 단지 더 높은 수준의 어셈블리 언어일 뿐"이라는 군중으로부터 많은 비판을 받습니다.(GCC가 엄격한 에일리어싱 의미론에 기초한 최적화를 도입했을 때 어떤 일이 일어났는지 기억하십니까?)

지금까지 GCC는 이러한 과감한 조치를 취하기 위한 요건을 갖춘 컴파일러로 알려져 왔지만, 다른 컴파일러는 언어에 의해 정의되지 않은 경우에도 인식된 "사용자 의도" 동작을 계속하는 것을 선호할 수 있습니다.

컴파일러에는 최적화를 위한 다양한 패스가 포함되어 있습니다.보통 각 패스에서 스테이트먼트에 대한 최적화 또는 루프 최적화가 이루어집니다.현재 루프 헤더를 기반으로 루프 본체를 최적화하는 모델은 없습니다.이것은 검출하기 어렵고, 흔하지 않습니다.

최적화한 것은 루프 불변 코드 모션입니다.이 작업은 일련의 기술을 사용하여 수행할 수 있습니다.

이러한 최적화에는 개념적인 장벽이 있습니다.컴파일러 작성자는 예를 들어 곱셈을 추가 및 시프트로 대체하는 등 강도 저하에 많은 노력을 기울입니다.그들은 곱셈이 나쁘다고 생각하는 것에 익숙해져 있다.그래서 누군가 다른 길로 가야 하는 경우는 놀랍고 직관에 어긋난다.그래서 아무도 그것을 실행할 생각을 하지 않는다.

언급URL : https://stackoverflow.com/questions/11276291/why-cant-or-doesnt-the-compiler-optimize-a-predictable-addition-loop-into-a