c - 設定 - 高速化プログラミング入門




コンパイラが予測可能な加算ループを乗算に最適化できないのはなぜですか? (4)

Mysticial 、ソートされていない配列よりもソートされた配列を処理する方が速いのはなぜですか?

関係するタイプのコンテキスト:

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

彼の答えでは、Intel Compiler(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];

うまくいけばミステリアンな(または他の誰か)も同様に素晴らしい答えを与えることができます。 これまで他の質問で述べた最適化については学ばなかったので、本当に感謝しています。


この回答はリンクされた特定のケースには適用されませんが、質問のタイトルに適用され、将来の読者にとって興味深いかもしれません:

有限精度のため、繰り返し浮動小数点加算は乗算と等価ではありません 。 検討してください:

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

デモ: http://ideone.com/7RhfP : http://ideone.com/7RhfP


この種の最適化には概念上の障壁があります。 コンパイラ作成者は、増分を加算やシフトに置き換えるなど、 強度低下に多くの労力を費やしています。 彼らは倍数が悪いと考えることに慣れています。 だからといって、別のやり方にしなければならない場合は、驚くべきことと直観に反します。 誰もそれを実装するとは思わない。


コンパイラには、最適化を行うさまざまなパスが含まれています。 通常、各パスでは、最適化ステートメントまたはループ最適化が行われます。 現在、ループヘッダに基づいてループボディの最適化を行うモデルは存在しない。 これは検出しにくく、あまり一般的ではありません。

最適化はループ不変のコードの動きでした。 これは一連の技術を使用して行うことができます。


コンパイラの開発と保守を行う人は、作業に費やす時間とエネルギーが限られているため、一般的には、よく書かれたコードを高速なコードに変換するという、ユーザの関心に集中したいと考えています。 彼らは、愚かなコードを高速なコードに変える方法を見つけようと、時間を費やしたくはありません。これがコードレビューの目的です。 高水準言語では、重要なアイデアを表現する「愚かな」コードがあり、開発者の時間を短縮する価値があります。たとえば、短期的な森林破壊とストリーム融合により、特定の種類の遅延型メモリを割り当てないタイトなループにコンパイルされるデータ構造を生成しました。 しかし、そのようなインセンティブは、単にループされた加算を乗算に変えることには適用されません。 速くしたいのであれば、それを乗算して書くだけです。





compiler-optimization