133

これは、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];

うまくいけば、ミスティック（または他の誰か）が同様に素晴らしい答えを与えることができます。他の質問で説明した最適化についてはこれまで学んだことがないので、本当に感謝しています。

4

7 に答える 7

106

コンパイラは一般的に変換できません

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ビットになりますがint、100000回に30000を追加するsumと、オーバーフローしません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が「どうやら、ループ交換後にループ崩壊パスを実行しない」と言ったのだと思います。

ループ交換自体は一般的に有効ではないことに注意してください（符号付き整数の場合）。

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）でsigned-32-bit-int-to-double変換を使用し1.0/nましnたunsigned int。これはgccの約2倍の速さでした。出力。しかし、間違って、多くの値が2^31、おっとよりも大きかった。）

于 2012-06-30T19:31:49.357 に答える
48

この回答は、リンクされている特定のケースには適用されませんが、質問のタイトルには適用され、将来の読者にとって興味深いものになる可能性があります。

精度が有限であるため、浮動小数点の繰り返し加算は乗算と同等ではありません。検討：

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

デモ

于 2012-06-30T18:11:23.763 に答える
6

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

行われた最適化は、ループ不変コードモーションでした。これは、一連の手法を使用して実行できます。

于 2012-06-30T18:00:17.793 に答える
4

整数演算について話していると仮定すると、一部のコンパイラはこの種の最適化を行う可能性があると思います。

同時に、繰り返し加算を乗算に置き換えるとコードのオーバーフロー動作が変わる可能性があるため、一部のコンパイラはそれを拒否する場合があります。符号なし整数型の場合、オーバーフロー動作は言語によって完全に指定されているため、違いはありません。しかし、署名されたものの場合、それは可能性があります（おそらく2の補数プラットフォームではありません）。署名されたオーバーフローが実際にCで未定義の動作を引き起こすことは事実です。つまり、オーバーフローのセマンティクスを完全に無視してもまったく問題ありませんが、すべてのコンパイラがそれを実行できるほど勇敢であるとは限りません。多くの場合、「Cは単なる高レベルのアセンブリ言語です」という群衆から多くの批判が寄せられます。（GCCが厳密なエイリアシングセマンティクスに基づく最適化を導入したときに何が起こったか覚えていますか？）

歴史的に、GCCは、そのような抜本的な手順を実行するために必要なものを備えたコンパイラーとしての地位を示してきましたが、他のコンパイラーは、言語によって定義されていない場合でも、知覚される「ユーザー意図」の動作に固執することを好む場合があります。

于 2012-06-30T18:09:44.437 に答える
4

今ではそうです-少なくとも、clangはそうします：

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

整数のオーバーフローはそれとは何の関係もありません。未定義動作を引き起こす整数オーバーフローがある場合は、どちらの場合でも発生する可能性があります。代わりに使用する同じ種類の関数をintlong次に示します。

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
于 2019-12-31T16:12:08.293 に答える
2

この種の最適化には概念的な障壁があります。コンパイラの作成者は、強度の低下に多大な労力を費やしています。たとえば、乗算を加算とシフトに置き換えます。彼らは、乗算は悪いと考えることに慣れています。したがって、一方が反対の方向に進むべきである場合は、驚くべきことであり、直感に反します。したがって、誰もそれを実装しようとは考えていません。

于 2012-06-30T18:20:54.753 に答える
1

コンパイラーを開発および保守する人々は、作業に費やす時間とエネルギーが限られているため、一般に、ユーザーが最も気にかけていること、つまり適切に記述されたコードを高速コードに変換することに集中したいと考えています。彼らは、ばかげたコードを高速なコードに変える方法を見つけることに時間を費やしたくありません。それがコードレビューの目的です。高水準言語では、重要なアイデアを表現する「ばかげた」コードが存在する可能性があり、開発者がそれを高速化するのに時間をかける価値があります。たとえば、ショートカットの森林伐採とストリームフュージョンにより、特定の種類の怠惰なHaskellプログラムを構築できます。メモリを割り当てないタイトなループにコンパイルされるデータ構造を生成しました。しかし、そのようなインセンティブは、ループ加算を乗算に変えることには適用されません。高速にしたい場合は、

于 2014-09-29T02:07:47.087 に答える