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

Schalter verwenden -fvia-C auch.

Answer 2

Eine Sache, die mir jetzt ins Auge gesprungen ist, ist, dass die Haskell-Ausgabe eine Fließkommazahl ist, während die C-Ausgabe eine Ganzzahl zu sein scheint. Ich habe mich noch nicht mit Haskell-Code auseinandergesetzt, aber gibt es vielleicht eine Stelle, an der in Haskell mit Fließkomma-Arithmetik gearbeitet wird, während C Ganzzahlen verwendet?