7 
void foo(const int constant)
{
    for(int i = 0; i < 1000000; i++) {
        // do stuff
        if(constant < 10) {              // Condition is tested million times :(
            // inner loop stuff
        }
    }
}

外側のループを実行するたびに、「定数」の値がチェックされます。ただし、定数は決して変更されないため、定数 < 10 の条件をテストするために多くの CPU 時間が浪費されていますか? 何度も何度も。人間は、最初の数回のパスの後、定数が決して変わらないことに気づき、何度も何度もチェックすることを賢く避けます。コンパイラはこれに気づき、インテリジェントに最適化しますか、それとも if ループの繰り返しは避けられませんか?

個人的には、この問題は避けられないと思います。コンパイラが外側のループの前に比較を配置し、ある種のブール変数「skip_inner_stuff」を設定したとしても、この変数は外側の for ループのパスごとにチェックする必要があります。

この件についてどう思いますか。問題を回避する上記のコード セグメントを記述するより効率的な方法はありますか?

4

7 に答える 7

6

あなたが説明する最適化は、 loop unswitchingとも呼ばれます。これは、長年にわたってコンパイラの最適化の標準的な部分でした。ただし、コンパイラが確実に実行するようにしたい場合は、サンプル コードを何らかの最適化レベル (gcc の -O2 など) でコンパイルし、生成されたコードを確認してください。

ただし、コードの一部がループ全体で不変であることをコンパイラが証明できない場合 (たとえば、コンパイル時に利用できない外部関数の呼び出しなど) は、実際には、手動でコードをループの外側に引き上げると、非常に大きなパフォーマンスの向上。

于 2013-09-08T07:16:05.190 に答える
3

コンパイラはコードを最適化できますが、コードに対して魔法のトリックを行うとは期待できませんでした。

最適化は、コードとコードの使用法に強く依存します。たとえば、次fooのように使用する場合:

foo(12345);

コンパイラはコードを非常に最適化できます。コンパイル時に結果を計算することさえできます。

しかし、次のように使用する場合:

int k;
cin >> k;
foo(k);

この場合、内部を取り除くことはできませんif(値は実行時に提供されます)。

MinGW/GCC-4.8.0 でサンプルコードを書きました:

void foo(const int constant)
{
    int x = 0;
    for (int i = 0; i < 1000000; i++)
    {
        x++;
        if (constant < 10)
        {
            x--;
        }
    }
    cout << x << endl;
}

int main()
{
    int k;
    cin >> k;
    foo(k);
}

アセンブリ コードの生成を見てみましょう。

004015E1  MOV EAX,0F4240                 // i = 1000000
004015E6  MOV EBP,ESP
004015E8  XOR EDX,EDX
004015EA  PUSH ESI
004015EB  PUSH EBX
004015EC  SUB ESP,10
004015EF  MOV EBX,DWORD PTR SS:[EBP+8]
004015F2  XOR ECX,ECX                    // set ECX to 0
004015F4  CMP EBX,0A                     // if constant < 10
          ^^^^^^^^^^
004015F7  SETGE CL                       // then set ECX to 1
004015FA  ADD EDX,ECX                    // add ECX to i
004015FC  SUB EAX,1                      // i--
004015FF  JNE SHORT 004015F2             // loop if i is not zero

ご覧のとおり、内部ifはコード内に存在します。を参照してくださいCMP EBX,0A。

繰り返しますが、ループのある行に強く依存します。

于 2013-09-08T08:20:23.650 に答える
2

他の人は、関連するコンパイラーの最適化について説明しています。場合によってはコンパイラに実際の値を提供するコードのインライン化によりconstant、テストを削除し、無条件に「内部ループのもの」を実行するか、完全に削除できます。

また、コンパイラが行うこととは別に、最新の CPU 設計では実際に「人間は最初の数回のパスの後、定数が決して変わらないことに気付く」のと同様のことを行うことに注意してください。これは動的分岐予測と呼ばれます。

重要なポイントは、整数のチェックは信じられないほど安価であり、分岐を取ることさえも非常に安価になる可能性があるということです。コストがかかる可能性があるのは、分岐の予測ミスです。最新の CPU はさまざまな戦略を使用して分岐がどちらに進むかを推測しますが、それらの戦略はすべて、同じ方向に 100 万回連続して進む分岐をすぐに正しく予測し始めます。

私が知らないのは、最新の CPU が、それconstantがループの不変条件であることを認識し、マイクロコードで完全なループの切り替えを解除できるほど賢いかどうかということです。しかし、分岐予測が正しいと仮定すると、ループの切り替え解除はおそらくマイナーな最適化です。コンパイラーが対象とするプロセッサー・ファミリーがより具体的であるほど、その分岐予測子の品質についてより多くのことを知ることができ、コンパイラーがループ・アンスイッチングの追加の利点がコードの肥大化に値するかどうかを判断できる可能性が高くなります。

もちろん、コンパイラがすべての巧妙さを提供しなければならない最小の CPU はまだあります。PC の CPU はその 1 つではありません。

于 2013-09-08T09:50:16.063 に答える
1

手で最適化できます：

void foo(const int constant)
{
    if (constant < 10) {
        for(int i = 0; i < 1000000; i++) {
            // do stuff

           // inner loop stuff here
        }
    } else {
        for(int i = 0; i < 1000000; i++) {
            // do stuff

            // NO inner loop stuff here
        }
    }
}

ほとんどのコンパイラがこのようなことを行うかどうかはわかりませんが、大したことではないようです。

于 2013-09-08T07:18:41.467 に答える
0

優れたコンパイラはそれを最適化します (最適化が有効になっている場合)。

GCCを使用している場合

  • 最適化を使用してコンパイルし、アセンブリ コードを生成します。

     gcc -Wall -O2 -fverbose-asm -S source.c

    less次に、生成されたアセンブリ コードを (エディタまたはページャーで) 調べます。source.s

  • GCC に大量 (数百!) の中間ファイルをダンプし、その中の中間 gimple 表現の中を調べるように依頼します。

     gcc -Wall -O2 -fdump-tree-all -c source.c

  • MELTとそのプローブを使用して、ギンプルの中をインタラクティブに調べます。

-Wallfrom gcc(またはg++C++ コードをコンパイルする場合)で常にすべての警告を表示する習慣を身につけてください。

ところで、実際には、そのような最適化（他の回答で説明されている「ループ不変コード巻き上げ」）は不可欠です。これは、このような種類の中間コードが非常に頻繁に発生するためfooです。 ..)

于 2013-09-08T07:15:40.520 に答える