ベンチマークで関数型言語が常に C に後れを取っているのはなぜですか? 静的に型付けされた関数型言語を使用している場合、C と同じコードにコンパイルするか、コンパイラでより多くのセマンティクスを使用できるため、さらに最適化されたコードにコンパイルできるように思えます。すべての関数型言語が C よりも遅いように見えるのはなぜですか? また、なぜ常にガベージ コレクションとヒープの過度の使用が必要なのですか?
メモリ割り当てが最小限に抑えられ、生成されたマシンコードが無駄がなく高速な、組み込み/リアルタイムアプリケーションに適した関数型言語を知っている人はいますか?
関数型言語は本質的に遅いですか?
ある意味、そうです。アセンブラを手動で使用して理論的に達成できるものよりも、必然的にオーバーヘッドを追加するインフラストラクチャが必要です。特に、第一級のレキシカル クロージャは、スコープ外で値を実行できるため、ガベージ コレクションでのみうまく機能します。
ベンチマークで関数型言語が常に C に後れを取っているのはなぜですか?
まず、選択バイアスに注意してください。C は、ベンチマーク スイートの最小公分母として機能し、達成できることを制限します。C と関数型言語を比較したベンチマークがある場合、それはほぼ間違いなく非常に単純なプログラムです。ほぼ間違いなく単純すぎて、今日の実用的な関連性はほとんどありません。C を単なるベンチマークとして使用して、より複雑な問題を解決することは実際には不可能です。
この最も明白な例は、並列処理です。今日、私たちは皆マルチコアを持っています。私の電話もマルチコアです。マルチコア並列処理は、C では難しいことで有名ですが、関数型言語では簡単に実現できます (私は F# が好きです)。他の例には、永続的なデータ構造から恩恵を受けるものすべてが含まれます。たとえば、元に戻すバッファは、純粋に機能的なデータ構造では簡単ですが、C のような命令型言語では膨大な量の作業になる可能性があります。
すべての関数型言語が C よりも遅いように見えるのはなぜですか? また、なぜ常にガベージ コレクションとヒープの過度の使用が必要なのですか?
関数型言語は、C で十分に簡単に記述できるコードを比較するベンチマークのみが表示され、関数型言語が優れ始めたより肉厚なタスクを比較するベンチマークは表示されないため、遅いように見えます。
しかし、今日の関数型言語の最大のボトルネックは、過剰な割り当て率であることを正しく認識しています。よくやった！
関数型言語がこれほど多くの割り当てを行う理由は、歴史的な理由と固有の理由に分けることができます。
歴史的に、Lisp の実装は多くのことを行ってきました。ボクシング歴50年。この特性は、Lisp のような中間表現を使用する他の多くの言語に広がりました。何年にもわたって、言語の実装者は、言語の実装における複雑さの迅速な修正として、ボックス化に頼ってきました。オブジェクト指向言語では、デフォルトでは、明らかにスタックに割り当てられる可能性がある場合でも、すべてのオブジェクトを常にヒープに割り当てるようになっています。その後、効率の負担がガベージ コレクターに押し付けられ、スタック割り当てに近いパフォーマンスを達成できるガベージ コレクターの構築に多大な労力が費やされました。通常は、バンプ割り当てのナーサリ生成を使用します。ボックス化を最小限に抑える関数型言語の設計と、さまざまな要件に合わせて最適化されたガベージ コレクターの設計を研究するために、さらに多くの努力を払う必要があると思います。
世代別ガベージ コレクターは、スタック割り当てとほぼ同じ速度でヒープを割り当てる言語に最適です。しかし、他の場所でかなりのオーバーヘッドが追加されます。今日のプログラムは、キューのようなデータ構造をますます使用しており (例えば、並行プログラミング用)、これらは世代別ガベージ コレクターに異常な動作を与えます。キュー内のアイテムが最初の世代よりも長く存続する場合、それらはすべてマークされ、次にすべてがコピー (「退避」) され、古い場所へのすべての参照が更新され、コレクションの対象になります。これは、必要な速度よりも約 3 倍遅いです (たとえば、C と比較して)。Beltway (2002) やImmixなどのマーク地域のコレクター(2008) この問題を解決する可能性があるのは、ナーサリがナーサリであるかのように収集できるリージョンに置き換えられるか、ほとんど到達可能な値が含まれている場合は別のリージョンに置き換えられ、ほとんど到達不能な値が含まれています。
C++ は以前から存在していましたが、Java の作成者はジェネリックに型消去を採用するという過ちを犯し、不要なボクシングにつながりました。たとえば、JVM よりも .NET で 17 倍高速に動作する単純なハッシュ テーブルをベンチマークしました。これは、.NET がこの間違いを犯さなかった (具体化されたジェネリックを使用している) ことと、.NET に値型があることが一因です。私は実際、Java を遅くしたのは Lisp のせいだと思っています。
最新の関数型言語の実装はすべて、過度にボックス化し続けています。Clojure や Scala などの JVM ベースの言語は、対象となる VM が値の型を表現することさえできないため、選択肢がほとんどありません。OCaml は、コンパイル プロセスの早い段階で型情報を流し、実行時にタグ付き整数とボックス化を使用してポリモーフィズムを処理します。その結果、OCaml はしばしば個々の浮動小数点数をボックス化し、常にタプルをボックス化します。たとえば、OCaml のバイトのトリプルは、64 ビットのヘッダーと 192 ビットのボディを含むヒープ割り当てブロックへのポインター (実行時に繰り返しチェックされる暗黙の 1 ビット タグが埋め込まれている) によって表されます。 3 つのタグ付き 63 ビット整数 (ここでも、3 つのタグは実行時に繰り返し検査されます!)。これは明らかに正気ではありません。
関数型言語でのボックス化解除の最適化に関していくつかの作業が行われましたが、実際に注目を集めることはありませんでした。たとえば、標準 ML の MLton コンパイラは、洗練されたボックス化解除の最適化を行う、プログラム全体を最適化するコンパイラでした。悲しいことに、それは時代遅れであり、「長い」コンパイル時間 (おそらく最新のマシンでは 1 秒未満です!) のために、人々はそれを使用することを思いとどまらせていました。
この傾向を打ち破った唯一の主要なプラットフォームは .NET ですが、驚くべきことに、それは偶然だったようです。Dictionary値型のキーと値に対して非常に最適化された実装があるにもかかわらず(ボックス化されていないため)、Eric Lippert のような Microsoft の従業員は、値型に関する重要なことは値渡しのセマンティクスであると主張し続けています。ボックス化されていない内部表現に起因するパフォーマンス特性ではありません。Eric は間違っていることが証明されたようです。.NET 開発者の多くは、値渡しよりもボックス化解除に関心があるようです。実際、ほとんどの構造体は不変であるため、参照が透過的であるため、値渡しと参照渡しの間に意味的な違いはありません。パフォーマンスは目に見えるものであり、構造体はパフォーマンスを大幅に向上させることができます。スタック オーバーフローを保存した構造体のパフォーマンスと構造体は、Rapid Addition のような商用ソフトウェアで GC レイテンシを回避するために使用されます。
関数型言語による大量の割り当てのもう 1 つの理由は固有のものです。ハッシュ テーブルのような命令型データ構造は、巨大なモノリシック配列を内部的に使用します。これらが永続的である場合、更新が行われるたびに巨大な内部配列をコピーする必要があります。そのため、バランスの取れたバイナリ ツリーのような純粋に機能的なデータ構造は、コレクションのあるバージョンから次のバージョンへの再利用を容易にするために、多くの小さなヒープ割り当てブロックに断片化されます。
Clojure は、辞書のようなコレクションが初期化中にのみ書き込まれ、その後、多くから読み取られる場合に、巧妙なトリックを使用してこの問題を軽減します。この場合、初期化ではミューテーションを使用して「舞台裏」で構造を構築できます。ただし、これは増分更新には役立たず、結果として得られるコレクションは、同等の命令型のコレクションよりも読み取りが大幅に遅くなります。利点として、純粋に機能的なデータ構造は持続性を提供しますが、命令型のデータ構造は持続性を提供しません。ただし、実際に永続化することでメリットが得られる実用的なアプリケーションはほとんどないため、多くの場合、これは有利ではありません。したがって、簡単に命令型スタイルに落として利益を得ることができる、純粋でない関数型言語が望まれます。
メモリ割り当てが最小限に抑えられ、生成されたマシンコードが無駄がなく高速な、組み込み/リアルタイムアプリケーションに適した関数型言語を知っている人はいますか?
まだお持ちでない場合は、Erlang と OCaml をご覧ください。どちらもメモリに制約のあるシステムには適していますが、どちらも特に優れたマシン コードを生成しません。
本質的に何もありません。これは、解釈されたOCaml が同等の C コードよりも速く実行される例です。これは、言語の違いにより、OCaml オプティマイザーが利用できる情報が異なるためです。もちろん、OCaml が C より断然速いという一般的な主張をするのはばかげています。要点は、それは何をどのように行うかによるということです。
そうは言っても、OCamlは (ほとんどの場合) 関数型言語の一例であり、純粋性とは対照的に、実際にはパフォーマンスのために設計されています。
Haskell は GCC の C++ よりもわずか 1.8 倍遅く、典型的なベンチマーク タスクでは GCC の C 実装よりも高速です。これにより、Haskell は非常に高速になり、C# (Mono) よりもさらに高速になります。
相対言語速度
記録として、私は iPhone のゲームに Lua を使用しています。したがって、高速な Haskell または Lisp を使用することもできます。
私は tuinstoel に同意しません。重要な問題は、関数型言語が使用されることを意図していたものに慣れたときに、関数型言語がより速い開発時間を提供し、より速いコードをもたらすかどうかです。私の言いたいことを垣間見るには、ウィキペディアの効率性の問題のセクションを参照してください。
実行可能ファイルのサイズが大きくなるもう 1 つの理由は、遅延評価と非厳密性です。コンパイラは、特定の式がいつ評価されるかをコンパイル時に把握できないため、これを処理するために一部のランタイムが実行可能ファイルに詰め込まれます (いわゆるサンクの評価を呼び出すため)。パフォーマンスに関して言えば、怠惰には良い面と悪い面の両方があります。一方では追加の潜在的な最適化が可能になりますが、他方ではコードサイズが大きくなる可能性があり、プログラマーは間違った決定を下す可能性が高くなります。