Comment réduire l'utilisation de la mémoire dans une application Haskell?

Question

Je suis novice en programmation fonctionnelle et apprends maintenant Haskell. En tant qu'exercice, j'ai décidé de mettre en œuvre la méthode explicite d'Euler pour l'équation de diffusion linéaire 1D. Bien que le code ci-dessous fonctionne correctement, je ne suis pas satisfait de ses performances. En fait, je suis préoccupé par la consommation de mémoire. Je crois que cela est lié à une évaluation paresseuse, mais je ne peux pas comprendre comment je peux réduire sa mémoire.

L’idée de l’algorithme est très simple, pour le rendre clair en termes impératifs: il faut un "tableau", et à chaque point intérieur, il ajoute une valeur, qui est calculée comme une combinaison des valeurs du point lui-même. et dans ses voisins. Les points limites sont des cas particuliers.

Voici donc mon module 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

Et un simple 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

À des fins de comparaison, j'ai également écrit une implémentation en C pur .

Maintenant, si j'essaie d'exécuter l'implémentation Haskell pour une taille suffisamment grande du tableau n , j'ai:

$ time ./eulerhs 200000
100000.00000000112

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

À titre de comparaison, la version C est plus rapide de près de deux ordres de grandeur:

$ time ./eulerc 200000
100000

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

  

EDIT : cette comparaison n’est pas vraiment juste, car la version de Haskell est   compilé avec des drapeaux de profilage et C   n'est pas. Si je compile les deux programmes   avec -O2 et les deux sans profilage   drapeaux, je peux augmenter n . Dans ce   la casse time ./eulerhs 1000000 prend   0m2.236s, tandis que temps ./eulerc   1000000 ne prend que 0m0.293s. Alors le   le problème reste avec tous   optimisations et sans profilage,   il est seulement compensé.

     

Je voudrais aussi noter que cette mémoire   attribution du programme Haskell   semble croître linéairement avec n .   C'est probablement OK.

Mais le pire est la mémoire requise. Ma version de Haskell nécessite plus de 100 Mo (mon estimation du strict minimum en C est de 4 Mo ). Je pense que cela peut être la source du problème. Selon le rapport de profilage, le programme passe 85% du temps au GC et

        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

