6

前の質問と同様に、Data.Binary.Putモナドを別のモナドにラップして、後で「何バイトを書き込むか」や「ファイル内の現在の位置は何か」などの質問をすることができるようにしようとしています。 。

以前は、些細な（IdentityT？）ラッパーを使用しているときにメモリリークが発生する理由を理解することで、問題を解決できると思いました。しかし、皆さんが些細なラッパーの問題を解決するのを手伝ってくれたとしても、StateTやWriterTのような便利なものでラップすると、メモリを大量に消費します（通常はクラッシュします）。

たとえば、これは私がそれをラップしようとしている1つの方法であり、大きな入力のためにメモリをリークします。

タイプOut=StateT Integer P.PutM（）

writeToFile::文字列->出力->IO（）
writeToFile path out = BL.writeFile path $ P.runPut $ do runStateT out 0
                                                         戻る （）

これは、問題を示すより完全なコードサンプルです。

私が知りたいのはこれです：

  1. メモリリークの原因となるプログラム内で何が起こっていますか？
  2. それを修正するにはどうすればよいですか？

2番目の質問では、データがディスク上でどのように見えるかをより詳細に説明する必要があると思います。これは基本的に、ツリーの各ノードがその子（およびいくつかの追加データ）へのオフセットテーブルとして表されるツリー構造です。したがって、オフセットテーブルへのn番目の子のオフセットを計算するには、0からn-1までの子のサイズに現在のオフセットを加えたものを知る必要があります（簡単にするために、各ノードに固定数の子があるとします）。

見てくれてありがとう。

更新：nominoloのおかげで、Data.Binary.Putをラップし、現在のオフセットを追跡し、メモリをほとんど使用しないモナドを作成できるようになりました。これは、継続を使用する別の状態のスレッドメカニズムを優先して、StateTトランスフォーマーの使用をやめることによって行われます。

このような：

タイプOffset=Int

newtype MyPut a = MyPut
  {unS ::forallr。（オフセット-> a-> P.PutM r）->オフセット-> P.PutM r}

インスタンスモナドMyPutここで
  a = MyPut $ \fs->fsaを返します
  ma >> = f = MyPut $ \ fb s-> unS ma（\ s'a-> unS（fa）fb s'）s

writeToFile :: String-> MyPut（）-> IO（）
writeToFileパスput=
  BL.writeFileパス$P.runPut$ peal put >> return（）
  ここで、peal myput = unS myput（\ o-> return）0

getCurrentOffset :: MyPut Int
getCurrentOffset = MyPut $ \ fo-> foo

lift'n ma = MyPut $ \ fs-> ma >> = f（s + n）

ただし、MyPutがディスクに書き込むバイト数の追跡にはまだ問題があります。特に、次のような署名付きの関数が必要です。 

getSize :: MyPut a-> MyPut Int
また
getSize :: MyPut a-> Int

私のアプローチは、MyPutモナドをWriterTトランスフォーマー（このようなもの）内にラップすることでした。しかし、それは再びあまりにも多くのメモリを消費し始めました。sclvがnominolosの回答の下のコメントで言及しているように、WriterTは継続の効果をどういうわけかキャンセルします。彼はまた、私がすでに持っているMyPutモナドから直接サイズを取得できるはずだと述べていますが、そうしようとするすべての試みは、コンパイルできないコードまたは無限ループで終わりました：-|。

誰かがさらに助けてくれませんか？

4

2 に答える 2

8

モナド変換子が怠惰すぎるようです。次のコマンドを使用してプログラムを実行することにより、ヒーププロファイルを（特別に作成しなくても）作成できます。

$ ./myprog +RTS -hT
$ hp2ps myprog.hp
$ open hp2ps.ps    # Or whichever viewer you have

PAPこの場合、s、FUN_1_0s 、sがたくさん表示されるだけなので、特に役に立ちませんFUN_2_0。これは、ヒープが部分的に適用された多数の関数と、1つの引数と2つの引数の関数で構成されていることを意味します。これは通常、何かが十分に評価されていないことを意味します。モナド変換子はこれでいくぶん悪名高いです。

