[解決済み] なぜコンパイラは予測可能な加算ループを乗算に最適化できないのでしょうか？

質問

の見事な回答を読んでいて思いついた質問です。 謎めいた を質問してみました。 なぜソートされた配列の方がソートされていない配列よりも処理が速いのでしょうか？ ?

関係する型のコンテキストです。

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

彼の回答では、Intel コンパイラ (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 の補数整数のオーバーフローに対するラップアラウンド動作が保証されている場合でも、結果が変わってしまいます (if data[c] が 30000 の場合、積は -1294967296 は、典型的な 32 ビット int に 30000 を加えた 100000 回が、ラップアラウンドを持つ sum に 30000 を加算すると、オーバーフローしない場合は sum を3000000000個増やすことになります）。符号なし量についても同じことが言えることに注意してください、異なる数値で、オーバーフローの 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 の発言 どうやら、loop-interchange の後に loop-collapsing パスを実行しないようです。

ループインターチェンジ自体は一般的に有効ではないことに注意してください (符号付き整数の場合)、なぜなら

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] が同じ符号を持つことを保証しているため、1つがオーバーフローすると、両方がオーバーフローします。

コンパイラがそれを考慮したかどうかはあまり自信はありませんが（@Mysticialさん、以下のような条件で試してみてください。 data[c] & 0x80 のような、正負の値に対して真となるような条件で試してみてはいかがでしょうか?） 私はコンパイラが無効な最適化を行うことがありました (たとえば、数年前、私は ICC (11.0) で 1.0/n ここで n は unsigned int . gccの出力の約2倍の速さでした。しかし、間違って、多くの値が 2^31 よりも大きな値を出力していました。）