Como reduzir o uso de memória em um aplicativo de Haskell?

https://stackoverflow.com/questions/459725

19-08-2019
|

Pergunta

Eu sou novo em programação funcional, e agora aprender Haskell. Como um exercício, decidi implementar o método de Euler explícito para equação de difusão linear 1D. Enquanto o código abaixo funciona corretamente, eu não estou feliz com o seu desempenho. Na verdade, eu estou preocupado com o consumo de memória. Eu acredito que ela está relacionada com avaliação preguiçosa, mas não consigo descobrir como eu pode reduzir seu uso de memória.

A idéia do algoritmo é muito simples, para que fique claro em termos imperativos: é preciso um array `', e cada ponto interior que acrescenta um valor, que é calculada como uma combinação dos valores no próprio ponto e em seus vizinhos. pontos de fronteira são casos especiais.

Assim, esta é a minha Euler1D.hs módulo:

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

e um simples Main.hs:

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 efeito de comparação, eu também escreveu uma pura implementação C .

Agora, se eu tentar executar aplicação Haskell para uma suficientemente grande tamanho do n array, eu tenho:

$ time ./eulerhs 200000
100000.00000000112

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

Para efeito de comparação, a versão C é mais rápido por quase duas ordens de grandeza:

$ time ./eulerc 200000
100000

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

Editar : Esta comparação não é realmente justo, porque a versão Haskell é compilado com bandeiras de perfil e C não é. Se eu compilar os dois programas com -O2 e ambos sem profiling bandeiras, eu posso aumentar n. Nisso caso time ./eulerhs 1000000 leva 0m2.236s, enquanto time ./eulerc 1000000 leva apenas 0m0.293s. Então o problema ainda permanece com toda otimizações e sem perfis, ele só é compensado.

Gostaria também de nota, que a memória alocação do programa Haskell parece crescer lineary com n. Este é provavelmente OK.

Mas o pior são os requisitos de memória. Minha versão Haskell requer mais de 100MB (minha estimativa do mínimo em C é 4MB ). Eu acho que esta pode ser a origem do problema. Segundo o relatório de perfil do programa gasta 85% do tempo no GC, e

        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

Eu estava surpreso ao ver que makeu0 é para caro. I decidiu que este é devido à sua avaliação preguiçosa (se seus thunks permanecem na memória até o fim do stepEuler).

Eu tentei essa mudança de Main.hs:

   let un = u0 `seq` stepEuler 0.5 u0

mas não notar qualquer diferença. Eu não tenho nenhuma idéia de como reduzir o uso de memória no stepEuler. Então, minhas perguntas são:

Existe uma maneira em Haskell a listas de construção / fazer compreensões lista estritamente? Neste caso, não há nenhum benefício para mantê-lo preguiçoso.
Como posso reduzir o uso de memória global neste caso? Suponho que, eu tenho que fazer algo estrito, mas não conseguem ver o que. Em outras palavras, se eu tiver que colocar algumas seqs e estrondos, onde e por quê?
E, finalmente, o mais importante, qual é a melhor estratégia para identificar tais construções dispendiosas?

Eu fiz ler um capítulo sobre a criação de perfis e otimização na Real World Haskell , mas ainda não está claro como exatamente eu posso decidir o que deve ser rigoroso e quais não.

Por favor, perdoe-me um longo post tal.

EDIT2 : Como sugerido por A. Rex nos comentários, eu tentei correr tanto programas em valgrind. E é isso que Eu observei. Para o programa Haskell (n = 200000) que encontrou:

malloc / livre: 33 alocações, 30 liberta, 84,109 bytes alocados. ... verificadas 55,712,980 bytes.

E para o programa C (depois de uma pequena correção):

malloc / free:. 2 alocações, 2 liberta, 3.200.000 bytes alocados

Assim, parece que, enquanto Haskell aloca blocos de memória muito menores, ele fazmuitas vezes, e devido ao atraso no coleta de lixo, que se acumulam e permanecem na memória. Então eu tenho outra pergunta:

É possível evitar uma série de pequenas alocações em Haskell? Basicamente, a declarar, que eu preciso processar toda a estrutura de dados em vez de apenas os seus fragmentos sobre demanda.

Solução

As listas não são a melhor estrutura de dados para este tipo de código (com lotes de (++), e (último)). Você perde um monte de constucting tempo e listas desconstruindo. Eu usaria Data.Sequence ou matrizes, como nas versões C.
Não há nenhuma chance para thunks de makeu0 a ser de lixo coletado, desde que você precisa para manter todos eles (bem, todos os resultados de "difusa", para ser exato) todo o caminho até o fim da computação, a fim de ser capaz de fazer "reverse" em applyBC. Que é coisa muito caro, considerando que você só precisa de dois itens da cauda da lista para o seu "zeroflux".

Aqui está rapidamente cortar de vocês código que tenta conseguir uma melhor fusão lista e faz menos lista (de) construção:

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 pontos, completa em 0,8 segundos vs 3,8 segundos para a versão inicial

Outras dicas

No meu sistema x86 de 32 bits, o programa utiliza apenas cerca de 40 MB de memória.

Você talvez confundindo a linha "Total de Alloc = 116,835,180 bytes" de sua saída de perfil com a quantidade de memória realmente é usado pelo programa a qualquer momento? A alocação total é de quanta memória foi alocado ao longo de toda a execução do programa; grande parte desta é liberado pelo coletor de lixo que você vá junto. Você pode esperar que o número de obter muito grande em um programa Haskell; Tenho programas que alocam muitos terrabytes de memória ao longo de toda a sua corrida, embora eles realmente têm um tamanho máximo de memória virtual de uma centena de megabytes ou mais.

Eu não me preocuparia muito com grandes dotações totais ao longo de um programa de corrida; essa é a natureza de uma linguagem pura, e tempo de execução do GHC tem um muito bom coletor de lixo para ajudar a compensar isso.

De modo mais geral, você pode descobrir onde a sua memória vai usar pilha de GHC ferramentas de criação de perfil. na minha experiência, eles não vão necessariamente dizer-lhe porque seus dados estão sendo vazado, mas pode pelo menos diminuir as causas potenciais.

Você também pode achar que ilumina este excelente post por Don Stewart sobre rigor compreensão, como ele interage com coleta de lixo, e como diagnosticar e problemas de correção.

O forçando "un-preguiça" usando $! Socorro? como por esta resposta .

pedido de Per Harleqin: Você já tentou definir opções de otimização? Por exemplo, com ghc, você pode usar adicionar "-O2" assim como você faria com gcc. (Embora eu não tenho certeza do que otimização existem níveis no GHC, a página homem não dizer exatamente ...)

Na minha experiência passada, definindo esta bandeira tem feito um tremenda diferença. Tanto quanto eu posso dizer, runhugs e uso ghc unoptimized a implementação mais básica, óbvia de Haskell; Infelizmente, isso às vezes não é muito eficiente.

Mas isso é apenas um palpite. Como eu disse no meu comentário, espero que alguém responde a sua pergunta também. Eu muitas vezes têm problemas analisar e corrigir o uso de memória do Haskell.

Use interruptor -fvia-C também.

Uma coisa que saltou aos meus olhos agora é que a saída Haskell é um float, enquanto a saída C parece ser inteiro. Eu ainda não vir a enfrentar código Haskell, mas há talvez algum lugar onde você aritmética de ponto em Haskell flutuante enquanto o C usa inteiros?

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow