12

次のコードを検討してください

 vector<double> v;
 // fill v
 const vector<double>::iterator end =v.end();
 for(vector<double>::iterator i = v.bgin(); i != end; ++i) {
   // do stuff
 }

g++、clang++、icc などのコンパイラは、このようなループを展開できますか? 残念ながら、アセンブリが出力からループが展開されるかどうかを確認できるかどうかはわかりません。（そして、私はg ++にしかアクセスできません。）

私には、これにはコンパイラーに代わって通常よりもスマートさが必要になるように思われます。最初にイテレーターがランダムアクセスイテレーターであると推測し、次にループが実行される回数を把握します。最適化が有効になっている場合、コンパイラはこれを行うことができますか?

返信ありがとうございます。時期尚早な最適化について講義を始める前に、これは好奇心のエクササイズです。

4

4 に答える 4

8

コンパイラが最新のパイプライン化されたアーキテクチャとキャッシュを使用してループをアンロールできるかどうかにかかわらず、「何かをする」ことが些細でない限り、そうするメリットはほとんどなく、多くの場合、そうすることでパフォーマンスが低下することを提案します。恩恵の。"do stuff" が重要な場合、ループをアンロールすると、この重要なコードの複数のコピーが作成され、キャッシュにロードするのに余分な時間がかかり、アンロールされたループの最初の反復が大幅に遅くなります。同時に、キャッシュからより多くのコードを削除します。これは、関数呼び出しを行った場合に "do stuff" を実行するために必要だった可能性があるため、キャッシュに再度再読み込みする必要があります。ループをアンロールする目的は、キャッシュレス パイプライン化された非分岐予測アーキテクチャが登場する前に、非常に理にかなっています。目的は、ループ ロジックに関連するオーバーヘッドを削減することです。現在、キャッシュベースのパイプライン化された分岐予測ハードウェアを使用すると、CPU は次のループ反復に十分にパイプライン化され、ループ コードを投機的に再度実行し、i==end 終了条件を検出するまでにプロセッサがスローします。投機的に実行された最終的な結果セットを取り出します。このようなアーキテクチャでは、ループ展開はほとんど意味がありません。コードをさらに肥大化させ、事実上何のメリットもありません。その時点で、プロセッサは投機的に実行された最終的な結果セットを破棄します。このようなアーキテクチャでは、ループ展開はほとんど意味がありません。コードをさらに肥大化させ、事実上何のメリットもありません。その時点で、プロセッサは投機的に実行された最終的な結果セットを破棄します。このようなアーキテクチャでは、ループ展開はほとんど意味がありません。コードをさらに肥大化させ、事実上何のメリットもありません。

于 2012-07-17T19:19:49.053 に答える
6

私には、これにはコンパイラに代わって通常よりもスマートさが必要になるように思われます。最初に反復子がランダムアクセス反復子であると推測し、次にループが実行される回数を把握します。

完全にテンプレートで構成される STL には、すべてのコードが含まれていますinline。そのため、ランダム アクセス反復子は、コンパイラが最適化の適用を開始した時点で既にポインターに縮小されています。STL が作成された理由の 1 つは、プログラマーがコンパイラーの裏をかく必要が少なくなるようにするためでした。そうでないことが証明されるまでは、正しいことを行うために STL に依存する必要があります。

もちろん、使用する STL から適切なツールを選択するのはあなた次第です...

編集：g++ループ展開を行うかどうかについての議論がありました。私が使用しているバージョンでは、ループ展開は-O、-O2、またはの一部ではありません-O3。次のコードを使用して、後者の 2 つのレベルで同一のアセンブリを取得します。

void foo (std::vector<int> &v) {
    volatile int c = 0;
    const std::vector<int>::const_iterator end = v.end();
    for (std::vector<int>::iterator i = v.begin(); i != end; ++i) {
        *i = c++;
    }
}

対応するアセンブリ-O2アセンブリ:

_Z3fooRSt6vectorIiSaIiEE:
.LFB435:
        movq    8(%rdi), %rcx
        movq    (%rdi), %rax
        movl    $0, -4(%rsp)
        cmpq    %rax, %rcx
        je      .L4
        .p2align 4,,10
        .p2align 3
.L3:
        movl    -4(%rsp), %edx
        movl    %edx, (%rax)
        addq    $4, %rax
        addl    $1, %edx
        cmpq    %rax, %rcx
        movl    %edx, -4(%rsp)
        jne     .L3
.L4:
        rep
        ret

オプションを追加する-funroll-loopsと、関数ははるかに大きなものに拡張されます。ただし、ドキュメントではこのオプションについて警告しています。

コンパイル時またはループの開始時に反復回数を決定できるループを展開します。-funroll-loops は、-frerun-cse-after-loop を意味します。また、完全なループ ピーリングを有効にします (つまり、一定回数の繰り返しでループを完全に削除します)。このオプションはコードを大きくしますが、実行が速くなる場合とそうでない場合があります。

ループを自分で展開することを思いとどまらせるためのさらなる議論として、上記の関数にDuff's Deviceを適用する図でこの回答を締めくくります。foo

void foo_duff (std::vector<int> &v) {
    volatile int c = 0;
    const std::vector<int>::const_iterator end = v.end();
    std::vector<int>::iterator i = v.begin();
    switch ((end - i) % 4) do {
    case 0: *i++ = c++;
    case 3: *i++ = c++;
    case 2: *i++ = c++;
    case 1: *i++ = c++;
    } while (i != end);
}

GCC には別のループ最適化フラグがあります。

-ftree-loop-optimize
ツリーでループの最適化を実行します。このフラグは、以降でデフォルトで有効になっています-O。

そのため、この-Oオプションは、反復回数が固定されたループの完全なループ展開 (ピーリング) を含む、最も内側のループの単純なループ最適化を有効にします。（これを指摘してくれたdocに感謝します。）

于 2012-07-17T19:30:52.023 に答える
1

短い答えはイエスです。可能な限り展開します。あなたの場合、end明らかに定義する方法に依存します（あなたの例は一般的だと思います）。最近のほとんどのコンパイラはアンロールするだけでなく、ベクトル化やその他の最適化も行います。これにより、独自のソリューションが水から吹き飛ばされることがよくあります。

つまり、時期尚早に最適化しないでください。冗談だ ：）

于 2012-07-17T18:58:44.820 に答える