24

を使用して確率分布から繰り返しサンプリングするコードがありますsequence。道徳的には、次のようなことを行います。

sampleMean :: MonadRandom m => Int -> m Float -> m Float
sampleMean n dist = do
  xs <- sequence (replicate n dist)
  return (sum xs)

もう少し複雑であることを除いて。私が興味を持っている実際のコードは、この Github repo のlikelihoodWeighting関数です。

実行時間は と非線形にスケーリングすることに気付きましたn。特に、n一定の値を超えるとメモリ制限に達し、実行時間が爆発的に増加します。確かではありませんが、これsequenceは の呼び出しまで評価されないサンクの長いリストを作成しているためだと思いますsum。

約 100,000 個のサンプルを超えると、プログラムの速度が遅くなり、クロールします。これを最適化したい (私の感覚では、1000 万のサンプルは問題にならないはずです) ので、プロファイリングすることにしましたが、プロファイラーの出力を理解するのに少し問題があります。

プロファイリング

main.hs100,000 サンプルで関数を実行する短い実行可能ファイルをファイルに作成しました。これが実行からの出力です

$ ghc -O2 -rtsopts main.hs
$ ./main +RTS -s

最初に気づいたことは、約 1.5 GB のヒープを割り当て、その時間の 60% をガベージ コレクションに費やしていることです。これは一般的に怠惰が多すぎることを示していますか?

 1,377,538,232 bytes allocated in the heap
 1,195,050,032 bytes copied during GC
   169,411,368 bytes maximum residency (12 sample(s))
     7,360,232 bytes maximum slop
           423 MB total memory in use (0 MB lost due to fragmentation)

Generation 0:  2574 collections,     0 parallel,  2.40s,  2.43s elapsed
Generation 1:    12 collections,     0 parallel,  1.07s,  1.28s elapsed

INIT  time    0.00s  (  0.00s elapsed)
MUT   time    1.92s  (  1.94s elapsed)
GC    time    3.47s  (  3.70s elapsed)
RP    time    0.00s  (  0.00s elapsed)
PROF  time    0.23s  (  0.23s elapsed)
EXIT  time    0.00s  (  0.00s elapsed)
Total time    5.63s  (  5.87s elapsed)

%GC time      61.8%  (63.1% elapsed)

Alloc rate    716,368,278 bytes per MUT second

Productivity  34.2% of total user, 32.7% of total elapsed

からの結果は次のとおりです。

$ ./main +RTS -p

これを初めて実行したとき、1 つの関数が繰り返し呼び出されていることが判明し、メモ化できることがわかりました。これにより、処理速度が 2 倍になりました。ただし、スペース リークは解決しませんでした。

COST CENTRE           MODULE                no. entries  %time %alloc   %time %alloc

MAIN                  MAIN                    1        0   0.0    0.0   100.0  100.0
 main                 Main                  434        4   0.0    0.0   100.0  100.0
  likelihoodWeighting AI.Probability.Bayes  445        1   0.0    0.3   100.0  100.0
   distributionLW     AI.Probability.Bayes  448        1   0.0    2.6     0.0    2.6
   getSampleLW        AI.Probability.Bayes  446   100000  20.0   50.4   100.0   97.1
    bnProb            AI.Probability.Bayes  458   400000   0.0    0.0     0.0    0.0
    bnCond            AI.Probability.Bayes  457   400000   6.7    0.8     6.7    0.8
    bnVals            AI.Probability.Bayes  455   400000  20.0    6.3    26.7    7.1
     bnParents        AI.Probability.Bayes  456   400000   6.7    0.8     6.7    0.8
    bnSubRef          AI.Probability.Bayes  454   800000  13.3   13.5    13.3   13.5
    weightedSample    AI.Probability.Bayes  447   100000  26.7   23.9    33.3   25.3
     bnProb           AI.Probability.Bayes  453   100000   0.0    0.0     0.0    0.0
     bnCond           AI.Probability.Bayes  452   100000   0.0    0.2     0.0    0.2
     bnVals           AI.Probability.Bayes  450   100000   0.0    0.3     6.7    0.5
      bnParents       AI.Probability.Bayes  451   100000   6.7    0.2     6.7    0.2
     bnSubRef         AI.Probability.Bayes  449   200000   0.0    0.7     0.0    0.7

これがヒーププロファイルです。ランタイムが 1.8 秒であると主張する理由がわかりません。この実行には約 6 秒かかりました。

ここに画像の説明を入力

プロファイラーの出力を解釈するのを手伝ってくれる人はいますか?つまり、ボトルネックがどこにあるかを特定し、スピードアップする方法を提案してくれますか?

4

4 に答える 4

14

を使用するという JohnL の提案を組み込むことで、すでに大きな改善が達成されています。これにより、メモリ使用量が約 10 分の 1 に削減され、GC 時間が大幅に短縮され、ほとんどまたは実際には無視できるようになりました。foldMlikelihoodWeighting

