Kontrolle der Speicherzuordnung/GC in einer Simulation?

Question

Ich habe ein wenig Mühe herauszufinden, wie Speicherverbrauch und GC-Zeit in einer Simulation in der State Monad zu reduzieren. Derzeit muss ich den kompilierten Code mit +RTS -K100M ausführen, um Stack-Speicherüberlauf zu vermeiden, und die GC-Statistiken sind ziemlich abscheulich (siehe unten).

Hier sind relevante Schnipsel des Codes. Der vollständige, funktionierende (GHC 7.4.1) Code kann unter http://hpaste.org/68527 gefunden werden.

-- Lone algebraic data type holding the simulation configuration. 
data SimConfig = SimConfig { 
     numDimensions :: !Int   -- strict 
    , numWalkers :: !Int   -- strict 
    , simArray  :: IntMap [Double] -- strict spine 
    , logP   :: Seq Double  -- strict spine 
    , logL   :: Seq Double  -- strict spine 
    , pairStream :: [(Int, Int)] -- lazy (infinite) list of random vals 
    , doubleStream :: [Double]  -- lazy (infinite) list of random vals 
    } deriving Show 

-- The transition kernel for the simulation. 
simKernel :: State SimConfig() 
simKernel = do 
    config <- get 
    let arr = simArray  config 
    let n  = numWalkers config 
    let d  = numDimensions config 
    let rstm0 = pairStream config 
    let rstm1 = doubleStream config 
    let lp = logP   config 
    let ll = logL   config 

    let (a, b) = head rstm0       -- uses random stream  
    let z0 = head . map affineTransform $ take 1 rstm1 -- uses random stream 
      where affineTransform a = 0.5 * (a + 1)^2 


    let proposal = zipWith (+) r1 r2 
      where r1 = map (*z0)  $ fromJust (IntMap.lookup a arr) 
        r2 = map (*(1-z0)) $ fromJust (IntMap.lookup b arr) 

    let logA = if val > 0 then 0 else val 
      where val = logP_proposal + logL_proposal - (lp `index` (a - 1)) - (ll `index` (a - 1)) + ((fromIntegral n - 1) * log z0) 
        logP_proposal = logPrior proposal 
        logL_proposal = logLikelihood proposal 

    let cVal  = (rstm1 !! 1) <= exp logA   -- uses random stream 

    let newConfig = SimConfig { simArray = if cVal 
              then IntMap.update (\_ -> Just proposal) a arr 
              else arr 
           , numWalkers = n 
           , numDimensions = d 
           , pairStream = drop 1 rstm0 
           , doubleStream = drop 2 rstm1 
           , logP = if cVal 
             then Seq.update (a - 1) (logPrior proposal) lp 
             else lp 
           , logL = if cVal 
             then Seq.update (a - 1) (logLikelihood proposal) ll 
             else ll 
           } 

    put newConfig 

main = do 
    -- (some stuff omitted) 
    let sim = logL $ (`execState` initConfig) . replicateM 100000 $ simKernel 
    print sim 

In Bezug auf den Haufen, scheint ein Profil, dass die System.Random Funktionen spulen, zusätzlich zu (,), Speicher Täter sind. Ich kann ein Bild nicht direkt einschließen, aber Sie können ein Heap-Profil hier sehen: http://i.imgur.com/5LKxX.png.

Ich habe keine Ahnung, wie man die Anwesenheit dieser Dinge weiter reduzieren kann. Die Zufallsvariablen werden außerhalb der State Monade generiert (um eine Aufteilung des Generators bei jeder Iteration zu vermeiden), und ich glaube, die einzige Instanz von (,) innerhalb simKernel entsteht beim Zupfen eines Paares aus der faulen Liste (pairStream), die in der Simulationskonfiguration enthalten ist.

Die Statistiken, einschließlich GC, sind wie folgt:

1,220,911,360 bytes allocated in the heap 
    787,192,920 bytes copied during GC 
    186,821,752 bytes maximum residency (10 sample(s)) 
     1,030,400 bytes maximum slop 
      449 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  2159 colls,  0 par 0.80s 0.81s  0.0004s 0.0283s 
    Gen 1  10 colls,  0 par 0.96s 1.09s  0.1094s 0.4354s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 0.95s ( 0.97s elapsed) 
    GC  time 1.76s ( 1.91s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 2.72s ( 2.88s elapsed) 

    %GC  time  64.9% (66.2% elapsed) 

    Alloc rate 1,278,074,521 bytes per MUT second 

    Productivity 35.1% of total user, 33.1% of total elapsed 

Und wieder muss ich die maximale Stapelgröße, um stoßen bis zu sogar die Simulation zu laufen. Ich weiß, dass irgendwo ein großer Thunk aufbauen muss. Aber ich kann nicht herausfinden, wo?

Wie kann ich die Heap/Stack-Zuweisung und GC in einem Problem wie diesem verbessern? Wie kann ich herausfinden, wo sich ein Thunk aufbauen kann? Ist die Verwendung der State Monade hier fehlgeleitet?

-

UPDATE:

ich vernachlässigt über den Ausgang des Profiler zu suchen, wenn sie mit -fprof-auto kompilieren. Hier ist der Kopf dieser Ausgabe:

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

MAIN        MAIN        58   0 0.0 0.0 100.0 100.0 
main        Main        117   0 0.0 0.0 100.0 100.0 
    main.randomList     Main        147   1 62.0 55.5 62.0 55.5 
    main.arr      Main        142   1 0.0 0.0  0.0 0.0 
    streamToAssocList    Main        143   1 0.0 0.0  0.0 0.0 
    streamToAssocList.go   Main        146   5 0.0 0.0  0.0 0.0 
    main.pairList     Main        137   1 0.0 0.0  9.5 16.5 
    consPairStream     Main        138   1 0.7 0.9  9.5 16.5 
    consPairStream.ys    Main        140   1 4.3 7.8  4.3 7.8 
    consPairStream.xs    Main        139   1 4.5 7.8  4.5 7.8 
    main.initConfig     Main        122   1 0.0 0.0  0.0 0.0 
    logLikelihood     Main        163   0 0.0 0.0  0.0 0.0 
    logPrior      Main        161   5 0.0 0.0  0.0 0.0 
    main.sim      Main        118   1 1.0 2.2 28.6 28.1 
    simKernel      Main        120   0 4.8 5.1 27.6 25.8 

Ich bin nicht sicher, wie diese genau zu interpretieren, aber der faule Strom von Zufallsdoppelzimmer, randomList, macht mich zusammenzucken. Ich habe keine Ahnung, wie das verbessert werden könnte.

Answer 1

Ich habe die HPaste mit einem Arbeitsbeispiel aktualisiert. Es sieht aus wie die Täter sind:

• Fehlende Strikt Anmerkungen in drei SimConfig Felder: simArray, logP und logL

 
    data SimConfig = SimConfig { 
      numDimensions :: !Int   -- strict 
     , numWalkers :: !Int   -- strict 
     , simArray  :: !(IntMap [Double]) -- strict spine 
     , logP   :: !(Seq Double)  -- strict spine 
     , logL   :: !(Seq Double)  -- strict spine 
     , pairStream :: [(Int, Int)] -- lazy 
     , doubleStream :: [Double]  -- lazy 
     } deriving Show 

• newConfig nie wegen State in der simKernel Schleife ausgewertet wurde faul. Eine andere Alternative wäre die Verwendung der strengen Monade State statt.

  put $! newConfig 
  

• execState ... replicateM baut auch Thunks.Ich ersetzte ursprünglich dies mit einem foldl' und bewegt die execState in den Schoß, aber ich würde in replicateM_ denken Swapping entspricht und leichter zu lesen:

  let sim = logL $ execState (replicateM_ epochs simKernel) initConfig 
  -- sim = logL $ foldl' (const . execState simKernel) initConfig [1..epochs] 
  

Und ein paar Anrufe zu mapM .. replicate mit replicateM ersetzt wurden . Besonders erwähnenswert in consPairList, wo es Speicherverbrauch ziemlich reduziert. Es gibt noch Raum für Verbesserungen, aber die niedrigste hängende Frucht beinhaltet unsichere InterleaveST ... also hörte ich auf.

Ich habe keine Ahnung, ob die Ausgabeergebnisse sind das, was Sie wollen:

 
fromList [-4.287033457733427,-1.8000404912760795,-5.581988678626085,-0.9362372340483293,-5.267791907985331] 

Aber hier sind die Statistiken:

 
    268,004,448 bytes allocated in the heap 
     70,753,952 bytes copied during GC 
     16,014,224 bytes maximum residency (7 sample(s)) 
     1,372,456 bytes maximum slop 
       40 MB total memory in use (0 MB lost due to fragmentation) 

            Tot time (elapsed) Avg pause Max pause 
    Gen 0  490 colls,  0 par 0.05s 0.05s  0.0001s 0.0012s 
    Gen 1   7 colls,  0 par 0.04s 0.05s  0.0076s 0.0209s 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT  time 0.12s ( 0.12s elapsed) 
    GC  time 0.09s ( 0.10s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 0.21s ( 0.22s elapsed) 

    %GC  time  42.2% (45.1% elapsed) 

    Alloc rate 2,241,514,569 bytes per MUT second 

    Productivity 57.8% of total user, 53.7% of total elapsed