컴파일러가 예측 가능한 추가 루프를 곱셈으로 최적화 할 수없는 이유는 무엇입니까?

컴파일러가 예측 가능한 추가 루프를 곱셈으로 최적화 할 수없는 이유는 무엇입니까?

---

이것은 질문에 대한 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];

바라건대 Mysticial (또는 다른 사람)도 똑같이 훌륭한 답변을 줄 수 있습니다. 나는 이전에 다른 질문에서 논의 된 최적화에 대해 배운 적이 없으므로 정말 감사합니다.

---

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

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];

후자는 전자가하지 않은 부호있는 정수의 오버플로를 일으킬 수 있기 때문입니다. 부호있는 2의 보수 정수의 오버플로에 대해 보장 된 랩 어라운드 동작으로도 결과가 변경됩니다 data[c](30000 인 경우 제품은 랩핑이 -1294967296있는 전형적인 32 비트 ints가되고 100000 번 추가하면 30000이 추가 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.

그렇게하지 않는 이유는 알 수 없다. 나는 Mysticial이 "루프 교환 후 루프 붕괴 패스를 실행하지 않는다"고 말했다.

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

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]이 추가 되면 모든 항목 이 동일한 부호를 갖도록 보장 되므로 하나가 넘치면 둘 다 수행됩니다.

I wouldn't be too sure that the compiler took that into account, though (@Mysticial, could you try with a condition like data[c] & 0x80 or so that can be true for positive and negative values?). I had compilers make invalid optimisations (for example, a couple of years ago, I had an ICC (11.0, iirc) use signed-32-bit-int-to-double conversion in 1.0/n where n was an unsigned int. Was about twice as fast as gcc's output. But wrong, a lot of values were larger than 2^31, oops.).

---

This answer does not apply to the specific case linked, but it does apply to the question title and may be interesting to future readers:

Due to finite precision, repeated floating-point addition is not equivalent to multiplication. Consider:

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);

Demo

---

The compiler contains various passes which does the optimization. Usually in each pass either an optimization on statements or loop optimizations are done. At present there is no model which does an optimization of loop body based on the loop headers. This is hard to detect and less common.

The optimization which was done was loop invariant code motion. This can be done using a set of techniques.

---

Well, I'd guess that some compilers might do this sort of optimization, assuming that we are talking about Integer Arithmetics.

At the same time, some compilers might refuse to do it because replacing repetitive addition with multiplication might change the overflow behavior of the code. For unsigned integer types, it shouldn't make a difference since their overflow behavior is fully specified by the language. But for signed ones, it might (probably not on 2's complement platform though). It is true that signed overflow actually leads to undefined behavior in C, meaning that it should be perfectly OK to ignore that overflow semantics altogether, but not all compilers are brave enough to do that. It often draws a lot of criticism from the "C is just a higher-level assembly language" crowd. (Remember what happened when GCC introduced optimizations based on strict-aliasing semantics?)

Historically, GCC has shown itself as a compiler that has what it takes to take such drastic steps, but other compilers might prefer to stick with the perceived "user-intended" behavior even if it is undefined by the language.

---

There's a conceptual barrier to this kind of optimization. Compiler authors spend a lot of effort on strength reduction -- for instance, replacing multiplications with adds and shifts. They get used to thinking that multiplies are bad. So a case where one ought to go the other way is surprising and counterintuitive. So nobody thinks to implement it.

---

The people who develop and maintain compilers have a limited amount of time and energy to spend on their work, so they generally want to focus on what their users care about the most: turning well-written code into fast code. They don't want to spend their time trying to find ways to turn silly code into fast code—that's what code review is for. In a high-level language, there may be "silly" code that expresses an important idea, making it worth the developers' time to make that fast—for example, short cut deforestation and stream fusion allow Haskell programs structured around certain kinds of lazily produced data structures to be compiled into tight loops that don't allocate memory. But that sort of incentive simply does not apply to turning looped addition into multiplication. If you want it to be fast, just write it with multiplication.

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