現在のソースでプロファイリングを実行すると、

probabilityIO              AI.Util.Util          26.1   42.4    413 290400000
weightedSample.go          AI.Probability.Bayes  16.1   19.1    255 131200080
bnParents                  AI.Probability.Bayes  10.8    1.2    171   8000384
bnVals                     AI.Probability.Bayes  10.4    7.8    164  53603072
bnCond                     AI.Probability.Bayes   7.9    1.2    125   8000384
ndSubRef                   AI.Util.Array          4.8    9.2     76  63204112
bnSubRef                   AI.Probability.Bayes   4.7    8.1     75  55203072
likelihoodWeighting.func   AI.Probability.Bayes   3.3    2.8     53  19195128
%!                         AI.Util.Util           3.3    0.5     53   3200000
bnProb                     AI.Probability.Bayes   2.5    0.0     40        16
bnProb.p                   AI.Probability.Bayes   2.5    3.5     40  24001152
likelihoodWeighting        AI.Probability.Bayes   2.5    2.9     39  20000264
likelihoodWeighting.func.x AI.Probability.Bayes   2.3    0.2     37   1600000

によって報告された 13MB のメモリ使用量-s、最大 5MB の常駐。それはもう悪くない。

とはいえ、まだまだ改善できる点はあります。まず、大まかな計画では、比較的小さなことですAI.UTIl.Array.ndSubRef。

ndSubRef :: [Int] -> Int
ndSubRef ns = sum $ zipWith (*) (reverse ns) (map (2^) [0..])

リストを逆にして、別のリストにマッピング(2^)するのは非効率的です。

ndSubRef = L.foldl' (\a d -> 2*a + d) 0

これは、リスト全体をメモリに保持する必要はなく (リストは短いため、おそらく大したことではありません)、逆順にする必要がなく、2 番目のリストを割り当てる必要もありません。割り当ての減少は顕著で、約 10% であり、その部分は測定可能なほど高速に実行されます。

ndSubRef                   AI.Util.Array          1.7    1.3     24   8000384

変更された実行のプロファイルに含まれていますが、全体の時間のごく一部しかかからないため、全体的な影響は小さくなります。で揚げる潜在的に大きな魚がweightedSampleありlikelihoodWeightingます。

weightedSampleそれがどのように変化するかを確認するために、少し厳密に加えてみましょう。

weightedSample :: Ord e => BayesNet e -> [(e,Bool)] -> IO (Map e Bool, Prob)
weightedSample bn fixed =
    go 1.0 (M.fromList fixed) (bnVars bn)
    where
        go w assignment []     = return (assignment, w)
        go w assignment (v:vs) = if v `elem` vars
            then
                let w' = w * bnProb bn assignment (v, fixed %! v)
                in go w' assignment vs
            else do
                let p = bnProb bn assignment (v,True)
                x <- probabilityIO p
                go w (M.insert v x assignment) vs

        vars = map fst fixed

