4

Numeric Haskell Repa Tutorial Wikiには、(文脈のために) 次のような一節があります。

10.1 Fusion と、それが必要な理由

Repa は、高速なコードを実現するために配列融合に大きく依存しています。フュージョンは、GHC がプログラムをコンパイルするときに実行するインライン化とコード変換の組み合わせの凝った名前です。フュージョン プロセスは、Repa ライブラリで定義された配列充填ループを、独自のモジュールで記述した「ワーカー」関数とマージします。融合プロセスが失敗した場合、結果のプログラムは必要以上に遅くなり、多くの場合、単純な Haskell リストを使用した同等のプログラムよりも 10 倍遅くなります。一方、フュージョンが機能する場合、結果として得られるコードは、同等にきれいに記述された C プログラムと同じくらい高速に実行されます。何が起こっているのかを理解すれば、フュージョンを機能させるのは難しくありません。

私が理解していない部分はこれです：

「融合プロセスが失敗した場合、結果のプログラムは必要以上に遅くなり、多くの場合、単純な Haskell リストを使用した同等のプログラムよりも 10 倍遅くなります。」

ストリーム フュージョンが失敗した場合に実行が遅くなる理由は理解できますが、なぜリストよりも実行が遅くなるのでしょうか?

ありがとう！

4

2 に答える 2

9

通常、リストは遅延型であり、Repa 配列は厳密型であるためです。

レイジー リスト トラバーサルの融合に失敗した場合、たとえば

map f . map g

中間の (怠惰な) コンスセルをそこに残すために、値ごとにO(1)のコストを支払います。

厳密なシーケンスで同じトラバーサルを融合できなかった場合は、厳密な中間配列を割り当てるために値ごとに少なくともO(n)を支払います。

また、融合はコードを認識できないStreamデータ型に分解するため、分析を改善するために、コンストラクターやその他のオーバーヘッドが多すぎるコードが残る可能性があります。

于 2012-12-03T20:39:20.373 に答える
3

編集: これは正しくありません。Don Nelson のコメントを参照してください (および彼の回答です。彼は私よりもライブラリについてよく知っています)。

不変配列はコンポーネントを共有できません。融合を無視して、不変配列への変更は、配列全体を再割り当てする必要があります。対照的に、リスト操作は非破壊的ですが、パーツを共有できます。f i (h:t) = i:tたとえば、最初のセルが元のリストの 2 番目のセルを指す新しいリストを作成することにより、一定時間でリストの先頭を置き換えます。さらに、リストはインクリメンタルに構築できるため、関数への繰り返し呼び出しによってリストを構築するジェネレーターなどの関数は、O(n) 時間で実行できますが、融合のない不変配列に対する同等の関数は、配列を次のように再割り当てする必要があります。関数を呼び出すたびに、O(n^2) 時間かかります。

于 2012-12-03T20:39:59.337 に答える