回避策は、継続渡しスタイルを使用して、より厳密なモナド変換子を使用することです。（彼は必要{-# LANGUAGE Rank2Types #-}です。

newtype MyStateT s m a =
  MyStateT { unMyStateT :: forall r. (s -> a -> m r) -> s -> m r }

継続渡しスタイルとは、結果を直接返す代わりに、別の関数である継続を呼び出し、この場合は結果を使用することを意味sしaます。インスタンス定義は少しおかしいように見えます。それを理解するには、上記のリンク（ウィキペディア）を読んでください。

instance Monad m => Monad (MyStateT s m) where
  return x = MyStateT (\k s -> k s x)
  MyStateT f >>= kk = MyStateT (\k s ->
    f (\s' a -> unMyStateT (kk a) k s') s)

runMyStateT :: Monad m => MyStateT s m a -> s -> m (a, s)
runMyStateT (MyStateT f) s0 = f (\s a -> return (a, s)) s0

instance MonadTrans (MyStateT s) where
  lift act = MyStateT (\k s -> do a <- act; k s a)

type Out = MyStateT Integer P.PutM ()

これを実行すると、一定のスペース（「最大常駐」ビット）が得られます。

$ ./so1 +RTS -s 
begin
end
   8,001,343,308 bytes allocated in the heap
     877,696,096 bytes copied during GC
          46,628 bytes maximum residency (861 sample(s))
          33,196 bytes maximum slop
            2 MB total memory in use (0 MB lost due to fragmentation)

Generation 0: 14345 collections,     0 parallel,  3.32s,  3.38s elapsed
Generation 1:   861 collections,     0 parallel,  0.08s,  0.08s elapsed

このような厳密なトランスフォーマーを使用することの欠点は、インスタンスを定義できなくなりMonadFix、特定の怠惰なトリックが機能しなくなることです。

于 2011-02-16T17:58:54.117 に答える
2

私はこれで遊んで始めて、より大きな問題が何であるかを理解しました-あなたのアルゴリズムはひどい複雑さを持っています。各子ツリーのサイズを1回計算するのではなく、getSizeを呼び出すたびに1回計算します。そして、getSizeを再帰的に呼び出します。リーフノードごとに、親でgetSizeが呼び出されるたびにgetSizeが1回呼び出されます。また、getSizeは、各親で1回呼び出され、さらにgetSizeがその親のいずれかで呼び出されるたびに1回呼び出されます。したがって、getsizeは、ツリーの深さで少なくとも幾何学的に呼び出されます。妥当なランタイムに似たものを取得するには、サイズをキャッシュする必要があります。

とは言うものの、これがリークなしで適切に実行されているように見えるコア関数のバージョンですが、上記の理由で実際にクロールしています。

type MyPut = S (Offset,Size) P.PutM

peal_1 :: (Monad m, Num t, Num t1) => S (t, t1) m a -> m a
peal_1 put = unS put (\o -> return) (0,0)

writeToFile :: String -> MyPut () -> IO ()
writeToFile path put =
  BL.writeFile path $ P.runPut $ (peal_1 put) >> return ()

getSize :: MyPut a -> MyPut Int
getSize x = S $ \f os -> unS (x >> getCurrentSize) f os

getCurrentOffset :: MyPut Int
getCurrentOffset = S $ \f os -> f os (fst os)

getCurrentSize :: MyPut Int
getCurrentSize = S $ \f os -> f os (snd os)

また、あなたの論理が一般的に正しいかどうかはわかりません。私のコードは、リークを修正しながら現在の動作を保持します。カットダウンデータセットでコードとコードを実行し、ビットごとに同一のファイルを作成することで、これをテストしました。

しかし、あなたの大規模なテストデータの場合、このコードは私がそれを殺す前に6.5Gを書き込みました（提供されたコードはそれ以前にヒープを使い果たしました）。getSizeの結果が破棄されている場合でも、putモナドの基になる呼び出しがgetSizeの呼び出しごとに1回実行されることは疑わしいですが、テストしていません。

私が提案した適切な解決策は、他の質問への回答として投稿されています：Haskellでツリーデータ構造をバイナリファイルに保存するにはどうすればよいですか？

于 2011-03-02T15:58:33.930 に答える