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.