158

更新されました。以下を参照してください。

C ++ 0xを使用すると、コンパイラが次のスニペットの「Hello」を出力できることを聞いて読んだことがあります。

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

それは明らかにスレッドと最適化機能と関係があります。しかし、これは多くの人々を驚かせる可能性があるように私には思えます。

誰かがこれが許可するために必要だった理由の良い説明を持っていますか?参考までに、最新のC++0xドラフトは次のように述べています。6.5/5

forステートメントの場合のfor-init-statementの外側で、ループが発生します。

  • ライブラリI/O関数を呼び出さず、
  • 揮発性オブジェクトにアクセスまたは変更せず、
  • 同期操作(1.10)またはアトミック操作(29節)を実行しません

実装によって終了すると想定される場合があります。[注:これは、終了が証明できない場合でも、空のループの削除などのコンパイラー変換を可能にすることを目的としています。—エンドノート]

編集:

この洞察に満ちた記事は、その標準のテキストについて述べています

残念ながら、「未定義動作」という言葉は使用されていません。ただし、標準で「コンパイラはPを想定する可能性がある」と記載されている場合は常に、プロパティnot-Pを持つプログラムのセマンティクスが未定義であることを意味します。

それは正しいですか、コンパイラは上記のプログラムに対して「Bye」を出力することを許可されていますか?


ここにはさらに洞察に満ちたスレッドがあります。これは、上記のリンクされた記事を行ったGuyによって開始された、Cと同様の変更に関するものです。他の有用な事実の中で、それらはC ++ 0xにも適用されるように見える解決策を提示します(更新:これはn3225ではもう機能しません-以下を参照してください!)

endless:
  goto endless;

コンパイラはそれを最適化することを許可されていないようです。なぜなら、それはループではなく、ジャンプだからです。別の男がC++0xとC201Xで提案された変更を要約します

ループを作成することにより、プログラマーは、ループが目に見える動作(I / Oの実行、揮発性オブジェクトへのアクセス、同期またはアトミック操作の実行)で何かを実行するか、 最終的に終了することを表明します。副作用のない無限ループを記述してその仮定に違反した場合、私はコンパイラーに嘘をつき、プログラムの動作は未定義になります。(運が良ければ、コンパイラーはそれについて警告するかもしれません。)この言語は、目に見える振る舞いなしに無限ループを表現する方法を提供していません(もはや提供していませんか?)。


2011年3月1日にn3225で更新:委員会はテキストを1.10 / 24に移動し、次のように述べます。

実装では、任意のスレッドが最終的に次のいずれかを実行すると想定する場合があります。

  • 終了、
  • ライブラリI/O関数を呼び出します。
  • 揮発性オブジェクトにアクセスまたは変更する、または
  • 同期操作またはアトミック操作を実行します。

gotoトリックはもう機能しません!

4

8 に答える 8

46

私にとって、関連する正当化は次のとおりです。

これは、終了が証明できない場合でも、空のループの削除などのコンパイラ変換を可能にすることを目的としています。

おそらく、これは、終了を機械的に証明することが困難であり、終了を証明できないことが、ループの前から後へ、またはその逆に非依存操作を移動したり、1つのスレッドでループ後の操作を実行したりするなど、有用な変換を行う可能性のあるコンパイラを妨げるためです。ループは別のループで実行され、以下同様に続きます。これらの変換がないと、1つのスレッドがループを終了するのを待つ間、ループが他のすべてのスレッドをブロックする可能性があります。(私は「スレッド」を大まかに使用して、個別のVLIW命令ストリームを含むあらゆる形式の並列処理を意味します。)

編集:ばかげた例:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

complex_io_operationここでは、一方のスレッドがループ内のすべての複雑な計算を実行している間に、もう一方のスレッドが実行する方が高速です。しかし、引用した句がないと、コンパイラは最適化を行う前に2つのことを証明する必要があります。1)complex_io_operation()ループの結果に依存しないこと、および2)ループが終了することです。1)の証明は非常に簡単で、2)の証明は停止性問題です。この句を使用すると、ループが終了し、並列化が成功すると想定できます。

また、設計者は、実稼働コードで無限ループが発生するケースは非常にまれであり、通常、何らかの方法でI/Oにアクセスするイベント駆動型ループのようなものであると考えていたと思います。その結果、彼らはより一般的なケース(無限ではないが、機械的に無限でないループを証明することは困難)を最適化することを支持して、まれなケース(無限ループ)を悲観的にしました。

ただし、これは、例の学習で使用される無限ループが結果として影響を受け、初心者コードで落とし穴が発生することを意味します。これが完全に良いことだとは言えません。

編集:あなたが今リンクしている洞察に満ちた記事に関して、私は「コンパイラはプログラムについてXを仮定するかもしれない」は「プログラムがXを満たさない場合、振る舞いは未定義である」と論理的に同等であると言います。これを次のように示すことができます。プロパティXを満たさないプログラムが存在するとします。このプログラムの動作はどこで定義されますか?標準は、プロパティXが真であると仮定して動作を定義するだけです。標準では、動作が未定義であると明示的に宣言されていませんが、省略により未定義であると宣言されています。

同様の議論を考えてみましょう。「コンパイラは、変数xがシーケンスポイント間で最大1回だけ割り当てられると想定する場合があります」は、「シーケンスポイント間でxに複数回割り当てることは未定義です」と同等です。

于 2010-08-28T22:01:26.160 に答える
36

誰かがこれが許可するために必要だった理由の良い説明を持っていますか?

はい、Hans Boehmは、N1528でこれの理論的根拠を提供しています。なぜ無限ループの未定義動作なのですか?、これはWG14ドキュメントですが、理論的根拠はC ++にも適用され、ドキュメントはWG14とWG21の両方を参照しています。

N1509が正しく指摘しているように、現在のドラフトは基本的に6.8.5p6の無限ループに未定義の動作を与えます。そうすることの主な問題は、コードが潜在的に終了しないループを移動できるようにすることです。たとえば、次のループがあるとします。ここで、countとcount2はグローバル変数であり(またはそれらのアドレスが取得されています)、pはローカル変数であり、そのアドレスは取得されていません。

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

これらの2つのループをマージして、次のループに置き換えることはできますか?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

無限ループに対する6.8.5p6の特別なディスペンスがないと、これは許可されません。qが循環リストを指しているために最初のループが終了しない場合、元のループはcount2に書き込みません。したがって、count2にアクセスまたは更新する別のスレッドと並行して実行できます。これは、無限ループにもかかわらずcount2にアクセスする変換バージョンでは安全ではなくなりました。したがって、変換によってデータの競合が発生する可能性があります。

このような場合、コンパイラがループの終了を証明できる可能性はほとんどありません。qが非循環リストを指していることを理解する必要があります。これは、ほとんどの主流コンパイラの能力を超えており、プログラム全体の情報がないと不可能なことがよくあります。

非終了ループによって課せられる制限は、コンパイラーが終了を証明できない終了ループの最適化、および実際の非終了ループの最適化に対する制限です。前者は後者よりもはるかに一般的であり、多くの場合、最適化する方が興味深いです。

明らかに、整数ループ変数を持つforループもあり、コンパイラーが終了を証明することは困難であり、したがって、コンパイラーが6.8.5p6なしでループを再構築することは困難です。のようなものでも

for (i = 1; i != 15; i += 2)

また

for (i = 1; i <= 10; i += j)

処理するのは簡単ではないようです。(前者の場合、終了を証明するためにいくつかの基本的な数論が必要です。後者の場合、そうするためにjの可能な値について何かを知る必要があります。符号なし整数のラップアラウンドは、この推論の一部をさらに複雑にする可能性があります。 )。

この問題は、コンパイラの並列化やキャッシュ最適化変換など、ほとんどすべてのループ再構築変換に当てはまるようです。どちらも重要性が増す可能性が高く、数値コードにとってすでに重要であることがよくあります。これは、特に私たちのほとんどが意図的に無限ループを作成することはめったにないため、可能な限り最も自然な方法で無限ループを作成できるという利点のために、かなりのコストになる可能性があります。

Cとの大きな違いの1つは、 C11は、 C ++とは異なり、特定の例をC11で明確に定義する定数式である式を制御するための例外を提供することです。

于 2015-06-22T19:22:47.913 に答える
16

正しい解釈はあなたの編集によるものだと思います。空の無限ループは未定義の動作です。

これが特に直感的な動作であるとは言えませんが、この解釈は、コンパイラがUBを呼び出さずに無限ループを任意に無視できるという代替の解釈よりも理にかなっています。

無限ループがUBの場合、それは、終了していないプログラムが意味があると見なされないことを意味します。C++ 0xによると、それらにはセマンティクスがありません

それもある程度意味があります。これらは特殊なケースであり、多くの副作用が発生しなくなり(たとえば、から何も返されませんmain)、無限ループを保持する必要があるため、多くのコンパイラの最適化が妨げられます。たとえば、ループに副作用がない場合、ループ全体で計算を移動することは完全に有効です。これは、最終的には計算がどのような場合でも実行されるためです。ただし、ループが終了しない場合は、プログラムがハングする前に実際に実行される操作を変更するだけなので、ループ全体でコードを安全に再配置することはできません。ぶら下がっているプログラムをUBとして扱わない限り、つまり。

于 2010-08-29T04:44:44.510 に答える
10

関連する問題は、コンパイラが副作用が競合しないコードを並べ替えることができることです。コンパイラが無限ループ用の非終了マシンコードを生成した場合でも、驚くべき実行順序が発生する可能性があります。

これが正しいアプローチだと思います。言語仕様は、実行の順序を強制する方法を定義します。並べ替えることができない無限ループが必要な場合は、次のように記述します。

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");
于 2010-08-29T05:20:17.440 に答える
8

これは、別のスレッドを参照するこのタイプの質問の線に沿っていると思います。最適化により、空のループが削除される場合があります。

于 2010-08-28T21:47:05.137 に答える
1

「後のコードが前のコードに依存せず、前のコードがシステムの他の部分に副作用を及ぼさない場合、コンパイラの出力は、おそらく最もよく説明できると思います。前者がループを含んでいる場合でも、前者のコードが実際にいつ完了するかどうかに関係なく、前者の実行の前、後、または混合して後のコードを実行できます。たとえば、コンパイラは次のように書き直すことができます。

void testfermat(int n)
{{
  int a = 1、b = 1、c = 1;
  while(pow(a、n)+ pow(b、n)!= pow(c、n))
  {{
    if(b> a)a ++; else if(c> b){a = 1; b ++}; else {a = 1; b = 1; c ++};
  }
  printf( "結果は");
  printf( "%d /%d /%d"、a、b、c);
}

なので

void testfermat(int n)
{{
  if(fork_is_first_thread())
  {{
    int a = 1、b = 1、c = 1;
    while(pow(a、n)+ pow(b、n)!= pow(c、n))
    {{
      if(b> a)a ++; else if(c> b){a = 1; b ++}; else {a = 1; b = 1; c ++};
    }
    signal_other_thread_and_die();
  }
  else//2番目のスレッド
  {{
    printf( "結果は");
    wait_for_other_thread();
  }
  printf( "%d /%d /%d"、a、b、c);
}

私はそれを心配するかもしれませんが、一般的に不合理ではありません:

  int total = 0;
  for(i = 0; num_reps> i; i ++)
  {{
    update_progress_bar(i);
    total + = do_something_slow_with_no_side_effects(i);
  }
  show_result(total);

になります

  int total = 0;
  if(fork_is_first_thread())
  {{
    for(i = 0; num_reps> i; i ++)
      total + = do_something_slow_with_no_side_effects(i);
    signal_other_thread_and_die();
  }
  そうしないと
  {{
    for(i = 0; num_reps> i; i ++)
      update_progress_bar(i);
    wait_for_other_thread();
  }
  show_result(total);

1つのCPUで計算を処理し、別のCPUでプログレスバーの更新を処理することにより、書き換えによって効率が向上します。残念ながら、プログレスバーの更新は本来よりも有用性が低くなります。

于 2010-09-01T19:20:38.357 に答える
0

それが無限ループである場合、それが自明でない場合のコンパイラにとって決定可能ではありません。

場合によっては、オプティマイザーがコードのより複雑なクラスに到達することがあります(たとえば、O(n ^ 2)であり、最適化後にO(n)またはO(1)を取得します)。

したがって、無限ループをC ++標準に削除できないようなルールを含めると、多くの最適化が不可能になります。そして、ほとんどの人はこれを望んでいません。これはあなたの質問にかなり答えると思います。


もう1つのこと:何もしない無限ループが必要な有効な例を見たことがありません。

私が聞いた1つの例は、他の方法で実際に解決する必要がある醜いハックでした。リセットをトリガーする唯一の方法は、ウォッチドッグが自動的に再起動するようにデバイスをフリーズすることであった組み込みシステムに関するものでした。

何もしない無限ループが必要な有効で良い例を知っているなら、教えてください。

于 2010-09-03T18:36:04.820 に答える
-1

ループは、不揮発性で同期されていない変数を介して他のスレッドと相互作用するという事実を除いて、無限になり、新しいコンパイラで誤った動作を引き起こす可能性があることを指摘する価値があると思います。

言い換えれば、グローバル変数を揮発性にします。また、ポインタ/参照を介してそのようなループに渡される引数も同様です。

于 2011-08-25T10:13:21.747 に答える