Wie kann man die Speichernutzung in einer Haskell-Anwendung reduzieren?

Question

Ich bin neu in der funktionalen Programmierung und lerne jetzt Haskell. Als Übung habe ich beschlossen, die explizite Euler-Methode für 1D lineare Diffusionsgleichung zu implementieren. Obwohl der untenstehende Code korrekt funktioniert, bin ich mit seiner Leistung nicht zufrieden. In der Tat bin ich besorgt über den Speicherverbrauch. Ich glaube, dass dies mit der trägen Auswertung zusammenhängt, kann aber nicht herausfinden, wie ich den Speicherverbrauch reduzieren kann.

Die Idee des Algorithmus ist wirklich einfach, um es in zwingenden Begriffen auszudrücken: Er nimmt ein "Array" und fügt zu jedem inneren Punkt einen Wert hinzu, der als Kombination der Werte im Punkt selbst und in seinen Nachbarn berechnet wird. Randpunkte sind Sonderfälle.

Dies ist also mein Modul 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

Und eine einfache 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

Zum Vergleich habe ich auch geschrieben eine reine C-Implementierung .

Wenn ich nun versuche, die Haskell-Implementierung für eine ausreichend große Größe des Arrays n habe ich:

$ time ./eulerhs 200000
100000.00000000112

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

Zum Vergleich: Die C-Version ist um fast zwei Größenordnungen schneller:

$ time ./eulerc 200000
100000

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

EDITAR : Dieser Vergleich ist nicht wirklich fair, denn die Haskell-Version wird mit Profiling-Flags kompiliert wird, während C nicht. Wenn ich beide Programme kompiliere mit -O2 und beide ohne Profilierung Flaggen, kann ich die n . In diesem Fall time ./eulerhs 1000000 nimmt 0m2.236s, während time ./eulerc 1000000 dauert nur 0m0,293s. Also bleibt das Problem bleibt also bei allen Optimierungen und ohne Profiling, ist es nur ein Versatz.

Ich möchte auch anmerken, dass die Erinnerung Zuweisung des Haskell-Programms linear zu wachsen scheint mit n . Das ist wahrscheinlich in Ordnung.

Am schlimmsten sind jedoch die Speicheranforderungen. Meine Haskell-Version benötigt über 100MB (meiner Schätzung nach ist das absolute Minimum in C 4MB ). Ich denke, dass dies die Ursache des Problems sein könnte. Laut Profiling-Bericht verbringt das Programm 85% der Zeit in GC, und

        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

Ich war erstaunt zu sehen, dass makeu0 es also teuer. Ich bin zu dem Schluss gekommen, dass dies auf die faule Auswertung zurückzuführen ist (wenn die Thunks bis zum Ende der Laufzeit im Speicher bleiben). stepEuler ).

Ich habe diese Änderung in Main.hs :

   let un = u0 `seq` stepEuler 0.5 u0

konnte aber keinen Unterschied feststellen. Ich habe keine Ahnung, wie man die Speichernutzung in stepEuler . Meine Fragen lauten also:

1. Gibt es in Haskell eine Möglichkeit, Listen zu erstellen / Listenauffassungen strikt durchzuführen? In diesem Fall gibt es keinen Vorteil, es faul zu halten.
2. Wie kann ich in diesem Fall die Speichernutzung insgesamt reduzieren? Ich nehme an, ich muss etwas streng machen, aber ich weiß nicht, was. Mit anderen Worten, wenn ich einige zu setzen haben seq s und Knalle, wo und warum?
3. Und schließlich, und das ist das Wichtigste, was ist die beste Strategie, um solche kostspieligen Konstrukte zu identifizieren?

Ich habe ein Kapitel über Profilerstellung und Optimierung gelesen in Haskell in der realen Welt aber es bleibt unklar, wie genau ich entscheiden kann, was streng sein soll und was nicht.

Bitte verzeihen Sie mir diesen langen Beitrag.

EDIT2 : Wie von A. Rex in den Kommentaren vorgeschlagen, habe ich versucht, beide Programme in valgrind laufen zu lassen. Und das ist, was ich beobachtet. Für das Haskell-Programm ( n =200000) gefunden:

malloc/frei: 33 Allokationen, 30 Freisetzungen, 84.109 Bytes zugewiesen. ... überprüft 55.712.980 Bytes.

Und für das C-Programm (nach einer kleinen Korrektur):

