performance - Perfilando un programa de Haskell

strictness

Question

Tengo un fragmento de código que repetidamente toma muestras de una distribución de probabilidad usando una sequence . Moralmente, hace algo como esto:

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

Excepto que es un poco más complicado. El código real en el que estoy interesado es la función de likelihoodWeighting Pesaje en este repositorio de Github .

Noté que el tiempo de ejecución es no lineal con n . En particular, una vez que n supera un cierto valor, alcanza el límite de memoria y el tiempo de ejecución explota. No estoy seguro, pero creo que esto se debe a que la sequence está formando una larga lista de thunks que no se evalúan hasta la llamada de la sum .

Una vez que supere las 100.000 muestras, el programa se ralentiza. Me gustaría optimizar esto (mi sensación es que 10 millones de muestras no deberían ser un problema), así que decidí crear un perfil, pero me cuesta un poco entender la salida del generador de perfiles.

Perfilado

main.hs un ejecutable corto en un archivo main.hs que ejecuta mi función con 100,000 muestras. Aquí está la salida de hacer

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

Lo primero que noté es que asigna casi 1.5 GB de pila y dedica el 60% de su tiempo a la recolección de basura. ¿Es esto generalmente indicativo de demasiada pereza?

 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

Aquí están los resultados de

$ ./main +RTS -p

La primera vez que ejecuté esto, resultó que había una función que se llamaba repetidamente, y resultó que podía memorizarla, lo que aceleró las cosas en un factor de 2. Sin embargo, no solucionó la fuga de espacio.

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

Aquí hay un montón de perfil. No sé por qué afirma que el tiempo de ejecución es de 1.8 segundos, esta ejecución tomó aproximadamente 6 segundos.

¿Alguien puede ayudarme a interpretar la salida del generador de perfiles, es decir, a identificar dónde está el cuello de botella, y proporcionar sugerencias sobre cómo acelerar las cosas?

Answer 1

Creo que su diagnóstico inicial es correcto y nunca he visto un informe de perfiles que sea útil una vez que se activan los efectos de memoria.

El problema es que estás atravesando la lista dos veces, una para la sequence y otra para la sum . En Haskell, los recorridos de listas múltiples de listas grandes son realmente malos para el rendimiento. La solución generalmente es usar algún tipo de pliegue, como foldM . Su función sampleMean se puede escribir como

{-# LANGUAGE BangPatterns #-}

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

por ejemplo, atravesar la lista solo una vez.

También puede hacer el mismo tipo de cosas con likelihoodWeighting pesaje. Para prevenir los golpes, es importante asegurarse de que el acumulador en su función de plegado tenga el rigor adecuado.

Answer 2

Junté un ejemplo muy elemental, publicado aquí: http://hpaste.org/71919 . No estoy seguro si es algo como tu ejemplo ... solo una cosa muy mínima que parece funcionar.

La -prof con -prof y -fprof-auto y la ejecución con 100000 iteraciones dieron como resultado el siguiente encabezado de la salida de creación de perfiles (perdone mis números de línea):

  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

Y aquí están las estadísticas de resumen:

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

Observe que el perfilador apuntó con su dedo a la sample . Forcé el return en esa función usando $! , y aquí hay algunas estadísticas de resumen después:

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

Mucho más productivo en términos de GC, pero no mucho cambiado en el tiempo. Es posible que pueda seguir iterando en esta forma de perfil / ajuste para dirigirse a sus cuellos de botella y obtener un mejor rendimiento.

Answer 3

Tengo problemas para digerir estos perfiles, pero me han pateado el trasero antes porque el MonadRandom en Hackage es estricto . Crear una versión perezosa de MonadRandom hizo que mis problemas de memoria desaparecieran.

Mi colega aún no ha obtenido permiso para liberar el código, pero he puesto Control.Monad.LazyRandom línea en Control.Monad.LazyRandom . O si desea ver algunos extractos que explican una búsqueda aleatoria totalmente perezosa, incluidas listas infinitas de cálculos aleatorios, consulte el Informe de experiencia: Haskell en biología computacional .

Answer 4

Ya se ha logrado una gran mejora al incorporar la sugerencia de foldM de usar foldM en la likelihoodWeighting foldM . Eso redujo el uso de memoria aproximadamente diez veces aquí, y redujo los tiempos de GC de manera significativa a casi o realmente insignificante.

Una ejecución de perfiles con los rendimientos de la fuente actual

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

y el uso de memoria de 13 MB informado por -s , ~ 5 MB de residencia máxima. Eso no es tan malo ya.

Aún así, quedan algunos puntos que podemos mejorar. Primero, una cosa relativamente menor, en el gran esquema, AI.UTIl.Array.ndSubRef :

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

Invertir la lista y mapear (2^) sobre otra lista es ineficiente, mejor es

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

que no necesita mantener toda la lista en la memoria (probablemente no sea un gran problema, ya que las listas serán cortas), ya que la reversión lo hace, y no es necesario asignar una segunda lista. La reducción en la asignación es notable, alrededor del 10%, y esa parte se ejecuta de manera sensiblemente más rápida,

ndSubRef                   AI.Util.Array          1.7    1.3     24   8000384

en el perfil de la ejecución modificada, pero dado que toma solo una pequeña parte del tiempo total, el impacto general es pequeño. Hay peces potencialmente más grandes para freír en la muestra weightedSample y la likelihoodWeighting weightedSample .

Agreguemos un poco de rigor en weightedSample para ver cómo eso cambia las cosas:

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

El parámetro de peso de go nunca se fuerza, ni el parámetro de asignación, por lo que pueden acumular thunks. Vamos a habilitar {-# LANGUAGE BangPatterns #-} y forzar que las actualizaciones surtan efecto inmediatamente, también evalúe p antes de pasarlo a 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

Eso trae una reducción adicional en la asignación (~ 9%) y una pequeña aceleración (~% 13%), pero el uso total de memoria y la residencia máxima no han cambiado mucho.

No veo nada más obvio para cambiar allí, así que echemos un vistazo a la likelihoodWeighting de likelihoodWeighting :

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

En la última línea, primero, w ya se evaluó en weightedSample ahora, por lo que no es necesario que lo seq aquí, la clave x es necesaria para evaluar el mapa actualizado, por lo que tampoco es necesario especificarlo. Lo malo en esa línea es M.adjust . adjust no tiene forma de forzar el resultado de la función actualizada, por lo que genera thunks en los valores del mapa. Puede forzar la evaluación de los troncales buscando el valor modificado y forzando eso, pero Data.Map proporciona una manera mucho más conveniente aquí, ya que la clave en la que se actualiza el mapa está garantizada para que esté presente, insertWith'' : insertWith''

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

(Nota: GHC se optimiza mejor con un patrón de explosión en m que con el return $! ... aquí). Eso reduce ligeramente la asignación total y no cambia considerablemente el tiempo de ejecución, pero tiene un gran impacto en la memoria total utilizada y la residencia máxima:

 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)

La mayor mejora en el tiempo de ejecución que se obtendría sería evitar el randomIO , el StdGen usado es muy lento.

Me sorprende cuánto tiempo toman las funciones bn* , pero no veo ninguna ineficiencia obvia en ellas.