6

私は2D曲線アルゴリズムを書いていて、効果的に合計を行うコードが少しありました:

for (i=0, end=...; i<end; i++) {
  value += coefficients[i] * expensiveToCalculateValue(i);
}

coefficients[i]一部の反復ステップでは値がゼロでした。0 回何かが 0 であるため (少なくとも単純な算術規則の下では)、最初に 0 かどうかをチェックし、coefficients[i]0 である場合はcontinue次の反復に進むことで、このコードを大幅に最適化できると考えました。追加、ソート、見事に機能します。

しかし、これには疑問が残ります:なぜこれが私のために行われないのですか? これは乗算の創造的なニッチ バージョンではなく、単純な算術演算です。実質的にすべての言語は、その時点から結果を不変にするオペランドが見つかった場合、バイナリ OR 演算と AND 演算を短絡します。

このコード (synax 用に変更) を Java、PHP、JavaScript、Perl、Python、C++ で実行してみました。また、Prolog が何をしたかを調べましたが、「ゼロ回 ...」と表示されると誰も気づきませんでした。潜在的に高価な 2 番目 (または 3 番目、4 番目など) の項を評価する必要はありません。

printed = 0;
function veryExpensive() {
  print "oh god this costs so much, x" + (printed++);
  return 0;
}
value = 0 * veryExpensive() * veryExpensive() * veryExpensive()

それらはすべてveryExpensive()3 回実行されるだけです。

さて、あなたがそのような人なら、結果が算術式に寄与しないにもかかわらず実行されることに依存できるという事実に基づいて、管理上のオーバーヘッド作業を行う関数を書くことができることveryExpensiveを理解しています(あなたがそうする場合)言語を悪用している可能性がありますが、誰もがプログラミングの人生のある時点で卑劣な忍者コードを愛しています)。言語が算術評価を最適化したとしても、コードの表現力が損なわれることはありません。

では、現在使用されている大量の言語が「true OR ...」および「false AND ...」を最適化するが、「zero TIMES ...」は最適化しない歴史的な前例はありますか? 二項演算を最適化するのに、MUL 0 を最適化しないのはなぜですか? (もし運が良ければ、私たちがショートしない理由について興味深い話を誰かが教えてくれるかもしれません)

アップデート

John Skeet と Nik Bougalis はどちらも、現存する言語でこれを最適化すると問題が発生する理由について良い議論をしていますが、Nik の答えは質問ともう少し一致しているので、彼の答えを「正しい」ものとしてマークしました。とはいえ、それらは同じ問題のさまざまな側面をカバーしているため、本当の答えは 2 つの組み合わせです。

4

2 に答える 2

9

それらはすべて、veryExpensive() を 3 回実行するだけです。

そして、そうすべきです。

しかし、それを行うのは、言語がたまたまこのケースに最適化されていないことを知っているからです。

いいえ、それは「おかしなことに」最適化しないという問題ではありません。言語仕様に違反しない最適化の問題です。

X * Y演算が最初に を評価してXから を評価しY、次に 2 つの値を乗算するように言語が指定しているY場合、 の値がXたまたま 0 である場合に の評価を削除するのは、単に不適切な最適化です。

もちろん、このように振る舞う演算子がしばしばあります-特に (C のような言語で):

  • またはのいずれa ? b : cのみを評価する条件演算子 b c
  • x || yfalse のy場合にのみ評価されますx
  • x && ytrue のy場合にのみ評価されますx

また、C# には、null の場合x ?? yにのみ評価される null 合体演算子があります。yx

乗算は次のように定義できますが、次のように思われます。

  • ほとんどの乗算演算では、条件付き実行の分岐ヒットは価値がありません。ただし、動作を明確に定義する必要があります。ショートサーキットかそうでないかのいずれかです。(IMO)未定義であってはなりません。
  • これにより、言語の指定と使用の両方がより複雑になります。おそらく、常に両方のオペランドを評価する「無条件の乗算」操作が必要になるでしょう( と 同様x | yx & y短絡していません)。

基本的に、関係者全員にとって追加の複雑さの価値があるとは思いません。

于 2013-03-07T17:51:20.317 に答える
2

コンパイラにランタイム チェックを自動的に追加させることは、意味がある場合とない場合があります。あなたの特定のケースでは、チェックによってパフォーマンスが向上したことはおそらく事実ですが、あなたの特定のケースは、最適化が判断されるすべてのケースではありません。

乗算が非常に高価であり、マイクロプロセッサがゼロによる乗算の内部最適化を行わず、ゼロ乗算の結果がゼロあることが保証されている場合 (たとえば)0 * NaN != 0、チェックは意味があるかもしれません。しかし、これは多数のandオペランドであり、ご存知のように and を短絡できます

数の準乱数分布と、0 と 0 以外の数の未知の比率があると仮定します。比率、ゼロおよび非ゼロ シーケンスの実行長、およびプロセッサの分岐予測アルゴリズムによっては、チェックが実際に問題を引き起こす場合があります (つまり、パイプライン ストール)。

コンパイラがあなたに代わってそのようなチェックを挿入する必要があるとまだ考えていますか?

于 2013-03-07T17:57:22.180 に答える