12

この質問のフォローアップとして、C＃に対するF＃の組み込みの不変性の利点は何ですか？--F＃コンパイラは、ほとんど不変のコードを処理していることを認識して、特定の最適化を行うことができると仮定して正しいですか？つまり、開発者が「Functional C＃」と書いたとしても、コンパイラーは、開発者がコーディングしようとした不変性のすべてを知らないため、同じ最適化を行うことができませんでしたね。

一般に、関数型言語のコンパイラーは、命令型言語では不可能な最適化を行うことができますか？可能な限り不変性で記述された言語でさえも可能でしょうか？

4

6 に答える 6

20

F＃コンパイラが、ほとんど不変のコードを処理していることを認識して、特定の最適化を行うことができると仮定するのは正しいですか？

残念ながら違います。コンパイラーの作成者にとって、「大部分が不変」と「不変」には大きな違いがあります。保証された不変性でさえ、オプティマイザにとってそれほど重要ではありません。それがあなたを買う主なものは、あなたが非常に攻撃的なインラインを書くことができるということです。

一般に、関数型言語のコンパイラーは、命令型言語では不可能な最適化を行うことができますか？可能な限り不変性で記述された言語でさえも可能でしょうか？

はい。ただし、ほとんどの場合、従来の最適化をより簡単に、より多くの場所に適用できるかどうかが問題になります。たとえば、不変性により、特定のメモリーセルの内容が変更されないことが保証されるため、共通部分式除去の適用がはるかに簡単になります。

一方、関数型言語が不変であるだけでなく純粋である（I / Oのような副作用がない）場合は、ソースレベルの式をより効率的な式に書き換えることを含む新しいクラスの最適化を有効にします。読むべき最も重要でより興味深いものの1つは、ショートカットの森林伐採です。これは、中間結果にメモリスペースを割り当てないようにする方法です。読むべき良い例は、ストリームフュージョンです。

静的に型付けされた関数型言語をコンパイルして高性能を実現する場合、重要なポイントは次のとおりです。

  • メモリを有効に活用してください。可能な場合は、「ボックス化されていない」値を使用して、ヒープへの割り当てと余分なレベルの間接参照を回避します。特にストリームフュージョンやその他の森林伐採技術は、割り当てを排除するため、すべて非常に効果的です。

  • 超高速のアロケータを用意し、複数の割り当てでヒープ枯渇チェックを償却します。

  • インライン関数は効果的に機能します。特に、モジュールの境界を越えて小さな関数をインライン化します。

  • 通常はクロージャ変換を通じて、第一級関数を効率的に表現します。部分的に適用された機能を効率的に処理します。

  • 従来のスカラーとループの最適化を見落とさないでください。それらはTILやObjectiveCamlのようなコンパイラに大きな違いをもたらしました。

HaskellやCleanのような怠惰な関数型言語を持っているなら、サンクに関係する専門的なこともたくさんあります。

脚注：

  • 完全な不変性で得られる興味深いオプションの1つは、非常にきめ細かい並列処理を実行する能力が高いことです。この話の終わりはまだ語られていません。

  • F＃は非常に制約が厳しいため、F＃用の優れたコンパイラーを作成することは、通常のコンパイラーを作成するよりも困難です（そのようなものがある場合）。関数型言語を念頭に置いて設計されていません。非常に制約のある問題でこのような素晴らしい仕事をしてくれたDonSymeと彼のチームのおかげです。

于 2010-02-06T02:53:59.953 に答える
7

いいえ。

F＃コンパイラは、メソッドまたはラムダの参照透過性を分析しようとはしません。.NET BCLは、このために設計されたものではありません。

F＃言語仕様では、キーワード「pure」が予約されているため、vNextでメソッドを手動で純粋としてマークすることが可能であり、ラムダ式のより積極的なグラフ削減が可能になります。

ただし、レコード型または代数型のいずれかを使用する場合、F＃はデフォルトの比較演算子と等式演算子を作成し、コピーセマンティクスを提供します。他の多くの利点（パターンマッチング、閉世界仮説）の中で、これは大きな負担を軽減します！

于 2010-02-06T01:14:35.633 に答える
5

はい、F＃を考慮しない場合は、たとえばHaskellを検討してください。副作用がないという事実は、最適化の多くの可能性を実際に開きます。

たとえば、Cのような言語で考えてみましょう。

int factorial(int n) {
    if (n <= 0) return 1;
    return n* factorial(n-1);
}

int factorialuser(int m) {
    return factorial(m) * factorial(m);
}

対応するメソッドがHaskellで書かれている場合、 factorialuserを呼び出すときにfactorialへの2回目の呼び出しはありません。C＃でこれを行うことは可能かもしれませんが、このような単純な例であっても、現在のコンパイラがそれを行うとは思えません。物事がより複雑になるにつれて、C＃コンパイラがHaskellが実行できるレベルに最適化するのは難しくなります。

現在、F＃は実際には「純粋な」関数型言語ではないことに注意してください。そこで、Haskellを持ち込みました（これは素晴らしいことです！）。

于 2010-02-06T00:57:34.593 に答える
3

残念ながら、F＃はほとんど純粋であるため、積極的な最適化の機会はそれほど多くありません。実際、F＃がC＃と比較してコードを「悲観化」する場所がいくつかあります（たとえば、観察可能な突然変異を防ぐために構造体の防御コピーを作成する）。明るい面としては、コンパイラはこれにもかかわらず全体的に優れた仕事をし、それでもほとんどの場所でC＃に匹敵するパフォーマンスを提供すると同時に、プログラムの推論を容易にします。

于 2010-02-06T01:26:32.730 に答える
2

私は主に「いいえ」と言います。

不変性または参照透過性から得られる主な「最適化」の利点は、のようなコードが表示されたときに「共通部分式除去」を実行できることなど...f(x)...f(x)...です。ただし、このような分析は非常に正確な情報なしでは実行できません。F＃は.Netランタイムで実行され、.Netにはメソッドを純粋（効果なし）としてマークする方法がないため、大量の組み込み情報と分析が必要です。これのいずれかを実行しようとさえします。

一方、Haskellのような言語（Haskellのように誰もが聞いたことがある、または使用している言語はほとんどないため、ほとんどの場合「Haskell」を意味します:)）は、怠惰で純粋であり、分析はより簡単です（すべてが純粋な、ナッツに行く）。

とは言うものの、そのような「最適化」は、システムの他の有用な側面（パフォーマンスの予測可能性、デバッグなど）とうまく相互作用しないことがよくあります。

「十分に賢いコンパイラがXを実行できる」という話はよくありますが、私の意見では、「十分に賢いコンパイラ」は神話であり、これからもそうなるでしょう。高速コードが必要な場合は、高速コードを記述します。コンパイラはあなたを救うつもりはありません。共通部分式除去が必要な場合は、ローカル変数を作成します（自分で行います）。

これは主に私の意見であり、反対票を投じたり反対したりすることを歓迎します（実際、「最適化が再びセクシーになる可能性がある」という上昇の理由として「マルチコア」が提案されているのを聞いたことがあります。ただし、コンパイラが重要な最適化（ソースコードのアノテーションではサポートされていない）を実行することを期待している場合は、希望が満たされるまで長時間待つ準備をしてください。

誤解しないでください。不変性は優れており、多くの状況で「高速」コードを作成するのに役立つ可能性があります。しかし、コンパイラがそれを最適化するからではなく、コードの記述、デバッグ、修正、並列化、プロファイリングが容易であり、時間を費やす最も重要なボトルネックを決定するためです（おそらくそれらを可変的に書き換えます）。効率的なコードが必要な場合は、開発、テスト、プロファイリングを迅速に行える開発プロセスを使用してください。

于 2010-02-06T01:40:42.330 に答える
2

関数型言語の追加の最適化が可能な場合もありますが、必ずしも不変性のためではありません。内部的には、多くのコンパイラはコードをSSA（単一静的代入）形式に変換します。この形式では、関数内の各ローカル変数は1回だけ割り当てることができます。これは、命令型言語と関数型言語の両方で実行できます。例えば：

x := x + 1
y := x + 4

になることができる

x_1 := x_0 + 1
y := x_1 + 4

ここでx_0、とx_1は異なる変数名です。これにより、プログラムの特定のポイントでの値を気にせずにコードを移動できるため、多くの変換が大幅に簡素化されます。ただし、これはメモリに格納されている値（つまり、グローバル、ヒープ値、配列など）では機能しません。繰り返しますが、これは関数型言語と命令型言語の両方に対して行われます。

ほとんどの関数型言語が提供する利点の1つは、強い型システムです。これにより、コンパイラーは、他の方法では不可能であると想定することができます。たとえば、異なるタイプの2つの参照がある場合、コンパイラはそれらがエイリアスできないことを認識します（同じものを指す）。これは、Cコンパイラが行うことができる仮定ではありません。

于 2010-02-06T01:29:49.470 に答える