¿Cómo reducir el uso de memoria en una aplicación Haskell?

https://stackoverflow.com/questions/459725

19-08-2019
|

Pregunta

Soy nuevo en programación funcional y ahora aprendo a Haskell. Como ejercicio, decidí implementar el método explícito de Euler para la ecuación de difusión lineal 1D. Si bien el siguiente código funciona correctamente, no estoy contento con su rendimiento. De hecho, me preocupa el consumo de memoria. Creo que está relacionado con la evaluación diferida, pero no puedo entender cómo puedo reducir su uso de memoria.

La idea del algoritmo es realmente simple, para dejarlo claro en términos imperativos: toma una 'matriz', y a cada punto interno agrega un valor, que se calcula como una combinación de los valores en el punto mismo y en sus vecinos Los puntos límite son casos especiales.

Entonces, este es mi módulo Euler1D.hs:

module Euler1D
( stepEuler
, makeu0
) where

-- impose zero flux condition
zeroflux :: (Floating a) => a -> [a] -> [a]
zeroflux mu (boundary:inner:xs) = [boundary+mu*2*(inner-boundary)]

-- one step of integration
stepEuler :: (Floating a) => a -> [a] -> [a]
stepEuler mu u@(x:xs) = (applyBC . (diffused mu)) u
    where
          diffused mu (left:x:[]) = []    -- ignore outer points
          diffused mu (left:x:right:xs) = -- integrate inner points
                   (x+mu*(left+right-2*x)) : diffused mu (x:right:xs)
          applyBC inner = (lbc u') ++ inner ++ (rbc u') -- boundary conditions
               where u' = [head u] ++ inner ++ [last u]
                     lbc = zeroflux mu             -- left boundary
                     rbc = (zeroflux mu) . reverse -- right boundary

-- initial condition
makeu0 :: Int -> [Double]
makeu0 n = [ ((^2) . sin . (pi*) . xi) x | x <- [0..n]]
    where xi x = fromIntegral x / fromIntegral n

Y un Main.hs simple:

module Main where

import System ( getArgs )
import Euler1D

main = do
      args <- getArgs
      let n = read $ head args :: Int
      let u0 = makeu0 n
      let un = stepEuler 0.5 u0
      putStrLn $ show $ sum un

Para comparar, también escribí una implementación C pura .

Ahora, si intento ejecutar la implementación de Haskell para un tamaño suficientemente grande de la matriz n , tengo:

$ time ./eulerhs 200000
100000.00000000112

real    0m3.552s
user    0m3.304s
sys     0m0.128s

En comparación, la versión C es más rápida en casi dos órdenes de magnitud:

$ time ./eulerc 200000
100000

real    0m0.088s
user    0m0.048s
sys     0m0.008s

EDIT : esta comparación no es realmente justa, porque la versión de Haskell es   compilado con banderas de perfil, y C   no es. Si compilo ambos programas   con -O2 y ambos sin perfilar   banderas, puedo aumentar n . En esto   caso time ./eulerhs 1000000 toma   0m2.236s, mientras que time ./eulerc   1000000 solo toma 0m0.293s. Entonces el   el problema aún persiste con todos   optimizaciones y sin perfilar,   solo está compensado.

Me gustaría también señalar que ese recuerdo   asignación del programa Haskell   parece crecer linealmente con n .   Esto probablemente esté bien.

Pero lo peor son los requisitos de memoria. Mi versión de Haskell requiere más de 100MB (mi estimación del mínimo en C es 4MB ). Creo que esta puede ser la fuente del problema. Según el informe de perfil, el programa pasa el 85% del tiempo en GC y

        total time  =        0.36 secs   (18 ticks @ 20 ms)
        total alloc = 116,835,180 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

makeu0                         Euler1D               61.1   34.9
stepEuler                      Euler1D               33.3   59.6
CAF:sum                        Main                   5.6    5.5

Me sorprendió ver que makeu0 es tan caro. Decidí que esto se debe a su evaluación perezosa (si sus thunks permanecen en la memoria hasta el final de stepEuler ).

Intenté este cambio en Main.hs :

   let un = u0 `seq` stepEuler 0.5 u0

pero no notó ninguna diferencia. No tengo idea de cómo reducir el uso de memoria en stepEuler . Entonces, mis preguntas son:

¿Hay alguna manera en Haskell para construir listas / hacer listas de comprensión estrictamente? En este caso, no hay ningún beneficio para mantenerlo perezoso.
¿Cómo puedo reducir el uso general de memoria en este caso? Supongo que tengo que hacer algo estricto, pero no veo qué. En otras palabras, si tengo que poner algunos seq sy bangs, ¿dónde y por qué?
Y finalmente, lo más importante, ¿cuál es la mejor estrategia para identificar construcciones tan costosas?

Leí un capítulo sobre creación de perfiles y optimización en Real World Haskell , pero no está claro cómo exactamente puedo decidir qué debería ser estricto y qué no.

Por favor, perdóname una publicación tan larga.

