2

またはcontainersのようなパッケージの重要なデータ構造は、純粋な Haskell で実装されていることがわかりました。質問: で実装した方が効率的ではないでしょうか? ghc が非常に優れていることは知っていますが、最適化されたコードと競合することはできません。Data.MapData.IntMapCC

4

3 に答える 3

10

これは興味深い質問ですが、何らかの方法で決定的な答えを提供できる人がいるかどうかはわかりません (大規模なテスト スイートを設計および構築し、膨大な数を生成することは別として)。

この質問の背後にある仮定は、「C は常に速く、Haskell は常に遅いので、Haskell ではなく C でコードを記述した方がよいのではないか?」という前提のようです。この仮定が実際に正確であるかどうかはわかりません。(私の限られた経験では、Haskellが遅いということではなく、Haskell が遅い (または非常に速い) 可能性があるということであり、どのような速度が得られるかを予測するのは厄介です。)

FFI を介して C を呼び出すと、オーバーヘッドが発生します。Haskell データ構造はガベージ コレクターによって処理されます。C 経由で使用されるメモリは手動で管理する必要があります。あなたはここでかなりの労力を費やしていますが、おそらくあなたが思っているほど多くの利益はありません.

C のデータ構造は、可変性があるため、より効率的である傾向があります。ほとんどの人は、Haskell で変更可能なデータ構造を操作したくありません。(ある意味では、そもそも Haskell を使用するすべての利点が無効になるので、なぜ気にする必要があるのでしょうか?) C で不変のデータ構造を使用すると、Haskell よりも遅くなることに気付くかもしれません。(たとえば、C は動的メモリ割り当てが非常に遅いと言われています。これは、永続的なデータ構造にとって問題になるでしょう。別の方法は、あちこちに物をコピーすることですが、これも高速にはなりません。)

その上、GHC は森林伐採などの巧妙な最適化を行います。これにより、実行時にコンテナーが完全に消失する場合があります。C コンパイラは、そのようなことはできませんでした。また、Haskell は怠惰な言語であるため、要求された作業を完全にスキップすることがあります。コンテナーが C で実装されている場合、これは機能しません。

要約すると、C でこのようなものを実装すると、「明らかに」はるかに高速になるはずです。実際には、答えはそれほど明確ではないと思います。

于 2012-09-12T11:27:38.310 に答える
5

GHC のランタイムは、不変の構造体を効率的に割り当てるために最適化されています。通常、このタスクでは C ランタイム (malloc) よりも優れています。その結果、C は主に、データ構造ではなく、アルゴリズムの最適化に使用されます。例外は、非常に低レベルのデータ構造、または高度に調整された変更可能な構造です。

于 2012-09-12T12:37:07.650 に答える
4

まず、Data.Map通常の命令マップではなく、いわゆる永続マップです。それ自体の複数のバージョンの効率的な保持をサポートする必要があります。C は、このタイプのデータ構造にはあまり適していません。たとえば、従来の C スタイルのメモリ管理はできません。

第二に、GHC ヒープ レイアウトは非常に複雑です。特に、Ord a比較のために辞書を使用する場合はそうです。そのため、古き良き C とのインターフェイスは簡単ではなく、インターフェイスのコストが、より優れたコード生成による利点を上回る可能性があります。

C での実装Data.Mapは可能ですが、このすべての簿記のために役立つ可能性はほとんどありません。試してみて、それよりも速いかどうかをお知らせください:) ご覧のとおり、コミュニティは何もできないと確信しているため、それは行われていません.

于 2012-09-12T11:28:28.650 に答える