問題タブ [space-leak]

独自のストリーミング コードを作成するにはどうすればよいでしょうか。私は約 1,000,000,000 組のウォー デッキをランダムに生成していました。それらをフォールドに遅延ストリーミングしたかったのですが、スペース リークが発生しました。コードの関連セクションは次のとおりです。

-O2 を付けて実行すると、最初にコンピュータがフリーズし始め、次にプログラムが停止し、コンピュータが復活します (そして、Google Chrome には、すべてのリソースを使い果たしたことを私に怒鳴るのに必要なリソースがあります)。

注: unsafeInterleaveIO を試しましたが、うまくいきませんでした。

完全なコードはhttp://lpaste.net/109977にあります。

楽しみのために、単純な最長パス アルゴリズムの実装を作成しようとしています (循環グラフで最長の非循環パスの長さを見つけるため)。私は命令型アルゴリズムを直接移植することから始めました。これは機能し、かなりうまく機能しました。

は、グラフ内の各ノードが現在アクセスされているかどうか、すべてが false に初期化されているかどうか、およびnodesvisitedはノードのベクトルであるかどうかを表す、ボックス化されていない bool の可変ベクトルです。

max次に、次のように、IORef としてではなく、フォールドで渡される値として持つことで、より機能的にしようとしました。

ただし、このバージョンは完了するのに失敗し、数分間実行されます (同じ入力に数秒かかりました) out of memory (requested 1048576 bytes)。lPathFun誰かが私のコードを見て、私が間違っていることを確認できれば幸いです。私はその中のすべてを厳密にしようとしましたが、それは役に立ちませんでした.また、すべてを怠惰にしようとしましたが、変更はありません. 代わりにstrictに変更type nodeして使用しようとしましたが、役に立ちませんでした。V.Vector routefoldM'

問題はスペースリークだと思います。これは、私がlPathFunOCaml に翻訳しようとしたところ、問題なく動作したためです (OCaml バージョンが手動再帰を使用しているという事実は違いを生むべきではありません: 私の機能的な Haskell バージョンも最初は手動再帰を使用していましたが、foldM を使用した場合と同じ問題に悩まされていました):

私が使用している GHC のバージョンは 7.8.3 です。

次の Haskell プログラムを考えてみましょう (私は主に学習目的でこれを行っています)。

実行すると、メモリはすぐに数 GB に増加します。中間計算 (出力アクション) の結果を確実に破棄するために、さまざまな組み合わせを試しました。なぜまだスペースが漏れているのですか？

全て。

https://www.hackerrank.com/challenges/missing-numbersのプログラミングクイズを解こうとしている ときに、スペースリークに遭遇しました。

主な機能はdifference、マルチセット差分を実装する です。リスト ':' とトリプル (,,) が -hT オプションのプロファイリングでヒープに保持されることがわかりました。ただし、大きなリストだけがの 2 つの引数であり、末尾再帰を続けるdifferenceと縮小します。differenceしかし、リストによって消費されるメモリは、プログラムが実行されるにつれて増加し続けます。

Triples は一時的な配列構造であり、マルチセットの各要素の数を記録するために使用されます。しかし、トリプルによって消費されるメモリも増加し続けており、その理由がわかりません。

同様の「スペースリーク」の質問をstackoverflowで閲覧しましたが、その考えを理解できませんでした. 確かに私には勉強することがたくさんあります。

コメントをお待ちしております。ありがとうございました。

ps) 実行可能ファイルは -O2 スイッチでコンパイルされます。

.

[編集] Carl のアドバイスのおかげで、値と配列を seq しました。ヒープ図を添付します。

[元のヒープ プロファイリング] [ ] 1

[値をシーケンシングした後v]

[値vとをシーケンシングした後Array]

Haskell の遅延評価を理解するのに苦労しています。

簡単なテストプログラムを書きました。4行のデータを読み取り、2番目と4番目の入力行には多くの数字があります。

wordsmap文字のストリームに対して遅延して実行されるため、このプログラムは一定のメモリを使用します 。

しかし、引数を追加するとt、状況が変わります。私の期待は、tおよびmap遅延wordsストリーム上であり、 でt使用されていないためconsumeList、この変更によりメモリ使用量が変更されることはありません。しかし、いいえ。

tQ1)まったく使用されていないのに、このプログラムがメモリを割り当て続けるのはなぜですか?

別の質問があります。レイジー ストリームをパターン マッチさせると[,]、(:)メモリ割り当ての動作が変更されます。

Q2)(:)と[,]は遅延評価の点で異なりますか?

どんなコメントでも大歓迎です。ありがとう

[編集]

Q3) では、メモリ消費を増やさずに、4 行目を先に処理し、2 行目を処理することは可能でしょうか?

Derek が案内する実験は次のとおりです。2 番目の例から y と k を切り替えると、同じ結果が得られました。

数日前にこの質問を投稿しました:動的プログラミングを使用した Haskell のパフォーマンスで、文字列の代わりに ByteStrings を使用することをお勧めしました。ByteStrings を使用してアルゴリズムを実装した後、プログラムがクラッシュし、メモリの制限を超えます。

メモリ消費量は に比例するように見えますn。入力文字列の長さは 1000 文字です。editDistance各ソリューションが印刷された後、Haskell が使用されているすべてのメモリを解放することを期待します。そうではありませんか？そうでない場合、どうすればこれを強制できますか?

私が見る唯一の他の実際の計算は for ですcostが、それを強制してseqも何もしませんでした。

私は最近、競争力のあるコーディング コンテストに参加しました。

この Haskell は、ghc 7.6.3 を実行しているジャッジ システムでスペース リークを引き起こしました。

コンペティション後、テストケースが公開されました。失敗例の 1 つがこれでした: (10^5 の閉じ括弧を含むファイル): https://cses.fi/download/1/b575d19a75bf724b50fa4a399f8187b6d6edb4ccb62bd1a774f9294969152e46

エラーは

また、GHC 7.6.3 であると私が信じているもので、コードが -O2 と -Wall でコンパイルされたことも知っています。

私の人生では、私のマシンで GHC 8.0.2 または 7.10.3 でエラーを再現することはできません。

コードに明らかなスペース リークがありますか?

編集：

以下に提案されているようにコードをテストし、そのように実装された折り畳みをテストしました：

バンジーパターンはより多くのテストケースを通過しましたが、バングパターンも厳密な再実装もfoldl'問題を解決しませんでした。元のまだ WOMM。確かに、これは一般的に有用なスタック交換の質問の範囲から外れており、古き良き宿題のように見え始めています。これもまた、ジャッジ システムの知識がなければ、かなりデバッグ不可能です。

Google の C++ テスト フレームワークで、私の目は次のように読みました。

.. 現在の関数からすぐに戻り、その後に続くクリーンアップ コードをスキップする可能性があり、スペース リークが発生する可能性があります。

私の脳はメモリリークが発生することを期待していました。

その用語は C++ で使用されていますか? もしそうなら、それはどういう意味ですか (つまり、メモリリークとどのように区別できますか)?

Haskellでは、スペース リークとは、プログラムまたは特定の計算が必要以上に多くのメモリを使用する状況を指します。

Javaでは、「スペース リーク」というフレーズを使用しても意味がありません。