J'ai été surpris de constater que makeu0 est donc cher. J'ai décidé que cela est dû à son évaluation paresseuse (si ses thunks restent en mémoire jusqu'à la fin de stepEuler ).

J'ai essayé cette modification dans Main.hs :

   let un = u0 `seq` stepEuler 0.5 u0

mais n'a pas remarqué de différence. Je ne sais pas comment réduire l'utilisation de la mémoire dans stepEuler . Donc, mes questions sont:

1. Haskell a-t-il un moyen de construire des listes / de comprendre les listes strictement? Dans ce cas, il n'y a aucun avantage à rester paresseux.
2. Comment puis-je réduire l'utilisation globale de la mémoire dans ce cas? Je suppose que je dois faire quelque chose de strict, mais je ne vois pas quoi. En d’autres termes, si je dois mettre des bangs seq , où et pourquoi?
3. Enfin, le plus important, quelle est la meilleure stratégie pour identifier ces constructions coûteuses?

J'ai lu un chapitre sur le profilage et l'optimisation dans Haskell dans le monde réel , mais on ne sait toujours pas comment je peux décider exactement de ce qui doit être strict et de ce qui ne l’est pas.

S'il vous plaît, pardonnez-moi un si long post.

  

EDIT2 : Comme l'a suggéré A. Rex dans les commentaires, j'ai essayé de lancer les deux   programmes en valgrind. Et c'est quoi   J'ai observé. Pour le programme Haskell   ( n = 200000) il a trouvé:

     

    

malloc / free: 33 octets, 30 libres, 84 109 octets alloués.     ...     vérifié 55 712 980 octets.

  

     

Et pour le programme C (après un petit correctif):

     

    

malloc / free: 2 allocations, 2 libres, 3 200 000 octets alloués.

  

     

Donc, il semble que pendant que Haskell   alloue des blocs de mémoire beaucoup plus petits,   il le fait souvent, et en raison de retarder   ramassage des ordures, ils accumulent   et re

Answer 1

1. Les listes ne sont pas la meilleure structure de données pour ce type de code (avec beaucoup de (++) et (dernier)). Vous perdez beaucoup de temps à constituer et à déconstruire des listes. J'utiliserais Data.Sequence ou des tableaux, comme dans les versions C.

2. Il n'y a aucune chance pour que les thunks de makeu0 soient ramassés, car vous devez les conserver tous (enfin, tous les résultats de "diffuse", pour être exact) jusqu'au bout fin du calcul pour pouvoir effectuer un "reverse" dans applyBC. Ce qui est très coûteux, étant donné que vous n’avez besoin que de deux éléments de la liste pour votre "zeroflux".

Voici un extrait rapide de votre code qui tente de réaliser une meilleure fusion de listes et moins de listes (de) construisant:

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

Pour 200 000 points, il se termine en 0,8 seconde contre 3,8 secondes pour la version initiale

Answer 2

Sur mon système x86 32 bits, votre programme n’utilise que 40 Mo environ de mémoire.

Confondez-vous peut-être le " total alloc = 116 835,180 bytes " ligne de votre sortie de profilage avec combien de mémoire est réellement utilisée par le programme à un moment donné? L'allocation totale est la quantité de mémoire allouée sur l'ensemble du programme; une grande partie de cela est libérée par le ramasse-miettes au fur et à mesure. Vous pouvez vous attendre à ce que ce nombre devienne très important dans un programme Haskell; J'ai des programmes qui allouent de nombreux terrabytes de mémoire tout au long de leur exécution, même s'ils ont en réalité une mémoire virtuelle d'une centaine de mégaoctets environ.

Je ne m'inquiéterais pas trop du montant total des allocations pendant l'exécution d'un programme; c’est la nature d’un langage pur et l’exécution de GHC dispose d’un très bon récupérateur de mémoire pour compenser cela.

Answer 3

Plus généralement, vous pouvez savoir où va votre mémoire en utilisant Les outils de profilage de tas de GHC. D'après mon expérience, ils ne vous diront pas nécessairement pourquoi vos données sont divulguées, mais peuvent au moins en réduire les causes potentielles.

Vous pouvez également trouver cela éclairant excellent article de Don Stewart sur le blog sur la compréhension de la rigueur, son interaction avec la récupération de place, et sur la manière de diagnostiquer et de résoudre les problèmes.

Answer 4

Est-ce que forcer & un; un-laziness " en utilisant $! Aidez-moi? selon cette réponse .

Answer 5

Demande de Harleqin: Avez-vous essayé de définir des indicateurs d'optimisation? Par exemple, avec ghc, vous pouvez utiliser add " -O2 " comme vous le feriez avec gcc. (Bien que je ne sache pas quels niveaux d'optimisation existent dans ghc; la page de manuel ne dit pas exactement ...)

Dans mon expérience passée, définir ce drapeau a fait une énorme différence. Autant que je sache, runhugs et ghc non optimisés utilisent l'implémentation la plus élémentaire et la plus évidente de Haskell; malheureusement, cela n’est parfois pas très efficace.

Mais ce n'est qu'une supposition. Comme je l'ai dit dans mon commentaire, j'espère que quelqu'un répondra bien à votre question. J'ai souvent des problèmes pour analyser et corriger l'utilisation de la mémoire par Haskell.

Answer 6

Utilisez également le commutateur -fvia-C .

Answer 7

Une chose qui me saute aux yeux maintenant est que la sortie Haskell est un float, alors que la sortie C semble être un entier. Je n’ai pas encore maîtrisé le code Haskell, mais y at-il un endroit où l’arithmétique en virgule flottante est possible dans Haskell alors que C utilise des entiers?