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

reducir el consumo de memoria ram

Question

Soy nuevo en la programación funcional, y ahora aprendo Haskell. Como ejercicio, decidí implementar el método explícito de Euler para la ecuación de difusión lineal 1D. Si bien el código siguiente funciona correctamente, no estoy contento con su rendimiento. De hecho, me preocupa el consumo de memoria. Creo que está relacionado con la evaluación perezosa, 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 para cada punto interno agrega un valor, que se calcula como una combinación de los valores en el punto mismo y en su vecinos Los puntos de frontera 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 la comparación, 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

Para 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

EDITAR : Esta comparación no es realmente justa, porque la versión de Haskell está compilada con indicadores de perfil, y C no. Si compilo ambos programas con -O2 y ambos sin indicadores de perfil, puedo aumentar n . En este caso, time ./eulerhs 1000000 toma 0m2.236s, mientras que time ./eulerc 1000000 toma solo 0m0.293s. Por lo tanto, el problema persiste con todas las optimizaciones y sin crear perfiles, solo se compensa.

También me gustaría señalar que la asignación de memoria del programa Haskell parece crecer linealmente con n . Esto es probablemente correcto.

Pero lo peor son los requisitos de memoria. Mi versión de Haskell requiere más de 100 MB (mi estimación del mínimo básico en C es de 4 MB ). Creo que esta puede ser la fuente del problema. Según el informe de perfil, el programa gasta 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 debía a su evaluación perezosa (si los thunk 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:

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

Leí un capítulo sobre la creación de perfiles y la optimización en Real World Haskell , pero sigue sin estar claro cómo puedo decidir exactamente 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 allocs, 30 libres, 84,109 bytes asignados. ... verificó 55,712,980 bytes.

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

malloc / free: 2 allocs, 2 libres, 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 la recolección de basura, se acumulan y permanecen en la memoria. Entonces, tengo otra pregunta:

• ¿Es posible evitar una gran cantidad de pequeñas asignaciones en Haskell? Básicamente, para declarar, necesito procesar toda la estructura de datos en lugar de solo sus fragmentos a pedido.

Answer 1

1. Las listas no son la mejor estructura de datos para este tipo de código (con muchas (++) y (últimas)). Pierde mucho tiempo construyendo y deconstruyendo listas. Usaría Data.Sequence o arrays, como en las versiones C.

2. No hay posibilidad de que los thunks de makeu0 sean recolectados como basura, ya que es necesario retenerlos a todos (bueno, todos los resultados de "diffuse", para ser exactos) hasta el final del cálculo para poder capaz de hacer "reversa" en applyBC. Lo cual es muy costoso, considerando que solo necesita dos elementos del final de la lista para su "zeroflux".

Aquí está el truco rápido de tu código que intenta lograr una mejor lista de fusión y hace menos lista (de) construir:

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

Answer 2

¿Obliga a la "falta de holgazanería" a usar $! ¿ayuda? según esta respuesta .

Answer 3

De forma más general, puede averiguar dónde va su memoria utilizando las herramientas de generación de perfiles de GHC. En mi experiencia, no necesariamente te dirán por qué se están filtrando tus datos, pero al menos pueden reducir las posibles causas.

También puede encontrar la iluminación de esta excelente publicación de Don Stewart sobre la comprensión del rigor, cómo interactúa con la recolección de basura y cómo diagnosticar y solucionar problemas.

Answer 4

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

¿Está confundiendo quizás la línea "total alloc = 116,835,180 bytes" de su salida de generación de perfiles con la cantidad de memoria que el programa utiliza realmente en un momento dado? La asignación total es la cantidad de memoria asignada durante la ejecución completa del programa; 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 sobre grandes asignaciones totales en el transcurso de una ejecución de 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.

Answer 5

Según la solicitud de Harleqin: ¿Has intentado establecer indicadores de optimización? Por ejemplo, con ghc, puede usar agregar "-O2" como lo haría con gcc. (Aunque no estoy seguro de qué niveles de optimización existen en ghc, la página de manual no dice exactamente ...)

En mi experiencia pasada, establecer esta bandera ha supuesto una gran diferencia. Por lo que puedo decir, runhugs y ghc no ghc usan 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 su pregunta. A menudo tengo problemas para analizar y corregir el uso de memoria de Haskell.

Answer 6

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

Answer 7

Use el interruptor -fvia-C también.