の重みパラメーターgoは強制されず、割り当てパラメーターも強制されないため、サンクを構築できます。{-# LANGUAGE BangPatterns #-}更新を有効にして強制的にすぐに有効にしましょう。また、pに渡す前に評価しprobabilityIOます。

go w assignment (v:vs) = if v `elem` vars
    then
        let !w' = w * bnProb bn assignment (v, fixed %! v)
        in go w' assignment vs
    else do
        let !p = bnProb bn assignment (v,True)
        x <- probabilityIO p
        let !assignment' = M.insert v x assignment
        go w assignment' vs

これにより、割り当てがさらに減少し (~9%)、速度がわずかに向上しました (~%13%) が、総メモリ使用量と最大居住地はあまり変化していません。

likelihoodWeighting他に明らかな変更点はないので、次を見てみましょう。

func m _ = do
    (a, w) <- weightedSample bn fixed
    let x = a ! e
    return $! x `seq` w `seq` M.adjust (+w) x m

最後の行で、最初wは既に評価されてweightedSampleいるので、ここでは必要ありませんseq。キーxは更新されたマップを評価するために必要なので、それseqも必要ありません。その行の悪い点はM.adjust. adjust更新された関数の結果を強制する方法がないため、マップの値にサンクが組み込まれます。変更された値を検索してそれを強制することで、サンクの評価を強制できますがData.Map、マップが更新されるキーが存在することが保証されているため、ここでははるかに便利な方法を提供しますinsertWith'。

func !m _ = do
    (a, w) <- weightedSample bn fixed
    let x = a ! e
    return (M.insertWith' (+) x w m)

m(注: GHCは、ここよりもbang-pattern をオンにした方が最適化されreturn $! ...ます)。これにより、割り当ての合計がわずかに減少し、実行時間はそれほど変化しませんが、使用されるメモリの合計と最大常駐には大きな影響があります。

 934,566,488 bytes allocated in the heap
   1,441,744 bytes copied during GC
      68,112 bytes maximum residency (1 sample(s))
      23,272 bytes maximum slop
           1 MB total memory in use (0 MB lost due to fragmentation)

実行時間の最大の改善はrandomIO、使用を避けることStdGenです。非常に遅いです。

関数にどれだけの時間がbn*かかるかに驚いていますが、それらに明らかな非効率性は見られません。

于 2012-07-22T15:08:27.880 に答える
7

私はこれらのプロファイルを消化するのに苦労していますが、MonadRandomHackage が厳格であるため、以前に尻を蹴られたことがあります。の怠惰なバージョンを作成するとMonadRandom、メモリの問題が解消されました。

私の同僚はまだコードをリリースする許可を得ていませんが、私はpastebinControl.Monad.LazyRandomでオンラインにしました。または、ランダム計算の無限リストを含む、完全に遅延したランダム検索を説明する抜粋を見たい場合は、Experience Report: Haskell in Computational Biologyをチェックしてください。

于 2012-07-22T18:42:11.097 に答える
4

あなたの最初の診断は正しいと思います、そして私は記憶効果が始まったら役に立つプロファイリングレポートを見たことがありません。

問題は、リストを2回トラバースしていることsequenceですsum。Haskellでは、大きなリストの複数のリストトラバーサルは、パフォーマンスに非常に悪い影響を及ぼします。解決策は、一般的に、などのある種の折り畳みを使用することfoldMです。あなたのsampleMean関数は次のように書くことができます

{-# LANGUAGE BangPatterns #-}

sampleMean2 :: MonadRandom m => Int -> m Float -> m Float
sampleMean2 n dist = foldM (\(!a) mb -> liftM (+a) mb) 0 $ replicate n dist

たとえば、リストを1回だけトラバースします。

同じようなこともできますlikelihoodWeighting。サンクを防ぐために、フォールド関数のアキュムレータが適切な厳密さを持っていることを確認することが重要です。

于 2012-07-22T02:23:40.273 に答える
4

ここに投稿された非常に基本的な例をまとめました: http://hpaste.org/71919。それがあなたの例のようなものかどうかはわかりません..うまくいったように見える非常に最小限のものです。

100000回の繰り返しでコンパイル-profおよび-fprof-auto実行すると、次のプロファイリング出力の先頭が得られました（私の行番号を許してください）：

  8 COST CENTRE                   MODULE               %time %alloc
  9 
 10 sample                        AI.Util.ProbDist      31.5   36.6
 11 bnParents                     AI.Probability.Bayes  23.2    0.0
 12 bnRank                        AI.Probability.Bayes  10.7   23.7
 13 weightedSample.go             AI.Probability.Bayes   9.6   13.4
 14 bnVars                        AI.Probability.Bayes   8.6   16.2
 15 likelihoodWeighting           AI.Probability.Bayes   3.8    4.2
 16 likelihoodWeighting.getSample AI.Probability.Bayes   2.1    0.7
 17 sample.cumulative             AI.Util.ProbDist       1.7    2.1
 18 bnCond                        AI.Probability.Bayes   1.6    0.0
 19 bnRank.ps                     AI.Probability.Bayes   1.1    0.0

そして、ここに要約統計があります：

1,433,944,752 bytes allocated in the heap
 1,016,435,800 bytes copied during GC
   176,719,648 bytes maximum residency (11 sample(s))
     1,900,232 bytes maximum slop
           400 MB total memory in use (0 MB lost due to fragmentation)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    1.40s  (  1.41s elapsed)
GC      time    1.08s  (  1.24s elapsed)
Total   time    2.47s  (  2.65s elapsed)

%GC     time      43.6%  (46.8% elapsed)

Alloc rate    1,026,674,336 bytes per MUT second

Productivity  56.4% of total user, 52.6% of total elapsed

プロファイラーが を指していることに注意してくださいsample。returnを使用してその関数を強制しまし$!た。その後の要約統計を次に示します。

1,776,908,816 bytes allocated in the heap
  165,232,656 bytes copied during GC
   34,963,136 bytes maximum residency (7 sample(s))
      483,192 bytes maximum slop
           68 MB total memory in use (0 MB lost due to fragmentation)

INIT    time    0.00s  (  0.00s elapsed)
MUT     time    2.42s  (  2.44s elapsed)
GC      time    0.21s  (  0.23s elapsed)
Total   time    2.63s  (  2.68s elapsed)

%GC     time       7.9%  (8.8% elapsed)

Alloc rate    733,248,745 bytes per MUT second

Productivity  92.1% of total user, 90.4% of total elapsed

GC に関してははるかに生産的ですが、時間はあまり変わりません。このプロファイル/微調整の方法で反復を続けて、ボトルネックをターゲットにし、パフォーマンスを向上させることができる場合があります。

于 2012-07-22T00:12:19.683 に答える