26

Haskell での遅延評価に関する私の苦労の 1 つは、メモリ使用量についての推論の難しさです。サンクを複製する機能があれば、これがずっと簡単になると思います。例を次に示します。

本当に大きなリストを作成しましょう:

let xs = [1..10000000]

それでは、悪い関数を作成しましょう。

bad = do
    print $ foldl1' (+) xs
    print $ length xs

最適化を行わないと、数十 MB の RAM が消費されます。後で長さを計算するために必要になるため、ガベージ コレクターは折りたたみ中に xs の割り当てを解除できません。

この関数を次のように再実装することは可能ですか:

good = do
    (xs1,xs2) <- copyThunk xs
    print $ foldl1' (+) xs1
    print $ length xs2

ここで、xs1 と xs2 は同じ値を表しますが、メモリ内で互いに独立しているため、フォールド中にガベージ コレクタが割り当てを解除でき、メモリの浪費を防ぐことができます。（計算コストが若干上がると思いますが？）

この些細な例では明らかに、コードをリファクタリングすることでこの問題を簡単に解決できますが、リファクタリングの方法が常に明らかであるとは限りません。または、リファクタリングによってコードの明瞭さが大幅に低下する場合もあります。

4

3 に答える 3

20

私は少し前に同じことを疑問に思っていて、そのようなサンク複製機能のプロトタイプの実装を作成しました。私のプレプリント「<a href="http://arxiv.org/abs/1207.2017" rel="noreferrer">dup – Haskell での明示的な非共有」で結果について読むことができ、http:/でコードを参照できます。 /darcs.nometa.de/ghc-dup . 残念ながら、この論文は今年の Haskell Symposium にも Haskell Implementors Workshop にも受け入れられませんでした。

私の知る限り、この問題に対する現実的な解決策はありません。いずれかのコンパイラの最適化が原因で壊れる可能性のあるユニット パラメータ トリックとしての壊れやすい回避策のみ。

于 2012-07-26T20:05:08.353 に答える
4

興味深い質問です。実装方法がわかりませんcopyThunk。しかし、他にもできることがあります (すでに知っていたらすみません):

xsFunction :: () -> [Int]
xsFunction = const [1..10000000]

better = do
  print $ foldl1' (+) $ xsFunction ()
  print $ length $ xsFunction ()

ここでは、式をサンクに入れることは絶対にありませんxsFunction ()。2回計算されるため、メモリが肥大化することはありません。

これに関する興味深いフォローアップは次のとおりです。

  • 実装できますcopyThunkか？
  • Haskell プログラマーは、この比較的低レベルの最適化をいじる必要がありますか? これでghcが私たちの裏をかくと想定できませんか？
于 2012-07-26T19:25:37.623 に答える
2

関数xsに変換します。これは醜いかもしれませんが、共有を妨げるため機能します:

let xs () = [1..1000000]

good = do
    print $ foldl1' (+) (xs ())
    print $ length (xs ())
于 2012-07-26T19:25:34.977 に答える