EDIT2 : como lo sugirió A. Rex en los comentarios, intenté ejecutar ambos   programas en valgrind. Y esto es lo que   Observé. Para el programa Haskell   ( n = 200000) encontró:


malloc / free: 33 asignaciones, 30 liberaciones, 84,109 bytes asignados.     ...     comprobado 55,712,980 bytes.


Y para el programa C (después de una pequeña corrección):


malloc / free: 2 asignaciones, 2 liberaciones, 3,200,000 bytes asignados.


Entonces, parece que mientras Haskell   asigna bloques de memoria mucho más pequeños,   lo hace a menudo, y debido a la demora en   recolección de basura, se acumulan   y re

Solución

Las listas no son la mejor estructura de datos para este tipo de código (con muchos (++) y (último)). Pierdes mucho tiempo construyendo y deconstruyendo listas. Usaría Data.Sequence o arrays, como en las versiones en C.
No hay posibilidad de que se recolecten basuras de makeu0, ya que es necesario conservarlas todas (bueno, todos los resultados de '' difusa '', para ser exactos) hasta el final fin del cómputo para poder hacer '' revertir '' en applyBC. Lo cual es muy costoso, teniendo en cuenta que solo necesita dos elementos del final de la lista para su "zeroflux".

Aquí hay un truco rápido de su código que intenta lograr una mejor fusión de listas y hace menos construcción de listas:

module Euler1D
( stepEuler
) where

-- impose zero flux condition
zeroflux mu (boundary:inner:xs) = boundary+mu*2*(inner-boundary)

-- one step of integration
stepEuler mu n = (applyBC . (diffused mu)) $ makeu0 n
    where
          diffused mu (left:x:[]) = []    -- ignore outer points
          diffused mu (left:x:right:xs) = -- integrate inner points
                   let y = (x+mu*(left+right-2*x))
                       in y `seq` y : diffused mu (x:right:xs)
          applyBC inner = lbc + sum inner + rbc -- boundary conditions
               where
                     lbc = zeroflux mu ((f 0 n):inner)             -- left boundary
                     rbc = zeroflux mu ((f n n):(take 2 $ reverse inner)) -- right boundary

-- initial condition
makeu0 n = [ f x n | x <- [0..n]]

f x n = ((^2) . sin . (pi*) . xi) x
    where xi x = fromIntegral x / fromIntegral n

Para 200000 puntos, se completa en 0,8 segundos frente a 3,8 segundos para la versión inicial

Otros consejos

En mi sistema x86 de 32 bits, su programa usa solo unos 40 MB de memoria.

¿Está confundiendo el " total alloc = 116,835,180 bytes " línea de su salida de perfil con la cantidad de memoria realmente utilizada por el programa en cualquier momento? La asignación total es la cantidad de memoria asignada en todo el programa ejecutado; gran parte de esto es liberado por el recolector de basura a medida que avanza. Puede esperar que ese número sea muy grande en un programa Haskell; Tengo programas que asignan muchos terrabytes de memoria en el transcurso de toda su ejecución, aunque en realidad tienen un tamaño máximo de memoria virtual de cien megabytes más o menos.

No me preocuparía demasiado por las grandes asignaciones totales en el transcurso de la ejecución de un programa; esa es la naturaleza de un lenguaje puro, y el tiempo de ejecución de GHC tiene un muy buen recolector de basura para ayudar a compensar esto.

De manera más general, puede averiguar a dónde va su memoria utilizando Herramientas de creación de perfiles de almacenamiento dinámico de GHC. En mi experiencia, no necesariamente le dirán por qué se están filtrando sus datos, pero al menos pueden reducir las causas potenciales.

También puede encontrar iluminando esto excelente publicación de blog de Don Stewart sobre la comprensión de la rigurosidad, cómo interactúa con la recolección de basura y cómo diagnosticar y solucionar problemas.

¿Forzar " falta de pereza " usando $! ¿ayuda? según esta respuesta .

Por solicitud de Harleqin: ¿Has intentado configurar banderas de optimización? Por ejemplo, con ghc, puede usar add " -O2 " tal como lo harías con gcc. (Aunque no estoy seguro de qué niveles de optimización existen en ghc; la página del manual no dice exactamente ...)

En mi experiencia pasada, establecer esta bandera ha hecho una tremenda diferencia. Por lo que puedo decir, runhugs y no optimizado ghc utilizan la implementación más básica y obvia de Haskell; desafortunadamente, esto a veces no es muy eficiente.

Pero eso es solo una suposición. Como dije en mi comentario, espero que alguien responda bien a su pregunta. A menudo tengo problemas para analizar y corregir el uso de memoria de Haskell.

Utilice el interruptor -fvia-C también.

Una cosa que me llamó la atención ahora es que la salida de Haskell es flotante, mientras que la salida de C parece ser entera. Todavía no he entendido el código de Haskell, pero ¿hay algún lugar donde tenga aritmética de coma flotante en Haskell mientras C usa números enteros?

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow