問題タブ [space-leak]

私は最近 Writer モナドをいじっていて、スペースリークのように見えるものに出くわしました。これらのことをまだ完全に理解しているとは言えませんので、ここで何が起こっているのか、そしてそれを修正する方法を知りたいです.

まず、このエラーをトリガーする方法は次のとおりです。

私は得る：

これをよりよく理解するために、Writer または Sum を使用せずに同様の機能を再実装しました。

seqしかし、方程式に追加することでこれを修正できます。

seq関数のさまざまな部分を試してみましfooたが、役に立たないようです。また、使用してみましControl.Monad.Writer.Strictたが、どちらも違いはありません。

Sumなんか厳しくする必要ある？それとも、まったく違うものを見逃していますか？

ノート

• ここで用語が間違っている可能性があります。Space leak Zooによると、私の問題は「スタック オーバーフロー」に分類されます。その場合、fooより反復的なスタイルに変換するにはどうすればよいですか? 私の手動再帰が問題ですか？
• Haskell Space Overflowを読んだ後-O2、何が起こるかを確認するために、 でコンパイルするという考えが浮かびました。これは別の質問のトピックかもしれませんが、最適化すると、私seqのbar関数でさえ実行に失敗します。 更新: を追加すると、この問題はなくなり-fno-full-lazinessます。

Haskell での遅延評価がスペース リークにつながる場合があることを何度も読みました。スペース リークを引き起こす可能性があるのは、どのようなコードですか? それらを検出する方法は？また、それらを回避するためにプログラマー側でどのような予防策を講じることができますか?

このコードをインタープリターに入力すると、メモリが急速に消費されます。

これが O(1) 以上のスペースを必要とする理由がわかりません。私がそうするだけなら（Showは弱い頭の正規形を強制するので、同じはずなので、seqは冗長ですか？）：

...うまくいきます。

通訳者以外ではこの状況を再現できません。

何が起きてる？

ここにいくつかのテストケースがあります: http://hpaste.org/69234

注意事項:

• インタープリターで実行することにより、wtf.hs をコンパイルせずに読み込みwtf<n>、ghci と入力します。
• コンパイルすることで、私はghc --make wtf.hs && ./wtf.
• lastsum厳密なアキュムレータまたはリスト内の最大要素を見つける関数に置き換えることができますが、スペースリークは引き続き発生します
• $!の代わりに使用した場合、この動作は見られませんでしseqた。
• ()これはCAFの問題かもしれないと思ったので、ダミーパラメータを追加してみました。何も変わりません。
• まったく使用しない と でEnum動作を再現できるため、おそらく関数 on では問題ありません。wtf5Enum
• Num、Int、またはで問題ない可能性があります。これらがなくてもおよびIntegerで動作を再現できるからです。wtf14wtf16

Peano 算術で問題を再現して、式からリストと整数を取り出しようとしました (10^9 の最後で をフェッチします) が、 を実装しようとすると、理解できない他の共有/スペース リークの問題に遭遇しました*。

mapAndSum以下のコードブロックの関数は、以下のすべての機能mapを組み合わせたものですsum（main関数に別の関数が適用されていることを気にしないsumでください。これは、出力をコンパクトにするためだけに役立ちます）。はmap遅延してsum計算されますが、は累積パラメータを使用して計算されます。アイデアはmap、メモリに完全なリストがなくても結果を消費でき、その後（のみ）sum「無料」で利用できるようにすることです。main関数は、を呼び出すときに反駁できないパターンに問題があったことを示していmapAndSumます。この問題について説明させてください。

Haskell標準によると、反駁できないパターンの例let (xs, s) = mapAndSum ... in print xs >> print sは次のように翻訳されます。

したがって、両方のprint呼び出しはペア全体への参照を運び、リスト全体がメモリに保持されます。

私たち（私の同僚のToni Dietzeと私）は、明示的なcaseステートメントを使用してこれを解決しました（「bad」と「good2」を比較してください）。ところで、これを見つけるのにかなりの時間がかかりました..！

さて、私たちが理解していないのは2つあります。

• mapAndSumそもそもなぜ機能するのですか？また、反駁できないパターンを使用しているため、リスト全体をメモリに保持する必要がありますが、明らかにそうではありません。そして、をに変換するletとcase、関数は完全に怠惰な動作になります（スタックがオーバーフローするまで、しゃれは意図されていません）。

  GHCによって生成された「コア」コードを調べましたが、それを解釈できる限り、実際には上記と同じ翻訳が含まletれていました。したがって、ここでは手がかりはなく、代わりにさらに混乱します。

• なぜ「悪い」のですか？最適化がオフの場合は機能しますが、オンの場合は機能しませんか？

実際のアプリケーションに関する1つの注意点は、大きなテキストファイルのストリーム処理（フォーマット変換）を実現すると同時に、別のファイルに書き込まれる値を蓄積することです。示されているように、私たちは成功しましたが、2つの質問が残っており、回答により、今後のタスクと問題に対するGHCの理解が向上する可能性があります。

ありがとうございました！

