Haskell（GHCコンパイラ付き）は予想よりずっと早い正しく使用すれば、低レベル言語にかなり近づくことができます。(Haskell ユーザーが好んで行うことは、C の 5% 以内 (またはそれを上回る) を達成することですが、GHC は Haskell を C にコンパイルするため、非効率的な C プログラムを使用していることになります)。) 私の質問は、なぜでしょうか?
Haskell は宣言型で、ラムダ計算に基づいています。マシン アーキテクチャは明らかに命令型であり、大まかに言うとチューリング マシンに基づいています。実際、Haskell には特定の評価順序さえありません。また、マシン データ型を扱う代わりに、常に代数データ型を作成します。
しかし、最も奇妙なのは高階関数です。関数をその場で作成し、それをあちこちに投げ回すと、プログラムが遅くなると思われるかもしれません。しかし、高階関数を使用すると、実際には Haskell が高速化します。実際、Haskell コードを最適化するには、より機械的にするのではなく、よりエレガントで抽象的なものにする必要があるようです。Haskell のより高度な機能は、パフォーマンスを向上させない限り、パフォーマンスにさえ影響を与えないようです。
文句を言っているように聞こえたら申し訳ありませんが、私の質問は次のとおりです。Haskell (GHC でコンパイル) は、その抽象的な性質と物理マシンとの違いを考慮すると、なぜ非常に高速なのでしょうか。
注: C やその他の命令型言語がチューリングマシンに似ている (ただし Haskell がラムダ計算に似ているほどではない) と私が言う理由は、命令型言語では有限の数の状態 (つまり行番号) とテープ (RAM) があり、状態と現在のテープによってテープに何をするかが決まるからです。Wikipedia のエントリを参照してください。チューリングマシンの同等物チューリングマシンからコンピュータへの移行について。
ベストアンサー1
私はDietrich Eppに同意します。GHCを高速化するのは、いくつかの要素の組み合わせです。
まず第一に、Haskell は非常に高レベルです。これにより、コンパイラはコードを壊すことなく積極的な最適化を実行できます。
SQL について考えてみましょう。ステートメントを記述するとSELECT、命令型のループのように見えるかもしれませんが、そうではありません。指定された条件に一致する行を探すために、テーブル内のすべての行をループしているように見えるかもしれませんが、実際には、「コンパイラ」(DB エンジン) は代わりにインデックス検索を実行している可能性があります。これは、パフォーマンス特性がまったく異なります。ただし、SQL は非常に高レベルであるため、「コンパイラ」はまったく異なるアルゴリズムを代用したり、複数のプロセッサや I/O チャネル、またはサーバー全体を透過的に適用したりすることができます。
Haskell も同じだと思います。Haskell に入力リストを 2 番目のリストにマッピングし、2 番目のリストを 3 番目のリストにフィルターし、結果の項目数をカウントするように指示しただけだと思うかもしれません。しかし、GHC がストリーム フュージョン書き換えルールを舞台裏で適用し、全体を 1 つのタイトなマシン コード ループに変換して、割り当てなしでデータを 1 回通過するだけですべての作業を実行するのは見たことがありません。これは、手作業で記述すると面倒で、エラーが発生しやすく、メンテナンスが不可能な類のことです。これが実際に可能なのは、コードに低レベルの詳細がないためです。
別の見方をすると… Haskell がなぜ速くないのか？ 何をすると遅くなるのだろうか？
これは、Perl や JavaScript のようなインタープリタ言語ではありません。Java や C# のような仮想マシン システムでもありません。ネイティブ マシン コードまでコンパイルされるため、オーバーヘッドはありません。
OO 言語 [Java、C#、JavaScript…] とは異なり、Haskell には完全な型消去機能があります [C、C++、Pascal…]。すべての型チェックはコンパイル時にのみ行われます。したがって、実行時の型チェックによって速度が低下することもありません。(ちなみに、null ポインターのチェックもありません。たとえば、Java では、JVM は null ポインターをチェックし、null ポインターを無視すると例外をスローする必要があります。Haskell では、そのチェックを行う必要がありません。)
「実行時にその場で関数を作成する」のは遅いように聞こえると言いますが、よくよく見れば、実際にはそうではありません。そうしているように見えるかもしれませんが、そうではありません。 と言う場合(+5)、それはソース コードにハードコードされています。実行時に変更することはできません。したがって、実際には動的関数ではありません。カリー化された関数でさえ、実際にはパラメータをデータ ブロックに保存しているだけです。実行可能なコードはすべて、実際にはコンパイル時に存在します。実行時の解釈はありません。(「eval 関数」を持つ他の言語とは異なります。)
Pascal について考えてみましょう。Pascal は古く、もう誰も使っていませんが、Pascal が遅いと文句を言う人はいません。Pascal には嫌いな点がたくさんありますが、遅さはそのうちの 1 つではありません。Haskell は、手動のメモリ管理ではなくガベージ コレクションがあることを除けば、Pascal とそれほど違いはありません。また、不変データにより、GC エンジンにいくつかの最適化が可能になります (遅延評価によって多少複雑になります)。
問題は、Haskell が高度で洗練されていて高水準に見えることだと思います。そして誰もが「わぁ、これは本当に強力だ、驚くほど遅いに違いない!」と思うのです。しかし、そうではありません。少なくとも、あなたが期待するような遅い方法ではありません。確かに、Haskell には素晴らしい型システムがあります。しかし、ご存知ですか? それはすべてコンパイル時に行われます。実行時には、それはなくなります。確かに、Haskell では 1 行のコードで複雑な ADT を構築できます。しかし、ご存知ですか? ADT は単なる普通の C ですunion。structそれ以上のものではありません。
本当の致命的な問題は遅延評価です。コードの厳密性/遅延性を正しく理解すれば、エレガントで美しいまま、驚くほど高速なコードを書くことができます。しかし、この点を間違えると、プログラムは数千倍遅くなり、なぜそうなるのかはまったくわかりません。
たとえば、私はファイル内の各バイトが何回出現するかをカウントする簡単なプログラムを書きました。25KB の入力ファイルの場合、プログラムの実行には20 分かかり、6 GBの RAM を消費しました。これは不合理です。しかし、問題が何であるかに気づき、バンパターンを 1 つ追加したところ、実行時間は0.02 秒に短縮されました。
ここで Haskell は予想外に遅くなります。慣れるまでには確かに時間がかかります。しかし、時間が経つにつれて、本当に高速なコードを書くのが簡単になります。
Haskell が高速なのはなぜでしょうか? 純粋さ、静的型、遅延。しかし何よりも、コードの期待を壊すことなくコンパイラが実装を大幅に変更できるほど十分に高レベルであることです。
でもそれは私の意見に過ぎないと思うのですが...