malloc/frei: 2 Allokationen, 2 Freisetzungen, 3.200.000 Bytes zugewiesen.

Es scheint also, dass Haskell viel kleinere Speicherblöcke zuweist, es oft tut, und aufgrund der Verzögerung bei der Müllabfuhr, sammeln sie sich an und bleiben im Speicher. Ich habe also eine andere Frage:

• Ist es möglich, einen Großteil der kleinen Zuweisungen in Haskell zu vermeiden? Im Grunde genommen, um zu erklären, dass ich die gesamte Datenstruktur verarbeiten und nicht nur ihre Fragmente bei Nachfrage.

Answer 1

1. Listen sind nicht die beste Datenstruktur für diese Art von Code (mit vielen (++), und (last)). Sie verlieren viel Zeit mit dem Auf- und Abbau von Listen. Ich würde Data.Sequence oder Arrays verwenden, wie in C-Versionen.

2. Es gibt keine Möglichkeit, dass Thunks von makeu0 im Müll landen, da man sie alle (also alle Ergebnisse von "diffuse", um genau zu sein) bis zum Ende der Berechnung aufbewahren muss, um "reverse" in applyBC durchführen zu können. Das ist eine sehr teure Sache, wenn man bedenkt, dass man nur zwei Elemente vom Ende der Liste für den "Zeroflux" benötigt.

Hier ist ein schneller Hack deines Codes, der versucht, eine bessere Listenfusion zu erreichen und weniger Listen (de)konstruiert:

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

Für 200000 Punkte benötigt er 0,8 Sekunden im Vergleich zu 3,8 Sekunden bei der ersten Version.

Answer 2

Auf meinem 32-Bit-x86-System benötigt Ihr Programm nur etwa 40 MB Speicher.

Verwechseln Sie vielleicht die Zeile "total alloc = 116.835.180 bytes" aus Ihrer Profiling-Ausgabe damit, wie viel Speicher tatsächlich vom Programm zu einem bestimmten Zeitpunkt verwendet wird? Die Gesamtzahl gibt an, wie viel Speicher während des gesamten Programmlaufs zugewiesen wurde; ein Großteil davon wird vom Garbage Collector im Laufe des Programms wieder freigegeben. Sie können davon ausgehen, dass diese Zahl in einem Haskell-Programm sehr groß werden kann; ich habe Programme, die im Laufe ihres gesamten Laufs viele Terrabytes an Speicher zuweisen, obwohl sie eigentlich eine maximale virtuelle Speichergröße von etwa hundert Megabyte haben.

Ich würde mir keine allzu großen Sorgen über große Gesamtzuweisungen im Laufe eines Programmlaufs machen; das liegt in der Natur einer reinen Sprache, und die Laufzeit von GHC hat einen sehr guten Garbage Collector, der dabei hilft, dies zu kompensieren.

Answer 3

Ganz allgemein können Sie herausfinden, wohin Ihr Speicher geht, indem Sie GHCs Werkzeuge zur Heap-Profilierung. Meiner Erfahrung nach können sie Ihnen nicht unbedingt sagen, warum Ihre Daten durchgesickert sind, aber sie können zumindest die möglichen Ursachen eingrenzen.

Vielleicht finden Sie auch Folgendes aufschlussreich ausgezeichneter Blogbeitrag von Don Stewart über das Verständnis von Strictness, die Wechselwirkung mit der Garbage Collection und die Diagnose und Behebung von Problemen.

Answer 4

Hilft die Erzwingung von "Un-laziness" mit $! diese Antwort .

Answer 5

Auf Harleqins Anfrage hin: Haben Sie versucht, Optimierungsflags zu setzen? Bei ghc können Sie zum Beispiel "-O2" hinzufügen, genau wie bei gcc (obwohl ich nicht sicher bin, welche Optimierungsstufen in ghc existieren; die Manpage sagt das nicht genau ...)

Meiner Erfahrung nach hat das Setzen dieser Markierung eine . Unterschied. Soweit ich das beurteilen kann, runhugs und nicht optimierte ghc die einfachste, naheliegendste Haskell-Implementierung verwenden; leider ist das manchmal nicht sehr effizient.

Aber das ist nur eine Vermutung. Wie ich in meinem Kommentar sagte, hoffe ich, dass jemand Ihre Frage gut beantwortet. Ich habe oft Probleme, die Speichernutzung von Haskell zu analysieren und zu beheben.