私はHaskellを初めて使用し、ストリーム処理スタイルでオイラーのふるいを実装しようとしています。

素数についてHaskellWikiページをチェックしたところ、ストリームの不思議な最適化手法が見つかりました。3.8そのウィキの線形マージ：

そしてそれは言う

「<strong>メリッサオニールのコードに従って、不要なメモ化を防ぎ、メモリリークを防ぐために、ここにダブルプライムフィードが導入されています。」</ p>

これはどうやってできるの？それがどのように機能するのか理解できません。

ここに完全なリポジトリがあります。これは非常に単純なテストで、postgresql-simple データベース バインディングを使用して 50000 個のランダムなものをデータベースに挿入します。MonadRandom を使用し、遅延して Thing を生成できます。

これがレイジー シング ジェネレーターです。

ケース 1と Thing ジェネレーターを使用した特定のコード スニペットを次に示します。

これは case2で、Things を stdout にダンプするだけです。

最初のケースでは、GC 時間が非常に悪いです。

2番目のケースでは時間は素晴らしいですが:

ヒープ プロファイリングを適用しようとしましたが、何もわかりませんでした。50000 個のすべての Thing が最初にメモリ内に構築され、次にクエリで ByteStrings に変換され、これらの文字列がデータベースに送信されるようです。しかし、なぜそれが起こるのですか？有罪コードはどのように判断するのですか?

GHC のバージョンは 7.4.2 です

すべてのライブラリとパッケージ自体のコンパイル フラグは -O2 です (サンドボックスで cabal-dev によってコンパイルされます)。

私は次の切り取られた動作に混乱しています：

それを使用してコンパイルすると-O2、スタックオーバーフローが発生します（20Mのメモリが使用されていることを示しています）。紛らわしいのは、次のいずれかの変更が行われた場合、実際には期待どおりに機能することです（スタックオーバーフローがなく、9Mのメモリが使用されています） 。

• Int64Int:(与えるevalFib :: Int64 -> Intと）の代わりに使用されSTUArray s Int64 Intます。実際、Int*（Int32、、など）は、または;Int16と同様にトリックを実行します。WordWord*
• newtype C a画像から削除されます。
• data C a = C !aの代わりに使用されますnewtype

私はこの振る舞いに頭を悩ませようとしています：それはGHC /アレイモジュールのバグですか（とで同じ振る舞いを示します7.4.2）7.6.2、それともそのように動作するはずですか？

PS面白いことに、コアの違いを確認するためにコンパイルしようとすると、ghc array.hs -O2 -fext-core両方のGHCバージョンが「ghc：panic！（「不可能」が発生した）」で失敗します。ここでも運がない。

Vectorうまくいけば良いパフォーマンスが得られるように、s を使用して Haskell で Floyd-Warshall の全ペア最短経路アルゴリズムの効率的な実装を書きたかったのです。

実装は非常に簡単ですが、代わりに 3 次元の |V|×|V|×|V| を使用します。前の値のみを読み取るため、2 次元ベクトルが使用されkます。

したがって、このアルゴリズムは実際には、2D ベクトルが渡されて新しい 2D ベクトルが生成される一連のステップにすぎません。最終的な 2D ベクトルには、すべてのノード (i,j) 間の最短パスが含まれます。

私の直感では、各ステップの前に前の 2D ベクトルが評価されていることを確認することが重要であることがわかったので、関数の引数と strictを使用BangPatternsしました。prevfwfoldl'

ただし、47978 個のエッジを持つ 1000 ノードのグラフでこのプログラムを実行すると、まったくうまくいきません。メモリ使用量が非常に高く、プログラムの実行に時間がかかりすぎます。プログラムは でコンパイルされましたghc -O2。

プロファイリング用にプログラムを再構築し、反復回数を 50 に制限しました。

+RTS -p -hc次に、 andを使用してプログラムを実行しました+RTS -p -hd。

これは... 興味深いですが、サンクが大量に蓄積されていることを示していると思います。良くない。

わかりましたので、暗闇で数回撮影した後、実際に評価されることを確認するために を追加deepseqしました。fwprev

これで見た目が良くなり、一定のメモリ使用量で実際にプログラムを最後まで実行できます。議論の強打prevが十分でなかったことは明らかです。

前のグラフとの比較のために、以下に を追加した後の 50 回の反復のメモリ使用量を示しますdeepseq。

さて、状況は良くなりましたが、まだいくつか質問があります。

1. これは、このスペース リークの正しい解決策ですか? deepseqa を挿入するのが少し醜いと思うのは間違っていますか?
2. ここでの s の使用法はVector慣用的/正しいですか? 反復ごとにまったく新しいベクトルを構築しており、ガベージ コレクターが古いVectors を削除することを期待しています。
3. このアプローチでこれをより速く実行するために他にできることはありますか?

参考までに、httpgraph.txt : //sebsauvage.net/paste/?45147f7caf8c5f29#7tiCiPovPHWRm1XNvrSb/zNl3ujF3xB3yehrxhEdVWw= をご覧ください。

ここにあるmain：