Controllare l'allocazione di memoria/GC in una simulazione?

Question

Sto avendo un po 'di problemi a capire come ridurre l'utilizzo della memoria e il tempo GC in una simulazione in esecuzione nella monade State. Attualmente devo eseguire il codice compilato con +RTS -K100M per evitare lo spazio di overflow dello stack, e le statistiche del GC sono piuttosto orribili (vedi sotto).

Ecco alcuni snippet rilevanti del codice. Il codice completo, funzionante (GHC 7.4.1) è disponibile al numero http://hpaste.org/68527.

-- 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 termini di mucchio, un profilo sembra spunto che le System.Random funzioni, oltre a (,), sono responsabili di memoria. Non riesco a includere direttamente un'immagine, ma qui puoi vedere un profilo di heap: http://i.imgur.com/5LKxX.png.

Non ho idea di come ridurre ulteriormente la presenza di quelle cose. Le variabili casuali vengono generate al di fuori della monade State (per evitare di suddividere il generatore su ogni iterazione) e credo che l'unica istanza di (,) all'interno di simKernel si verifichi quando si coglie una coppia dall'elenco lazy (pairStream) incluso nella configurazione di simulazione.

Le statistiche, tra GC, sono i seguenti:

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 

E ancora, devo urtare la dimensione massima dello stack per eseguire anche la simulazione. So che ci deve essere un grosso thunk che cresce da qualche parte .. ma non riesco a capire dove?

Come posso migliorare l'allocazione heap/stack e GC in un problema come questo? Come posso identificare dove si può costruire un thunk? L'uso della monade State qui è fuorviato?

-

UPDATE:

ho trascurato di guardare oltre l'uscita del profiler quando si compila con -fprof-auto. Ecco il capo di quella uscita:

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 

Non sono sicuro di come interpretare questo esattamente, ma il flusso pigro dei doppi casuali, randomList, mi fa trasalire. Non ho idea di come potrebbe essere migliorato.

Answer 1

Ho aggiornato l'hpaste con un esempio funzionante. Sembra che i colpevoli sono:

• mancanti annotazioni rigore nella tre SimConfig campi: simArray, logP e 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 non è mai stata valutata nel ciclo simKernel a causa di State essere pigro. Un'altra alternativa potrebbe essere quella di utilizzare la monad rigida State.

  put $! newConfig 
  

• execState ... replicateM costruisce anche thunk.Originariamente ho sostituito questo con un foldl' e spostato il execState nella piega, ma penserei scambiare in replicateM_ è equivalente e più facile da leggere:

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

E un paio di telefonate a mapM .. replicate sono stati sostituiti con replicateM . Particolarmente degno di nota in consPairList dove riduce un po 'l'utilizzo della memoria. C'è ancora spazio per migliorare, ma il frutto più basso coinvolge non sicuriInterleaveST ... quindi mi sono fermato.

ho idea se i risultati di output sono ciò che si vuole:

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

Ma qui ci sono le statistiche:

 
    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